stringtranslate.com

Отношение (математика)

Иллюстрация примера отношения на множестве A = {a, b, c, d} . Стрелка от x к y указывает, что отношение выполняется между x и y . Отношение представлено набором {(a,a), (a,b), (a,d), (b,a), (b,d), ( c,b), (d,c), (d,d)} упорядоченных пар.

В математике отношение обозначает некоторый вид отношения между двумя объектами в наборе , который может иметь место или не иметь его. [1] Например, « меньше чем » — это отношение на множестве натуральных чисел ; оно имеет место, например, между значениями 1 и 3 (обозначается как 1 < 3 ), а также между 3 и 4 (обозначается как 3 < 4 ), но не между значениями 3 и 1 или между 4 и 4 , то есть 3 < 1 и 4 < 4 оба оцениваются как ложные. Другой пример: « является сестрой » — это отношение на множестве всех людей, оно имеет место, например, между Марией Кюри и Брониславой Длуской , и наоборот. Члены множества могут не находиться в отношении «в определенной степени» — они либо находятся в отношении, либо нет.

Формально отношение R над множеством X можно рассматривать как множество упорядоченных пар ( x , y ) элементов X . [2] Отношение R выполняется между x и y , если ( x , y ) является элементом R . Например, отношение « меньше чем » на натуральных числах — это бесконечное множество R меньше пар натуральных чисел, которое содержит как (1,3) , так и (3,4) , но ни (3,1) , ни (4,4) . Отношение « является нетривиальным делителем » на множестве однозначных натуральных чисел достаточно мало, чтобы его можно было показать здесь: R dv = { (2,4), (2,6), (2,8), (3,6), (3,9), (4,8) } ; например, 2 является нетривиальным делителем 8 , но не наоборот, следовательно, (2,8) ∈ R dv , но (8,2) ∉ R dv .

Если R — это отношение, которое выполняется для x и y, то часто пишут xRy . Для большинства общих отношений в математике вводятся специальные символы, такие как " < " для "меньше , чем" и " | " для "является нетривиальным делителем" и, наиболее популярный " = " для "равно" . Например, " 1 < 3 ", " 1 меньше, чем 3 " и " (1,3) ∈ R меньше " означают одно и то же; некоторые авторы также пишут " (1,3) ∈ (<) ".

Исследуются различные свойства отношений. Отношение R является рефлексивным, если xRx выполняется для всех x , и иррефлексивным, если xRx выполняется ни для одного x . Оно симметрично, если xRy всегда подразумевает yRx , и асимметрично, если xRy подразумевает, что yRx невозможно. Оно транзитивно, если xRy и yRz всегда подразумевают xRz . Например, « is less than » является иррефлексивным, асимметричным и транзитивным, но не рефлексивным и не симметричным. « is sister of » является транзитивным, но не рефлексивным (например, Пьер Кюри не является сестрой самого себя), не симметричным и не асимметричным; в то время как быть иррефлексивным или нет может быть вопросом определения (является ли каждая женщина сестрой самой себя?), « is dector of » является транзитивным, а « is parent of » — нет. Известны математические теоремы о комбинациях свойств отношений, таких как «транзитивное отношение является иррефлексивным тогда и только тогда, когда оно асимметрично».

Особое значение имеют отношения, которые удовлетворяют определенным комбинациям свойств. Частичный порядок — это отношение, которое является рефлексивным, антисимметричным и транзитивным, [3] отношение эквивалентности — это отношение, которое является рефлексивным, симметричным и транзитивным, [4] функция — это отношение , которое является право-уникальным и лево-тотальным (см. ниже). [5] [6]

Поскольку отношения являются множествами, ими можно манипулировать с помощью операций над множествами, включая объединение , пересечение и дополнение , что приводит к алгебре множеств . Кроме того, исчисление отношений включает операции взятия обратного и составления отношений . [7] [8] [9]

Вышеуказанное понятие отношения [a] было обобщено для признания отношений между членами двух различных множеств ( гетерогенное отношение , например, « лежит на » между множеством всех точек и множеством всех прямых в геометрии), отношений между тремя или более множествами ( финитное отношение , например, «человек x живет в городе y в момент времени z » ) и отношений между классами [b] (например, « является элементом » в классе всех множеств, см. Бинарное отношение § Множества и классы ).

Определение

Для заданного множества X отношение R над X — это множество упорядоченных пар элементов из X , формально: R ⊆ { ( x , y ) | x , y ∈ X } . [2] [10]

Утверждение ( x , y ) ∈ R читается как « x является R -связанным с y » и записывается в инфиксной нотации как xRy . [7] [8] Порядок элементов важен; если x ≠ y , то yRx может быть истинным или ложным независимо от xRy . Например, 3 делит 9 , но 9 не делит 3 .

Представление отношений

Отношение R на конечном множестве X можно представить как:

Транзитивное [c] отношение R на конечном множестве X может быть также представлено как

Например, на множестве всех делителей числа 12 определим отношение R div следующим образом:

x R div y, если x является делителем y и x ≠ y .

Формально, X = { 1, 2, 3, 4, 6, 12 } и R div = { (1,2), (1,3), (1,4), (1,6), (1,12), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12) } . Представление R div в виде булевой матрицы показано в средней таблице; представление в виде диаграммы Хассе и в виде ориентированного графа показано на левом рисунке.

Следующие значения эквивалентны:

В качестве другого примера определим отношение R el к R следующим образом:

x R e l y, если x 2 + xy + y 2 = 1 .

Представление R el в виде 2D-графика дает эллипс, см. правую картинку. Поскольку R не является конечным, то ни ориентированный граф, ни конечная булева матрица, ни диаграмма Хассе не могут быть использованы для изображения R el .

Свойства отношений

Некоторые важные свойства, которыми может обладать отношение R над множеством X :

Рефлексивный
для всех x ∈ X , xRx . Например, ≥ является рефлексивным отношением, а > — нет.
Иррефлексивный (или строгий )
для всех x ∈ X , а не xRx . Например, > является иррефлексивным отношением, а ≥ — нет.

Предыдущие 2 альтернативы не являются исчерпывающими; например, красное отношение y = x 2 , приведенное на диаграмме ниже, не является ни иррефлексивным, ни рефлексивным, поскольку оно содержит пару (0,0) , но не (2,2) соответственно.

Симметричный
для всех x , y ∈ X , если xRy , то yRx . Например, «является кровным родственником» является симметричным отношением, поскольку x является кровным родственником y тогда и только тогда, когда y является кровным родственником x .
Антисимметричный
для всех x , y ∈ X , если xRy и yRx , то x = y . Например, ≥ является антисимметричным отношением; так же как и > , но бессодержательно (условие в определении всегда ложно). [11]
Асимметричный
для всех x , y ∈ X , если xRy , то не yRx . Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. [12] Например, > является асимметричным отношением, но ≥ — нет.

Опять же, предыдущие 3 альтернативы далеки от исчерпывающего рассмотрения; в качестве примера для натуральных чисел можно привести отношение xRy , определяемое соотношением x > 2, которое не является ни симметричным (например, 5 R 1 , но не 1 R 5 ), ни антисимметричным (например, 6 R 4 , но также и 4 R 6 ), не говоря уже о том, что оно асимметрично.

Переходный
для всех x , y , z ∈ X , если xRy и yRz , то xRz . Транзитивное отношение является иррефлексивным тогда и только тогда, когда оно асимметрично. [13] Например, «является предком» является транзитивным отношением, тогда как «является родителем» — нет.
Подключен
для всех x , y ∈ X , если x ≠ y , то xRy или yRx . Например, в натуральных числах < связно, а " является делителем " - нет (например, ни 5 R 7 , ни 7 R 5 ).
Сильно связаны
для всех x , y ∈ X , xRy или yRx . Например, на натуральных числах ≤ сильно связно, а < — нет. Отношение сильно связно тогда и только тогда, когда оно связно и рефлексивно.
Примеры четырех типов отношений между действительными числами : один к одному (зеленый), один ко многим (синий), многие к одному (красный), многие ко многим (черный). Используется представление в виде двумерного графика.

Свойства уникальности:

Инъективный [d] (также называемый лево-уникальным [14] )
Для всех x , y , z ∈ X , если xRy и zRy , то x = z . Например, зеленые и синие отношения на диаграмме инъективны, но красное — нет (поскольку оно связывает и −1 , и 1 с 1 ), как и черное — нет (поскольку оно связывает и −1 , и 1 с 0 ).
Функциональный [15] [16] [17] [d] (также называемый право-уникальным , [14] право-определенным [18] или унивалентным [9] )
Для всех x , y , z ∈ X , если xRy и xRz , то y = z . Такое отношение называется частичной функцией . Например, красное и зеленое отношения на диаграмме являются функциональными, но синее — нет (поскольку оно связывает 1 как с −1, так и с 1 ), как и черное (поскольку оно связывает 0 как с −1, так и с 1).

Свойства совокупности:

Последовательный [d] (также называется тотал или лево-тотал )
Для всех x ∈ X существует некоторый y ∈ X такой, что xRy . Такое отношение называется многозначной функцией . Например, красные и зеленые отношения на диаграмме являются полными, но синее отношение не является таковым (поскольку оно не связывает −1 ни с каким действительным числом), как и черное отношение (поскольку оно не связывает 2 ни с каким действительным числом). В качестве другого примера, > является последовательным отношением над целыми числами. Но это не последовательное отношение над положительными целыми числами, потому что в положительных целых числах нет y такого, что 1 > y . [19] Однако < является последовательным отношением над положительными целыми числами, рациональными числами и действительными числами. Каждое рефлексивное отношение является последовательным: для данного x выберите y = x .
Сюръективный [d] (также называется право-тотальным [14] или on )
Для всех y ∈ Y существует x ∈ X такой, что xRy . Например, зеленые и синие отношения на диаграмме сюръективны, но красное — нет (поскольку оно не связывает ни одно действительное число с −1 ), как и черное (поскольку оно не связывает ни одно действительное число с 2 ).

Комбинации свойств

Отношения, которые удовлетворяют определенным комбинациям вышеуказанных свойств, особенно полезны и поэтому получили собственные названия.

Отношение эквивалентности
Отношение, которое является рефлексивным, симметричным и транзитивным. Это также отношение, которое является симметричным, транзитивным и последовательным, поскольку эти свойства подразумевают рефлексивность.

Заказы:

Частичный заказ
Отношение, которое является рефлексивным, антисимметричным и транзитивным.
Строгий частичный порядок
Отношение, которое является иррефлексивным, асимметричным и транзитивным.
Общий заказ
Отношение, которое является рефлексивным, антисимметричным, транзитивным и связанным. [20]
Строгий общий порядок
Отношение, которое является иррефлексивным, асимметричным, транзитивным и связанным.

Свойства уникальности:

Один на один [d]
Инъективное и функциональное. Например, зеленое отношение на диаграмме является отношением один к одному, а красное, синее и черное — нет.
Один-ко-многим [d]
Инъективное и не функциональное. Например, синее отношение на диаграмме — один ко многим, а красное, зеленое и черное — нет.
Многие-к-одному [d]
Функциональное и неинъективное. Например, красное отношение на диаграмме — отношение «многие к одному», а зеленое, синее и черное — нет.
Многие-ко-многим [d]
Не инъективно и не функционально. Например, черное отношение на диаграмме — многие-ко-многим, а красное, зеленое и синее — нет.

Свойства уникальности и тотальности:

Функция [d ]
Отношение, которое является функциональным и тотальным. Например, красные и зеленые отношения на диаграмме являются функциями, а синие и черные — нет.
Инъекция [d ]
Функция, которая является инъекцией. Например, зеленое отношение на диаграмме является инъекцией, а красное, синее и черное — нет.
Сюръекция [d ]
Функция, которая является сюръективной. Например, зеленое отношение на диаграмме является сюръекцией, а красное, синее и черное — нет.
Биекция [d ]
Функция, которая является инъективной и сюръективной. Например, зеленое отношение на диаграмме является биекцией, а красное, синее и черное — нет.

Операции над отношениями

Союз [э]
Если R и S являются отношениями над X, то R ∪ S = { ( x , y ) | xRy или xSy } является отношением объединения R и S . Элементом тождества этой операции является пустое отношение. Например, ≤ является объединением < и = , а ≥ является объединением > и = .
Пересечение [е]
Если R и S — отношения над X, то R ∩ S = { ( x , y ) | xRy и xSy } — отношение пересечения R и S . Элементом тождества этой операции является универсальное отношение. Например, «является младшей картой той же масти, что и» является пересечением «является младшей картой, чем» и «принадлежит к той же масти, что и».
Состав [э]
Если R и S являются отношениями над X, то S ∘ R = { ( x , z ) | существует y ∈ X, такой что xRy и ySz } (также обозначается как R ; S ) является относительным произведением R и S . Элементом тождества является отношение тождества. Порядок R и S в обозначении S ∘ R , используемом здесь, согласуется со стандартным порядком обозначений для композиции функций . Например, композиция "является матерью" ∘ "является родителем" дает "является прародителем по материнской линии", в то время как композиция "является родителем" ∘ "является матерью" дает "является бабушкой". Для первого случая, если x является родителем y , а y является матерью z , то x является прародителем по материнской линии z .
Обратный [e]
Если R — отношение над множествами X и Y, то R T = { ( y , x ) | xRy } — обратное отношение R над множествами Y и X. Например , = — обратное отношение к себе , как и ≠ , а < и > — обратные друг другу, как и ≤ и ≥ .
Дополнение [е]
Если R — отношение над X, то R = {( x , y ) | x , y ∈ X и не xRy } (также обозначается как R или ¬ R ) — дополнительное отношение R. Например, = и ≠ являются дополнениями друг друга, как и ⊆ и ⊈, ⊇ и ⊉ , и ∈ и ∉ , а для полных порядков также < и ≥ , и > и ≤ . Дополнение обратного отношения R T является обратным к дополнению:
Ограничение [е]
Если R — отношение над X , а S — подмножество X , то R | S = {( x , y ) | xRy и x , y ∈ S } — этоотношение ограничения R к S. Выражение R | S = { ( x , y ) | xRy и x ∈ S }являетсяотношение левого ограничения R к S ; выражение R | S = { ( x , y ) | xRy и y ∈ S }называетсяправое ограничение отношения Rк S. Если отношение являетсярефлексивным, иррефлексивным,симметричным,антисимметричным,асимметричным,транзитивным,полным,трихотомическим , частичнымпорядком,полным порядком,строгим слабым порядком,полным предпорядком(слабым порядком) илиотношением эквивалентности, то таковыми являются и его ограничения. Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, т. е. в общем случае не равно. Например, ограничение отношения « x является родителем y » на женщин дает отношение « x является матерью женщины y »; его транзитивное замыкание не связывает женщину с ее бабушкой по отцовской линии. С другой стороны, транзитивное замыкание «является родителем» является «является предком»; его ограничение на женщин связывает женщину с ее бабушкой по отцовской линии.

Отношение R между множествами X и Y называетсясодержится в отношении S над X и Y , записанном как R ⊆ S , если R является подмножеством S , то есть для всех x ∈ X и y ∈ Y , если xRy , то xSy . Если R содержится в S и S содержится в R , то R и S называютсяравными, записанными как R = S . Если R содержится в S , но S не содержится в R , то R называетсяменьше S , записывается какR ⊊ S. Например , нарациональных числахотношение>меньше≥и равно композиции> ∘ >.

Теоремы об отношениях

Примеры

Обобщения

Вышеуказанное понятие отношения было обобщено для допуска отношений между членами двух различных множеств. При заданных множествах X и Y неоднородное отношение R над X и Y является подмножеством { ( x , y ) | x ∈ X , y ∈ Y } . [2] [22] Когда X = Y , получается описанное выше понятие отношения; его часто называют однородным отношением (или эндоотношением ) [23] [24], чтобы отличить его от его обобщения. Вышеуказанные свойства и операции, отмеченные " [d] " и " [e] " соответственно, обобщаются на неоднородные отношения. Примером неоднородного отношения является "океан x граничит с континентом y ". Наиболее известными примерами являются функции [f] с различными областями и диапазонами, такие как sqrt : N → R + .

Смотрите также

Примечания

  1. ^ называется «однородным бинарным отношением (на множествах)», когда важно разграничение его обобщений
  2. ^ обобщение множеств
  3. ^ см. ниже
  4. ^ abcdefghijklm Эти свойства также распространяются на гетерогенные отношения.
  5. ^ abcdefg Эта операция также обобщается на неоднородные отношения.
  6. ^ то есть, право-уникальные и лево-полные гетерогенные отношения

Ссылки

  1. ^ Столл, Роберт Р. Теория множеств и логика . Сан-Франциско, Калифорния: Dover Publications. ISBN 978-0-486-63829-4.
  2. ^ abc Кодд 1970
  3. ↑ Халмош 1968, гл. 14
  4. ^ Халмош 1968, Гл. 7
  5. ^ "Определение отношения – Math Insight". mathinsight.org . Получено 11.12.2019 .
  6. ^ Халмош 1968, Гл. 8
  7. ^ ab Эрнст Шредер (1895) Алгебра и логика относительности, через Интернет-архив
  8. ^ ab CI Lewis (1918) Обзор символической логики, стр. 269–279, через интернет-архив
  9. ^ ab Schmidt 2010, Глава 5
  10. ^ Эндертон 1977, Гл. 3. стр. 40
  11. ^ Смит, Эгген и Сент-Андре 2006, с. 160
  12. ^ Нивергельт 2002, стр. 158
  13. ^ Flaška et al. 2007, стр. 1 Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
  14. ^ abc Kilp, Knauer & Mikhalev 2000, стр. 3. Те же четыре определения появляются в следующих работах: Pahl & Damrath 2001, стр. 506, Best 1996, стр. 19–21, Riemann 1999, стр. 21–22
  15. ^ Ван Гастерен 1990, стр. 45.
  16. ^ "Функциональное отношение - Энциклопедия математики". encyclopediaofmath.org . Получено 2024-06-13 .
  17. ^ "функциональное отношение в nLab". ncatlab.org . Получено 2024-06-13 .
  18. ↑ Мая 2007 г.
  19. ^ Яо и Вонг 1995
  20. ^ Розенштейн 1982, стр. 4
  21. ^ Шмидт и Штрёляйн 1993
  22. ^ Эндертон 1977, Гл. 3. стр. 40
  23. ^ Мюллер 2012, стр. 22
  24. ^ Pahl & Damrath 2001, стр. 496

Библиография