Изброими и неизброими множества

Твърдение 1: Изброима фамилия от изброими множества

• Изброимо множество е множество, което може да бъде обходено: всеки елемент е в определена позиция в последователността.
• Изброима фамилия от множества е фамилия от множества, на която е възможно да се присвои индекс (номер) от естествените числа.
• Обединението на изброима фамилия от изброими множества е също изброимо множество.
• Таблицата показва елементите на отделните множества, за да се демонстрира как се организира обединението.
• Биекцията h: N → N×N е ключова, за да се обходи таблицата систематично. h(x) = (i,j) показва как да се открие елементът от таблицата.
• Използва се функция f : N → ⋃i∈N Ai, която изброява елементите на обединението чрез индекса h(x) от h: N → N×N.

Дефиниция 2: Характеристична функция

• Характеристичната функция на множество В, fB : А → {0,1} , показва дали елемент x ∈ А е и в В или не.
• fB(x) = 1, ако x ∈ В
• fB(x) = 0, ако x ∉ В

Теорема 3: Множеството P(N) е неизброимо

• P(N) е мощността (брой) на всички подмножества на множеството от естествени числа N.
• Биекцията между подмножества на А и характеристични функции гарантира, че броят на подмножествата е безкраен.
• Конструкцията на fD чрез диагонализация е ключът към доказателството.
• h е сюрекция от N към {f | f : N → {0, 1}} означава, че всички функции са обхванати.
• Конструкцията на fD демонстрира противоречие, което доказва, че h не може да е сюрекция.
• Множеството от всички функции от N в {0, 1} е неизброимо. Това означава, че P(N) е неизброимо, което е и целта на доказателството.

Следствие 4: Р(А) е неизброимо, ако А е изброимо

• Ако А е изброимо, то множеството от всички подмножества на А е неизброимо (по-голямо).
• Биекцията g : P(N) → P(A), g(X) = {f(x) | x ∈ X }, показва еквивалентност.

Основни комбинаторни принципи

• Принцип на Дирихле: Ако има повече елементи от множество А, отколкото места в множество В, не може да има инекция от А в В.
• Принцип на биекцията: Мощността на крайни множества А и В са равни, тогава и само тогава, когато има биекция между А и В.
• Принцип за събирането: |A ∪ B| = |A| + |B| - |A ∩ B|
• Принцип за включване и изключване: Използва се за изчисляване на обединението на няколко множества чрез разглеждането на пресечни множества, които се повтарят в изчисленията.
• Принцип за умножението: Редуване на изборите; |A × B| = |A| * |B|