Приветствую всех читателей! В данной статье мы рассмотрим такой математический объект, как отношение, узнаем что это такое и какие отношения бывают. Для понимания материала данной статьи рекомендуется ознакомиться с первой и второй частями цикла по Наивной Теории Множеств.
СОДЕРЖАНИЕ СТАТЬИ:
- Что такое отношение?
- Вполне определённость
- Графическое отображение отношений
- Свойства отношений:
- - Рефлексивность и антирефлексивность
- - Симметричность и антисимметричность
- - Транзитивность и антитранзитивность
- - Связность
- «Несвязные» отношения
- Разнообразие отношений. N-арные отношения
- Заключение и упражнения
ЧТО ТАКОЕ ОТНОШЕНИЕ.
Итак,
БИНАРНОЕ ОТНОШЕНИЕ R на множестве A это некое подмножество A². Говорят, что отношение ВЕРНО или ВЫПОЛНЯЕТСЯ для элементов x, y ∈ A, если (x, y) ∈ R. В таком случае пишут xRy. Говорят, что отношение НЕВЕРНО или НЕ ВЫПОЛНЯЕТСЯ для элементов x, y ∈ A, если (x, y) ∉ R. В таком случае пишут xR/y (то есть, R перечёркивается).
Простейшие примеры отношений известны нам ещё с начальной школы: отношение «больше», обозначаемое «>», отношение «меньше», обозначаемое «>», и отношение «равно», обозначаемое «=». Однако, не стоит забывать о других часто используемых отношениях. Все основные приведены в списке:
- Равенство "="
- Неравенство "≠"
- Больше ">"
- Больше или равно; не меньше "⩾"
- Меньше "<"
- Меньше или равно; не больше "⩽"
- Тождественно равно "≡"
- Делит; является делителем "|"
ВПОЛНЕ ОПРЕДЕЛЁННОСТЬ.
В рамках Наивной Теории Множеств отношения задаются, как и любые другие множества, некоторым логическим правилом. Здесь важно отметить, что отношения должны быть «вполне определены». Для множеств эта черта также была необходима, однако не играла столь существенной роли в написанном цикле.
Множество называется ВПОЛНЕ ОПРЕДЕЛЁННЫМ, если можно точно определить, является ли какой-либо объект его элементом.
К примеру, множество целых чисел Z вполне определено, ведь мы точно можем сказать, является ли некий объект целым числом, или нет. Однако множество красивых цветов не вполне определено. Например, один человек может сказать, что красный - красивый цвет, а другой - что некрасивый. Множество всех красных вещей также не вполне определено, ведь непонятно, включать ли туда розовые объекты: они вроде красные, а вроде не совсем.
Можно отметить, что если множество задано полным перечислением своих элементов, то оно всегда вполне определено. Например, если M = {Блоб, Лигр, Рой}, то, хотя мы можем и не знать, что вообще такое эти Блоб, Лигр и Рой, мы всё равно знаем, что, например, Блоб входит в M, а мяч или число 2- не входят.
Отношение, как было сказано, также должно быть вполне определено. Для отношений «вполне определённость» можно адаптировать так:
Отношение R на множестве A ВПОЛНЕ ОПРЕДЕЛЕНО, если можно точно сказать, верно ли для любых двух x, y ∈ A, что (x, y) ∈ R, или нет.
Например, отношение «больше», заданное для целых чисел - вполне определённое, а потому с ним удобно работать. Но отношение «сильно больше» не вполне определено. Число 10 это сильно больше, чем 2? А число 0 сильно больше, чем -999? Из-за того, что отношение «сильно больше» не вполне определено, мы не можем с ним работать.
ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ ОТНОШЕНИЙ.
Как и многие другие вещи, связанные с множествами, отношения можно отобразить в виде некого графа. Например, пусть у нас есть множество A = {a, b, c, d} и отношение на нём R = {(a, a), (a, b), (b, c), (c, a), (a, c), (b, c)}. Для начала, изобразим элементы A, как вершины графа:
Теперь, если для x, y ∈ A верно xRy, то есть (x, y) ∈ R, начертим ориентированную дугу (то есть стрелку) между x и y:
Итак, мы получили графическое отображение отношения R на множестве A. Вот примеры ещё нескольких отношений:
СВОЙСТВА ОТНОШЕНИЙ.
Можно было заметить, что некоторые отношения имеют характерные черты, такие как «двусторонние» стрелки или «петли», замыкающиеся на самом объекте. Такие вещи свойственны отношениям с определёнными свойствами. Вообще говоря, математики придумали довольно много свойств отношений, но основных среди них семь.
РЕФЛЕКСИВНОСТЬ И АНТИРЕФЛЕКСИВНОСТЬ.
Отношение R на A называется РЕФЛЕКСИВНЫМ, если для любого x ∈ A верно xRx.
Например, можно заметить, что отношение «равно» рефлексивно, ведь какой бы x мы не взяли, будет верно x = x. Также отношение «равноостаточно по модулю» будет рефлексивным, ведь для любого целого x и, вообще говоря, любого положительного целого m будет верно x ≡ x (mod m). Однако, например, отношение «больше» не будет рефлексивным, ведь вообще ни для какого x не может быть верным x > x. Стоит также запомнить, что тут упоминается именно «для любого», а не «для какого-то», то есть отношение {(a, a), (b, a)} на {a, b} рефлексивным не будет, ведь существует элемент x ∈ A (в данном случае b), для которого неверно xRx (то есть, неверно bRb).
Графически рефлексивное отношение выделяется тем, что при каждом элементе множества имеется «петля», замыкающаяся на этом же элементе.
Отношение R на A называют АНТИРЕФЛЕКСИВНЫМ, если для любого x ∈ A неверно xRx
Например, заметим, что отношение «больше» антирефлексивно, ведь ни для какого x неверно x > x. Антирефлексивным будет и отношение «не равно», ведь ни для какого x неверно x ≠ x. Но вот отношение «равно» не будет антирефлексивным, ведь существует хотя бы один (по факту, все) элементы, для которых x = x.
Графически антирефлексивное отношение выделяется полным отсутствием «петлей», замыкающихся на самом элементе.
Важно отметить, что если отношение не антирефлексивно, то оно не становится автоматически рефлексивным, и наоборот. Это происходит из-за того, что «для всех» при отрицании превращается в «существует», например «для всех x верно xRx» превращается при отрицании в «существует x, для которого неверно xRx». То есть, отношение может не быть ни рефлексивным, ни антирефлексивным, как вышеупомянутое отношение R = {(a, a), (a, b), (b, c), (c, a), (a, c), (b, c)}, ведь неверно и что для любого x верно xRx, и что для любого x неверно xRx (контрпримеры - bR/b и aRa). Очевидно, правда, что отношение не может одновременно быть и рефлексивным, и антирефлексивным. То есть, не может быть только того, что отношение одновременно рефлексивно и антирефлексивно - остальное может быть.
Отношение R на A называют СИММЕТРИЧНЫМ, если для любых x, y ∈ A из xRy следует yRx.
Например, отношение «равно» будет симметричным, ведь для любых x и y, если x = y, то, очевидно, y = x. Симметричным будет и отношение «равноостаточно по модулю», ведь для любых x и y, если x ≡ y (mod m), то и y ≡ x (mod m). Однако отношение «больше» симметричным не будет, ведь есть такие x и y, что из x > y не будет следовать y > x. Не будет симметричным и отношение «больше или равно», ведь существуют такие x и y, что из x ≥ y не следует y ≥ x (например, 3 ≥ 2, но 2 < 3).
Симметричным будет и отношение параллельности прямых и плоскостей: если a || b, то и b || a. Также симметрично отношения подобия фигур: если, к примеру, треугольник ABC подобен треугольнику DEF, то верно, что и треугольник DEF подобен треугольнику ABC. По тем же принципам будут симметричны отношения перпендикулярности прямых и плоскостей.
Графически симметричность отношения выделяется тем, что если между двумя разным элементами имеется стрелка, то она обязательно «двусторонняя».
Важно отметить, что в определении симметричности в качестве следования используется именно логическая импликация. Это означает, что если xR/y и одновременно yR/x, то отношение R всё ещё может быть симметричным, ведь верно F → F. Логическая импликация ложна только в одном случае - когда T → F. То есть, если для некоторой пары элементов x и y верно xRy, но неверно yRx, то отношение не симметрично.
Отношение R на A называют АНТИСИММЕТРИЧНЫМ, если для если для любых x, y ∈ A из xRy следует yR/x.
Например, отношение «больше» антисимметрично, ведь для любого x и y, если верно x > y, то неверно y > x. Отношение «равно» не антисимметрично, ведь существуют некоторые x и y (на деле, все x = y), для которых верно x = y и y = x. По тем же причинам отношение «равноостаточно по модулю» не будет антисимметричным.
Графически антисимметричные отношения выделяются тем, что если между двумя элементами есть стрелка, то она обязательно односторонняя, то есть отсутствуют двусторонние стрелки.
Важно отметить, что помимо того, что и здесь используется логическая импликация, также
Отношение НЕ МОЖЕТ БЫТЬ одновременно РЕФЛЕКСИВНО и АНТИСИММЕТРИЧНО.
Почему? Потому что если для любого x верно xRx, то и для любых x = y верно xRy и yRx. Однако, при этом отношение может быть одновременно симметрично и антирефлексивно, например, отношение {(a, b), (b, a)} на {a, b}.
Также, как и в случае с рефлексивностью, отношение может одновременно не быть ни симметричным, ни антисимметричным.
ТРАНЗИТИВНОСТЬ И АНТИТРАНЗИТИВНОСТЬ.
Отношение R на A называют ТРАНЗИТИВНЫМ, если для любых x, y, z ∈ A из xRy и yRz следует xRz.
Например, отношение «равно» будет транзитивным, ведь для любых x, y и z, если x = y и y = z, то x = z. Отношение «больше» также будет транзитивным, ведь если x > y и y > z, то x > z. Однако отношение «не равно» транзитивным не будет, ведь не всегда, если x ≠ y и y ≠ z, то верно x ≠ z (например, 1 ≠ 2 и 2 ≠ 1, но 1 = 1).
Транзитивными будут также и упомянутые выше отношения параллельности прямых и плоскостей или отношение подобия фигур.
Графически транзитивность выделяется своеобразными «треугольниками». То есть, если можно пройти из a в b и потом из b в c, то можно и сразу пройти из a в c. Существует как бы «короткий путь» из a в c:
Важно отметить, что отношение не транзитивно тогда и только тогда, когда верно xRy и yRz, но при этом неверно xRz хотя бы для одной тройки элементов. Вновь, по причине свойств логической импликации.
Отношение R на A называют АНТИТРАНЗИТИВНЫМ, если для любых x, y, z ∈ A из xRy и yRz следует xR/z.
Пример антитранзитивного отношения в «чисто алгебраическом» виде вспомнить сложно, поэтому мы рассмотрим знакомую игру «Камень, ножницы, бумага». Итак, сокращая названия по первым буквам, мы имеем множество A = {к, н, б} и отношение «Бьёт» B на нём, где B = {(к, н), (н, б), (б, к)}. Заметим, в общем случае, для x, y и z здесь неверно, что из xBy и yBz следует xBz. Например, камень бьёт ножницы, и ножницы бьют бумагу, но камень не бьёт бумагу.
Все же «основные» «алгебраические» отношения, такие как «равно» или «больше» и подобные, не будут антитранзитивными.
Говоря о «геометрических» отношениях, отношение перпендикулярности прямых будет антитранзитивным, если если a ⊥ b и b ⊥ с, то a || c. Также будет антитранзитивно отношение перпендикулярности между двумя прямыми и одной плоскостью или между двумя плоскостями и одной прямой. Но вот отношение перпендикулярности между тремя плоскостями не антитранзитивно (предлагаю подумать над тем, почему это так, читателю).
Графически антитранзитивность выделяется тем, что ни для каких последовательно связанных a, b и c не существует короткого пути из a в c.
Важно отметить, что, подобно случаю с антисимметричностью:
Отношение НЕ МОЖЕТ одновременно быть РЕФЛЕКСИВНЫМ и АНТИТРАНЗИТИВНЫМ.
Почему? Если положить x = y = z, то для рефлексивного отношения R будет верно, что существует некоторые x, y и z такие, что из xRy и yRz следует xRz (по сути, из xRx и xRx следует xRx), а значит такое отношение не антитранзитивно.
Как уже стало ясно, транзитивность и антитранзитивность не являются антонимами, и отношение может одновременно не быть ни транзитивным, ни антитранзитивным.
СВЯЗНОСТЬ.
Вообще говоря, связность слегка отличается от ранее названных свойств, ведь даже в учебнике Ричарда Хаммака «Book of Proof», по памяти из которого я и пишу статью, такое свойство не было указано. Однако на википедии оно упоминается и используется для дальнейшей классификации отношений (которую мы рассмотрим в следующей статье). Итак,
Отношение R на A называют СВЯЗНЫМ, если для любых x, y ∈ A и x ≠ y верно xRy или yRx
Стоит отметить, что здесь как «или» используется логическая дизъюнкция, то есть, должно быть верно одно из трёх: xRy и yRx, ¬xRy и yRx, или xRy и ¬yRx.
Например, отношение «больше или равно» - связное, ведь x ≥ y или y ≥ x. Связно также и отношение «больше», ведь если x ≠ y, то либо x > y, либо y > x. Отношение «не равно» также связно, ведь из x ≠ y, к удивлению, следует x ≠ y. Однако отношение «равно», например, не связно, ведь если x = 3 и y = 5, то неверно как x = y, так и y = x.
Наиболее ясное понятие о связности даёт графическое отображение. Связное отношение отличается тем, что любые два элемента имеют между собой стрелку, то есть граф - иронично - связный. Например, вот отношение:
Каждые две различные вершины имеют между собой стрелку. Однако, стоит нам убрать факт того, что 4 > 3:
И теперь вершины 4 и 3 не соединены напрямую, а значит и отношение перестаёт быть связным.
«НЕСВЯЗНЫЕ» ОТНОШЕНИЯ.
Всё это время мы рассматривали, в основном, отношения, где имеется хотя бы одна связь между какими-то двумя различными элементами. Однако, теперь мы рассмотрим отношения, которые не имеют ни одной связи между различными элементами. Это не термин, но мы будет называть НЕСВЯЗНЫМИ отношения, где для любых двух x ≠ y неверно xRy.
В первую очередь, очевидно, что несвязные отношения будут не связными. Однако ещё следует рассмотреть свойства рефлексивности, симметричности и транзитивности. Все рассматриваемые отношения можно разделить на три группы:
- Для любого x неверно xRx;
- Для некоторых x верно xRx, но для некоторых неверно xRx;
- Для любого x верно xRx.
Можно увидеть, что первый и третий случаи соответствуют антирефлексивному и рефлексивному отношениям, соответственно. Второй же вбирает в себя все не рефлексивные и притом не антирефлексивные отношения.
Теперь рассмотрим несвязные отношения, в целом. Можно заметить, что если x, y и z попарно различны, то xR/y, yR/x, yR/z и xR/z, а значит условия симметричности и транзитивности принимают вид F → F, что всегда истинно. Если же x = y и y ≠ z (общность не теряется) или x = y = z, то, условие симметричности принимает вид либо F → F (если xR/x), либо T → T (если xRx), как и условие транзитивности, причём обе импликации F → F и T → T всегда истинны. То есть, условия симметричности и транзитивности у несвязных отношений всегда выполняются, а значит
Любое «несвязное» отношение СИММЕТРИЧНО, ТРАНЗИТИВНО и НЕ СВЯЗНО.
Однако несвязные отношения могут различаться свойством рефлексивности и набором элементов x таких, что xRx. (Читатель мог заметить, что я упомянул рефлексивное и антирефлекснивное несвязные отношения в единственном числе. Подумайте, почему это так, и каким множествам, или даже привычным отношениям, такие отношения соответствуют)
РАЗНООБРАЗИЕ ОТНОШЕНИЙ. N-АРНЫЕ ОТНОШЕНИЯ.
Поскольку отношение - то же самое множество, то в рамках Наивной Теории Множеств мы можем создавать свои произвольные отношения, например O = {(x, y) ∈ R² | y = 1000 + x}, означающее, что xOy тогда и только тогда, когда y больше x ровно на 1000. Или мы можем задать P = {(x, y) ∈ R² | |x - y| ≤ 3}, причём xPy тогда и только тогда, когда расстояние между точками x и y на числовой прямой равно 3 или меньше.
Стоит вспомнить, что мы в начале статьи определили именно бинарные отношения.
N-АРНЫМ ОТНОШЕНИЕМ R на множестве A называется некое подмножество A^n. Говорят, что отношение верно для a1, a2, a3, … , an ∈ A, если (a1, a2, a3, … , an) ∈ R. В таких случаях пишут R(a1, a2, a3, … , an).
N-арные отношения используются уже реже, но всё же используются. Например, тернарные отношения для трёх аргументов можно использовать для описания пифагоровых троек. То есть, пусть K = {(a, b, c) ∈ N³ | a² + b² = c²}, тогда, например, K(3, 4, 5), но не K(2, 3, 4). Или можно задать кватернарное отношение для четырёх аргументов. Пусть это будет L = {(a, b, c, d) ∈ N^4 | a² + b² + c² = d²}, то есть L(1, 2, 2, 3), но не L(1, 1, 1, 2). Заметим, что L выполняется тогда и только тогда, когда его аргументы - пифагорова четвёрка.
Выделяются среди N-арных отношений унарные отношения. Фактически, унарное отношение R на A - это просто подмножество A, каждый элемент которого обладает некоторым свойством, которое и определяет R. Например, мы можем задать R = {x ∈ Z | 2 | x}, и любой x ∈ R будет обладать свойством «делится на 2». Внимательный читатель скажет: «Но это ведь ничем не отличается от простого подмножества A». И да, унарные отношения принято вообще не рассматривать, поскольку они просто выражают подмножество A с определённым свойством.
ЗАКЛЮЧЕНИЕ И УПРАЖНЕНИЯ.
Что ж. Я хотел сделать небольшую статью про математические отношения, но получилось, как всегда. В следующей статье мы рассмотрим классификацию отношений на основе их свойств и почему «~» - это очень важно. А пока что, приведу несколько упражнений, в том числе некоторые из книги «Book of Proof» Ричарда Хаммака.
УПРАЖНЕНИЯ:
- Являются ли следующие множества и отношения вполне определёнными:
- - Множество {x | x ≠ x}?
- - Множество {x | 2x = x}?
- - Множество {x ∈ Z | 2x = x}?
- - Отношение R на множестве больших чисел A, если R равно множеству {(x, y) ∈ A² | x > y}?
- - Отношение R на множестве больших чисел A, если R равно множеству {(x, y) ∈ A² | x > y ^ y > x}?
- - Отношение R на множестве целых чисел Z, если R = {(x, x) ∈ Z²}? Какое знакомое отношение напоминает последнее отношение?
- Графически отобразите отношения:
- - Отношение «больше или равно» на множестве {1, 3, 4, 6, 8, 100}
- - Отношение «такого же цвета» на множестве {Красный мяч, Жёлтый шар, Синий куб, Красная машина, Белое облако, Синее небо, Жёлтый дом}
- - Отношение «поедает» на множестве обитателей дубового леса {Кабан, Лось, Волк, Гусеница, Сова, Лиса, Змея, Мышь, Дуб, Жёлудь, Кукушка, Белка, Куница, Горностай}
- Проверьте следующие отношения на рефлексивность, симметричность, транзитивность, соответствующие анти- свойства и связность:
- - Отношение «делит», где «x делит y» Обозначается x | y. Причём, считается, что 0 | 0.
- - Отношение «меньше» для действительных чисел.
- - Отношение «того же цвета» на множестве цветных объектов из прошлого упражнения.
- - Отношение перпендикулярности прямых на одной плоскости.
- - Отношение «может увидеть» для людей, находящихся в следующих комнатах, если они не будут переходить в другое место. Толстыми линиями обозначены стены, окружностями - сами люди с видом сверху.
- В статье я сказал, что перпендикулярность трёх плоскостей не антитранзитивна. Подумайте почему и приведите контрпример.
- Со звёздочкой. Пусть R - симметричное и транзитивное отношение на A, причём в A имеется такой элемент a, что для любого x из A верно aRx. Докажите, что R - рефлексивно.
- Заметим, что ∅ ⊆ A², а значит ∅ - вполне себе отношение на A. Проверьте ∅ на рефлексивность, симметричность, транзитивность, анти- свойства, связность. К какому «виду» отношений можно отнести ∅ из тех, что мы обсудили в статье? Единственное ли оно такое в этом виде?
- Заметим также, что A² ⊆ A². Проверьте A² на рефлексивность, симметричность, транзитивность, анти- свойства, связность.
- Можно было заметить, что бинарные отношения, по сути - функции, превращающие некоторую пару объектов в значение истинности, то есть бинарное отношение R на A можно задать, как функцию R: A² → {T, F}. В связи с этим отношения можно рассмотреть и логические функции, как отношения на {T, F}. Рассмотрите на рефлексивность, симметричность, транзитивность, анти- свойства и связность логические операторы, постройте графическое изображение:
- - Логическое И (обозначается a ^ b)
- - Логическое ИЛИ (обозначается a v b)
- - Логическую импликацию (обозначается a → b)
- - Логическую эквивалентность / тождественность (обозначается a ⇔ b)
- - Логическое исключающее ИЛИ (обозначается a ⊕ b)
- - Логическое НЕ И (обозначается a ↑ b)
- - Логическое НЕ ИЛИ (обозначается a ↓ b)
Благодарю за внимание!