?

Log in

No account? Create an account
независимое - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

независимое [янв. 30, 2014|06:47 pm]
Anatoly Vorobey
[Tags|]

Забавная ссылка:

What are some reasonable-sounding statements that are independent of ZFC?

Там есть интересные примеры утверждений, которые не зависят от аксиом теории множеств (т.е. невозможно в ней ни доказать их, не опровергнуть), хоть на первый взгляд такими и не кажутся.

Самый удачный пример - это выглядящее несомненно верным утверждение: если множество A меньше размером множества B, то у A есть меньше подмножеств, чем у B.

Это хороший пример, потому что на первый взгляд это выглядит как одно из типичных утверждений, которые несоменно верны, но требуют аксиомы выбора для своего доказательства (т.е. C в ZFC, Choice в системе Zermelo-Fraenkel with Choice). Например, без аксиомы выбора нельзя доказать, что счетное объединение счетных множеств само счетно. Или еще хороший парадоксальный пример: без аксиомы выбора, в одной ZF, возможна ситуация, в которой квадрат можно разбить на больше частей, чем в нем есть точек.

Но обычно аксиома выбора закрывает все эти дырки, и в ZFC такие аномалии исчезают; а вот процитированное выше утверждение, хоть и тоже кажется таковым, все же независимо от ZFC.
СсылкаОтветить

Comments:
[User Picture]From: janatem
2014-01-30 05:47 pm
без аксиомы выбора, в одной ZF, возможна ситуация, в которой квадрат можно разбить на больше частей, чем в нем есть точек

Непонятно. Ведь ZF строго слабее ZFC, поэтому ложное в ZFC никак не может быть истинным в ZF. Наверно вместо «возможна ситуация, в которой» имелось в виду «нельзя опровергнуть, что».
(Ответить) (Thread)
[User Picture]From: alexeybobkov
2014-01-30 07:56 pm
"возможна ситуация", видимо, означает "возможно такое расширение системы аксиом".
(Ответить) (Parent) (Thread)
[User Picture]From: comichelle
2014-01-30 08:31 pm
как не может, а отрицание аксиомы выбора?
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2014-01-30 08:39 pm
В ZF, насколько я понимаю, нет отрицания аксиомы выбора.
(Ответить) (Parent) (Thread)
[User Picture]From: comichelle
2014-01-30 09:57 pm
да, конечно. Неправильно прочитала.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2014-01-30 10:15 pm
Да. "Возможна ситуация, в которой" = "можно построить модель ZF, в которой"
(Ответить) (Parent) (Thread)
[User Picture]From: psilogic
2014-01-30 05:53 pm
А что такое definable well-ordering?
(Ответить) (Thread)
[User Picture]From: alexeybobkov
2014-01-30 08:16 pm
Я бы предположил, что это "конструктивно заданное полное упорядочивание".
Да, то, что утверждение "There is no definable well-ordering of the real numbers." недоказуемо в ZFC - это круто. Это взрывает мой мозг.

Edited at 2014-01-30 20:17 (UTC)
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2014-01-30 08:25 pm
Определимое с помощью логической формулы 1-го порядка с параметрами, т.е. есть формула ψ и множества a1...an такие что, x предшествует y в упорядочивании равносильно тому, что ψ(x,y,a1...an) - верное высказывание. Если V=L то существует определимое полное упорядочивание всей вселенной теории множеств, не только вещественных чисел.
(Ответить) (Parent) (Thread)
[User Picture]From: alexeybobkov
2014-01-30 08:44 pm
А можно подробнее, что такое V и L? Буду благодарен.
(Ответить) (Parent) (Thread)
[User Picture]From: alexeybobkov
2014-01-30 08:49 pm
Нашёл, но это вряд ли можно в нескольких словах объяснить, так что вопрос снимается.)
(Ответить) (Parent) (Thread)
[User Picture]From: psilogic
2014-01-30 09:01 pm
Иными словами, вместо констатации существания упорядочивания - некая "вменяемая" формула для сравнения?
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2014-01-30 09:08 pm
Ну да ("формула" - в смысле, определяемом в мат. логике, т.е. выражение из символов ∈ , =, знаков переменных, логических союзов и кванторов общности и существования.)
(Ответить) (Parent) (Thread)
[User Picture]From: alexeybobkov
2014-01-31 07:43 am
А есть ли при этом "формула" (в каком-либо смысле) для определения наименьшего элемента в любом заданном непустом подмножестве?
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2014-01-31 10:03 am
формулу, которая говорит, что данный элемент - минимальный в множестве, легко получить из формулы, определяющей порядок
(Ответить) (Parent) (Thread)
[User Picture]From: special_linear
2014-01-30 06:48 pm
> Например, без аксиомы выбора нельзя доказать, что счетное объединение счетных множеств само счетно.

Кажется, аксиома выбора необходима все же для доказательства |AxA|=|A| лишь в случае более чем счетных множеств. Или имеется в виду, что биекции счетных множетсв на N не зафиксированы заранее и требуется их счетное число выбрать?
(Ответить) (Thread)
[User Picture]From: ilya_dogolazky
2014-01-30 10:03 pm
Я тоже про это подумал, NxN=N вроде получается прямым вождением пальца по бумаге, так что тут наверное не требуется аксиома выбора. Наверное действительно дело в том, что доказательство (\forall i\in N A_i=N) => \cup_1^\infty A_i=NxN её требует.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2014-01-30 10:19 pm
Да, без аксиомы выбора вы не можете одновременно выбрать по одной биекции каждого из счетных множеств на N.

Есть счетная аксиома выбора - ослабленная версия, с ней уже можно строить значительную часть обычной математики.
(Ответить) (Parent) (Thread)
[User Picture]From: gaz_v_pol
2014-02-01 07:00 am
Правильно ли я понял, что равномощность плоскости и прямой доказать без аксиомы выбора нельзя? Странно, но ведь есть же совершенно конструктивное построение, см. https://ru.wikipedia.org/wiki/Кривая_Пеано
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2014-02-01 12:50 pm
Нет, почему нельзя? Можно.
(Ответить) (Parent) (Thread)
[User Picture]From: eterevsky
2014-01-31 06:38 am
По-моему, |A×A| = |A| и для больших мощностей доказывается без аксиомы выбора. Ну вот например, |R×R| = |R| доказывается вполне конструктивно: берём цифры через одну.
(Ответить) (Parent) (Thread)
From: onanymous.myopenid.com
2014-01-31 06:56 am
Такой трюк проходит только для мощностей вида 2α (update: вру, даже для таких не всегда работает). Общее же равенство равносильно AC.

Edited at 2014-01-31 07:08 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: kosovsky_family
2014-01-31 01:10 pm
Сначала долго думал что такое размер множества. Потом пошел по ссылке. Понял, что речь про мощность. пытался понять как у большего множества может быть меньше мощность. Потом прочитал, что написано по ссылке. И понял, что они равномощны.

Но равномощность $2^{|\omega|}$ и $2^{|\omega_1|}$ мне не кажется чем-то совершенно неправдоподобным. Ведь равномощны же, например $2^c$ и $N^c$.
(Ответить) (Thread)
From: ztarlitz
2014-02-01 05:09 am
А парадокс со сферой которую можно разбить и сложить из частей две такие же сферы, разве не из этой же серии?
(Ответить) (Thread)
From: oblomov_jerusal
2014-02-01 05:47 am
Это в ZFC. Это пример парадоксальных следствий аксиомы выбора.
(Ответить) (Parent) (Thread)
From: ztarlitz
2014-02-01 07:06 am
Ну да в ZFC, ну так и пост вроде про ZFC, нет?
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2014-02-01 08:57 am
Это утверждение, разрешимое в ZFC. Пост про утверждения, в ZFC неразрешимые.
(Ответить) (Parent) (Thread)
From: ztarlitz
2014-02-01 09:59 am
Ой, а я думал он в ZFC сохраняется. Получается я ошибся и мой предыдущий коммент не в тему. А вот ZFC с аксиомой регулярности, снимает эти противоречия?
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2014-02-01 10:01 am
> Ой, а я думал он в ZFC сохраняется.

Он там появляется. Это утверждение, независимое от ZF, но доказуемое в ZFC.

> снимает эти противоречия?

О каких противоречиях вы говорите?
(Ответить) (Parent) (Thread)