Еще раз об аксиоме выбора

[EminentVictorians]

mihaild в сообщении #1613945 писал(а):

Строить множества нельзя. Запрещено.
Можно только потребовать, чтобы Вас отвели в место, где нужные Вам множества уже построены. Но там легко может оказаться построено что-то еще, чего Вы не хотели, но запретить такое у Вас не получится. Более точно, если нужный Вам юниверсум где-то есть, то рядом с ним есть и не очень нужный Вам юниверсум, но отличить их Вы не сможете.

Я вообще не так на это смотрю (и мой внутренний антиплатонист тоже напрягся )

У меня есть некоторый запас множеств (в моем случае это вообще ровно одно множество) и есть некоторый набор аксиом, которые выполняют роль "операций", позволяющих из одних множеств сделать другие. На самом деле, вот это словосочетание "построить множество" - это просто вольность речи. Аксиомы просто говорят о том, что если мы знаем факт существования одних множеств, то существуют и другие множества (например, если мы знаем, что существует множество $x$, то аксиома булеана говорит нам о том, что существует множество $2^x$ его подмножеств; неформально можно сказать, что мы построили множество всех подмножеств множества $x$).

mihaild в сообщении #1613945 писал(а):

"Где" оно есть?

Там же, где и все остальные множества - в универсуме. А универсум - в нашей психике.

[epros]

mihaild в сообщении #1613950 писал(а):

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

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

mihaild в сообщении #1613950 писал(а):

А существует ли вообще хоть какое-то множество двоичных последовательностей, принадлежность к которому разрешима (в том смысле, что есть $f$, который по программе $g$, задающей двоичную последовательность, говорит, задает ли эта программа элемент множества или нет), не являющееся объединением конечномерных цилиндров (множеств вида "сначала вот такой префикс, потом что угодно")?

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

mihaild в сообщении #1613950 писал(а):

Пусть у нас есть функция $A$, которая по алгоритму, выдающему двоичную последовательность, говорит, кто выиграл. Стратегия первого игрока - это функция из битовых строк четной длины в биты, стратегия второго игрока - функия из нечетных строк тоже в биты. Пусть $\langle f, g\rangle$ - алгоритм, выдающий битовую строку, получающуюся игрой этих двух стратегий друг против друга. Тогда у первого игрока есть выигрышная стратегия, если $\exists f \forall g: A(\langle f, g\rangle)$.

Как неконстуктивная постановка задачи годится. Но вообще говоря $\langle f, g\rangle$ именно как алгоритм не существует. Возьмём в качестве примера стратегии $f$ такую функцию: Пронумеруем все машины Тьюринга, стартующие с нулевой ленты. Пусть $f$ выдает единицу, если машина Тьюринга с номером, соответствующим номеру шага, останавливается и нуль в ином случае. Алгоритма, вычисляющего всю полученную в результате битовую строку, заведомо не существует.

[mihaild]

EminentVictorians в сообщении #1613967 писал(а):

Там же, где и все остальные множества - в универсуме

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

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

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

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

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

Но вообще говоря $\langle f, g\rangle$ именно как алгоритм не существует

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

[EminentVictorians]

mihaild в сообщении #1613978 писал(а):

Т.е. Вы хотите, чтобы в юниверсуме существовало множество, являющееся моделью ZFC, причем минимальной.

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

[mihaild]

EminentVictorians в сообщении #1613980 писал(а):

Мой универсум - это и есть модель ZFC

Тогда у Вас вообще не получится говорить о "минимальности".
И если я ночью прокрадусь и к Вашим требованиям допишу, что должны существовать сильно недостижимые кардиналы, или натуральное число, кодирующее противоречивость ZFC, то Вам будут приносить юниверсумы с ними.

[EminentVictorians]

mihaild в сообщении #1613984 писал(а):

Тогда у Вас вообще не получится говорить о "минимальности".

А я до сих пор верю, что мой универсум единственный.

[mihaild]

EminentVictorians в сообщении #1613987 писал(а):

А я до сих пор верю, что мой универсум единственный

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

[EminentVictorians]

mihaild в сообщении #1613988 писал(а):

один с сильно недостижимыми кардиналами, другой без

Да я просто не очень ориентируюсь в этих недостижимых кардиналах. В моем-то универсуме их ведь нету. Они могут быть в другом универсуме, определяемом другими аксиомами (мои + еще 1 аксиома существования недостижимого кардинала). А я-то холю и лелею свой универсум, какая мне разница, что там в других происходит? Или я не так понял, о чем речь?

-- 19.10.2023, 21:43 --

Я имел в виду, что единственен универсум, определяемый моими аксиомами. Другой набор аксиом может определить другой универсум, с этим я не спорю.

[Geen]

EminentVictorians в сообщении #1613980 писал(а):

т.к. его нельзя "построить"

Но он есть, несомненно!...

-- 19.10.2023, 22:22 --

EminentVictorians в сообщении #1613989 писал(а):

Другой набор аксиом может определить другой универсум, с этим я не спорю.

Добавление аксиомы не может увеличить "универсум"....

[mihaild]

EminentVictorians в сообщении #1613989 писал(а):

В моем-то универсуме их ведь нету

Откуда Вы знаете? Вот я ночью прокрался и подкинул. И Вы меня не поймаете.

[EminentVictorians]

Geen в сообщении #1614000 писал(а):

Но он есть, несомненно!...

Ну да, а что? Просто универсум - это не множество.

Можно дать такие определения:

Классом называется любая совокупность элементов из универсума.
(разница между совокупностью элементов и подмножеством примерно такая же как между сюрьективной функцией и функциональным суждением из аксиомы 6).

Лемма 1.
Любое множество является классом.

Доказательство:
Пусть $M$ - множество. Тогда $M \in U$. Возьмем произвольный $x \in M$. Имеем: $x \in M \in U$ $\Rightarrow$ $x \in U$ (вторая аксиома). Чтд.

Лемма 2.
Сам универсум $U$ не является множеством.

Доказательство:
Предположим, что $U$ - множество. Тогда, $U \in U$ $\Rightarrow$ $U \in U \in U \in ...$.
Получили противоречие с аксиомой регулярности. Чтд.

По-моему, все в порядке.

Geen в сообщении #1614000 писал(а):

Добавление аксиомы не может увеличить "универсум"....

Почему? Возьмем аксиому существования сильно недостижимого кардинала. Она добавит этот самый сильно недостижимый кардинал в мой универсум. (на дефолтные множества она вроде как не скажется).

mihaild в сообщении #1614005 писал(а):

Откуда Вы знаете? Вот я ночью прокрался и подкинул. И Вы меня не поймаете.

Я не понимаю аналогию. Есть список аксиом, он неизменный и я про него помню. С чего он измениться-то должен?

[mihaild]

EminentVictorians в сообщении #1614009 писал(а):

Я не понимаю аналогию. Есть список аксиом, он неизменный и я про него помню. С чего он измениться-то должен?

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

EminentVictorians в сообщении #1613989 писал(а):

Я имел в виду, что единственен универсум, определяемый моими аксиомами

Вот это неправда. И никаким перечислимым списком аксиом задать единственный в каком-то разумном смысле юниверсум не получится.

[EminentVictorians]

mihaild в сообщении #1614012 писал(а):

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

Тогда как это доказать?

-- 19.10.2023, 23:15 --

Вообще не понимаю. Вот есть универсум, в котором есть недостижимый кардинал. "Он там есть" = "он существует". А как мы поняли, что он существует в этом универсуме? У нас есть только один способ: доказать исходя из аксиом. Но аксиомы везде одинаковые. Значит, можно провести такое же доказательство для другого универсума и там тоже будет существовать этот недостижимый кардинал. Где ошибка?

[dgwuqtj]

EminentVictorians, вы как будто пытаетесь определить конструктивный универсум $V$. Только он тоже не единственный, а зависит как минимум от того, насколько большие ординалы бывают. Есть некие сложности с тем, чтобы просто взять все множества, существование которых доказуемо в ZF, и сделать из них универсум.

[mihaild]

EminentVictorians в сообщении #1614013 писал(а):

Тогда как это доказать?

Пусть $I$ - утверждение о существовании недостижимого кардинала. Известно (но сложно доказывается, я только в одну сторону умею) что если ZFC непротиворечива, то $\text{ZFC} \not\vdash I$ и $\text{ZFC} \not\vdash \neg I$. Соответственно, по теоерме о полноте, существует юниверсум ZFC, в котором $I$ выполнено, и существует в котором не выполнено.