Ещё раз про мощность P(N)

[Interceptor]

Никак не могу понять, ну почему мощность всех подмножеств множества N равна мощности континуума? Разве нельзя установить взаимно однозначное соответствие между N и P(N)? Я понимаю, что мне как студенту тех вуза в такие дебри лезть не стоит Но в учебнике про это пишут вскользь, а понять хочется

[paha]

мощность множества $P(X)$ всех подмножеств любого множества $X$ строго больше мощности последнего:

$$ {\rm card}P(X)>{\rm card}X $$

-- Чт апр 01, 2010 22:48:26 --

а доказательство для $\mathbb{N}$... Любое подмножество определяется своей характеристической функцией. Характеристическая функция на $\mathbb{N}$ -- это последовательность нулей и единиц. Любое вещественное число в двоичной записи -- тоже.

-- Чт апр 01, 2010 22:51:11 --

Общий случай - ищите в гугле "диагональную процедуру" Кантора

[ewert]

Interceptor в сообщении #305452 писал(а):

Разве нельзя установить взаимно однозначное соответствие между N и P(N)?

Нельзя. Медицинский факт.

Interceptor в сообщении #305452 писал(а):

Я понимаю, что мне как студенту тех вуза в такие дебри лезть не стоит

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

[Interceptor]

Цитата:

мощность множества $P(X)$ всех подмножеств любого множества $X$ строго больше мощности последнего:

$$ {\rm card}P(X)>{\rm card}X $$

Это, как я понимаю, следует из того, что количество подмножеств всегда больше количества элементов множества, а именно $2^n$?

Цитата:

Нельзя. Медицинский факт.

Но почему нельзя каждое подмножество пронумеровать так же как, например, множество Z?

Цитата:

а доказательство для $\mathbb{N}$... Любое подмножество определяется своей характеристической функцией. Характеристическая функция на $\mathbb{N}$ -- это последовательность нулей и единиц. Любое вещественное число в двоичной записи -- тоже.

Похоже и правда лучше не лезть

[maxmatem]

а вы попробуйте пронумеровать и увидите что это просто не возможно!
ну уж если так хочется понять возьмите Колмогорова,Фомин - элементы теории функций и функциональный анализ и почитайте......

[Maslov]

Interceptor в сообщении #305466 писал(а):

Похоже и правда лучше не лезть

Да тут нет ничего сложного.
Характеристическая функция подмножества множества натуральных чисел -- это просто функция, сопоставляющая каждому натуральному числу значение 1, если это число принадлежит данному множеству, и 0 в противном случае.
Например, характеристическая функция множества $X = {1, 3}$ будет такой:
$f_X(1) = 1$
$f_X(2) = 0$
$f_X(3) = 1$
$f_X(k) = 0~~ \text{при}~~ k > 3$

Ну а характеристическая функция множества четных натуральных чисел такая:
$f_X(k) = 1~~ \text{если}~~ k~-~\text{четное}$
$f_X(k) = 0~~ \text{если}~~ k~-~\text{нечетное}$

Т.о., каждому подмножеству множества натуральных чисел $\mathbb N$ соответствует последовательность 0 и 1, причем для разных подмножеств эти последовательности будут разными. Поэтому если все подмножества множества $\mathbb N$ можно пронумеровать, то можно пронумеровать и последовательности 0 и 1 и наоборот.

Ну а дальше вступает в действие та самая диагональная процедура:
Предположим, нам удалось пронумеровать все последовательности 0 и 1.
Для примера пусть начало этого списка выглядит так:
$n_1 = 0~0~1~...$
$n_2 = 1~1~0~...$
$n_3 = 1~1~1~...$
$. . . . . . $

Построим новую последовательность 0 и 1 таким образом, что ее
1-й элемент отличается от $n_1[1]$
2-й элемент отличается от $n_2[2]$
3-й элемент отличается от $n_3[3]$
и т.п.
(т.е., в нашем случае новая последовательность начинается так $\{1, 0, 0, ... \}$)

По построению очевидно, что в нашей нумерации эта новая последовательность отсутствует, т.к. от каждой последовательности, входящей в нумерацию, она в какой-то позиции да отличается.
Т.о., мы пришли к противоречию с нашим предположением, что существует нумерация всех последовательностей 0 и 1, а значит такой нумерации не существует.

А следовательно, не существует и нумерации всех подмножества множества $\mathbb N$.

[Interceptor]

Цитата:

Т.о., каждому подмножеству множества натуральных чисел $\mathbb N$ соответствует последовательность 0 и 1, причем для разных подмножеств эти последовательности будут разными. Поэтому если все подмножества множества $\mathbb N$ можно пронумеровать, то можно пронумеровать и последовательности 0 и 1 и наоборот.

То есть я правильно понял, что, например, подмножество$ \{2, 3\}$ множества $\{ 1, 2, 3, 4, 5, ...\}$ будет выглядеть как 0 1 1 0 0 0 ...?

[Maslov]

Правильно поняли.

[Interceptor]

Maslov в сообщении #305487 писал(а):

Правильно поняли.

Спасибо, Вы очень доступно объяснили.