Множество всех частичных функций

[Sdy]

Для начала приведу все те рассуждения, которые приводят меня к проблеме в задании.
Занимаюсь я по книге Terence Tao, Analysis I.
Даётся вот такая аксиома:
Axiom 3.10 (Power set axiom).
Let X and Y be sets. Then there exists a set, denoted $Y^X$ , which consists of all the functions from $X$ to $Y$ , thus $f \in Y^X \Leftrightarrow$ ( $f$ is a function with domain $X$ and range $Y$).
Далее просят доказать:
Lemma 3.4.9. Let $X$ be a set. Then the set $\{Y : Y \text{ is a subset of X }\}$ is a set.
Моё доказательство.
Рассмотрим множество функций $\{0,1\}^X$, которое по имеющейся аксиоме существует. Применим аксиому замены и каждую функцию из этого множества заменим на множество элементов из $X$, на которых функция принимает значение $1$. Ну а так как мы умеем устанавливать биекцию между всеми подмножествами множества и бинарными последовательностями, мы получаем, что существует множество, состоящее из всех подмножеств данного множества. $\triangle$
Далее нужно доказать вот такое утверждение.
Exercise 3.4.7.
Let $X$, $Y$ be sets. Define a partial function from $X$ to $Y$ to be any function $f: X' \to Y'$ whose domain $X'$ is a subset of $X$, and whose range $Y'$ is a subset of $Y$ . Show that the collection of all partial functions from $X$ to $Y$ is itself a set. (Hint: use Exercise 3.4.6, the power set axiom, the replacement axiom, and the union axiom.)
Моё доказательство.
Рассмотрим множество всех подмножеств $Y$ - $2^Y$ и множество всех подмножеств $X$ - $2^X$. Они являются множествами по доказанному нами утверждению. Но тогда по аксиоме $3.10$ множество всех функций из $2^X$ в $2^Y$ является множеством $P = 2^{Y^{2^X}}$. Но множество $P$ - это и есть множество всех частичных функций из $X$ в $Y$, значит утверждение доказано. $\triangle$
Вопрос.Что не так с моим доказательством? Мне оно кажется правильным, но я же не применил ни аксиому замены, ни аксиому объединения, а в подсказке написано, что они нужны.

[mihaild]

Sdy в сообщении #1429727 писал(а):

Но множество $P$ - это и есть множество всех частичных функций из $X$ в $Y$, значит утверждение доказано

Нет, с чего бы?
Возьмем например $X = \varnothing$, $Y$ непусто. Тогда множество всех частичных функций одноэлементно, но $2^X$ непусто, значит $Y^{2^X}$ непусто и соответственно $P$ состоит из более чем одного элемента.

[Sdy]

mihaild, спасибо за ответ.
Теперь это нужно как-то в голове уложить. Интуитивно казалось, что множество $P$ совпадает с множеством частичных функций.

[Sdy]

mihaild, да, действительно, эти множества не обязаны совпадать, ведь функции из $2^X$ "несут" всевозможные подмножества $X$, в то время как нам нужны функции, которые будут "нести" эти подмножества не разом, а "по одному".
Попробую так.
Доказательство.
Если $Y' \subset Y$, тогда функция, $f' : X' \to Y'$ это та же самая функция, что $f':X' \to Y$, так на всех значениях $x \in X'$ они принимают одинаковые значения.
Тогда рассмотрим множество всех подмножеств множества $X$ - $2^X$. Каждый элемент $X'$ этого множества заменим на $Y^{X'}$ по аксиоме замены, так как любому множеству отвечает только одно множество всевозможных функций из него. Значит мы получили множество вида $\{Y^{X_1}, Y^{X_2},...\}$. Теперь по аксиоме объединения мы можем получить множество, состоящее из всех элементов $Y^{X_i} \forall i$, а значит мы доказали, что множество всех частичных функций действительно является множеством. $\triangle$
Вопрос.
Помимо проверки корректности этого доказательства, хотел бы спросить, могу ли я вообще говорить, что если $f' : X' \to Y', Y' \subset Y$, то это та же самая функция, что и $f' = f'' : X' \to Y$? Просто Тао определяет равенство только тех функций, что имеют одинаковые области определения и значений, но я не очень понимаю, что нам мешает определить равенство $f'$ и $f''$, ведь это одни и те же функции в том смысле, что они совпадают на всей области определения, так почему бы их не отождествить?
Или это приводит к противоречиям?

-- 12.12.2019, 04:21 --

Добавление.
Наверное, можно обойтись без каверкания равенства функций.
Возьмём просто множества $2^X$ и $2^Y$ и произвольные элементы $X' \in 2^X$, $Y' \in 2^Y$.
Для начала образуем множество $Y'^{X'}$. Оно существует по имеющейся аксиоме. Далее будем по аксиоме парного объединения объединять все множества $Y_i^{X'} : Y_i \in 2^Y \forall i$, получим множество $P_1$, элементы которого - все функции вида $Y_i^{X'} \forall Y_i \in 2^Y$. На него и заменим по аксиоме замены наше $X'$ из $2^X$. Проделаем этот процесс для всех $X' \in 2^X$. Получим множество из всех множеств функций из $X' \to Y'$. А далее воспользуемся аксиомой объединения и получим необходимое нам множество частичных функций. $\triangle$
Это рассуждение верно?

[mihaild]

Есть разные определения функции. График функции - это всегда множество пар с понятными свойствами. Функцией можно назвать либо (1) сам график, либо (2) тройку (домен, кодомен, график), либо (3) двойку (кодомен, график) (т.к. домен можно восстановить по графику; я краем уха слышал, что в теории категорий нельзя, но ничего толком про это не знаю).

Например, если мы считаем $\mathbb{N}$ подмножеством $\mathbb{R}$, то по первому определению функции $f: \mathbb{R} \to \mathbb{N}$, $f(x) = 0$ и $g: \mathbb{R} \to \mathbb{R}$, $g(x) = 0$ совпадают, а по второму и третьему - нет. Иногда это может быть удобно, иногда нет.

Аналогично ваш переход можно делать по первому определению, но нельзя по второму и третьему. Но доказать требуемое можно и если брать эти определения, только придется немного повозиться, чтобы из одной функции сварить все возможные (и тут вроде аксиома выделения понадобится еще - она уже есть к этому моменту?).

[Sdy]

mihaild, спасибо за ответ.

mihaild в сообщении #1429791 писал(а):

и тут вроде аксиома выделения понадобится еще - она уже есть к этому моменту?

Нет, к сожалению. Значит нужно обходиться без этого.
Да и функция у Тао определяется вот таким образом:
Definition 3.3.1 (Functions).
Let $X$, $Y$ be sets, and let $P(x, y)$ be a
property pertaining to an object $x \in X$ and an object $y \in Y$ , such that
for every $x \in X$, there is exactly one $y \in Y$ for which $P (x, y)$ is true
(this is sometimes known as the vertical line test). Then we define the
function $f : X \to Y$ defined by $P$ on the domain $X$ and range $Y$ to be
the object which, given any input $x \in X$, assigns an output $f (x) \in Y$ ,
defined to be the unique object $f(x)$ for which $P(x, f (x))$ is true. Thus,
for any $x \in X$ and $y \in Y$ ,
$y = f (x) \Leftrightarrow P (x, y)$ is true.
Пар и понятия "отношения" он не вводил ещё явным образом.

Моё изменённое доказательство верно или тоже что-то не так?

[mihaild]

Sdy в сообщении #1429787 писал(а):

будем по аксиоме парного объединения объединять все множества $Y_i^{X'} : Y_i \in 2^Y \forall i$

Парного объединения не хватит - вам нужно объединить неизвестное количество множеств (может быть даже бесконечное). Нужно стандартное объединение всех множеств из семейства.

И общая схема вроде бы правильная, но, если уж вы хотите всё доводить до формального уровня, то ИМХО стоило бы написать последовательно, к какому множеству какие замены применяются.

[Sdy]

mihaild, спасибо за ответ.
У меня возникает такая проблема - пусть есть $2^X=\{X_1,...,X_n,...\}$ и $2^Y = \{Y_1,...,Y_m,...\}$.
Я хочу взять множества $y_{11}=Y_1^{X_1},..., y_{m1}=Y_m^{X_1}$ и заменить $X_1$ на множество, элементами которого являются элементы множеств $y_{i1}$. Но для использования аксиомы объединения, множества $y_{i1}$ сами должны лежать в каком-нибудь множестве $Y_{m1}$. Я не очень понимаю, как его получить, поэтому и пытался воспользоваться аксиомой парного объединения. Просто взять все $y_{i1}$ и "положить во множество" я вроде бы как не могу, так как я умею образовывать множества только из объекта $a - \{a\}$ и из двух объектов $a$ и $b$.
Как мне получить это множество, опираясь только на уже введенные аксиомы? Или я что-то не так понимаю?

-- 14.12.2019, 22:47 --

mihaild, мне пришла вот такая идея в голову:
Одна из аксиом говорит нам о существовании множества натуральных чисел.
Если это множество, то существует множество всех его подмножеств.
Тогда возьмём подмножество $\mathbb{N}$ - $\{1,...,m,...\}$, и каждый его элемент $i$ заменим на $y_{i1}$; у нас получается биекция, аксиома замены значит работает и мы получаем искомое множество $Y_{m1}$.
Так можно?

[mihaild]

Sdy в сообщении #1430190 писал(а):

Но для использования аксиомы объединения, множества $y_{i1}$ сами должны лежать в каком-нибудь множестве $Y_{m1}$

Замените сначала каждый элемент $y$ множества $2^Y$ на $y^{X_1}$. Потом возьмите объединение по получившемуся множеству.

[Sdy]

mihaild, спасибо за ответ, так и правда процесс будет прозрачнее.
Тогда получается вот такое
Доказательство.
Мы доказали, что множество всех подмножеств является множеством, поэтому можем множество всех подмножеств множества $X$ обозначить как $2^X = \{X_1,...,X_n,...\}$, множества $Y$ - $2^Y = \{Y_1,...,Y_m,...\}$.
Для каждого $X_j$ образуем множество $Y_{mi}$ таким образом - возьмём множество $2^Y$ и заменим все его элементы $Y_i$ на элементы $Y_i^{X_j}$. Так как множества таких функций $\forall Y_i$ единственны, аксиома замены тут работает и мы получим с помощью ее множества вида $Y_{mj}=\{Y_1^{X_j},...,Y_m^{X_j},...\}$.
Теперь по аксиоме объединения из таких множеств получим множества $Y_{mj}'$, которые состоят из всевозможных функций из $X_j$ в каждое из $Y_i$. Тогда по аксиоме замены (опять же, вследствие единственности множества таких функций) мы можем каждый $X_j$ заменить на $Y_{mj}'$ и получить множество вида $2^{X'}=\{Y_{m1}',...,Y_{mn}',...\}$. Применив к нему аксиому объединения мы получим множество, которое состоит из всех функций $f : \forall X' \subseteq X \to \forall Y' \subseteq Y$. $\triangle$
Так верно?

[mihaild]

Да, верно (индексы не проверял, но такой порядок замен и объединений должен работать). Немного неудачная формулировка:

Sdy в сообщении #1430206 писал(а):

возьмём множество $2^Y$ и заменим все его элементы $Y_i$ на элементы $Y_i^{X_j}$

Мы заменяем $Y_i$ не на элементы $Y_i^{X_j}$ а на само $Y_i^{X_j}$.

[Sdy]

mihaild, спасибо за ответ.

mihaild в сообщении #1430207 писал(а):

Мы заменяем $Y_i$ не на элементы $Y_i^{X_j}$ а на само $Y_i^{X_j}$.

Да, это и имел ввиду, выразился не совсем точно.

У меня ещё остался вопрос, по поводу этого:

mihaild в сообщении #1429840 писал(а):

Парного объединения не хватит - вам нужно объединить неизвестное количество множеств (может быть даже бесконечное).

Просто сталкиваюсь с этим не первый раз (сталкивался, например, в теории меры где у нас есть алгебра, а есть сигма-алгебра) и так до конца и не понял.
Возьмём этот конкретный случай. Пусть есть множество $Y = \{Y_1,...,Y_n,...\}$ и его элементы $Y_i$ - также являются множествами произвольной природы. Возьмём первые его два элементы, они множества, объединим их по имеющейся аксиоме о парном объединении, получим множество $Y_{12}$. Далее возьмём $3$-е множество, объединим с $Y_{12}$, получим $Y_{123}$. Будем и дальше продолжать этот процесс, получим объединение всех множеств $Y_1,...,Y_n,...$. Почему так нельзя сделать? Разве тут не помогает индукция? (Получили таким образом объединение $n$ множеств, объединим его с $n+1$-м, получим с помощью парного объединения множество из всех элементов...).

[mihaild]

Sdy в сообщении #1430208 писал(а):

Пусть есть множество $Y = \{Y_1,...,Y_n,...\}$ и его элементы $Y_i$ - также являются множествами произвольной природы

Бывают и несчетные семейства множеств, но это тут не главное.

Sdy в сообщении #1430208 писал(а):

Получили таким образом объединение $n$ множеств, объединим его с $n+1$-м, получим с помощью парного объединения множество из всех элементов...

Нет, для каждого $n$ получим объединение первых $n$ множеств. И действительно, если у нас есть объединение двух множеств, то есть и объединение любого конечного числа. Но не бесконечного.
Например семейство всех конечных подмножеств бесконечного множества замкнуто относительно конечного объединения, но не замкнуто относительно бесконечного.

[Sdy]

mihaild, спасибо за ответ.
Пока в голове это уложить не могу. Что вроде как $\forall n \in \mathbb{N}$ мы получаем объединение $Y_1,...,Y_n$, а объединить все - не получится.
То есть, я говорю - "Я вот смог объединить $m$ множеств". Мне говорят - "Всё верно, но туда не вошел элемент из $m+1$, поэтому вы объединили не все бесконечное множество множеств". Я говорю - "Ну хорошо, я могу объединить и $m+1$ множество.". Мне говорят - "Замечательно, но туда не вошел какой-нибудь элемент из $m+2$. И так до бесконечности?
То есть строго говоря, так как я умею объединять сколько угодно большие, но все таки конечные последовательности (назовём их так) множеств, всегда найдется множество с большим номером, такое, что не вошло в объединение, так как их бесконечно много? Так это формально доказывается?

[mihaild]

Sdy в сообщении #1430217 писал(а):

Что вроде как $\forall n \in \mathbb{N}$ мы получаем объединение $Y_1,...,Y_n$, а объединить все - не получится

Это совершенно стандартная ситуация. Для первых $n$ натуральных чисел есть число, превосходящее их все, а для всех натуральных чисел - нет.

Sdy в сообщении #1430217 писал(а):

Так это формально доказывается?

Смотря что вы тут хотите доказать.
Если то, что из аксиомы парного объединения не выводится общая аксиома объединения - то нет, не так (и я не знаю, как это доказывается, и даже верно ли это вообще).
То, что рассуждение не работает, формально вообще не доказывают. Просто при формализации рассуждения обнаруживается, что либо в нем есть не обоснованный переход, либо оно доказывает не то, что нужно.
Рассуждение с объединением по индукции счетного семейства множеств доказывает $\forall n \exists X \forall m < n: Y_m \subseteq X$. А нужно нам $\exists X \forall n \forall m < n: Y_m \susbseteq X$ (точнее нам нужно $\exits X \forall m: Y_m\subseteq X$, но это экивалентно, а первая формулировка больше похоже на то, что получается).
Переставлять кванторы нельзя (точнее заносить всеобщность под существование существование под всеобщность можно, если носитель не пуст, но обратно нельзя): у каждой лошади есть цвет, но нет общего цвета для всех лошадей.