2.5. Мощность множества

Некоторые множества не могут быть выписаны явно, так как «достаточно велики». Однако при их определении мы просто «…» понимаем как «и так далее».

Рассмотрим множество A={1, 2, ..., n}, которое имеет n элементов. Говорят, что мощность множества A есть n, и записывают: A = card(A) = n.

Множество X конечно, если X= или если для некоторого nN существует множество {1, 2, ..., n} такое, что оно имеет то же самое число элементов (мощность), что и X.

Если X и никакого n не может быть найдено, то X называют бесконечным. Примерами таких множеств являются N – множество натуральных (целых положительных) чисел: N = { 1, 2, 3, …}

и Z ‑ множество целых чисел: Z = {.., -2, -1, 0, 1, 2, …}

2.6. Прямое Произведение множеств

Рассмотренные выше операции над множествами позволяли получать множества, элементы которых брались из исходных множеств. Рассмотрим операцию, позволяющую получить множество, элементы которого имеют иную, более сложную структуру, чем элементы исходных множеств. На интуитивном уровне: рассмотрим множество столбцов шахматной доски F={a, b, ..., h} и множество строк R={1, 2, ..., 8}. Можно образовать множество клеток шахматной доски по множеству столбцов и множеству строк вида {a1, a2, ..., h8}.

Более строго: пусть x₁, x₂, ..., x_n – последовательность из n элементов. Скобки указывают порядок, в котором записаны элементы. Таким образом, x₁, x₂, ..., x_n  x₂, x₁, ..., x_n при x₁  x₂. Будем называть такую последовательность кортежем длины n. Кортеж длины 2 будем называть парой.

Пусть даны n множеств A₁, A₂, ..., A_n; множество всех кортежей x_1, x₂, ..., x_n таких, что x₁ A₁, x₂ A₂,... , x_n A_n называют прямым произведением A₁, A₂, ..., A_n и обозначают A₁ A₂  ...  A_n.

Другое обозначение – . Другое название – декартово произведение.

Прямое произведение одинаковых множеств удобно записывать через степень: A  A  ...  A= Aⁿ.

Пример 2.9.

Пусть X={0, 1}, Y={x, y}, Z = {0, 1, 2}.

Тогда X  Y = {0,x, 0,y, 1, x, 1, y}

Y X= {x,0, x,1, y,0, y,1}.

Таким образом, X  Y  Y X.

X  Z = {0,0, 0,1, 0,2, 1,0, 1,1, 1,2}.

Здесь (0,1) и (1,0) — элементы X  Z, но различные. 

Еще два тождества:

22. (A  B)  C = (A  C)  (B  C)

23. (A  B)  C = (A  C)  (B  C)

2.7. Бинарные отношения

Если говорить неформально, то отношение – связь между элементами некоторого множества, то есть из прямого произведения выделяется подмножество, обладающее какими-то свойствами, – это и будет отношение. Более строгое определение:

n-местным отношением  на множестве A называется пара =А, R, где R Aⁿ.

Другими словами, упорядоченная последовательность элементов x₁, x₂, ..., x_n , где x_i  A, связана отношением  тогда и только тогда, когда x₁, x₂, ..., x_n  R.

При n=2 (это наиболее часто встречается) отношение называется бинарным. Следовательно, бинарное отношение на множестве A есть подмножество A  А.

Пример 2.10.

Пусть A= {1, 2, 3, 4, 5, 6}. R={x,y): x, y  A, x – делитель y и x  5}. Тогда R может быть записано в явном виде:

R = { 1,1, 1,2, 1,3, 1,4, 1,5, 1,6,

2,2, 2,4, 2,6, 3,3, 3,6, 4,4, 5,5}. 

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

Для любого множества A тождественное отношение I_A определяется свойством R_I= {a,a: a  A}, а универсальное отношение U_A – свойством R_U= {a,b: a  A, b A}.

Таким образом, R_U = A² (любые два элемента А связаны отношением U_A).

Так как   A², то  является отношением на A и называется пустым отношением.

Для бинарного отношения R на множестве А определим область определения D(R) следующим образом:

D(R) = { x: x, y  R}

и область значений W(R) следующим образом:

W(R) = { y: x, y  R}

Пример 2.11.

Пусть R — отношение такое же, как в примере 2.10. Тогда D(R) = {1, 2, 3, 4, 5}, W(R)=A. 

Замечание об обозначении отношений. Существует практика обозначения отношений строчными греческими буквами (, ,  и т.п.). Используют два вида обозначений:

a  b, т.е. a связано с b отношением , если =А, R и a, b  R 

Пусть  — бинарное отношение. Определим обратное отношение ^-1=А, R^-1 следующим образом: ^-1 = {x,y: y,x  R}

Таким образом,  ^-1 связывает те же пары элементов, что и , но «в другом порядке».

Следовательно: если   A  B, то  ^-1  B  A,