Отношения на множестве

Бинарным отношением на множестве Х называется всякое подмножество декартова произведения множества Х на себя

Рефлексивность: Отношение Р на множестве Х называется рефлексивным, если каждый элемент множества Х связан отношением Р сам с собой

хХ хРх

Граф: в каждой точка графа есть петля

Антирефлексивность: Отношение Р на множестве Х называется антирефлексивным, если ни один элемент множества Х не связан отношением Р сам с собой

хХ хРх

Граф: нет ни одной петли

Симметричность: Отношение Р на множестве Х симметрично, если из того, что элементы х и у  Х связаны отношением Р, всегда следует, что элементы у и х тоже связаны отношением Р.

х, уХ если хРу, то уРх

Граф: если есть стрелка от х к у, то должна быть и от у к х

Антисимметричность: Отношение Р на множестве Х называется антисимметричным, если для любых двух разных элементов множества Х если х связан отношением Р с у, то у не связан отношением Р с х.

х уХ если хРу то уРх

Граф: если есть стрелка от х к у, то стрелки от у к х нет.

Транзитивность: Отношение Р на множестве Х называют транзитивным, если для любых х, у, z  Х если х и у связаны отношением Р, y и z связаны отношением Р, то х и z также связаны отношением Р

 х, у, z  Х если хРу, yPz, то xPz

Граф: если есть стрелка от х к у, от у к z, то должна быть от x к z

Связанность: Отношение Р на множестве Х называется связанным, если для любых двух разных х, уХ либо х связан отношением Р с у, либо у связан отношением Р с х.

х уХ или хР,у или уРх

Граф: есть стрелка или от х к у, или от у к х.

Эквивалентность: Отношение Р на множестве Х называется отношением эквивалентности, если Р рефлексивно, транзитивно и симметрично на множестве Х

Р+С+Тр=Экв

Теорема Отношение порождает разбиение множества на классы тогда и только тогда, когда это отношение является отношением эквивалентности на данном множестве.

Порядок: Отношение Р на множестве Х называется отношением порядка, если Р антисимметрично и транзитивно на множестве Х

Ас+Тр=Порядок

Виды отношения порядка:

1. Порядок + Рефлексивность  Нестрогий порядок (, делимость)

2. Порядок + Антирефлексивность  Строгий порядок (, короче, старше)

3. Порядок + Связанность  Линейный порядок (выше,  на N)

4. Порядок без Связанности  Частичный порядок (делимость на N)