Погружение теории в метатеорию

[Профессор Снэйп]

Наиболее классический пример --- теоремы Гёделя о неполноте. Кодируем утверждение о числах числами, переводим высказывание о доказуемости утверждений на язык арифметики, представляя его в виде утверждения о числах...

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

1) Доказать, что существует ровно континнум отображений $\varphi$ из $\mathbb{N}_+ = \{ 1, 2, 3, \ldots \}$ в $\mathbb{N} = \{ 0, 1, 2, \ldots \}$ таких, что $\varphi(x \cdot y) = \varphi(x) + \varphi(y)$.

2) Сколько существует инъективных $\varphi$, удовлетворяющих условиям предыдущего пункта?

[Dan B-Yallay]

1) $\|\mathbb N^{ \mathbb N}\|=\aleph_0$ (Мощность функций из натуральных в натуральные - континуум).
Для произвольного подмножества $ P\subset \mathbb N_+$ определим

$$ \varphi_{_P}(x) = \begin{cases} x, \quad x \in P \\ 0, \quad , else \end{cases}$$

Тоже континуум получается.

OOps. Невнимательно прочитал. Показалось $ \varphi$- функция Коши.

[Kallikanzarid]

Dan B-Yallay в сообщении #449336 писал(а):

Для произвольного подмножества $ P\subset \mathbb N_+$ определим

$$ \varphi_{_P}(x) = \begin{cases} x, \quad x \in P \\ 0, \quad , else \end{cases}$$

Не удовлетворяет условию $\varphi(xy) = \varphi(x) + \varphi(y)$.

[Профессор Снэйп]

Dan B-Yallay в сообщении #449336 писал(а):

1) $\|\mathbb N^{ \mathbb N}\|=\aleph_0$ (Мощность функций из натуральных в натуральные - континуум).

Нет ли здесь какого-нибудь противоречия?

[Kallikanzarid]

Что-то пока туго. Задачу (1) можно эквивалентно сформулировать как отыскание мощностей:
1) $\mathbf{Mon}(\mathbb{N}_+, \mathbb{N})$ (UPD: или $\mathbf{Grp}(\mathbb{Q}, \mathbb{Z})$, если я не ошибаюсь)
2) $[\mathbf{FinOrd}, \mathbf{BoolAlg}]_\times$

Но что-то мне подсказывает, что я не туда копаю <_<

[Dan B-Yallay]

Профессор Снэйп в сообщении #449377 писал(а):

Dan B-Yallay в сообщении #449336 писал(а):

1) $\|\mathbb N^{ \mathbb N}\|=\aleph_0$ (Мощность функций из натуральных в натуральные - континуум).

Нет ли здесь какого-нибудь противоречия?

Aleph 1!!

А вообще я думаю надо будет выбирать подмножества Р из множества простых и задавать функцию соответсвенно. Все равно континуум.

[Kallikanzarid]

Dan B-Yallay в сообщении #449394 писал(а):

:D Aleph 1!!

С чего бы это? :)

[Профессор Снэйп]

Dan B-Yallay в сообщении #449394 писал(а):

Aleph 1!!

При условии, что КГ верна

На самом деле решение и ответ не зависит от того, принимаем мы континуум-гипотезу или нет. В первом пункте ответ --- фундаментальная константа континуум, во втором --- ещё более фундаментальная константа, не скажу какая

(Спойлер)

На самом деле первая задача нудновата и, на мой взгляд, лишена изящества. Отправляем множество простых чисел в $\mathbb{N}$ произвольным образом, затем однозначно доопределяем это отображение на единице и составных числах. Множество простых чисел счётно, счётное в счётное отображается континуумом способов.

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

[Dan B-Yallay]

Kallikanzarid в сообщении #449395 писал(а):

Dan B-Yallay в сообщении #449394 писал(а):

:D Aleph 1!!

С чего бы это? :)

$\aleph_0$ is the cardinality of the set of all natural numbers (Wiki)
$2^{\aleph_0}=\aleph_1$ (+CH, Wiki)

[Kallikanzarid]

Dan B-Yallay в сообщении #449402 писал(а):

$2^{\aleph_0}=\aleph_1$ (Wiki)

Не-а.

[Профессор Снэйп]

Dan B-Yallay в сообщении #449402 писал(а):

$\aleph_0$ is the cardinality of the set of all natural numbers (Wiki)
$2^{\aleph_0}=\aleph_1$ (+CH, Wiki)

Шо за бред Вы такой учитали? Гиперссылку в студию!!!

[Kallikanzarid]

Профессор Снэйп в сообщении #449400 писал(а):

(Оффтоп)

Отправляем множество простых чисел в $\mathbb{N}$ произвольным образом, затем однозначно доопределяем это отображение на единице и составных числах. Множество простых чисел счётно, счётное в счётное отображается континуумом способов.

[Dan B-Yallay]

Профессор Снэйп в сообщении #449407 писал(а):

Dan B-Yallay в сообщении #449402 писал(а):

$\aleph_0$ is the cardinality of the set of all natural numbers (Wiki)
$2^{\aleph_0}=\aleph_1$ (+CH, Wiki)

Шо за бред Вы такой учитали? Гиперссылку в студию!!!

http://en.wikipedia.org/wiki/Aleph_0#Aleph-naught. ( +CH = Continuum Hypothesis true.)

[Профессор Снэйп]

Dan B-Yallay в сообщении #449414 писал(а):

( +CH = Continuum Hypothesis true.)

Во, золотые слова! Заключая контракт, нужно внимательнее всего читать написанное в скобочках и мелким шрифтом!

Существенная часть цитаты из приведённой статьи выглядит так:

Цитата:

$\mathbf{CH}$ is equivalent to the identity $2^{\aleph_0} = \aleph_1$.

И ещё, парой строчек выше:

Цитата:

It is not clear where this number fits in the aleph number hierarchy.

P. S. Где-то, кстати, тема была про $\aleph_1$: например, можно доказать, что существует ровно $\aleph_1$ типов изоморфизма счётных суператомных булевых алгебр. Вроде даже две темы было.

[Kallikanzarid]

Ответ на задачу (2) - ноль. Пусть $p$ и $q$ - простые, $p \neq q$. При этом так как необходимо $\varphi(1) = 0$, то $\varphi(p) \neq 0,\ \varphi(q) \neq 0$. Тогда $\varphi(p^{\varphi(q)} q^{\varphi(p)}) = 2 \varphi(p) \varphi(q) = \varphi(p^{2 \varphi(q)})$, следовательно $p^{\varphi(q)} q^{\varphi(p)} = p^{2 \varphi(q)}$, что противоречит основной теореме арифметики.