Алгебраическое представление решеток. Булевы решетки

Введем обозначения Sup(a, b) = a È b, Inf(a, b) = a Ç b,

Если выполняются законы:

1. a È b = b È a 1’. a Ç b = b Ç a

2. (a È b) È c = a È b È c

2’. (a Ç b) Ç c = a Ç b Ç c

3. a È (a Ç b) = a 3’. а Ç (b È a) = a

4. a È a = a 4’. а Ç a = a

то имеет место решетка.

То есть решетка можно определить как алгебру Z = < L, Ç, È >, для операций которой выполняются вышеперечисленные законы.

Решетка называется дистрибутивной, если дополнительно к вышеперечисленным выполняется дистрибутивный закон:

5. a È b Ç c = (a È b) Ç(a È c)

5'. а Ç (b È c) = a Ç b È a Ç c

Решетка называется ограниченной, если она имеет максимальный и минимальный элементы. Например, если взять отрезок действительной оси от 0 до 1 (вместе с конечными точками) и отношение "меньше", то это будет ограниченная решетка. Убрав крайние точки, получаем неограниченную решетку.

Обычно минимальный элемент решетки обозначают как 0, а максимальный как 1.

ā - дополнение а, если а È ā = 1 и а Ç ā =0

Решетка является решеткой с дополнением, если каждый элемент имеет хотя бы одно дополнение.

Ограниченная дистрибутивная решетка с дополнением является булевой.

Мощность множества натуральных чисел.

N -множество натуральных чисел.

Z - множество целых чисел.

Q - множество рациональных чисел.

R -множество целых чисел.

С - множество комплексных чисел.

N - мощность множества N.

Аксиоматика Пеано

Наименьшей бесконечной мощностью является счетная мощность - мощность множества натуральных чисел. Это бесконечное множество можно задать с помощью системы аксиом:

1. 0 Î N

2. n Î N Þ n^’ Î N

3. n Î N Þ n^’ ¹ 0

4. n Î N, m Î N, n^’ = m^’ Þ n = m

A = N

5. 0 Î A Í N }

n Î A Þ n^’ ÎA }

где n^’ - элемент, следующий за n.

N = À₀ (алеф-нуль) - счетная мощность.

Мощность множества действительных чисел. Теорема Кантора.

Аналогом мощности действительных (вещественных) чисел служит множество точек

на отрезке действительной оси или на всей действительной оси.

Теорема Кантора.

N < R (À₀ < À₁)