О множестве, которое содержит само себя в качестве элемента

[Dialectic]

Здравствуйте!

Может ли кто-нибудь привести пример множества, которое содержит само себя, в качестве своего элемента?

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

[Someone]

Dialectic писал(а):

Может ли кто-нибудь привести пример множества, которое содержит само себя, в качестве своего элемента?

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

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

К.Куратовский, А.Мостовский. Теория множеств. "Мир", Москва, 1970.

Отсутствие аксиомы регулярности заметно усложняет авторам жизнь, но они справляются. Забавно, что они прямо говорят, что считают аксиому регулярности истинной, но, тем не менее, не хотят включать её в число аксиом теории множеств (без объяснения причины).

Что касается явного примера, то в тех случаях, когда решение какого-либо вопроса теории множеств зависит от используемой аксиоматики, "наивный" пример, как правило, становится невозможным. В данном случае, вероятно, требуется какая-нибудь аксиома существования множества, являющегося своим элементом, или построение модели, содержащей такие множества, что вряд ли просто.

[e2e4]

Someone конечно все хорошо объяснил, но по-моему за примером далеко ходить не надо, достаточно начать: Пусть $A$ - множество всех множеств, не содержащих ____. Подставить произвольный предмет.

Можно еще что-нибудь придумать, хотя не знаю, корректно ли это рассматривать в рамках теории множеств, тут происходит подмена понятий: множество ABCD - это множество всех сочетаний, составленных из букв A, B, C, D.

[Dialectic]

Спасибо Someone. А можете в двух словах объяснить, что такое "модель"? А то это слово часто встречается, особенно в работах по логике, только смысл как то трудно улавливается.

Добавлено спустя 7 минут 41 секунду:

e2e4 писал(а):

Someone конечно все хорошо объяснил, но по-моему за примером далеко ходить не надо, достаточно начать: Пусть $A$ - множество всех множеств, не содержащих ____. Подставить произвольный предмет.

Под словом "предмет" понимается всё, что угодно?Или только числовые множества?

e2e4 писал(а):

Можно еще что-нибудь придумать, хотя не знаю, корректно ли это рассматривать в рамках теории множеств, тут происходит подмена понятий: множество ABCD - это множество всех сочетаний, составленных из букв A, B, C, D.

Вы имеете ввиду множество {A,B,C,D} - это множество всех сочетаний, составленных из букв A, B, C, D? Если так, пока не могу сообразить.

[Someone]

e2e4 писал(а):

по-моему за примером далеко ходить не надо, достаточно начать: Пусть $A$ - множество всех множеств, не содержащих ____. Подставить произвольный предмет

Подобные конструкции легко приводят к противоречию (парадокс Рассела).

e2e4 писал(а):

Можно еще что-нибудь придумать, хотя не знаю, корректно ли это рассматривать в рамках теории множеств, тут происходит подмена понятий: множество ABCD - это множество всех сочетаний, составленных из букв A, B, C, D.

Множество всех сочетаний, составленных из букв $A$, $B$, $C$, $D$, не является сочетанием, составленным из букв $A$, $B$, $C$, $D$.

По поводу того, что можно и что нельзя рассматривать в теории множеств, можно сказать следующее. Стандартно предполагается, что все объекты теории множеств являются множествами (теории типа Цермело - Френкеля) или классами (теории типа Гёделя - Бернайса; в этом случае множеством называется класс, который является элементом какого-нибудь класса). Однако возможны теории множеств, в которых, кроме множеств или классов, есть ещё объекты, называемые атомами; атомы могут быть элементами множеств или классов, но сами ни множествами, ни классами не являются.

Dialectic писал(а):

А можете в двух словах объяснить, что такое "модель"?

Модель - это совокупность объектов и отношений, для которых выполняются все аксиомы теории.

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

[Профессор Снэйп]

Ну там вот выше уже правильно заметили, что существование таких множеств не допускается аксиомой регулярности.

Года четыре назад на другом форуме я как-то написал довольно большую телегу насчёт этой и других аксиом ZFC. Повторять все эти рассуждения здесь было бы долго, лучше посмотрите сюда.

Аксиома регулярности допускает различные формулировки. Наиболее часто встречается следующая:

Для любого непустого множества $x$ найдётся $y \in x$, такой что $x \cap y = \varnothing$.

Как отсюда вывести утверждение о том, что ни одно множество не может содержать себя в качестве элемента? Довольно просто. Предположим, что $x \in x$. По аксиоме выделения существует множество

$$ y = \{ z \in x : z \in z \} $$

Так как $x \in y$, то $y \neq \varnothing$. Выберем $t \in y$, такой что $t \cap y = \varnothing$. Однако так как $t \in y$, то $t \in t$ и $t \in t \cap y$, так что $t \cap y \neq \varnothing$. Противоречие.

Можно, кстати, и по другому . Пусть $x \in x$. По аксиоме пары существует множество $y = \{ x \}$. Так как $x \in y$, то $y \neq \varnothing$. Значит, существует $t \in y$, такой что $t \cap y = \varnothing$. Однако $x$ является единственным элементом $y$, так что $t = x$ и $x \in t \cap y$. Опять противоречие.

В качестве упражнения предлагаю Вам доказать следующее утверждение:

Не существует бесконечной последовательности множеств $x_0, x_1, x_2, \ldots$, такой что $x_{i+1} \in x_i$ для любого $i \in \mathbb{N}$.

Иногда аксиому регулярности формулируют в виде этого утверждения

Добавлено спустя 40 минут 43 секунды:

Dialectic писал(а):

А можете в двух словах объяснить, что такое "модель"? А то это слово часто встречается, особенно в работах по логике, только смысл как то трудно улавливается.

По существу Вам уже ответили:

Someone писал(а):

Модель - это совокупность объектов и отношений, для которых выполняются все аксиомы теории.

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

Примеры моделей: группы, кольца, поля, частично упорядоченные множества etc.

Если интересно, то можно и более формально

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

Определение. Сигнатурой называется упорядоченная пара $\langle \langle P, F, C \rangle, \mu \rangle$, где $P$, $F$ и $C$ --- произвольные попарно не пересекающиеся множества, а $\mu$ --- функция из $P \cup F$ в $\mathbb{N} \setminus \{ 0 \}$.

В этом определении $F$ называют множеством функциональных символов, $P$ множеством предикатных символов, $C$ множеством константных символов, а $\mu$ --- функцией местности. Таким образом, у каждого предикатного и функционального символа есть местность. Иногда (например, в книге Ершова и Палютина) множество константных символов отдельно не выделяют, $\mu$ рассматривают как функцию в $\mathbb{N}$ (а не в $\mathbb{N}$ без нуля) и считают, что константные символы --- это функциональные символы местности $0$.

Определение. Моделью (или алгебраической системой) сигнатуры $\langle \langle P, F, C \rangle, \mu \rangle$ называется пара $\mathfrak{M} = \langle M, int \rangle$, где $M$ --- произвольное непустое множество, а $int$ --- функция с областью определения $P \cup F \cup C$ и такая, что

1) для $c \in C$ $int(c) \in M$;
2) для $f \in F$ $int(f)$ есть функция из $M^{\mu(f)}$ в $M$;
3) для $p \in P$ $int(p)$ есть подмножество множества $M^{\mu(p)}$.

В этом определении множество $M$ называют носителем модели $\mathfrak{M}$ (на западе носитель обозначают словом "universe", так что и в русскоязычной литературе часто вместо слова "носитель" используют слово "универсум"), а функцию $int$ --- интерпретацией. Смысл во всём этом такой: сигнатура --- это набор имён (для каких-то элементов, функций и предикатов на носителе, которые "заслуживают специального обозначения", а интерпретация --- это соответствие, которое каждому имени сопоставляет объект, этим именем названный.

В качестве примера модели рассмотрим упорядоченное поле действительных чисел. Сигнатура для него такая:

$$ P = \{ \leqslant \},\, F = \{ +, \cdot \},\, C = \{ 0,1 \},\, \mu(\leqslant) = \mu(+) = \mu(\cdot) = 2 $$

Носителем является множество $\mathbb{R}$, а интерпретация сопоставляет символам сигнатуры "их обычные значения" (то есть символу $\leqslant$ множество всех упорядоченных пар действительной прямой, у которых первая компонента лежит на действительной оси левее второй, символу $+$ --- стандартную операцию сложения, символу $0$ --- стандартный ноль и т. д.)

Если что непонятно --- спрашивайте.

[e2e4]

Dialectic писал(а):

e2e4 писал(а):

Someone конечно все хорошо объяснил, но по-моему за примером далеко ходить не надо, достаточно начать: Пусть - множество всех множеств, не содержащих ____. Подставить произвольный предмет.

Под словом "предмет" понимается всё, что угодно?Или только числовые множества?

Все что угодно, кроме множеств. Например, вилка.

Someone писал(а):

Подобные конструкции легко приводят к противоречию (парадокс Рассела).

Насколько я помню, парадокс Рассела сформулирован в виде: пусть $A$ - множество всех множеств, не содержащих самих себя в качестве элемента.
Мой пример вроде бы противоречия не содержит. Если не сложно, приведите его к противоречию, это поучительно.

И еще - даже если какие-то конструкции приводят к противоречию, это вовсе не означает, что они не существуют (точнее, это надо доказать, а что-то мне подсказывает, что это недоказуемо). У меня сложилось мнение, что попытки ввести в теорию множеств запреты на "множества множеств" есть просто "костыли", поддерживающие эту теорию в данный момент времени. Наверняка найдется какое-нибудь красивое решение указанного парадокса.

Someone писал(а):

e2e4 писал(а):

Можно еще что-нибудь придумать, хотя не знаю, корректно ли это рассматривать в рамках теории множеств, тут происходит подмена понятий: множество ABCD - это множество всех сочетаний, составленных из букв A, B, C, D.

Множество всех сочетаний, составленных из букв A, B, C, D, не является сочетанием, составленным из букв A, B, C, D.

Конечно не является. Поэтому я и говорю о подмене понятий. Хотя, если ввести формальное правило, ставящие однозначное соответствие между объектом (множеством) и его обозначением (автоматическое разименовывание указателя в терминах Си ), то почему бы и нет?

[Профессор Снэйп]

e2e4 писал(а):

И еще - даже если какие-то конструкции приводят к противоречию, это вовсе не означает, что они не существуют (точнее, это надо доказать, а что-то мне подсказывает, что это недоказуемо). У меня сложилось мнение, что попытки ввести в теорию множеств запреты на "множества множеств" есть просто "костыли", поддерживающие эту теорию в данный момент времени. Наверняка найдется какое-нибудь красивое решение указанного парадокса.

???

Это что: попытка разобраться в теории множеств или "критика официальной науки", наподобие предпринятой г-ном Metaphysic в недавно закрытой теме?

Если первое, то, конечно, можно и нужно разбираться, что именно вызывает непонимание. Если второе, то поможет только отсылка в биореактор

[e2e4]

Цитата:

Если второе, то поможет только отсылка в биореактор

Ну я пошел...

[Dialectic]

Спасибо всем за изложение понятия "модель", к его изучению
я вернусь позже, а сейчас хочу привести пример множества, которое
содержит себя в качестве своего элемента. (пример взят из книги
Пенроуза "Новый ум короля").
Определим множество М - как множество состоящее из всех бесконечных множеств. Поскольку бесконечных множеств существует бесконечное количество, то множество М-обладает тем
свойством, что оно содержит бесконечное количество элементов, следовательно множество М должно быть включено в множество М
как элемент!

[Brukvalub]

Dialectic писал(а):

Определим множество М - как множество состоящее из всех бесконечных множеств.

Рассмотрение таких множеств как раз и приводит к противоречиям, поэтому в аксиоматических теориях их запрещено рассматривать (о чем Вам писали выше). Просто Пенроуз плохо учил теорию множеств, вот и оконфузился.

[Dialectic]

Brukvalub писал(а):

Dialectic писал(а):

Определим множество М - как множество состоящее из всех бесконечных множеств.

Рассмотрение таких множеств как раз и приводит к противоречиям, поэтому в аксиоматических теориях их запрещено рассматривать (о чем Вам писали выше). Просто Пенроуз плохо учил теорию множеств, вот и оконфузился.

Где конкретно в приведёном примере противоречие? То что, в той или иной аксиоматической теории может возникнуть противоречие,ещё не означает, что конретный пример приведённый Пенроузом противоречив.

[Brukvalub]

Dialectic писал(а):

То что, в той или иной аксиоматической теории может возникнуть противоречие,ещё не означает, что конретный пример приведённый Пенроузом противоречив.

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

[Dan B-Yallay]

А перечень всевозможных перечней тоже приводит к противоречию?

[Brukvalub]

Dan B-Yallay писал(а):

А перечень всевозможных перечней тоже приводит к противоречию?

Перечень - это часть становой упряжи?