Доказательство Кантора

[Sed]

Множество $2^A$ - это множество подмножеств $A$, по аксиоме множества подмножеств $\forall a \exists d \forall b (b\in d \leftrightarrow b \subseteq a)$

[Urnwestek]

Верно! Ещё парочка задач:

0.45. Дать определение подмножества множества A.
0.47. Что означает запись $A \subseteq B$ ?

[Sed]

0.47. $A$ - подмножество $B$ или $b \subseteq a \leftrightarrow \forall c(c \in b \to c\in a)$
0.45. $p \subseteq A$, конкретно - это $p_1=\varnothing$ и $p_2=D$ (где $D=\{A\}$).

А Вы скоро к нумерации действительными числами придете ?

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Дискуссионные темы (М)»

[Urnwestek]

Цитата:

А Вы скоро к нумерации действительными числами придете ?

С вами вполне можно и к сюрреальным числам Конвея прийти. (:

Цитата:

(где $D=\{A\}$).

Лучше это не обговаривать, мы ведь условились, что D — это любое множество? На досуге можете попробовать, подаказывать существование $A = \{\{\},\{A\}\}$ и, тем самым, противоречивость ZFC. А сейчас на это лучше не отвлекаться. (:

Цитата:

0.47. или $b \subseteq a \leftrightarrow \forall c(c \in b \to c\in a)$

Прекрасно!


0.473 Подставьте формально в эту запись "$b \subseteq a \leftrightarrow \forall c(c \in b \to c\in a)$ " следующее
$a = \{\{\}, D \}$
$b = \{\{\}, D \}$
0.4733 Будет ли b подмножеством a? Если да, то
0.4735 Будет ли b элементом $2^a$? Если нет, объяснить почему, если да, то
0.4737 Перерешать задачу 1.

[Sed]

0.473 подставил
0.4733 да
0.4735 да
0.4737 $A=2^A=\{\{\},D\}$, а т.к. $D=\{A\}$, а $A=\{\{\},D\}$, то в чуть более полной записи: $\{\{\}, \{\{\},D\}\}$, откуда видно, что $b=\{\{\},D\}$ и действительно является подмножеством и элементом $A$ и $2^A$.

[Someone]

Sed в сообщении #770549 писал(а):

Someone в сообщении #770247 писал(а):

То есть, — это упорядоченная пара $(a,f(a))$ для некоторого $a \in A$ ? А нафиг Вам это множество $\Omega$ понадобилось? Оно для доказательства не нужно. К тому же, по-моему, Вы с ним преизрядно запутались.

Это был бы контрпример к теореме, множество - функция, ставящая в 1-1 соответствие собственные элементы и подмножества.

provincialka в сообщении #770317 писал(а):

Если у вас $x\in A \times 2^A$ или $x\in f$ - это пара (элемент, подмножество), то к нему нельзя применять $f$, то есть выражение $f(x)$ не имеет смысла.

А почему нельзя ?
Хотя Someone и говорит, что регулярность не причем, я все-таки чуток посопротивляюсь.
Если и исходное множество $A$ и декартово произведение $D=A \times 2^A$ состоят из упорядоченных пар, то при отсутствии аксиомы регулярности ничто не мешает нам поставить знак равенства между парами из множества $A$ и парами из множества $D$.
К примеру, $A=(a,b), 2^A = ((), (a), (b), (a,b)), D=A \times 2^A = ( (a,()), (a,(a)), (a,(b)), (a,(a,b)), (b,()), (b,(a)), (b,(b)), (b,(a,b)) )$, теперь приравниваем $a=(a,()), b=(a,(a,b))$ и получаем $((a,(a)), (a,(b)), (b,()), (b,(a)), (b,(b)), (b,(a,b)) )$
Без аксиомы регулярности легитимны множества $a \in a$.
Т.к. аксиома экстенсиональности остается в силе, то $a=\{a\}$, а множество подмножеств будет $\{\{\},\{a\}\}$, биекции нет.
Тогда положим $a=2^a$, т.е. $a=\{\{\},\{a\}\}$, множество подмножеств останется тем же $\{\{\},\{a\}\}$ и будет равно исходному множеству $a$.
Все, биекция между множеством элементов и множеством подмножеств построена, исходная в теореме Кантора биективная функция $f$ - это множество $a$ (конечно, на случай отказа от аксиомы регулярности).

Разберитесь со скобками: где круглые, где фигурные. Они имеют разный смысл. Вы же всё свалили в одну кучу, да ещё приравниваете что попало чему попало. Пока это выглядит как полный бред.

Поскольку обсуждаемая теорема Кантора действительно доказывается без аксиомы регулярности, нет нужды разбираться в Ваших путаных выдумках, разбирайтесь в них сами.

Основой доказательства является следующее утверждение: если $T\subseteq A$ и задано отображение $F\colon T\to 2^A$, то множество $Z=\{t\in T:t\notin F(t)\}$ не является значением отображения $F$ ни для какого $t\in T$.
Доказательство. Множество $Z$ существует по аксиоме выделения. Из определения множества $Z$ следует, что

$$t\in Z\Leftrightarrow t\notin F(t).$$

Если мы предположим, что существует такой элемент $t_0\in T$, что $F(t_0)=Z$, то сразу получаем противоречие:

$$t_0\in Z\Leftrightarrow t_0\notin Z.$$

Поэтому такого элемента $t_0$ нет.

Если теперь взять $T=A$, то получим, что никакое отображение $F\colon A\to 2^A$ не является сюръективным. Тем более оно не может быть биективным. Поэтому мощности множеств $A$ и $2^A$ различны. А поскольку неравенство $\lvert A\rvert\leqslant\lvert 2^A\rvert$ очевидно, то $\lvert A\rvert<\lvert 2^A\rvert$.

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

[Urnwestek]

Извините, но у меня с вами скоро крыша съедет (не в обиду вам, просто я, наверное, плохо умею объяснять), задач минус пятого порядка не будет. (:
Если коротко, тезисы:

О $A = \{A\}$
1) В ZFC множество, входящее в свой собственный элемент не существует.
2) В ZFC без аксиомы регулярности нужно доказывать его существование, прежде чем работать с ним.
3) Из доказательства его существования в ZFC без аксиомы регулярности следует противоречивость ZFC с аксиомой регулярности, так что занятие это безблагодарное.
4) Оперировать несуществующим объектом — не комильфо.

О теореме Кантора:
1) Вы под символами $2^A$, где $A$ — множество, понимаете нечто совершенно иное, чем большинство людей, поэтому слова Кантора поняли неправильно. Почитайте учебники и разберите примеры множеств $2^A$, когда $A$ — конечно. Есть много хороших учебников по ТМ, где это разбирается; я, например, учился по Thomas Jech "Set Theory", но, уверен, в соседних темах вы найдёте и много других хороших учебников!

Удачи вам в постижении ТМ! (:

[Someone]

Urnwestek в сообщении #770722 писал(а):

1) В ZFC множество, входящее в свой собственный элемент не существует.
2) В ZFC без аксиомы регулярности нужно доказывать его существование, прежде чем работать с ним.
3) Из доказательства его существования в ZFC без аксиомы регулярности следует противоречивость ZFC с аксиомой регулярности, так что занятие это безблагодарное.

Вот именно. Более того, доказывается прямо противоположное: если ZFC без аксиомы регулярности непротиворечива, то ZFC с аксиомой регулярности тоже непротиворечива.

Между прочим, в книге К. Куратовского и А. Мостовского "Теория множеств" излагается ZFC без аксиомы регулярности. Обсуждаемая здесь "теорема Кантора" благополучно доказывается. Вообще, отсутствие аксиомы регулярности создаёт некоторые технические трудности, однако при желании без неё можно обойтись. (Добавление: трудности возникают в различных построениях, но не в доказательстве теоремы о мощности множества подмножеств. Эта теорема к аксиоме регулярности совершенно безразлична.)

Кстати, кто-нибудь может сказать, в какой работе Кантор доказывал эту теорему? Я внимательно просмотрел весь сборник его работ, но этой теоремы не нашёл. Возможно, пропустил.

[arseniiv]

Sed в сообщении #770639 писал(а):

Множество конечно, просто его полная запись бесконечна.

$a$, для которого $a = 2^a$, не может быть конечным. Я же привёл доказательство того, что в нём содержатся множества вида $\{^{n\text{ раз}}\varnothing\}^{n\text{ раз}}$. (И да, оно не тоже опирается на аксиому регулярности.)

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

И вообще складывается впечатление, что Sed — тролль.

[Xaositect]

Someone в сообщении #770781 писал(а):

Кстати, кто-нибудь может сказать, в какой работе Кантор доказывал эту теорему? Я внимательно просмотрел весь сборник его работ, но этой теоремы не нашёл. Возможно, пропустил.

В биографиях говорят про "Über eine elementare Frage der Mannigfaltigkeitslehre". С немецким у меня плохо, а перевода я не нашел, но там явно описывается диагональный метод и если я правильно понял, то в конце говорится что-то про то, что для каждого кардинального числа существует большее.

[Sed]

(Оффтоп)

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

И вообще складывается впечатление, что Sed — тролль.

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

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

Я один, а Вас много (на тот Ваш пост я тоже ответил, как мог, на остальное – сильно опоздал) постараюсь отвечать подробней (по мере сил и времени), отвечал сначала на более простые задания.

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

$a$, для которого $a = 2^a$, не может быть конечным. Я же привёл доказательство того, что в нём содержатся множества вида $\{^{n\text{ раз}}\varnothing\}^{n\text{ раз}}$. (И да, оно не тоже опирается на аксиому регулярности.)

Из того, что множество представимо $\{^{n\text{ раз}}a\}^{n\text{ раз}}$ (если я правильно понимаю Вашу запись), не обязательно следует, что оно бесконечно. Т.к. мы говорим о множествах, которые могут быть своим элементом $a \in a$.
Возьмем множество $a=\{a\}$ в котором не содержится пустого множества $\varnothing \notin a$, его полная запись бесконечна и имеет вид $\{^{n\text{ раз}}a\}^{n\text{ раз}}$

Впрочем, об этом позже.

Я сейчас кое-что попытаюсь доказать, а Вы укажите на ошибку. Потом уже буду отвечать на Ваши вопросы.

Дано множество $a=\{1,2,3\}$
Его булеан $2^a=\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}, \{1,2,3\}\}$
Выделим множество $b=\{x \in 2^a | (0<|x \cap a|<2)\} = \{\{1\},\{2\},\{3\}\}$ (можно и другое трехэлементное, например $\{\{1,2\},\{2,3\},\{1,2,3\}\}$...
И докажем, методом Кантора, что любая функция из $a$ в $b$ не является биекцией.

Теорема. Любая функция из $a$ в $b$ не является биекцией.
Доказательство.
Возьмем произвольную $F: a \to b$ и докажем, что $f$ - не является биекцией, методом от противного.
Пусть $f$ - биекция.
По аксиоме выделения существует множество $B=\{x\in a | x \notin f(x)\}\subset a$.
Раз $f$ - биекция, существует какой-то элемент $b\in a$, соответствующий этому подмножеству, т.е. $f(b)=B$. Возможны два варианта:

1) $b\in B$. С одной стороны, так как $B=f(b)$, это значит $b\in f(b)$. С другой стороны, поскольку $B$ содержит только элементы, удовлетворяющие условию $x \notin f(x)$, $b$ тоже должно ему удовлетворять, т.е. $b\in B$, т.е. $b \notin f(b)$

2) $b \notin B$, то есть $b \notin f(b)$. Поскольку $B$ содержит все элементы, удовлетворяющие условию $x\notin f(x)$, $b$ тоже должен ему принадлежать, т.е. $b\in B$.

В обоих случая получаем противоречие. Значит, исходная посылка о то, что $f$ биекция неверна. $f$ была выбрана произвольно, значит любая функция из $f$ не может являться биекцией.

[Someone]

Sed в сообщении #771084 писал(а):

Дано множество $a=\{1,2,3\}$
Его булеан $2^a=\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}, \{1,2,3\}\}$
Выделим множество $b=\{x \in 2^a | (0<|x \cap a|<2)\} = \{\{1\},\{2\},\{3\}\}$
И докажем, методом Кантора, что любая функция из $a$ в $b$ не является биекцией.

Теорема. Любая функция из $a$ в $b$ не является биекцией.
Доказательство.
Возьмем произвольную $F: a \to b$ и докажем, что $f$ - не является биекцией, методом от противного.
Пусть $f$ - биекция.
По аксиоме выделения существует множество $B=\{x\in a | x \notin f(x)\}\subset a$.
Раз $f$ - биекция, существует какой-то элемент $b\in a$, соответствующий этому подмножеству, т.е. $f(b)=B$.

Две ошибки в последнем предложении. Одна из них состоит в том, что Вы используете букву "$b$" в двух совершенно различных смыслах: как константу — обозначение конкретного множества $b=\{\{1\},\{2\},\{3\}\}$, и как переменную — обозначение произвольного элемента множества $a$. Вторая ошибка состоит в том, что построенное множество $B$ (подмножество множества $a$) не обязано быть элементом множества $b$, так как $b\neq 2^a$, поэтому последующие рассуждения лишены каких-либо оснований и ничего не доказывают. Соответственно, я их не анализирую. Есть ещё опечатка выше: Вы одно и то же отображение обозначаете двумя разными буквами "$F$" и "$f$".

-- Сб окт 05, 2013 22:06:09 --

(Оффтоп)

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

В биографиях говорят про "Über eine elementare Frage der Mannigfaltigkeitslehre". С немецким у меня плохо, а перевода я не нашел, но там явно описывается диагональный метод и если я правильно понял, то в конце говорится что-то про то, что для каждого кардинального числа существует большее.

Спасибо, нашёл. У меня с немецким языком вообще никак, но зато есть сборник работ Кантора на русском языке, напечатанный издательством "Наука" в 1985 году. В нём это статья № 9 "Об одном элементарном вопросе учения о многообразиях". Статью эту я смотрел, но, поскольку искомое утверждение не сформулировано в виде теоремы, а затеряно в тексте, при просмотре я его не заметил.

[Sed]

Someone в сообщении #771100 писал(а):

Две ошибки в последнем предложении. Одна из них состоит в том, что Вы используете букву "$b$" в двух совершенно различных смыслах: как константу — обозначение конкретного множества $b=\{\{1\},\{2\},\{3\}\}$, и как переменную — обозначение произвольного элемента множества $a$. Есть ещё опечатка выше: Вы одно и то же отображение обозначаете двумя разными буквами "$F$" и "$f$".

Поправил:

Sed в сообщении #771084 писал(а):

Дано множество $a=\{1,2,3\}$
Его булеан $2^a=\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}, \{1,2,3\}\}$
Выделим множество $b=\{x \in 2^a | (0<|x \cap a|<2)\} = \{\{1\},\{2\},\{3\}\}$
И докажем, методом Кантора, что любая функция из $a$ в $b$ не является биекцией.

Теорема. Любая функция из $a$ в $b$ не является биекцией.
Доказательство.
Возьмем произвольную $f: a \to b$ и докажем, что $f$ - не является биекцией, методом от противного.
Пусть $f$ - биекция.
По аксиоме выделения существует множество $B=\{x\in a | x \notin f(x)\}\subset a$.
Раз $f$ - биекция, существует какой-то элемент $c\in a$, соответствующий этому подмножеству, т.е. $f(c)=B$.

Someone в сообщении #771100 писал(а):

Вторая ошибка состоит в том, что построенное множество $B$ (подмножество множества $a$) не обязано быть элементом множества $b$, так как $b\neq 2^a$, поэтому последующие рассуждения лишены каких-либо оснований и ничего не доказывают. Соответственно, я их не анализирую.

Это не имеет значения, т.к. рассматривается $f: a\to b$, а не $f:a\to 2^a$. Впрочем, даже если принять Ваш аргумент, т.е. что множество $B$ может и не быть в $b$, но быть в $2^a$, то тем более в $a$ есть элемент $x\notin f(x)$, т.е. биекции нет. Можно даже добавить этот аргумент в теорему.

[Someone]

Sed в сообщении #771113 писал(а):

Это не имеет значения, т.к. рассматривается $f: a\to b$, а не $f:a\to 2^a$. Впрочем, даже если принять Ваш аргумент, т.е. что множество $B$ может и не быть в $b$, но быть в $2^a$, то тем более в $a$ есть элемент $x\notin f(x)$, т.е. биекции нет. Можно даже добавить этот аргумент в теорему.

Точно тролль, причём, очень наглый. Пора банить.

Вы ведь "пытаетесь" доказать отсутствие биекции $a$ на $b$, и рассматриваете отображение $a$ в $b$. Поэтому элементы, не принадлежащие $b$, по определению не имеют прообразов и не должны их иметь, поскольку наличие таких прообразов противоречило бы биективности. В частности, если построенное множество $B$ не является элементом множества $b$, то просто по определению отображения $f$ не существует такого элемента $x\in a$, чтобы выполнялось $f(x)=B$, а если бы он, не дай бог, существовал, то $f$ не могло бы быть биекцией $a$ на $b$. Поэтому доказывать это (отсутствие $x\in a$) не нужно, хотя рассуждения Кантора в этом случае тоже работают и показывают, что такого $x$ нет — в полном согласии с определением отображения $f$. Поскольку $B\notin b$, это не приводит к противоречию и никак не опровергает биективности $f$.

Вы действительно этого не понимаете? Тогда, может быть, попросить модераторов заблокировать Вас за патологическую безграмотность? Прецеденты были.