Мощности континуума

1⁰. В любом бесконечном множестве M можно так выбрать счётное подмножество A Í M, что |M| = |M \ A|.

Будем рассуждать примерно так же, как ранее при доказательстве факта существования в бесконечном множестве бесконечной последовательности различных элементов (т.е. существования в бесконечном множестве счётного подмножества).

Выберем в M элемент a₁ Î M и заметим, что M \ {a₁} ¹ Æ. Значит можно выбрать b₁ Î M \ {a₁} и заметить, что M₁ = M \ {a₁ , b₁} ¹ Æ. Если уже построены попарно различные элементы a₁ , … , a_k , b₁ , … , b_k Î M со свойством M_k = M \ {a₁ , … , a_k , b₁ , … , b_k } ¹ Æ, то в M_k выберем элемент a_k+1 , а затем выберем b_k+1 в M_k \ {a_k+1} и снова получим

M_k+1 = M \ {a₁ , … , a_k , a_k+1 , b₁ , … , b_k , b_k+1 } ¹ Æ (?!).

Таким образом, во множестве M выделено два счётных подмножества A = {a₁ , a₂ , … } и B = {b₁ , b₂ , … }. Зачем множество B ? С его помощью докажем, что |M \ A| = |M|. Для этого зададим отображение f : M ® M \ A следующим образом: f(x) = .

Легко понять что получится биективное отображение.

2⁰. Всякое бесконечное подмножество счётного множества само счётно.

Пусть множество А счётно, B Í A. Тогда A = {а₁ , а₂ , ... , a_n , … }. Пусть будет первым элементом этой последовательности, принадлежащим множеству В, – вторым элементом с этим же свойством и т. д. Полагая = b_n , n Î N, получаем, что элементы подмножества В составляют последовательность b₁ , b₂ , ... , b_n , ... , т.е. B счётно.

3⁰. При добавлении конечной или счётной совокупности элементов к счётному множеству получается счётное множество.

Если к счётному множеству A = {a₁ , a₂ , ...} добавлено конечное множество B = {b₁ , … , b_k}, то взаимно-однозначное соответствие f: N ® A È B устанавливается формулой f(n) = . Если же B = {b₁ , b₂ , … } – счётно, то f(n) = :

4⁰. При добавлении конечной или счётной совокупности элементов к бесконечному множеству M получается равномощное ему множество K .

Действительно, в бесконечном множестве M выделим счётное подмножество A (см. рисунок ниже). Тогда для добавленного конечного или счётного множества K¢ = K \ M уже доказано, что |A È K¢| =À₀ = |A|. Поэтому существует биекция j : A ® A È K, которая распространяется до биекции f: M ® M È K с помощью следующей формулы: f(m) = :

5⁰.Множество R всех действительных чисел равномощно любому отрезку (a; b), [a; b), (a; b], [a; b], т.е.

|(a; b)| = |[a; b)| = |(a; b]| = |[a; b]| = |R| = c.

Биективноесоответствие f : (a; b) ® R устанавливается школьной функцией f(x) = tg . Равномощность перечисленных отрезков следует из свойства 4⁰.

6⁰. Если объединение счётного семейства конечных множеств бесконечно, то оно счётно. В частности, счётным является объединение счётного семейства попарно непересекающихся конечных множеств.

В самом деле, пусть даны конечные множества А₁ , А₂ , ... , А_n , ... и пусть их объединением будет множество В. Пронумеруем сначала все элементы конечного множества А₁ , затем продолжим эту нумерацию, занумеровав все элементы множества А₂ , и т.д. В итоге будут перенумерованы все элементы множества B, причём процесс нумерации не может закончиться на конечном шаге (иначе множество B было бы конечным). Значит, каждое натуральное число будет номером некоторого элемента из В, что и требовалось доказать.

Замечание: Условие на пересечение множеств существенно: если взять все множества равными, то получится конечное, а не счётное множество. Однако можно утверждать, что если объединение счётного семейства конечных множеств бесконечно, то это объединение счётно.

7⁰. Объединение конечного или счётного семейства счётных множеств есть счётное множество.

Пусть даны счётные множества A_i = {a_i1 , a_i2 , …} (i Î Nили i Î {1, … , k}). Расположим их элементы в виде бесконечной прямоугольной таблицы одного из приведённых ниже видов: слева таблица для счётного семейства множеств, а справа – для конечного. Эти таблицы будем обходить в предписанном порядке (номера клеток написаны ниже самих элементов). На каждом шаге каждому ещё не пронумерованному элементу присвоим очередной номер.

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

8⁰. Декартово произведение двух счётных множеств счётно.

В самом деле, пусть A = {a₁ , a₂ , … } и B = {b₁ , b₂ , … } – два счётных множества. Тогда A´B = {(a; b) | aÎ A Ù b Î B} = {(a_i ; b_j) | i, j Î N}, и пересчёт элементов этого множества можно осуществить так же, как и при доказательстве предыдущего свойства: вместо a_ij нужно рассматривать пару (a_i ; b_j ).

9⁰. Декартово произведение любого конечного семейства счётных множеств счётно.

Пусть A₁ , … , A_n – счётные множества. Тогда счётность декартова произведения можно доказать индукцией по n Î N: база имеется при n = 2, а индукционный переход обеспечивается формулой A₁´ … ´ A_n = (A₁ ´ … ´ A_n–1 ) ´ A_n .

10⁰. Декартов квадрат [0; 1]´[0; 1] = {(a; b) Î R´R | a, b Î [0; 1]} равномощен отрезку [0; 1], т.е. |[0; 1]´[0; 1]| = c = |[0; 1]|.

Нужно установить биекцию f : [0; 1] ® [0; 1]´[0; 1] , однако сделать это непосредственно не так-то просто. Поэтому привлечём новые идеи о сравнении мощностей, которые строго будут обоснованы в следующем параграфе. Вначале докажем, что |[0; 1]| £ |[0; 1]´[0; 1]|, построив вложение (инъекцию) g : [0; 1] ® [0; 1]´[0; 1], а затем, вложив декартов квадрат в отрезок, докажем и обратное неравенство |[0; 1]´[0; 1]| £ |[0; 1]|. Из двух полученных неравенств будет следовать искомое равенство мощностей.

Ясно, что |[0; 1]| £ |[0; 1]´[0; 1]|, т.к. существует много инъективных отображений g : [0; 1] ® [0; 1]´[0; 1], например, заданное правилом g(x) = (x; 0).

Для доказательства обратного неравенства |[0; 1]´[0; 1]| £ |[0; 1]| построим инъективное отображение f : [0; 1]´[0; 1] ® [0; 1], используя десятичную запись действительных чисел: для a = 0, a₁a₂ … , b = 0, b₁b₂ … Î [0; 1] зададим значение f((a; b)) = g Î [0; 1], где g = 0, a₁b₁a₂b₂ … a_nb_n … , т.е. в десятичной записи числа g цифры числа a поставим на нечётные места, а цифры числа b – на чётные места. При этом в качестве десятичного представления числа 1 (и только для него) будем рассматривать запись 0, 999… с бесконечным “хвостом” девяток. Тогда у числа g представление с бесконечным “хвостом” девяток может получиться только в случае наличия таких “хвостов” у a и у b, т.е при a = 1 = 0,999… = b и g = 0, 999…= 1 . Ясно, что f – отображение.

Оно инъективно: если f((a; b)) = f((e; d)), где e = 0, e₁e₂ … и d = 0, d₁d₂ … , то 0, a₁b₁a₂b₂ … = f((a; b)) = f((e; d)) = 0, e₁d₁e₂d₂ … , и a_n = e_n и b_n = d_n при любом n Î N (подробно разберите все возникающие случаи !!). Поэтому a = e, b = d и (a; b) = (e; d).

Таким образом, доказаны неравенства

|[0; 1]| £ |[0; 1]´[0; 1]| и |[0; 1]´[0; 1] | £ |[0; 1]| ,

из которых следует (пока интуитино), что |[0; 1]| = с = |[0; 1]´[0; 1]|.

Замечание: построеноое отображение f: [0; 1]´[0; 1] ® [0; 1] не сюръективно, т.к. у числа g = 0,1119 … 19 … = 0,11(19) Î [0; 1] нет прообраза: если a = 0,a₁a₂ … , b = 0,b₁b₂ … и f((a; b)) = g, то a = 0,111… = 0,(1), b = 0,199…9… = 0,20…, но

f((a; b)) = 0,12101010…10… = 0,12(10) ¹ 0,11(19) = g

– противоречие.

11⁰. Если |A| = |B| , |C| = |D| , то |A´B| = |C´D|.В частности, декартово произведение R´R равномощно R, т.е. имеет мощность континуума: |R´R| = c = |R|.

Биекция f : A´B ® C´D задаётся правилом f((a; b)) = ((g(a); h(b))) Î C´D, где g : A ® C и h : B ® D – биекции.

Второе утверждение следует из того, что |R| = |[0; 1]| и предыдущего свойства.

Теперь легко понять, что |C| = с = |R|. Учитывая, что |R| = |R´R|, докажем, что |C| = |R´R|. Взаимно однозначное соответствие f : С® R´R устанавливается очевидным образом: f(a+i×b) = (a; b) Î R´R.

Таким образом, проведённое в этом параграфе исследование мощностей показало, что À₀ = |N| = |Z| = |Q| < |R| = |C| = c.

Применим полученные результаты для решения старого и важного вопроса XIX в. о существовании трансцендентных чисел.

Действительное (или комплексное число) a называется алгебраическим, если оно является корнем некоторого многочлена f(x) с целыми коэффициентами. Множество всех многочленов с целыми коэффициентами обычно обозначается так:

Z[x] = { f(x) = a_n×xⁿ+a_n–1×x^n–1+…+a₁×x+a₀ | n Î N È {0} Ù a_i Î Z(0 £ i £ n)}.

Поэтому можно записать

А_R = {a Î R | $ f(x) Î Z[x] f(a) = 0}, А_С= {a Î С | $ f(x) Î Z[x] f(a) = 0}

для множеств всех действительных и комплексных алгебраических чисел соответственно. Ясно, что A_R Í A_C.

Если действительное (или комплексное число) не является алгебраическим, т.е. оно не является корнем никакого многочлена f(x) с целыми коэффициентами, то такое число называется действительным (или комплексным) трансцендентным. Таким образом, множества T_Rи T_C всех действительных (или комплексных) трансцендентных чисел можно задать так: T_R = R \ А_Rи T_С = С \ А_С. Ясно, что T_R Í T_C .

С алгебраическими числами все давно знакомы:

Примеры: 1. Любое рациональное число a = Î Q является алгебраическим, т.к. удовлетворяет уравнению n×x – m = 0 с целыми коэффициентами (f(x) = n×x – m). Таким образом, Q Í A_R Í A_C.

2. Î A_R , т.к. является корнем многочлена f(x) = x² – 2 с целыми коэффициентами.

3. a = – i Î A_C , т.к. a² = 2 – 2×i× – 1 = 1 – 2×i× и (a – 1)² = –8. Таким образом, a является корнем многочлена f(x) = (x–1)² + 8 = x² – 2×x + 9 с целыми коэффициентами.

4. a = – Î A_R. Поиск аннулирующего это число многочлена аналогичен предыдущему примеру:

(a – )³ = – 5, a³ – 3× ×a² + 9×a – 3× = –5, a³ + 9×a + 5 = 3× ×(a² + 1),

(a³ + 9×a + 5)² = 27×(a² + 1)², a⁶ + 81×a² + 25 + 18×a⁴ + 10×a³ + 90×a = 27×(a⁴ + 2×a² + 1),

a⁶ – 9×a⁴ + 10×a³ + 27×a² + 90×a – 2 = 0.

Значит, a – корень многочлена f(x) = x⁶ – 9×x⁴ + 10×x³ + 27×x² + 90×x – 2 Î Z[x].

5. Оказывается, что (A_R , +, × ) и (A_С , +, × ) – поля относительно обычных операций сложения и умножения действительных и комплексных чисел. Более того, поле A_C алгебраически замкнуто, т.е. если a Î С является корнем многочлена b_n×xⁿ + … + b₁×x + b₀ с алгебраическими коэффициентами b_n , … , b₀ Î A_C , то a Î A_C . Эти нетривиальные результаты доказываются в курсе алгебры. Из них следует, что сколь угодно сложное выражение, полученное из алгебраических чисел с помощью операций сложения, умножения, деления, извлечения корней будет представлять алгебраическое число. Например, алгебраическим будет число

.

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

Теорема (о счётности Z[x]). |Z[x]| = À₀ .