Равенство множеств

[almost]

(Оффтоп)

Спросил жену, что она думает о парадоксе брадобрея.
Удивительная женская логика, сначала она сказала, что "брадобрей" - это женщина, потом, подумала и сказала: "Брадобрей" - это парикмахерская.
А я сразу понял, что парадокс - ее рекламный слоган
"ООО Брадобрей" - бреет всех, кто не бреется сам !

[Виктор Викторов]

Детектив из трех определений.

Итак, на страницах 25-26 второго издания нам сообщили о точке зрения а) (которая мне очень нравится) и сказали, что в основном именно этой точки зрения авторы и будут придерживаться в этой главе. Но уже на странице 27 читаем: «Держа в уме позицию (с) по отношению к равенству мы представляем следующее определение». Что же это за позиция (с)?

«c) Равенство вводится посредством определения. В этом случае определение должно быть таким, что [свойства] (i)-(iv) становятся доказуемыми либо только доводами <arguments> логики, либо доводами <arguments>, которые также могут использовать аксиомы теории множеств.» Abraham A. Fraenkel, Yehoshua Bar-Hillel, Azriel Levy «FOUNDATIONS OF SET THEORY» SECOND REVISED EDITION, 1973 страница 26.

Теперь посмотрим, что же это за определение.
«Определение II. Говорят, что $x$ конгруэнтно по членству <membership-congruent> $y$ $(x=_my)$ тогда и только тогда, когда для всех $z$ $x\in z$ влечет $y\in z{,}$ и также тогда и только тогда, когда для всех $u$ $u\in x$ влечет $u\in y{,}$ другими словами, $x=_my$ если каждое множество, которое содержит одно из них также содержит и другое, и каждый элемент содержащийся в одном из них также содержится и в другом.
В символической записи: $x =_my=_{Df}\forall z(x\in z\leftrightarrow y\in z)\wedge \forall u(u\in x\leftrightarrow u\in y){.}$»
Abraham A. Fraenkel, Yehoshua Bar-Hillel, Azriel Levy «FOUNDATIONS OF SET THEORY» SECOND REVISED EDITION, 1973 страница 27.

Что-то знакомое, но как-то не так. А, вот в чём дело! В первом издании было:
«Определение IIа. $x$ называется равным $y$ ($x = y$) тогда и только тогда, когда для всех $z$ $x\in z$ влечет $y\in z{,}$ и обратно, $y\in z$ влечет $x\in z{,}$ т. е. если каждое множество, содержащее одно из множеств $x$ и $y{,}$ содержит также и другое. Если $x$ не равно $y{,}$ оно называется отличным от $y$ ($x\neq y$) (или множества $x$ и $y$ называются различными).
В символической записи: $x =y=_{Df}(\forall z)(x\in z\equiv y\in z){.}$
Определение IIb. $x$ называется равным $y$ тогда и только тогда, когда $x\subseteq y$ и $y\subseteq x$ одновременно, т. е. каждое из множеств $x$ и $y$ есть подмножество другого. Иначе говоря (формулируя в первоначальных терминах), $x = y{,}$ если каждый член одного из этих множеств есть также и член другого. В противном случае $x$ отлично от $y$ (или $x$ и $y$ различны).
В символической записи: $x =y=_{Df}(\forall z)(z\in x\equiv z\in y){.}$» Абрахам Френкель, Иегоша Бар-Хиллел "Основания теории множеств". Издательство "Мир" Москва 1966. Страница 47-48.

Во втором издании два определения объединили в одно. И ... не только. Это теперь не определение равенства, а определение «конгруэнтности по членству» т. е. некоторой эквивалентности! (Я ведь обещал детектив). Также слегка незаконно использовано слово «элемент», но не будем придираться к мелочам. Конечно, позже из этой «конгруэнтности по членству» сделают равенство. Но сам факт замены определения равенства, которое весьма смахивало на определение эквивалентности, определением «конгруэнтности по членству» уже интересен. Продолжение следует.

[Delvistar]

(Оффтоп)

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

Если множество $L$(люди), разбить на два подмножества $L_{1}$ - кто бреется сам, и $L_{2}$ - кто сам не бреется, и отметить не пересекаемость "брить только из подмножества $L_{2}$, то мы не найдём ни одного элемента подмножества $L_{3}$, так как его нет или же оно пустое.

Подобный парадокс, это красивая обвёртка простой задачи. Имеется множество $\mathbb{N}$, состоящее из двух не пересекаемых подмножеств. Чётных чисел и не чётных. Разве мы можем найти натуральное число, которое может быть и чётным и не чётным одновременно?

[Виктор Викторов]

Delvistar в сообщении #440298 писал(а):

Если множество $L$(люди), разбить на два подмножества $L_{1}$ - кто бреется сам, и $L_{2}$ - кто сам не бреется, и отметить не пересекаемость "брить только из подмножества $L_{2}$, то мы не найдём ни одного элемента подмножества $L_{3}$, так как его нет или же оно пустое.
Подобный парадокс, это красивая обвёртка простой задачи. Имеется множество $\mathbb{N}$, состоящее из двух не пересекаемых подмножеств. Чётных чисел и не чётных. Разве мы можем найти натуральное число, которое может быть и чётным и не чётным одновременно?

Да. Действительно, взглянув на разбиение, всё становится ясно. Но «обвёртка» тоже важна.

Вот ещё одна «обвёртка» «ТЕОРЕМА 1. Существует в точности одно пустое множество.» Α. Α. ФРЕНКЕЛЬ И. БАР-ХИЛЛЕЛ «ОСНОВАНИЯ ТЕОРИИ МНОЖЕСТВ» страница 60. То, что надо обосновывать существование пустого множества, несомненно верно. А вот почему из учебника в учебник качует очевидное доказательство единственности пустого множества (ведь каждое множество единственно по аксиоме объемности, почему же такая честь пустому множеству), я долго не понимал. Не понимал до тех пор, пока не обратил внимание на очевидный, но нигде не упоминаемый факт, что пустое множество единственное множество нулевой мощности.

[Виктор Викторов]

С разрешения AGu публикую его письмо:

AGu писал(а):

Добрый день.

Виктор Викторов писал(а):

"Определение IIа. $x$ называется равным $y$ ($x = y$) тогда и только тогда, [...]

[...] когда $(\forall\,z)(z\in x\Leftrightarrow z\in y)$. Здесь подразумевается, что ни рассматриваемое исчисление, ни рассматриваемая сигнатура не содержат символ равенства и отношение равенства вводится посредством определения. В этом случае формула $x=y$, грубо говоря, представляет собой сокращение формулы $(\forall\,z)(z\in x\Leftrightarrow z\in y)$. Кстати, насколько я помню, при таком подходе потребуются некоторые дополнительные аксиомы — чтобы обеспечить доказуемость всех аксиом равенства, принятых в исчислении предикатов с равенством. (Помнится, когда-то я изучал этот вопрос. Если это важно, дайте знать, я пороюсь в своих давних материалах.) Как бы то ни было, будем считать, что в рассматриваемой аксиоматике все же доказуемы все традиционные аксиомы исчисления предикатов с равенством.

Виктор Викторов писал(а):

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

Чтобы ответить на этот вопрос, его нужно формализовать. На мой взгляд, естественной формализацией фразы «совокупность, состоящая из $x$ и $y$, состоит из одного множества» может служить служит формула $\bigl|\{x,y\}\bigr|=1$. Тогда фраза «совокупность из равносоставленных $x$ и $y$ состоит из одного множества» после перевода на формальный язык наверняка окажется доказуемой. (Я говорю «наверняка окажется», а не «окажется», так как не знаю, какие в точности аксиомы рассматриваются в обсуждаемом контексте.) Кстати, в формуле $\bigl|\{x,y\}\bigr|=1$ тоже полно сокращений. В частности, в ней используется символ равенства, раскрываемый тем же способом, что и раньше (т.е. в смысле определения IIa).

Виктор Викторов писал(а):

Френкель знал, что рано или поздно этот вопрос будет задан. Он рассмотрел в книге "Set Theory and Logic" множество $F=\left\{1, 2, 3, 4\right\}$ и множество $D$ всех степеней алгебраических уравнений разрешимых в радикалах. Очевидно, что $F=D$. Но также справедлива фраза "в восемнадцатом веке было неизвестно, что множество $D$ равно множеству $F$".

Здесь вводятся определения двух новых термов — $F$ и $D$, которые теперь не являются переменными и служат соответствующими сокращениями. Поэтому формула $F=D$ — это не атомарная формула, записывающая равенство двух переменных, а формула, которая после раскрытия используемых в ней термов $F$ и $D$ является весьма навороченной. Обозначим эту навороченную формулу символом $\Phi$. Фраза «очевидно, что $F=D$» означает, что современным математикам очевидна доказуемость формулы $\Phi$, а фраза «в восемнадцатом веке было неизвестно, что множество $D$ равно множеству $F$» означает, что в 18-м веке доказуемость $\Phi$ была открытой проблемой.

Виктор Викторов писал(а):

А заменив в этой фразе букву D на букву F, получаем абсурд (absurdity).

Никакого абсурда я здесь не вижу. Как я уже говорил, в данном контексте $F$ и $D$ — это не символы переменных, а определяемые термы. Формула $F=D$ (которую мы обозначили символом $\Phi$) является навороченной и ее доказуемость видна далеко не сразу, в то время как $F=F$ — это гораздо более простая формула $\Psi$, доказуемость которой (после раскрытия терма $F$) несомненна (и сейчас, и в 18-м веке).

Виктор Викторов писал(а):

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

При желании символы $F$ и $D$ можно называть именами. Только это не имена «множеств». Это имена (сокращения) термов, т.е. неких записей. Сейчас известна доказуемость сложной формулы, выражающей равенство двух (разных) термов $F$ и $D$, а раньше доказуемость этой формулы не была известна. Так что все очень просто. Если угодно, можно сказать и так: сейчас всем известна доказуемость формулы $F=D\Leftrightarrow F=F$, а раньше это было проблемой. (Еще раз обращаю внимание на тот факт, что в данном контексте $F$ и $D$ — это не символы переменных, а сокращения неких довольно громоздких термов.)

Виктор Викторов писал(а):

Надо сказать, что одно непонимание рождает другое. Вот теорема о существования и единственности пустого множества.
«ТЕОРЕМА 1. Существует в точности одно пустое множество.» […] Всё, что мы получаем из аксиомы объёмности, это равенство двух пустых множеств.

Кажущееся непонимание легко устраняется должной формализацией. Надо просто формализовать фразу «пустое множество единственно». Это делается так. Сначала определим фразу «$x$ пустое» как сокращение формулы $\neg(\exists\,z)(z\in x)$. Далее для произвольной формулы $\varphi$ с одной свободной переменной определим фразу «множество со свойством $\varphi$ единственно» как сокращение формулы $(\forall\,x)(\forall\,y)\bigl(\varphi(x)\,\&\,\varphi(y)\Rightarrow x=y\bigr)$. Теперь ясно, как следует понимать фразу «пустое множество единственно». Она служит сокращением формулы $\Phi\,:=\,(\forall\,x)(\forall\,y)\bigl(\neg(\exists\,z)(z\in x)\,\&\,\neg(\exists\,z)(z\in y)\Rightarrow x=y\bigr)$. Теорема 1 «по сути» и есть формула $\Phi$. (В теореме 1, правда, утверждается как единственность, так и существование, но это уже несущественная деталь.) Как видите, после формализации все неясности исчезают.

Виктор Викторов писал(а):

Кстати, и сама теорема «Существует в точности одно пустое множество» в части единственности повернулась ко мне другой стороной. Каждое множество единственно, а не только пустое.

Опять-таки чтобы ответить на вопрос, его нужно формализовать. В данном случае нужно формализовать фразу «каждое множество единственно». Откровенно говоря, я не вижу глубокого смысла в этой фразе. На ум приходит только тривиальная формула $(\forall\,x)(\exists!\,y)(y=x)$ или, что почти то же самое, $(\forall\,x)(\forall\,y)(\forall\,z)(y=x\,\&\,z=x\Rightarrow y=z)$. Если Вы действительно имели в виду что-то похожее, то, как видите, какой-либо существенной аналогии с единственностью пустого множества тут нет. Пустое множество — это множество, удовлетворяющее некоторому фиксированному условию. Поэтому можно говорить о единственности пустого множества как множества, удовлетворяющего этому условию. Говорить же о единственности «любого» множества странновато, так как в этом случае у нас нет фиксированного условия и прежний подход к раскрытию термина «единственное» применить не удается.

Виктор Викторов писал(а):

Смысл в другом: существуют различные множества каждой мощности кроме нулевой, но существует только одно множество мощности нуль.

В обсуждаемых фразах не было речи о мощностях, так что едва ли это объяснение можно счесть «ожидаемым». Смысл фразы о единственности пустого множества раскрывается формулой $(\forall\,y)(\forall\,z)($ «$y$ пустое» $\&$ «$z$ пустое» $\Rightarrow y=z)$ с должным раскрытием закавыченных сокращений.

Виктор Викторов писал(а):

Буду рад Вашему ответу. Думаю, что его есть смысл опубликовать на сайте

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

[epros]

Виктор Викторов в сообщении #440474 писал(а):

А вот почему из учебника в учебник качует очевидное доказательство единственности пустого множества (ведь каждое множество единственно по аксиоме объемности, почему же такая честь пустому множеству), я долго не понимал.

А разгадка, наверное, заключается в том, что слово "пустое" означает не имя собственное, присвоенное данному множесту, а некое свойство. То, что множество, обладающее неким свойством ("пустоты"), единственно, не есть самоочевидный факт.

[Виктор Викторов]

epros в сообщении #450063 писал(а):

Виктор Викторов в сообщении #440474 писал(а):

А вот почему из учебника в учебник качует очевидное доказательство единственности пустого множества (ведь каждое множество единственно по аксиоме объемности, почему же такая честь пустому множеству), я долго не понимал.

А разгадка, наверное, заключается в том, что слово "пустое" означает не имя собственное, присвоенное данному множеству, а некое свойство. То, что множество, обладающее неким свойством ("пустоты"), единственно, не есть самоочевидный факт.

Имя собственное здесь ни при чем. Я говорю о том, что существует единственное множество нулевой мощности. А AGu считает, что фундаментальным является именно свойство множества быть пустым

AGu писал(а):

... определим фразу «$x$ пустое» как сокращение формулы $\neg(\exists\,z)(z\in x)$.

Т. е. пустое множество – множество с уникальным свойством $\neg(\exists\,z)(z\in x)$.

[epros]

Виктор Викторов в сообщении #450082 писал(а):

Я говорю о том, что существует единственное множество нулевой мощности. А AGu считает, что фундаментальным является именно свойство множества быть пустым

Что значит "фундаментальным"? Аксиома пустого множества утверждает существование множества с НЕКИМ свойством. Без аксиомы экстенсиональности его единственность не очевидна.

[AGu]

epros в сообщении #450317 писал(а):

Виктор Викторов в сообщении #450082 писал(а):

Я говорю о том, что существует единственное множество нулевой мощности. А AGu считает, что фундаментальным является именно свойство множества быть пустым

Что значит "фундаментальным"?

Лучше было бы сказать «определяющим». Для ясности привожу фрагмент нашей переписки о том, что можно понимать под «единственностью пустого множества».

AGu писал(а):

Виктор Викторов писал(а):

Речи-то о мощности ещё нет, но есть всего одна мощность (нулевая), с единственным множеством этой мощности. Каждой другой мощности существует, по крайней мере, два различных множества (и это скромно сказано).

Все это верно, но «$x$ имеет нулевую мощность» — всего лишь одно из эквивалентных свойств, выделяющих (единственное) пустое множество. Чем хуже, например, свойство «${\mathcal P}(x)$ имеет мощность 1» или, скажем, «$(\forall\,y\in x)(y\in y)$»? Таких свойств можно напридумывать сколько угодно, но главное из них — «пустота», т.е. $\neg(\exists\,z)(z\in x)$, поскольку именно оно выбирается в качестве определения понятия «пустое множество».

epros писал(а):

Без аксиомы экстенсиональности его единственность не очевидна.

Безусловно. Более того, существуют вполне естественные и полезные варианты теории множеств, не включающие аксиому экстенсиональности и допускающие наличие так называемых праэлементов (urelements), каждый из которых ничего не содержит. Ясно, что в моделях таких теориий может быть «сколько угодно пустых множеств».

[Someone]

Я поленился перечитывать эту длинную тему, так что не уверен, что скажу что-то новое.
Мне кажется, что многие проблемы отпадут, если перестать воспринимать аксиому объёмности как определение равенства множеств. Аксиомы, определяющие равенство объектов, целесообразно вынести в математическую логику. А аксиома объёмности означает всего лишь, что не существует никаких свойств, различающих множества, кроме элементов. Тем более, что существуют теории множеств с атомами, для которых аксиома объёмности не выполняется.

-- Пн июн 13, 2011 23:57:24 --

AGu в сообщении #450325 писал(а):

Более того, существуют вполне естественные и полезные варианты теории множеств, не включающие аксиому экстенсиональности и допускающие наличие так называемых праэлементов (urelements), каждый из которых ничего не содержит. Ясно, что в моделях таких теориий может быть «сколько угодно пустых множеств».

Вот и AGu примерно то же пишет.

[dydx]

Я думаю, что Френкель хотел показать, что между самими объектами (множествами) и их именами (т.е. между записью и её смыслом) существует еще какая та третья сущность, которая пока еще никем четко не описана и не формализована. Когда мы говорим, что есть два равных множества, то мы на самом деле говорим не о количестве самих объектов или их имен, а о количестве этих промежуточных сущностей. Например, компьютер - это множество каких-то деталей, и поэтому можно сказать, что два компьютера равны, если у них одинаковые детали. И представьте теперь, что у нас есть два физических, но равных по этому определению компьютера. Идеализированный компьютер, которому они равны, - он один. Но физически этих компьютеров два. Вот они и есть эта третья сущность. Точнее не они, а наше представление о них. Это не значит, что она обязательно есть что-то, что связано с материальным: в примере Френкеля с множествами $F$ и $D$ этой связи нет. Т.е. помимо синтаксиса и семантики, возможно, есть еще что-то, что мы упускаем (не придаем значения) в силу может каких-то ограничений нашей психики. Я думаю, что эти вопросы касаются того, как устроено и как функционирует наше сознание. И ответы на них могут привести к разгадке тайны сознания и создания сильного искусственного интеллекта.

[dydx]

dydx в сообщении #643922 писал(а):

И представьте теперь, что у нас есть два физических, но равных по этому определению компьютера.

Или даже не физических, а просто воображаемых или смоделированных.

[Doil-byle]

epros в сообщении #450063 писал(а):

То, что множество, обладающее неким свойством ("пустоты"), единственно, не есть самоочевидный факт.

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

[Someone]

Собственно, аксиомы равенства содержательно означают, что равные объекты формальной теории полностью взаимозаменяемы во всех формулах и термах, поэтому "рассматриваются как один и тот же объект". Не секрет, что это, мягко выражаясь, не совсем то же самое, что "являются одним и тем же объектом". Модель теории с равенством, в которой равные объекты являются одним и тем же объектом, называется нормальной. Если носитель (универсум) модели теории является множеством, то можно получить нормальную модель, просто профакторизовав модель по отношению равенства.

[Doil-byle]

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

Если носитель (универсум) модели теории является множеством, то можно получить нормальную модель, просто профакторизовав модель по отношению равенства.

Да, я понял Вас, спасибо. Правда, в той модели, которая строится в книжке, которую я читал, универсум - не множество. А я пока читал теорию множеств лишь в одной книжке, и ничто помимо неё мне в этом не ведомо.