Счетное множество

Бесконечное множество М= {a1, a2, a3, ….} называется счетным, если оно эквивалентно множеству натуральных чисел, т.е. элементы счетного множества можно занумеровать. Пример – множество четных чисел, множество нечетных чисел. Покажем, что счетным будет и множество целых чисел Z.

nN, zZ , z=[n/2](-1)ⁿ ([] – отбрасывание дробной части числа)

1↔0; 2↔1; 3↔-1; 4↔2; 5↔-2

Доказывается, что: 1)объединение конечного множества и счетного есть множество счетное; 2)объединение конечного числа счетных множеств есть множество счетное 3)объединение счетного числа счетных множеств есть множество счетное.

Способ нумерации счетного множества:

1 ) a1 a2 a3 … 2) 1 1 1 1 1…

b1 b2 b3… 1 1 1 1 1…

……… 1 1 1 1 1…

f1 f2 f3… 1 1 1 1 1…

Несчетное множество

Теорема: множество действительных чисел (0,1) несчетно.

Заметим, что некоторые числа этого интервала могут изображаться двумя способами:

½ = 0,50000000… и ½= 0,49999999… => все m_i ≠0 и все m_i ≠9

Предположим, что все числа (0,1) можно занумеровать:

1↔0, α₁, α₂, α₃, α₄,…

2↔0,β₁, β₂, β₃, β₄,…

3↔0,γ₁, γ₂, γ₃, γ₄,…, построим следующее число a(0,1) a=0,₁, ₂, ₃,…, где 0<d₁<9, 0<d₂<9, 0<d₃<9 … и d₁<> α₁ , d₂<> α₂, d₃<> α₃ и т.д.

a(0,1) но по построению это число не совпадает ни с одним из пронумерованных чисел, т.е. мы нашли число, которое не получило номера, что говорит о том, что множество точек (0,1) несчетно, а следовательно, несчетным будет множество действительных чисел плоскости, пространства.

Доказывается, что из всех бесконечных множеств самым малым по мощности является счетное множество, и если мы удалим из бесконечного множества счетное, то останется множество, эквивалентное данному, отсюда вытекает, что множество иррациональных чисел несчетно, т.к. это разность между всеми действительными и рациональными числами, т.е. I=R\Q.

Множество трансцидентных чисел – несчетное множество

Множества, эквивалентные множеству точек Î(0,1), называются множествами мощности континуума. Множества непрерывных функций, заданных на (0,1) имеют мощность континуума.

Существование множеств сколь угодно большой мощности.

Если M={a1,…,an}, то |M|=n

Теорема: мощность множества всех подмножеств конечного множества(степень) имеет мощность 2ⁿ ,т.е. |P(M)|=2^|M|=2ⁿ

Доказательство: пусть имеем конечное множество М, составим степень этого множества. P(M)={0,{a1},…,{an},{a_i,a_i+1,…,{ak…am}}}. Поставим в соответствие каждому элементу множества МР(М) n-значное двоичное число по закону: если элемент ai из множества М является элементом М, то на i-том месте двоичного числа ставим 1, в противном случае – 0.

aiN

{a1}↔10…0 тем самым мы перечислили все n- значные

{an}↔0…010… двоичные числа, а их всего 2ⁿ

{a1,a2}↔110…0

{a1…am}↔1…1

Следствие: |N|<|P(M)| для конечных множеств. Покажем, что это неравенство имеет место и для бесконечных множеств.

Пусть М- бесконечное множество М={a1,a2,a3,…}, составим степень Р(М)={0,{a1},…,{a1,a2},…}, если каждому элементу ai множества М поставить в соответствие элемент ai в степени (ai↔{ai}P(M) ), то => |M||P(M)|.

Чтобы доказать теорему, мы должны показать, что Р(М) не эквивалентно М, тем самым |M|<|P(M)|.

Предположим противное, а именно что можно установить взаимно однозначное соответствие между элементами множеств М и Р(М).

М Р(М) При этом может встретиться такой случай, что элемент,

a1↔{ } (1) стоящий в левой части (1) , входит в правую часть,

a2↔{ } тогда этот элемент назовем включенным, или элемент,

… стоящий в левой части, не входит в правую часть, тогда

ak↔0 мы назовем его невключенным. Составим множество S

… из всех невключенных элементов, ÎМ. Множество S не пусто (ak), но множество S ai↔{a1…} и т.д. является элементом степени SÎP(M)S будет соответствовать какой-то элемент pÎM, т.е. рÎМ, р↔S,  он является включенным или нет.

Пусть р – включенное, тогда он содержится в S, чего быть не может, т.к. S состоит из невключенных элементов. Пусть теперь р – невключенное, тогда он не содержится в S, но S состоит из всех невключенных Þ элемент рÎМ не является ни включенным, ни невключенным. Это противоречие доказывает теорему.

Из этой теоремы вытекает, что множества сколь угодно высокой мощности не существует: |M|<|P(M)|<|P|P(M)||<…

Пример: множество всех действительных функций – мощность выше континуума.