Несчетность

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

ewert писал(а):

А кстати, Википедия в ZFC -- формализована?

Википедия сообщает нам информацию, а не доказывает математические утверждения. Следовательно, в формализации через ZFC не нуждается.

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

[TOTAL]

Каюсь, всю жизнь пользовался нелицензионными доказательствами, да простит меня корпорация ZFC.

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

TOTAL писал(а):

Каюсь, всю жизнь пользовался нелицензионными доказательствами, да простит меня корпорация ZFC.

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

Кстати, в первом пункте моего первого сообщения в этой теме... там доказано, что $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$, то есть континуальность множества $\mathbb{R}$. Это больше, чем просто несчётность. А несчётность доказывается проще...

[ewert]

кстати, как можно доказать континуальность множества, мощность которого по определению есть континуум?

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

ewert писал(а):

кстати, как можно доказать континуальность множества, мощность которого по определению есть континуум?

Ну тогда считайте, что доказана континуальность множества $\mathcal{P}(\mathbb{N})$. Или, другими словами, равенство $c = 2^{\aleph_0}$.

[TOTAL]

ewert писал(а):

кстати, как можно доказать континуальность множества, мощность которого по определению есть континуум?

Может быть, из определения всё доказательство и состоит?

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

ewert писал(а):

Профессор Снэйп писал(а):

Ну тогда считайте, что доказана континуальность множества $\mathcal{P}(\mathbb{N})$.

Уговорили, так и посчитаем. Однако же: как Вы докажете теорему Кантора?

Стандартно.

Пусть $f$ есть биекция $X$ на $\mathcal{P}(X)$. Рассмотрим множество $Y = \{ x \in X : x \not\in f(x) \}$. Тогда $Y = f(y)$ для некоторого $y \in X$. Если $y \in Y$, то $y \in f(y)$ и $y \not\in Y$. Если же $y \not\in Y$, то $y \not\in f(y)$ и $y \in Y$. Противоречие с существованием $f$.

[ewert]

Да я ужо застиснялси.

[TOTAL]

Профессор Снэйп писал(а):

Пусть $f$ есть биекция $X$ на $\mathcal{P}(X)$. Рассмотрим множество $Y = \{ x \in X : x \not\in f(x) \}$. Тогда $Y = f(y)$ для некоторого $y \in X$. Если $y \in Y$, то $y \in f(y)$ и $y \not\in Y$. Если же $y \not\in Y$, то $y \not\in f(y)$ и $y \in Y$. Противоречие с существованием $f$.

Я не вижу отличия этого доказательства от "диагонального построения".

[ewert]

нет, это всё же не диагональное построение. Не вникая даже в детали -- хотя бы потому, что $X$ здесь не обязано быть счётным. Оно вообще любое (непустое). И теорема Кантора -- это действительно святое. Так что по этому пункту я зря пытался придраться.

А вот претензии к доказательству счётности $\mathbb Q$ и теореме Кантора-Бернштейна остаются.

[TOTAL]

Отличие ищите не в том, какое множество.
Укажите отличие в рассуждениях, которое делает одно доказательство полноценным, а другое нет.

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

ewert писал(а):

нет, это всё же не диагональное построение.

Да не, диагональное по сути. Ноги оттуда растут; написанное есть, по сути, обобщение диагонального метода. Но у него есть одна отличительная особенность: оно строгое. Короткое и красиво выглядит!

ewert писал(а):

А вот претензии к доказательству счётности $\mathbb Q$ и теореме Кантора-Бернштейна остаются.

Какие претензии? Я и не знал, что у Вас есть какие-то претензии.

[ewert]

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

Какие претензии? Я и не знал, что у Вас есть какие-то претензии.

А я ведь писал, между прочим. Теорема Кантора-Бернштейна в данном случае -- откровенно из пушки по воробьям, всё следует из гораздо более элементарных соображений.

Но могу и ещё добавить. Вы там какую-то формулу для биекции сочинили (ну или воспроизвели, не важно). Я лично её в упор не понимаю. И дело вовсе не в моей глюпости, а в принципе. Я её отказываюсь понимать. Ибо это -- всего лишь трюк, а вот счётность декартовых произведений счётных множеств -- это именно принцип.

Добавлено спустя 5 минут 48 секунд:

TOTAL в сообщении #177129 писал(а):

Укажите отличие в рассуждениях, которое делает одно доказательство полноценным, а другое нет.

Ну, я могу лишь сказать, что ссылка на теорему Кантора действительно выглядит более идейной. А что имел в виду ув. Профессор -- судить не берусь. Мне дискретников ни в жисть не понять.

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

ewert писал(а):

Теорема Кантора-Бернштейна в данном случае -- откровенно из пушки по воробьям, всё следует из гораздо более элементарных соображений.

Теорема Кантора-Бернштейна --- строгое утверждение. На что ещё можно ссылаться, как не на неё?

Эти Ваши "элементарные соображения"... Насколько они опираются на определения?

Опр. 1 $|A| \leqslant |B|$, если существует инъекция из $A$ в $B$.

Опр. 2 $|A| = |B|$, если существует биекция $A$ на $B$.

Опр. 3 Множество $A$ называется счётным, если $|A| = |\mathbb{N}|$.

Ваши "элементарные соображения" приводят к построению биекции между $\mathbb{Q}$ и $\mathbb{N}$?

ewert писал(а):

Вы там какую-то формулу для биекции сочинили (ну или воспроизвели, не важно). Я лично её в упор не понимаю. И дело вовсе не в моей глюпости, а в принципе. Я её отказываюсь понимать. Ибо это -- всего лишь трюк, а вот счётность декартовых произведений счётных множеств -- это именно принцип.

Ну, если угодно... Есть теорема (довольно сложная и, кстати, эквивалентная аксиоме выбора)

Теорема Если множество $A$ бесконечно, то $|A^2| = |A|$.

Можете на неё ссылаться, если хотите. Но просто в случае, когда $A = \mathbb{N}$, биекция между $\mathbb{N}^2$ и $\mathbb{N}$ легко выписывается в явном виде:

$$ c : \langle x,y \rangle \mapsto \frac{(x+y)^2 + 3x + y}{2} = \frac{(x+y)(x+y+1)}{2} + x $$

Формула для неё легко выводится из формулы суммы арифметической прогрессии. Посмотрите закономерность!

$$ c(0,0) = 0 $$

$$ c(0,1) = 1 $$

$$ c(1,0) = 2 $$

$$ c(0,2) = 3 $$

$$ c(1,1) = 4 $$

$$ c(2,0) = 5 $$

$$ c(0,3) = 6 $$

$$ c(1,2) = 7 $$

И так далее. При помощи этой формулы множество $\mathbb{N}^2$ "пересчитывается по диагоналям".

[ewert]

Не хочу смотреть на закономерность! За ненадобностью. Биекция очевидным образом устанавливается из картинки, которую пуристы (если им времени не жаль) запросто могут перевести на формальный язык.

А уж ссылка на аксиому выбора -- так и вообще не комильфо.

------------------------------------------------------------------------------------
Я Вас чего-то перестаю понимать. Вы же преподаватель. Должна же у Вас быть какая-то иерархия утверждений! А тут чуть что -- так сразу: Бронштейн, аксиома выбора...