Упорядоченные пары

[Doctor Faust]

У Зорича (параграф 1.4) дано следующее определение декартова произведения:
$X \times Y = \lbrace p \in P(P(X) \cup P(Y)) \mid p = (x,y) \land (x \in X) \land (y \in Y) \rbrace$,
где $P(A)$ есть множество всех подмножеств А.
По определению (Куратовский): $(x,y) = \lbrace \lbrace x \rbrace, \lbrace x,y \rbrace \rbrace$. То есть, упорядоченная пара $p = (x,y) = \lbrace \lbrace x \rbrace, \lbrace x,y \rbrace \rbrace$ является элементом $P(P(X) \cup P(Y))$.

Пусть, к примеру, $X = \lbrace x \rbrace$, $Y = \lbrace y \rbrace$. Тогда $P(X) = \lbrace \lbrace x \rbrace, \varnothing \rbrace$, $P(Y) = \lbrace \lbrace y \rbrace, \varnothing \rbrace$, $P(X) \cup P(Y) = \lbrace \lbrace x \rbrace, \lbrace y \rbrace, \varnothing \rbrace = \lbrace \lbrace x \rbrace, \lbrace y \rbrace \rbrace$, $P(P(X) \cup P(Y)) = \lbrace \lbrace \lbrace x \rbrace \rbrace, \lbrace \lbrace y \rbrace \rbrace, \lbrace \lbrace x \rbrace, \lbrace y\rbrace \rbrace, \varnothing \rbrace = \lbrace \lbrace \lbrace x \rbrace \rbrace, \lbrace \lbrace y \rbrace \rbrace, \lbrace \lbrace x \rbrace, \lbrace y \rbrace \rbrace \rbrace$. Очевидно, что $X \times Y = \lbrace (x,y) \rbrace$. В то же время пары $(x,y) = \lbrace \lbrace x \rbrace, \lbrace x,y \rbrace \rbrace$ во множестве $P(P(X) \cup P(Y))$ я не нахожу. Что я напутал?

Самому кажется, что неправильно построил $P(P(X) \cup P(Y))$, но в чём именно проблема, понять не могу.

[Xaositect]

Doctor Faust в сообщении #691696 писал(а):

У Зорича (параграф 1.4) дано следующее определение декартова произведения:
$X \times Y = \lbrace p \in P(P(X) \cup P(Y)) \mid p = (x,y) \land (x \in X) \land (y \in Y) \rbrace$,
где $P(A)$ есть множество всех подмножеств А.
По определению (Куратовский): $(x,y) = \lbrace \lbrace x \rbrace, \lbrace x,y \rbrace \rbrace$. То есть, упорядоченная пара $p = (x,y) = \lbrace \lbrace x \rbrace, \lbrace x,y \rbrace \rbrace$ является элементом $P(P(X) \cup P(Y))$.

Пусть, к примеру, $X = \lbrace x \rbrace$, $Y = \lbrace y \rbrace$. Тогда $P(X) = \lbrace \lbrace x \rbrace, \varnothing \rbrace$, $P(Y) = \lbrace \lbrace y \rbrace, \varnothing \rbrace$, $P(X) \cup P(Y) = \lbrace \lbrace x \rbrace, \lbrace y \rbrace, \varnothing \rbrace = \lbrace \lbrace x \rbrace, \lbrace y \rbrace \rbrace$

Стоп. Последнее равенство почему? Какие множества называются равными?

[Doctor Faust]

Те, которые состоят из одних и тех же элементов. Последнее равенство - это просто сокращённая запись. Или так писать всё же неправильно?

-- 06.03.2013, 13:10 --

Ведь говоря, что множество $X$ состоит из одного элемента $x$, мы подразумеваем, что пустое в $X$ тоже входит (т. к. оно является элементом любого множества), но вместо $X = \lbrace x, \varnothing \rbrace$ мы пишем просто $X = \lbrace x \rbrace$.

[Xaositect]

Это типичная ошибка при изучении теории множеств.
Пустое множество - это полноценное множество, оно может выступать в качестве элемента другого множества и сокращать его таким образом нельзя. В вашем равенстве $\{\{x\},\{y\},\varnothing\} = \{\{x\},\{y\}\}$ у левого множества три элемента, а у правого - два. Поэтому это равенство верным быть не может.
В качестве упражнения для привыкания к этому, можете выписать $PPP\varnothing$.

-- Ср мар 06, 2013 14:16:40 --

Цитата:

мы подразумеваем, что пустое в $X$ тоже входит (т. к. оно является элементом любого множества)

Это неверно. Пустое множество не является элементом любого. Например, оно не является элементом саого себя, не является элементом $\{\{\varnothing\}\}$.

-- Ср мар 06, 2013 14:19:27 --

Эта типичная ошибка периодически на форуме обсуждается, посмотрите, например, вот эту тему: post654959.html#p654959

[Doctor Faust]

Спасибо, понял свою ошибку. Пустое множество является не элементом любого множества, а подмножеством любого множества.
Тогда должно быть так: $P( \lbrace \lbrace x \rbrace , \lbrace y \rbrace , \varnothing \rbrace) = \lbrace \lbrace \lbrace x \rbrace \rbrace , \lbrace \lbrace y \rbrace \rbrace , \lbrace \varnothing \rbrace, \lbrace \lbrace x \rbrace , \lbrace y \rbrace \rbrace , \lbrace \lbrace x \rbrace , \varnothing \rbrace , \lbrace \lbrace y \rbrace , \varnothing \rbrace , \lbrace \lbrace x \rbrace , \lbrace y \rbrace , \varnothing \rbrace , \varnothing \rbrace$.
Но нужного множества $\lbrace \lbrace x \rbrace , \lbrace x, y \rbrace \rbrace$ опять нет.

[Xaositect]

Действительно. Видимо, опечатка. Должно быть $P(P(X\cup Y))$

[CyberBeast]

Всем привет! Спасибо за то, что вы есть) Я как-раз начинаю изучать дискретную математику и сталкиваюсь с подмножеством множества сложностей)

Xaositect, спасибо за Ваше замечание. Для того чтобы разобраться с определением кортежа я решил проиграть "на пальцах" Ваш вариант определения. Для случая $X:=\{1\}; Y:=\{2\}$, результирующее множество, как я и ожидал, содержит элементы $\{\{1\}, \{1, 2\}\}$ и $\{\{2\}, \{1, 2\}\}$. Но когда я попытался расписать квадрат множества, состоящего из одного элемента, то меня ожидал сюрприз, так как $X\cup X=X$. Может кто-то объяснить? Заранее благодарен.

PS Еще меня смущает запись $ \lbrace x , \lbrace x, y \rbrace \rbrace$. Встречал здесь и у Новикова "Дискретная математика для программистов" стр. 33. Вроде же в ZFC $\{x\}\ne x$?

[whitefox]

Имхо, вместо $P(P(X\cup Y))$ должно быть $P((X\cup Y)\cup P(X\cup Y))$

[wormer]

У Зорича опечатка, должно быть $P(P(X \cup Y))$. В книге "Колмогоров А.Н., Драгалин А.Г. Математическая логика. Изд. 3-е, стереотипное. - М.: КомКнига, 2006" на стр. 141 аналогичное определение дается именно так (вторая часть, гл. I, параграф 3, пункт 3). Ограничение $P(P(X \cup Y))$ фиктивное - оно следует из $(p = (x, y)) \wedge (x \in X) \wedge (y \in Y)$. Кстати, более строго надо писать $X \times Y = \{ p \in P(P(X \cup Y)) \, | \, \exists x \exists y ((p = (x, y)) \wedge (x \in X) \wedge (y \in Y)) \}$.

Расписываем $X \times X$ для $X = \{x\}$: $P(P(X)) = P(\{\{x\}, \varnothing\})$ = \{ \{\{x\}\}, \{\varnothing\}, \{\{x\}, \varnothing\}, \varnothing \}. В нашем случае упорядоченная пара $(x, x)$ - это одноэлементное множество $\{ \{x\}, \{x, x\} \} = \{ \{x\} \}$, которое мы без труда находим в $P(P(X))$. Противоречий не вижу.

Упорядоченная пара $(x, y)$ по Куратовскому - это $\{ \{x\}, \{x, y\} \}$ и в порядочных источниках пишут именно так. Надо думать, в других местах - это опечатки, потому что в теории множеств как ни крути сам элемент и множество из него состоящее - это разные объекты, будь то наивная теория множеств, теория Цермело-Френкеля или какая-либо другая.

[arseniiv]

Не обязательно опечатки. $\{x,\{x,y\}\}$ тоже подходит для представления упорядоченных пар, но с этой штукой, говорят, больше возни при обосновании.

[Lia]

Часть дискуссии отделена в «Упорядоченная пара по Куратовскому»