Конечных множеств счётное число(?)

[arseniiv]

Можно как-нибудь показать, что в ZF(C) конечных множеств счётное число? Или это не так?

[caxap]

Каждому вещественному числу $a$ сопоставим конечное множество $\{a\}$. Их континуум.

[arseniiv]

Я неправильно выразился. Конечных множеств, все элементы которых конечны и все элементы их элементов, и т. д. конечны тоже. То есть есть такое индуктивное определение:
1. $\varnothing \in S$
2. $a \subset S \implies a \in S$
(вроде так), где $S$ — то ли множество, то ли собственно класс интересующих меня конечных множеств.

[paha]

caxap в сообщении #371976 писал(а):

Каждому вещественному числу $a$ сопоставим конечное множество $\{a\}$. Их континуум.

все они изоморфны в $SET$. Имелось ввиду, конечно, классов изоморфизма

-- Вс ноя 07, 2010 18:36:32 --

arseniiv в сообщении #371974 писал(а):

Можно как-нибудь показать, что в ZF(C) конечных множеств счётное число? Или это не так?

я, разумеется, не понимаю, что такое ZF(C), но все конечные множества можно пересчитать их мощностями

[caxap]

arseniiv в сообщении #371982 писал(а):

такое индуктивное определение:

$\{\varnothing\}$,$\{\varnothing},\{\varnothing\}\}$ и т. д. -- это ординалы по фон Нейману (см. Верещагин, Шень "Начала теории множеств"). Множество всех конечных ординалов $\omega$ счётно.

[arseniiv]

Если вот это отображение взаимно-однозначно (я в этом не очень сомневаюсь, но строгие доказательства плохо получаются), то, значит, $S \sim \mathbb N$.
Отображение $s \colon \mathbb N_0 \to S$: $s(\sum_{k = 0}^\infty {2^k a_k}) = \left\{s(k) \, |\, a_k = 1\right\}$, где $\forall k \in \mathbb N_0 \left( a_k \in \{0,\,1\} \right)$, притом $s(0) = \varnothing$.

Ой, тут уже написали. сахар, а $\{\{\varnothing\}\}$ тоже ординал?

paha в сообщении #371995 писал(а):

все конечные множества можно пересчитать их мощностями

Эээ… что вы имели ввиду?

[paha]

arseniiv в сообщении #372005 писал(а):

Эээ… что вы имели ввиду?

два конечных множества изоморфны в категории $SET$, если у них равное количество элементов

[arseniiv]

Ну нет, так не интересно, считать все множества с одним и тем же количеством элементов один раз.

[paha]

arseniiv в сообщении #372016 писал(а):

Ну нет, так не интересно

тогда

caxap в сообщении #371976 писал(а):

Каждому вещественному числу $a$ сопоставим конечное множество $\{a\}$. Их континуум.

Клиент всегда прав:)))

[caxap]

arseniiv в сообщении #372005 писал(а):

а $\{\{\varnothing\}\}$ тоже ординал?

Нет. $0:=\varnothing$, $1:=\{\varnothing\}$, $2:=\{\varnothing,\{\varnothing\}\}$, $3:=2\cup\{2\}$ и т. д. Рекомедую посмотреть Верещагина.

[arseniiv]

Ну вот, а по моему индуктивному определению:

$\varnothing \in S \implies \{\varnothing\} \subset S \implies \{\varnothing\} \in S \implies \{\{\varnothing\}\} \subset S \implies \{\{\varnothing\}\} \in S$.

Нечётные импликации по определению $\subset$, чётные по определению $S$. Значит, элементы $S$ — не только ординалы!

[caxap]

Стойте. Получается $S$ сам себя ещё содержит? Это точно противоречит какой-то аксиоме ZF. Или у вас $\subset$ строгое?

[arseniiv]

Строгое.

-- Вс ноя 07, 2010 22:01:48 --

Мне кажется, $s$ всё-таки взаимно однозначное отображение, но уже заинтересовал другой вопрос: найти какое-нибудь отношение линейного порядка $R \subset S^2$ такое, что $aRb$ достаточно легко вычислить, потому что отношения по рангам и по мощностям множеств частичные.

-- Вс ноя 07, 2010 22:02:56 --

Имел ввиду, частичного порядка.

[Xaositect]

arseniiv в сообщении #371982 писал(а):

Я неправильно выразился. Конечных множеств, все элементы которых конечны и все элементы их элементов, и т. д. конечны тоже. То есть есть такое индуктивное определение:

Это называется "наследственно-конечные множества" и их можно представить как деревья, а деревьев счетное число

-- Вс ноя 07, 2010 20:50:40 --

arseniiv в сообщении #372071 писал(а):

Мне кажется, $s$ всё-таки взаимно однозначное отображение, но уже заинтересовал другой вопрос: найти какое-нибудь отношение линейного порядка $R \subset S^2$ такое, что $aRb$ достаточно легко вычислить

А в каком виде Вы свои множества представляете?
Это как-то связано с тем языком, который мы в CS разделе обсуждали?

-- Вс ноя 07, 2010 20:57:44 --

arseniiv в сообщении #372005 писал(а):

Если вот это отображение взаимно-однозначно (я в этом не очень сомневаюсь, но строгие доказательства плохо получаются), то, значит, $S \sim \mathbb N$.
Отображение $s \colon \mathbb N_0 \to S$: $s(\sum_{k = 0}^\infty {2^k a_k}) = \left\{s(k) \, |\, a_k = 1\right\}$, где $\forall k \in \mathbb N_0 \left( a_k \in \{0,\,1\} \right)$, притом $s(0) = \varnothing$.

Взаимно-однозначно.

[arseniiv]

Xaositect в сообщении #372143 писал(а):

Это как-то связано с тем языком, который мы в CS разделе обсуждали?

В точку!

Xaositect в сообщении #372143 писал(а):

А в каком виде Вы свои множества представляете?

Как раз деревьями: запись TSet содержит односвязный список таких же записей; считается пустым множеством, если список пустой.

Xaositect в сообщении #372143 писал(а):

Взаимно-однозначно.

Спасибо! Меня сомневало обратное к нему отображение, в математике ведь не принято доказывать алгоритмами. Но всё равно оно не нужно, т. к. достаточно интересные наследственно-конечные множества (спасибо, что сказали название!) не влезут даже в число размером с килобайт, наверно; так что я решил оставить деревья, но чтобы их эффективно сравнивать, надо упорядочить поддеревья, вот для чего мне нужно $R$.

Вынужден уйти спать.