Несоразмерность показательного множества и аксиома выделения

[bubu gaga]

Есть типичное доказательство того, что не существует биекции из множества $M$ во подмножесто его подмножеств $\mathcal{P}(M)$. Для любого отбражения $f$ строится множество элементов $X$ для которых $x \in X \Rightarrow x \notin f(X)$. После этого оказывается, что такому множеству не соответствует ни один элемент из $M$.

Правда ли, что способность строить $X$ основывается на аксиоме выделения? Если ли ограничения на предикат $P$ в этой аксиоме? Или любая комбинация из $\cap, \cup, \Rightarrow, \in, \subset$ подойдёт?

Спасибо.

[ewert]

Насчёт предикатов не в курсе, но аксиома выбора в стандартном доказательстве не при чём.

[bubu gaga]

ewert писал(а):

но аксиома выбора в стандартном доказательстве не при чём.

Доказательство начинается так, что мы с помощью предиката строим множество

$$ X = \bigl\{x \in M \; | \; x \notin f(x) \bigr\} $$

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

Спасибо.

[ewert]

bubu gaga писал(а):

Доказательство начинается так, что мы с помощью предиката строим множество

$$ X = \bigl\{x \in M \; | \; x \notin f(x) \bigr\} $$

В этой записи $x$ -- некий элемент, в то время как $f(x)$ -- некое подмножество. Доказательство начинается с предположения о том, что между элементами и подмножествами существует некое взаимно однозначное соответствие, и в этом предположении никакой аксиомы выбора нет (просто потому, что это -- предположение). Далее все элементы делятся на два класса -- принадлежащие подмножеству, сопоставленному этому элементу, и не принадлежащие. Здесь используется лишь тот факт, что для любой пары (элемент, подмножество) имеет смысл понятие "содержится"; это -- тоже никакая не аксиома выбора. Ну а дальше ни о каких аксиомах уже вообще нет речи, просто проверяется противоречивость этих утверждений.

[bubu gaga]

Понятно. Спасибо!

[AGu]

bubu gaga писал(а):

Правда ли, что способность строить $X$ основывается на аксиоме выделения? Если ли ограничения на предикат $P$ в этой аксиоме?

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