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

[Xaositect]

Во-первых, Вы опять путаетесь в терминологии.
Функции для непустого $A$ пустыми быть не могут. Соответсвенно, когда Вы говорите о пустоте $f_1$ и $f_2$, Вы имеете в виду что-то другое.
Пустота множества $B$ и Ваш пункт (1) никакого значения в доказательстве не имеет.

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

пустоты $B$ (отсутствия прообраза $f$)

Отсутствие прообраза $B$ -- это не пустота $B$, а утверждение $\forall b\, (f(b) \neq B)$, и мы его доказываем, а не предполагаем.

Вы согласились с тем, что мы получили противоречие. Никаких предположений о множестве $B$ мы при этом делали, соотвественно неверным должно быть одно из предположений, которые у нас есть:
1. $f$ -- функция из $A\to 2^A$ (условие теоремы)
2. $f$ -- биекция
Больше никаких предположений (в частности, предположения о пустоте $B$) мы не делали.

[provincialka]

Боже, Sed, как вы все запутали! Ну пусть, в частном случае, $B$ пусто, т.е. не существует элементов не входящих в свой образ. То есть каждый элемент входит в свой образ. То есть каждый образ элемента содержит хотя бы один элемент, а именно, свой прообраз.

Хорошо, но у пустого множества (равного здесь $B$) нет элементов! А мы доказали, что у всех образов - есть. Значит что? Что $B$ - не образ, никакого элемента.

И вообще, если вы согласны с рассуждением в общем случае, зачем пытаетесь его опровергнуть в случае частном?

[Someone]

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

Вроде логику понял, но все-равно не могу признать этого перехода. Почему из пустоты $B$ следует, опровержение посылки о биективности $f_2$,

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

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

Доказывая пустоту$B$, т.е. отсутствие элементов $x\in f(x)$

Ерунду пишете. Очень глупую. Посмотрите на определение $B$.

[Sed]

Спасибо всем, Вы меня почти убедили.

Но я кажется нашем глюк, заставлявший меня путать свойство $x \notin f(x)$, как свойство, выделяющее (по аксиоме выделения) функцию $f$, как подмножество декартова произведения $A \times P(A)$ и то же самое свойство $x \notin f(x)$, как свойство, выделяющее подмножество самого множества $A$.

Еще раз процитирую из теоремы Кантора одно предложение: "Рассмотрим множество $B$, состоящее из всех элементов $A$, не принадлежащих своим образам при отображении $f$ (оно существует по аксиоме выделения): $B=\{x\in A : x \notin f(x)\}$."

Что такое $f(x)$ ?

1). $f(x)$ - это некое подмножество $A$ (одно из...).
В таком случае $f$ - это не функция. $f$ - это некое подмножество $A$ (одно, двух, трех...и т.д. элементное).
Т.е. когда выделяется подмножество с этим свойством $B=\{x\in A : x \notin f(x)\}$, то выделяется только те элементы $A$, которые не являются элементами некоего (неопределенного никак подмножества $A$, обозначенного $f(x)$.

2). $f(x)$ - это элемент подмножества декартова произведения $A \times P(A)$ (т.е. отношения с известными ограничениями для функций).
Тогда $f(x)$ не может быть подмножеством $A$ (одним из...), т.к. $f(x)$ обязано состоять только из упорядоченных пар, вида $(x,y), x \in A, y \in P(A)$. Такое, наверно, возможно, в частном случае $x=(x,y)$, но это означает, что множество $A$ обязано быть упорядоченным и не регулярным (элементы содержат себя).
Что же касается случая $B=\{x\in A : x \notin f(x)\}$, то тут вообще непонятно, что за свойство $x\notin f(x)$ ? Любые множества не входящие в какое-либо подмножество декартова произведения $A \times P(A)$ ? Тогда (при отсутствии упорядоченности или регулярности $A$) $B$ будет содержать все элементы $A$, а при наличии таковых я вообще не могу интерпретировать эту "корректную" запись.

В общем, объясните, мне пожалуйста, что такое $f(x)$ ? Если это множество, то элементом какого множества оно является: подмножества декартова произведения или множества всех подмножеств $A$ ?
Свойство $\varphi=\{x\notin f(x)\}$ в формуле $B=\{x\in A : \varphi \}$ что означает: что $x$ - не является элементом некоего подмножества $A$ или что $x$ не является элементом некоего подмножества декартова произведения множества $A$ и всех его подмножеств ?

Когда в теореме рассуждают: если $y\in B$, то $y \in f(y)$, а тогда по определению $B, y \notin B$ и наоборот, если $y \notin B$, то $y \notin f(y)$, а следовательно $y \in B$, то не происходит ли путаницы между свойствами, выраженными одной и той же формулой, но отнесенной к разным объектам: сначала к $B$, как подмножеству $A$, выделенному при условии $x \notin f(x)$, где $f(x) \subseteq P(A)$, а потом как подмножеству $A$, выделенному при условии $f(x) \subseteq A \times P(A)$ ?

[Xaositect]

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

1). $f(x)$ - это некое подмножество $A$ (одно из...).
В таком случае $f$ - это не функция. $f$ - это некое подмножество $A$ (одно, двух, трех...и т.д. элементное).
Т.е. когда выделяется подмножество с этим свойством $B=\{x\in A : x \notin f(x)\}$, то выделяется только те элементы $A$, которые не являются элементами некоего (неопределенного никак подмножества $A$, обозначенного $f(x)$.

$f(x)$ - это именно что подмножество $A$. Почему Вы думаете, что $f$ в таком случае не функция, я не понимаю. $f$ --- это функция, которая каждому элементу $A$ сопоставляет некоторое подмножество $A$.

$x\in A$
$f\colon A\to 2^A$
Значит, $f(x)\in 2^A$.

А вот график функции $f$, то есть множество всех пар вида $(x, f(x))$, будет подмножеством $A\times 2^A$.

[provincialka]

Я придумала интерпретацию, аналогичную "парадоксу брадобрея". Пусть элементы $x\in A$ - солдаты, а $f(x)$ - множество солдат, которых может брить $x$. Предположим, что для каждого подмножества $A_1$ из $A$ есть солдат, который бреет только тех, кто входит в $A_1$. Рассмотрим множество $B$ тех, кто не бреет сам себя. По предположению, должен существовать солдат, который бреет только солдат из $ B$. Входит ли он в $B$?

Если входит, значит, в частности, он бреет себя, но такие солдаты не входят в $B$ по постррению. И наоборот, если не входит, то он удовлетворяет свойству, по которому он должен входить в $B$. Противоречие!

[Xaositect]

(Оффтоп)

Самое обидное, что я вот сейчас читаю "Homotopy type theory" и понимаю, что я без проблем могу написать это доказательство для проверки на компьютере. А вот человеку объяснить, чтобы он проверил и понял, не могу. Нету у меня педагогического таланта.

[provincialka]

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

(Оффтоп)

Самое обидное, что я вот сейчас читаю "Homotopy type theory" и понимаю, что я без проблем могу написать это доказательство для проверки на компьютере. А вот человеку объяснить, чтобы он проверил и понял, не могу. Нету у меня педагогического таланта.

(Оффтоп)

Да все нормально Вы объясняете. Просто клиент упорный попался.

[Sed]

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

Самое обидное, что я вот сейчас читаю "Homotopy type theory" и понимаю, что я без проблем могу написать это доказательство для проверки на компьютере. А вот человеку объяснить, чтобы он проверил и понял, не могу. Нету у меня педагогического таланта.

Ошибаетесь, Вы отлично все объясняете, я вроде понял, что $f(x)$ - это не элемент какого-то подмножества прямого произведения $D \subseteq \{A \times 2^A\}$, а элемент множества значений, т.е. $2^A$.
Вроде бы для понимания теоремы достаточно.

Но мне все-равно хочется докопаться до глюка в своей голове. Мне осталось понять, что свойство $\varphi =\{x \notin f(x)\}$ выделяет в $f$. Сам не знаю, зачем.
Т.к. $f \subseteq \{A \times 2^A\}$ и состоит из упорядоченных пар $(x,f(x))$, то множество $\Omega =\{x \in f : x \notin f(x)\}$ тоже состоит из упорядоченных пар $(x,f(x))$, т.е. тоже является неким отношением на $\{A \times 2^A\}$, возможно $f$... Или нет ?

(Оффтоп)

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

Да все нормально Вы объясняете. Просто клиент упорный попался.

Да, уж, сожалею.

[provincialka]

У вас опять путаница в обозначениях. Из чего состоит $\Omega$, чему принадлежит $x$ - исходному множеству $A$ или множеству пар $f$?

А то отношение между $A$ и $2^A$, которое Вы ищете - ну, оно существует, хотя может быть и тривиальным (пустым). Как еще его можно интерпретировать - не вижу. Это набор солдатов, не бреющих смих себя, и каждому дан список тех, кого он может боить.

Кстати, нельзя писать, что это "отношение на $\{A\times 2^A\}$. Во первых, это соотношение между $A$ и $2^A$, а во-вторых, зачем там фигурные скобки? Это уж получается множество из одного элемента.

[Sed]

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

Кстати, нельзя писать, что это "отношение на $\{A\times 2^A\}$. Во первых, это соотношение между $A$ и $2^A$, а во-вторых, зачем там фигурные скобки? Это уж получается множество из одного элемента.

Вы правы, несомненно, я зря там наставил скобок, все это моя путаница с предикатами и множествами (они так неразличимы, порой, простите, скобки нужно убрать, конечно).

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

У вас опять путаница в обозначениях.
Из чего состоит $\Omega$

?
Она определена так: $\Omega =\{x \in f : x \notin f(x)\}$. Т.к. у нас $f$- произвольное по условию, то и $\Omega$ определенней станет только после определения $f$.

Хотя, поразмыслив, я понял, что лучше определить так: $\Omega =\{x \in A \times 2^A : x \notin f(x)\}$. Т.е. $\Omega$ - это такое отношение (функция, возможно), на R на $A \times 2^A$, для которого истинно $\varphi = (x \notin f(x))$.

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

…чему принадлежит $x$ - исходному множеству $A$ или множеству пар $f$?

$x \in f$.

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

А то отношение между $A$ и $2^A$, которое Вы ищете - ну, оно существует, хотя может быть и тривиальным (пустым). Как еще его можно интерпретировать - не вижу. Это набор солдатов, не бреющих смих себя, и каждому дан список тех, кого он может боить.

Гениально ! По-моему именно это я и хотел выразить !

Это множество пусто, только если принимается аксиома регулярности. В противном случае, существуют множества: $x=(y,f(x)), y=(x,f(y))$ удовлетворяющие условию $\varphi =\{x \notin f(x)\}$ и тем не менее,являющиеся "антибиективными" (не знаю, как лучше выразить это 1-1 соответствие, когда ни инъекция, ни сюръекция, не существуют), а 1-1 соответствие есть.

[Someone]

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

Мне осталось понять, что свойство $\varphi =\{x \notin f(x)\}$ выделяет в $f$.

В $f$ ничего не выделяет. Да нам и не надо ничего выделять в $f$. Нам нужно выделить в множестве $A$ подмножество $B$, не имеющее прообраза. Вот именно это условие $\varphi=(x\notin f(x))$ (с круглыми скобками, а не с фигурными, которые имеют другой смысл) и делает: $B=\{x:x\in A\wedge x\notin f(x)\}$. Разумеется, надо доказать, что не существует такого $x\in A$, что $f(x)=B$.

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

$x \in f$.

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

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

если принимается аксиома регулярности

Аксиома регулярности для доказательства не нужна, и не надо её сюда впутывать.

[provincialka]

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

[Sed]

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$ (конечно, на случай отказа от аксиомы регулярности).

[Sed]

Теперь я могу продемонстрировать, где в теореме Кантора "слабое звено", на примере своего множества $a =\{\{\},\{a\}\}$.
Выпишу явно биективную функцию $f$: $((\{\} \to \{\}), (\{a\} \to \{a\}) )$

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

Теорема. Для любого множества $A$ не существует биекции между $A$ и $2^A$.

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

До этого момента все верно. Множество $B=f(b)=\varnothing$ более явно: $\varnothing = \{\varnothing \in \{\varnothing,\{a\}\} | \varnothing \notin \varnothing\}$.

Цитата:

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

Теперь мне предельно ясно в чем ошибка. Из того, что $b \notin B$ никак не следует, что $b\in B$. И как я сразу не обратил внимание на странную запись $B=f(x)=\{x\in A|x\notin B\}$ ?
Тут же явное противоречие заложено, как множество $B$ может состоять из элементов, которые ему не принадлежат ??!! Ну, бред же… Т.е. так, конечно можно определить множество, но разве что пустое !

Цитата:

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

Не-е, ложна не исходная посылка, ложно само умозаключение, основанное на существовании по аксиоме выделения множества $B$, которое "содержит элементы, которое оно не содержит".