Доказательство перечислимости вещественных чисел

[lyakusha_qwerty]

Составим функцию $f: N \rightarrow R$. Из аксиомы выбора следует, что существует функция $c$, которая принимает на вход любое непустое множество и выдает его элемент.

Зададим вспомогательную функцию $h$, определенную на $N \cup \{0\}$:
$h(0) = R$
Иначе $h(i) = h(i-1) \setminus c(h(i-1))$

А теперь построим функцию $f$:
$f(1) = c(h(0))$
Иначе $f(i) = c(h(i - 1))$

$f$ - сюрьекция (наверное вот оно неправильное утверждение? Можно пруфов или контрпруфов к этому?), а ещё она инъекция, следовательно она биекция. ЧТД.

-- 12.10.2017, 11:31 --

Блин, а ведь существует $c$, из подмножеств $R$, в которых есть хотя бы 1 элемент вне $[0, 1]$, никогда не выберет элемент из $[0, 1]$. Следовательно то, что я по интуиции назвал сюрьекция - не всегда сюрьекция. А доказать, что она хоть для некоторых c является сюрьекцией, наверное невозможно, да? Если да, то я понял ошибку, и тему можно закопать.

[Xaositect]

lyakusha_qwerty в сообщении #1255068 писал(а):

Из аксиомы выбора следует, что существует функция $c$, которая принимает на вход любое непустое множество и выдает его элемент.

Немного не так: для любого множества непустых множеств существует функция на этом множестве, для которой $f(x) \in x$. Но в данном случае это, скорее всего, неважно.

lyakusha_qwerty в сообщении #1255068 писал(а):

Иначе $h(i) = h(i-1) \setminus c(h(i-1))$

Наверное, имелось в виду $h_i = h(i - 1) \setminus \{c(h(i - 1))\}$?

lyakusha_qwerty в сообщении #1255068 писал(а):

$f$ - сюрьекция (наверное вот оно неправильное утверждение? Можно пруфов или контрпруфов к этому?)

Можно, для этого даже необязательны действительные числа.
Определим функцию $c$ для любых непустых подмножеств $A \subset N$ следующим образом:

$$c(A) = \begin{cases} \min \{n \in A \mid n = 2k\}, \text{если $A$ содержит хотя бы один четный элемент},\\ \min A, \text{если $A$ не содержит четных элементов}\end{cases}$$

Тогда ваша $f(x)$ будет $f(x) = 2x$, не сюрьекция.

-- Чт окт 12, 2017 09:38:11 --

lyakusha_qwerty в сообщении #1255068 писал(а):

Блин, а ведь существует $c$, из подмножеств $R$, в которых есть хотя бы 1 элемент вне $[0, 1]$, никогда не выберет элемент из $[0, 1]$. Следовательно то, что я по интуиции назвал сюрьекция - не всегда сюрьекция. А доказать, что она хоть для некоторых c является сюрьекцией, наверное невозможно, да? Если да, то я понял ошибку, и тему можно закопать.

Да, все так.