Количество множеств

[dydx]

Аксиоматическая теория множеств строится поверх логики предикатов. Как известно, понятие терм определяется рекурсивно, и можно доказать, что число термов не более, чем счетно. Тогда получается, что так как в аксиоматической теории множеств каждый терм - это какое-то множество, то количество всех множеств не более, чем счетно. Prove me wrong.

[arseniiv]

И какое же множество представляет терм $x$?

[Sonic86]

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

[dydx]

arseniiv
Я неправильно выразился. Количество множеств, для которых существует формальное доказательство их существования (и единственности), не более, чем счетно. Вот, что я хотел сказать.

-- 11.11.2012, 18:38 --

Sonic86
Да. Как-то так.

[Sonic86]

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

Да. Как-то так.

Ну в таком случае ничего сильно необычного тут нет (я когда-то тут спрашивал аналогичный вопрос в связи с несчетностью $\mathbb{R}$)

[dydx]

Вообще, это парадоксально: мы можем доказать, что существует несчетное множество множеств, но не можем доказать, что каждое из этих множеств-элементов существует.

[Sonic86]

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

Вообще, это парадоксально: мы можем доказать, что существует несчетное множество множеств, но не можем доказать, что каждое из этих множеств-элементов существует.

Наверное, немного так: если мы построим некоторый язык, в котором могут быть выписаны некоторые из этих множеств, то в нем всегда будет множество, которое в языке не описывается. Множество есть, а синтаксиса нет.

[Someone]

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

Вообще, это парадоксально: мы можем доказать, что существует несчетное множество множеств, но не можем доказать, что каждое из этих множеств-элементов существует.

Какое именно "каждое из этих"? Предъявляйте конкретное множество, будем разбираться, существует оно или нет.

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

Аксиоматическая теория множеств строится поверх логики предикатов. Как известно, понятие терм определяется рекурсивно, и можно доказать, что число термов не более, чем счетно. Тогда получается, что так как в аксиоматической теории множеств каждый терм - это какое-то множество, то количество всех множеств не более, чем счетно. Prove me wrong.

Да, но нигде не сказано, что каждое множество - это терм.

[dydx]

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

Какое именно "каждое из этих"?

Доказать существование элементов данного несчетного множества.

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

Предъявляйте конкретное множество, будем разбираться, существует оно или нет.

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

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

Да, но нигде не сказано, что каждое множество - это терм.

Я уже говорил, что неправильно выразился.

[arseniiv]

(Здесь была ерунда.)

[Someone]

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

Доказать существование элементов данного несчетного множества.

Не понял. Элементы существующего множества существуют по определению. Множество содержит только существующие элементы. Если Вы про какой-то элемент можете доказать, что он не существует, то его ни в каком множестве нет.

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

Но как доказать, что все подмножества натуральных чисел существуют?

Какие именно "все"? Предъявляйте конкретное подмножество натурального ряда, будем разбираться, существует или нет.

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

Я неправильно выразился. Количество множеств, для которых существует формальное доказательство их существования (и единственности), не более, чем счетно.

Э-э-э... Не понял. Доказательства формализованной теории множеств не являются объектами самой этой теории, и она ничего не может сказать о счётности или несчётности множества доказательств. Объектами теории множеств являются множества, а не доказательства.

[dydx]

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

Элементы существующего множества существуют по определению.

По какому такому определению?

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

Множество содержит только существующие элементы.

А если еще неизвестно, существует элемент или нет? В смысле, вот нет пока формального доказательства, что этот элемент существует. Не в том смысле, что есть формальное доказательство, что он не существует.

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

Если Вы про какой-то элемент можете доказать, что он не существует, то его ни в каком множестве нет.

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

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

Какие именно "все"? Предъявляйте конкретное подмножество натурального ряда, будем разбираться, существует или нет.

Инструкция: если $M$ - подмножество натурального ряда, то доказать, что оно существует. Теперь понятно?
Но мы ведь не сможем таким образом проверить каждое из этих подмножеств. Поэтому мы не можем утверждать, что каждое из них существует (или не существует).

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

Доказательства формализованной теории множеств не являются объектами самой этой теории, и она ничего не может сказать о счётности или несчётности множества доказательств.

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

[dydx]

Докажите, что $\exists x (P_{i-1}(x) \land i \notin x)$ для любого м-натурального $i$, где $P_0(x)=0 \in x$, $P_i(x) = P_{i-1}(x) \land i \in x$. Количество требуемых для этого формальных доказательств м-счетно.

-- 12.11.2012, 00:26 --

Нет, не так.
Докажите, что $\exists x (r \in x \land r^2 \notin x)$ для любого м-действительного $r$. Каждый раз, перед тем как найти формальное доказательство, будем выдумывать новое слово конечной длины для обозначения выбранного действительного числа. Количество требуемых для этого формальных доказательств м-несчетно. Но м-несчетного количества доказательств не существует, т.к. количество слов м-счетно.

-- 12.11.2012, 00:49 --

Поэтому нельзя доказать, что все эти множества существуют.

[dydx]

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

для любого м-действительного $r$

Ой, не м-действительного, а просто действительного.

-- 12.11.2012, 01:35 --

Хотя нет, несколько моих предыдущих сообщений - это не совсем то, что я хотел сказать. Потому что можно возразить, что формула $\forall r (r \in \mathbb{R} \to \exists x (r \in x \land r^2 \notin x))$ имеет формальное доказательство. Но это не решение проблемы о которой я пытаюсь рассказать, потому что это доказательство, как бы, основано на том, что уже есть формальные доказательства существования каждого действительного числа. Т.е. мы просто перекладываем вопрос существования одних объектов на существование других объектов...

[dydx]

Хм, возможно проблема в следующем. Аксиома бесконечности:
$\exists a \ (\varnothing \in a \land \forall b (b \in a \to b \cup \{b\} \in a))$, где $b \cup \{b\} = \{c: c \in b \lor c = b\}$.
Здесь неявно предполагается, что $\forall a \exists c \forall b (b \in c \leftrightarrow (b \in a \lor b = a))$. Это вообще можно доказать?

-- 12.11.2012, 03:27 --

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