Антиномия всемогущества

Бог всемогущ, поэтому он может создать такой камень, который сам не сможет поднять.

Но Бог всемогущ, поэтому он может поднять любой камень.
 
 

Антиномия Рассела

Рассмотрим все множества, не содержащие самих себя. Рассмотрим множество всех таких множеств. Тогда: если оно не содержит себя, то оно содержит себя.
 
 

Парадокс ╚ Деревенский парикмахер╩

 ОТНОШЕНИЕ - произвольное подмножество R множества Aⁿ всех кортежей (упорядоченных наборов) вида бa₁,...,a_n), где a₁,...,a_n -элементы некоторого множества A; в этом случае говорят, что R есть n-местное отношение на A. Понятие отношения служит в математике для выражения на теоретико-множественном языке связей между объектами. Множество всех таких элементов a, которые входят хотя бы в один кортеж, принадлежащий отношению R называется полем этого отношения. Двухместные отношения называются бинарными. Если R - бинарное отношение, то вместо б a, bсО R, часто пишут aRb. Частным случаем понятия отношения является соответствие.

Через Ообозначается отношение принадлежности, т.е. x О A означает, что элемент x принадлежит множеству A.

Если x не является элементом множества A, то это записывается x П A.

Два множества A и B считаются равными, если они состоят из одних и тех же элементов. Пишется A = B, если A и B равны, и A ╧  B в противном случае.

Через Н обозначается отношение включения множеств, т.е. A Н B означает, что каждый элемент множества A является элементом множества B. В этом случае A называется подмножествомB, а B - надмножествомA. Если A Н B и A ╧ B, то A называется собственным подмножеством B, и в этом случае пишем A М B.

Множество, не содержащее элементов, называется пустым и обозначается через Ж .

Объединением (ДИЗЪЮНКЦИЕЙ, СУММОЙ) множествA и B называется множество
 
 

Пересечением (КОНЪЮНКЦИЕЙ) множествA и B называется множество
 
 

Разностью множеств A и B называется множество
 
 

Симметрической разностью множеств A и B называется множество
 
 

Мощностью (или КАРДИНАЛЬНЫМ ЧИСЛОМ) множества называется количество элементов в нем.

Некоторое, общее для всех множеств данной мощности, надмножество, называется универсальным множеством или УНИВЕРСУМОМ и обозначается обычно как U. Разность  U \ A называется дополнением множества A и обозначается через -A.

Соответствие, бинарное отношение между двумя множествами A и B - произвольное подмножество Rдекартова произведенияA ╢B.
 
 

Если a ОA, b О B и (a, b) О R, то пишут также R(a, b) или aRb. Если R = Ж  - пустое множество, то соответствие называется пустым, а если R = A ╢ B, то соответствие называется полным.

Пусть R Н A ╢ B. Областью определения Dom R называется множество элементов a О A, для каждого из которых найдется хотя бы один элемент b О B такой, что aRb. Областью значений, или образом, Im R соответствия R называется множество элементов b О B, для каждого из которых найдется хотя бы один элемент a ОA такой, что aRb. Соответствие R называется всюду определенным, если Dom R = A, и сюръективным, если Im R = B.

Для каждого a ОA множество элементов bО B таких, что aRb, называется образомa относительно R и обозначается im _R a. Прообразом элемента b О B относительно R называется множество элементов a О  A таких, что aRb; прообраз обозначается coim _R b. Ясно, что

Im R = И  _{a О A} im _R a, Dom R =  И_{b О B} coim _R b.

Каждое соответствие однозначно определяет функцию a (r)  im _R a, которая отображает множество A в множество подмножеств B. Обратно, всякая функция f из множества A в множество подмножеств B определяет некоторое соответствие R(f ): aR(f )b тогда и только тогда, когда b Оf(a). Указанные сопоставления взаимно однозначны, что позволяет рассматривать соответствия как частично определенные многозначные функции.

Для конечных множеств A и B широко используются матричное и графовое представления соответствия. Пусть A = {a₁, a₂, ..., a_n}, B = {b₁, b₂, ..., b_m} и R Н A ╢B. Соответствию R сопоставляется матрица размера n ╢  m, строки которой помечены элементами из A, столбцы - элементами из B , а на пересечении строки a_i и столбца b_j стоит 1, если a_i R b_j , и 0 в противном случае. Например,
 
 

Тогда R сопоставляется матрица
 
 

Каждая матрица подобного вида однозначно определяет соответствие между A и B.

При графовом представлении элементы множеств A и B изображаются точками на плоскости. Обычно эти точки обозначаются теми же символами, что и соответствующие элементы. Точки a и b соединяются направленной дугой от a к b, если aRb. Например, соответствие R = {(a, x), (a, y), (b, y), (c, x)} изобразится следующим ориентированным графом:
 
 

Всякое соответствие R Н A ╢  B устанавливает т.н. соответствие Галуа между подмножествами множества A и подмножествами множества B. Именно, если X Н  A, то через G  (X) обозначается пересечение  З _{a О  X} im _R a; аналогично, для Y Н B вводится множество G^-1(Y)= З _{b О  Y} coim _R b.
 
 

Пусть X^* = G^-1 (G  (X)), Y^* = G (G ^-1(Y)),

тогда X Н X^*, Y Н  Y^*;

из X₁ Н X₂ следует G  (X₁) К  G  (X₂);

из Y₁ Н Y₂ следует G^-1(Y₁) К G ^-1(Y₂); X^** = X^*; Y^** = Y^*_.
 
 

Подмножество X Н A  (Y Н  B) называется замкнутым, если X = X^* (Y = Y^*)_. Соответствие Галуа устанавливает биективное соответствие между замкнутыми подмножествами в A и B.
 
 

Множество А: {Лена, Петя, Маша, Вася, Женя, Эллочка}

Множество B: {Горький, Достоевский, Лермонтов, Некрасов, Пушкин, Толстой, Фет}

Множество R (подмножество множества AxB): (Лена, Некрасов); (Лена, Фет); (Петя, Горький); (Петя, Пушкин); (Петя, Толстой); (Маша, Пушкин); (Маша, Лермонтов);(Вася, Пушкин); (Вася, Достоевский); (Женя, Фет); (Вася, Толстой); (Женя, Горький)

Помимо теоретико-множественных операций для соответствия вводится операция умножения. Если R Н A ╢  B, S Н B ╢  C, то произведение RS состоит из таких пар (a, c), для которых найдется элемент b О B такой, что (a, b) О R, (b, c) О S. Умножение соответствий ассоциативно и обладает следующими свойствами: если R₁ Н R₂, то R₁S Н R₂S; (RS)^#  = R^#S^#. Кроме того, специальные соответствия - отношения тождества, или диагонали, D _A, состоящие из всех пар (a, a), a ОA, играют роль единиц для умножения соответствий. Именно, если R Н A ╢  B, то D _AR = R = RD _B.

Для всякого соответствия R выполнено включение R Н  RR^#R. Если вместо включения выполняется равенство, то соответствие называется дифункциональным. Соответствие R Н A ╢ B называется функциональным, если RR^# К D_A и R^#R Н D _B. Функциональные соответствия - это в точности графики функций из A в B. Всякое соответствие R представимо в виде R = F^#G, где F, G - функциональные соответствия.

Пусть R Н A ╢  A. Cоответствие R называется: a) рефлексивным, если R К D_A; b) симметричным, если R = R^#; c) антисимметричным, если R З R^# НD _A; d) асимметричным, если R З R^#  = Ж ; e) транзитивным, если R² Н  R. Отношение R называется: a) предпорядком, если оно рефлексивно и транзитивно; b) порядком, если оно рефлексивно, транзитивно и антисимметрично; c) толерантностью, если оно рефлексивно и симметрично; d) эквивалентностью, если оно рефлексивно, симметрично и транзитивно.

Если R -  эквивалентность, то множество A распадается на непересекающиеся классы эквивалентных элементов, или на классы эквивалентности. Множество классов эквивалентности называется фактормножеством множества A по отношению R. Всякое дифункциональное соответствие R Н A ╢ B задает на своих областях определения и значений отношения эквивалентности, фактормножества по которым равномощны.

В определении соответствия можно считать A и B однотипными математическими структурами, для которых можно построить декартово произведение с той же структурой, и считать R подструктурой декартова произведения A ╢ B. Тогда получаются определения соответствия между группами, кольцами, векторными пространствами и т.п.