Потужність множини

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Потужність множини, або кардинальне число множини, — характеристика множин (у тому числі нескінченних), що узагальнює поняття кількості (числа) елементів скінченної множини.

В основі цього поняття лежать природні уявлення про порівняння множин:

  1. Будь-які дві множини, між елементами яких може бути встановлено взаємно однозначну відповідність (бієкція), містять однакову кількість елементів (мають однакову потужність).
  2. Зворотно: множини, рівні за потужністю, мусять допускати таку взаємно однозначну відповідність.
  3. Частина множини не перевершує повної множини за потужністю (тобто за кількістю елементів).

До побудови теорії потужності множин, множини розрізнялися за ознаками: порожня/непорожня і скінченна/нескінченна, також скінченні множини розрізнялися за кількістю елементів. Нескінченні ж множини не можна було порівняти.

Потужність множин дозволяє порівнювати нескінченні множини. Наприклад зліченні множини є самими «маленькими» нескінченними множинами.

Потужність множини A позначається через |A|. Сам Кантор використовував позначення \overline{\overline{A}}. Іноді використовують позначення \# A або \mathrm{card}(A).

Потужність скінченних множин[ред.ред. код]

Для множин зі скінченною кількістю елементів, потужність множини є фактично кількістю елементів цієї множини. Інакше можна сказати, що множина A є скінченною, якщо існує таке натуральне число n, що A ~ {k, kNkn}. В іншому випадку, множина називається нескінченною.

Між двома скінченними множинами A і B існує взаємно однозначна відповідність тоді і тільки тоді, коли їхні потужності збігаються, тобто |A|=|B|.

Нехай A = {a1,a2,…,an} — скінченна множина з n елементів (|A|=n), тоді кількість усіх підмножин множини A дорівнює 2n, тобто 2|A|.

Множину всіх підмножин деякої множини A (скінченної або нескінченної) часто позначають через β(A) (або B(A) чи 2|A|) і називають булеаном множини A. Очевидно, що для скінченної множини A виконується |B(A)|= 2|A|.

Потужність нескінченних множин[ред.ред. код]

В загальному випадку, справедливому і для нескінченних множин, множини A та B є рівнопотужні, або мають однакову потужність, якщо можна встановити взаємно однозначну відповідність між елементами цих множин, тобто якщо існує бієкція f:AB. Рівнопотужні множини позначаються як A ~ B.

Відношення рівнопотужності є рефлексивним, симетричним та транзитивним, тобто є відношенням еквівалентності.

Для нескінченних множин потужність множини може збігатися з потужністю її власної підмножини.

Приклади:

Множина натуральних чисел N рівнопотужна множині S={1,4,9,16,…}, яка складається з квадратів натуральних чисел. Необхідна бієкція встановлюється за законом (n, n2), n∈N, n2S.

Множина Z всіх цілих чисел рівнопотужна множині P всіх парних чисел. Тут взаємно однозначна відповідність встановлюється таким чином: (n,2n), n∈Z, 2n∈P.

Числа алеф[ред.ред. код]

Потужність множини натуральних чисел N позначається символом \aleph_0 (алеф-нуль). Наступні кардинальні числа в порядку зростання позначають \aleph_1, \aleph_2,\dots.

Зліченність та скінченність множин[ред.ред. код]

Множина A називається зліченною, або зліченно-нескінченною, якщо |A| ~ |N|. В цьому випадку кажуть, що елементи такої множини можна занумерувати. Зліченними є множини цілих Z, натуральних N та раціональних Q чисел.

Множина, яка є скінченна, або зліченна, називається не більш ніж зліченною.

Нескінченна підмножина зліченної множини є зліченна. Також нескінченна множина містить зліченну підмножину.

Для незліченних множин, їхня потужність \ge \aleph_0. Тобто, зліченна множина в певному розумінні є «найменшою» з нескінченних множин. Незліченними є множини дійсних R та комплексних C чисел.

Потужність континууму[ред.ред. код]

Про множини, рівнопотужні множині дійсних чисел [або дійсних чисел з інтервалу (0, 1)] кажуть, що вони мають потужність континуума, і потужність таких множин позначається символом c. Континуум-гіпотеза стверджує, що с=\aleph_1.

Властивості[ред.ред. код]

  • Дві скінченні множини рівнопотужні тоді й тільки тоді, коли вони складаються з однакового числа елементів. Тобто для скінченної множини поняття потужності збігається із звичним поняттям кількості.
  • Для нескінченних множин потужність може збігатись з потужністю своєї власної підмножини, наприклад |{\mathbb N}|=|\mathbb Z|.
    • Більш того, множина нескінченна тоді і тільки тоді, коли вона містить рівнопотужну власну (тобто таку, що не збігається з основною множиною) підмножину.
  • Теорема Кантора гарантує існування потужнішої множини для будь-якої даної: Множина всіх підмножин множини A має більшу потужність, ніж A, або |2^A| > |A|.
  • За допомогою канторового квадрата можна також довести наступне корисне твердження: Декартів добуток нескінченної множини A з самою собою рівнопотужний A.
  • Потужність декартового добутку:
    |A\times B|=|A|\cdot |B|
  • Формула включення-виключення в найпростішому виді:
    |A\cup B|=|A| + |B| - |A\cap B|

Див. також[ред.ред. код]

Література[ред.ред. код]