Jump to content

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

(Перенаправлено из Отношения (математика) )
Иллюстрация примера отношения на множестве 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 и 3 (обозначается как 1 < 3 ), а также между 3 и 4 (обозначается как 3 < 4 ), но не между значениями 3 и 1 и не между 4 и 4 , т.е. , 3 < 1 и 4 < 4 оба оцениваются как ложные.Другой пример: « сестра » — это отношение на множестве всех людей, оно имеет место, например, между Марией Кюри и Брониславой Длуской , и наоборот.Члены множества не могут находиться в отношениях «в определенной степени» — они либо находятся в отношениях, либо нет.

Формально отношение R над множеством X можно рассматривать как набор пар ( x , y ) членов X. упорядоченных [1] Отношение R сохраняется между x и y, ( x , y ) является членом R. если Например, отношение « меньше чем » для натуральных чисел представляет собой бесконечное множество R less пар натуральных чисел, которое содержит как (1,3), так и (3,4) , но ни (3,1), ни (4). ,4) .Отношение « является нетривиальным делителем » : на множестве однозначных натуральных чисел достаточно мало, чтобы его можно было показать здесь R дв = { (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 less » означают одно и то же; некоторые авторы также пишут « (1,3) ∈ (<) ».

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

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

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

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

Определение

[ редактировать ]

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

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

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

[ редактировать ]
Представление отношения R el знак равно { ( Икс , y ) ∈ R × R | х 2 + ху + у 2 = 1 }, поскольку 2D-график дает эллипс .
и
х
1 2 3 4 6 12
1 ДаДаДаДаДаДа
2 НетДаНетДаДаДа
3 НетНетДаНетДаДа
4 НетНетНетДаНетДа
6 НетНетНетНетДаДа
12 НетНетНетНетНетДа
Представление R div
как булева матрица
Представление R div в виде диаграммы Хассе (черные линии) и ориентированного графа (все линии)

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

  • Ориентированный граф : каждый член X соответствует вершине; направленное ребро из x в y существует тогда и только тогда, когда x , y ) R. (
  • Булева матрица : члены X расположены в некоторой фиксированной последовательности x 1 , ..., x n ; матрица имеет размеры n × n , причем элемент в строке i , столбце j равен , если ( x i , x j ) ∈ R , и , в противном случае.
  • 2D-график : В качестве обобщения булевой матрицы отношение на –бесконечном– множестве может R действительных чисел быть представлено в виде двумерной геометрической фигуры: используя декартовы координаты , нарисуйте точку в ( x , y ) всякий раз, когда ( Икс , у ) ∈ р .

Переходный [с] отношение R на конечном множестве X можно также представить как

  • Диаграмма Хассе : каждый член X соответствует вершине; направленные ребра рисуются так, что направленный путь от x до y существует тогда и только тогда, когда ( x , y ) ∈ R . По сравнению с представлением в виде ориентированного графа, диаграмме Хассе требуется меньше ребер, что приводит к менее запутанному изображению. Поскольку отношение « существует направленный путь от x до y » транзитивно, в диаграммах Хассе могут быть представлены только транзитивные отношения. Обычно диаграмма строится так, что все ребра направлены вверх, а стрелки опущены.

Например, на множестве всех делителей числа 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 в виде булевой матрицы показано в средней таблице; представление как в виде диаграммы Хассе, так и в виде ориентированного графа показано на левом рисунке.

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

  • x R div y верно.
  • ( Икс , y ) ∈ р дел .
  • Путь от x до y существует в диаграмме Хассе, представляющей R div .
  • Ребро от x до y существует в ориентированном графе, представляющем R div .
  • В логической матрице, представляющей R div , элемент в строке x и столбце y равен " ".

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

x R el y, если x 2 + ху + у 2 = 1 .

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

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

[ редактировать ]

Некоторые важные свойства, которыми может обладать отношение 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 . Например, — антисимметричное отношение; то же самое и > , но бессмысленно (условие в определении всегда ложно). [10]
Асимметричный
для всех x , y X , если xRy , то не yRx . Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. [11] Например, > является асимметричным отношением, а – нет.

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

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

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

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

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

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

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

[ редактировать ]
Отношения по собственности
Рефлексивность
Пример
Частичный заказ Рефл Антисим Да Подмножество
Строгий частичный порядок Иррефл Асим Да Строгое подмножество
Общий заказ Рефл Антисим Да Да Алфавитный порядок
Строгий общий порядок Иррефл Асим Да Да Строгий алфавитный порядок
Отношение эквивалентности Рефл Сим Да Равенство

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

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

Заказы:

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

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

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

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

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

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

[ редактировать ]
Союз [и]
Если R и S — отношения над X, то R S знак равно { ( Икс , y ) | xRy или xSy } это объединения отношение R и S. — Элементом идентификации этой операции является пустое отношение. Например, — это объединение < и = , а — это объединение > и = .
Пересечение [и]
Если R и S — отношения над X , то R S знак равно { ( x , y ) | xRy и xSy } это пересечения R и S. отношение Элементом идентичности этой операции является универсальное отношение. Например, «является младшей картой той же масти, что» является пересечением «является младшей картой, чем» и «принадлежит той же масти, что и».
Состав [и]
Если R и S являются отношениями над X , то S R знак равно { ( Икс , z ) | существует y X такой, что xRy и ySz } также обозначаемый R ; S является относительным произведением R ( и S. ) Элементом идентичности является отношение идентичности. Порядок R и S в обозначениях S R , используемых здесь, соответствует стандартному порядку обозначений композиции функций . Например, композиция «является матерью» «является родителем» дает «является бабушкой и дедушкой по материнской линии», а композиция «является родителем» «является матерью» дает «является бабушкой». В первом случае, если x является родителем y , а y является матерью z , то x является прародителем z по материнской линии .
Конверсы [и]
Если R — отношение над множествами X и Y, то R Т знак равно { ( у , Икс ) | xRy } отношение R Y над X и . обратное Например, = является обратным самому себе, как и , а < и > являются обратными друг другу, как и и .
Дополнить [и]
Если R — отношение над X, то R знак равно { ( x , y ) | x , y X , а не xRy } также обозначаемый R или ¬R ) является дополнительным отношением R. ( Например, = и являются дополнением друг друга, как и и , и , а также и , а для полных порядков также < и , и > и . Дополнение обратного отношения R Т является обратным дополнению:
Ограничение [и]
Если R — отношение над X , а S — подмножество X , то R | S знак равно { ( Икс , y ) | xRy и x , y S } — это ограничения отношение R к S . Выражение Р | S знак равно { ( Икс , y ) | xRy и x S } — это левого ограничения отношение R к S ; выражение Р | С знак равно { ( Икс , у ) | 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. , Например, для рациональных чисел отношение > меньше, чем , и равно композиции > ∘ > .

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

[ редактировать ]
  • Отношение асимметрично тогда и только тогда, когда оно антисимметрично и иррефлексивно.
  • Транзитивное отношение иррефлексивно тогда и только тогда, когда оно асимметрично.
  • Отношение рефлексивно тогда и только тогда, когда его дополнение иррефлексивно.
  • Отношение является сильно связным тогда и только тогда, когда оно связно и рефлексивно.
  • Отношение равно обратному тогда и только тогда, когда оно симметрично.
  • Отношение связно тогда и только тогда, когда его дополнение антисимметрично.
  • Отношение является сильно связным тогда и только тогда, когда его дополнение асимметрично. [20]
  • Если отношение R содержится в отношении S , то
    • Если R рефлексивно, связно, сильно связно, тотально слева или тотально справа, то то же самое относится и к S .
    • Если S иррефлексивно, асимметрично, антисимметрично, уникально слева или уникально справа, то и R таким же является .
  • Отношение является рефлексивным, иррефлексивным, симметричным, асимметричным, антисимметричным, связным, сильно связным и транзитивным, если обратное отношение соответственно.

Обобщения

[ редактировать ]

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ называется «однородным бинарным отношением (на множествах)», когда важно разграничение его обобщений
  2. ^ обобщение множеств
  3. ^ см . ниже
  4. ^ Перейти обратно: а б с д и ж г час я дж к л м Эти свойства также распространяются на гетерогенные отношения.
  5. ^ Перейти обратно: а б с д и ж г Эта операция также обобщается на гетерогенные отношения.
  6. ^ то есть уникальные справа и гетерогенные отношения слева
  1. ^ Перейти обратно: а б с Кодд 1970 г.
  2. ^ Халмос 1968 , Глава 14
  3. ^ Халмош 1968 , Глава 7
  4. ^ «Определение отношения – Math Insight» . mathinsight.org . Проверено 11 декабря 2019 г.
  5. ^ Халмос 1968 , Глава 8
  6. ^ Перейти обратно: а б Эрнст Шредер (1895) Алгебра и логика родственников , через Интернет-архив
  7. ^ Перейти обратно: а б К.И. Льюис (1918) Обзор символической логики , стр. 269–279, через интернет-архив.
  8. ^ Перейти обратно: а б Шмидт 2010 , гл. 5
  9. ^ Эндертон 1977 , глава 3. с. 40
  10. ^ Смит, Эгген и Сент-Андре 2006 , с. 160
  11. ^ Нивергельт 2002 , с. 158
  12. ^ Флашка и др. 2007 , стр.1 Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
  13. ^ Перейти обратно: а б с Килп, Кнауэр и Михалев 2000 , с. 3. Те же четыре определения встречаются в следующих статьях: Pahl & Damrath 2001 , p. 506, Бест 1996 , стр. 19–21, Риман 1999 , стр. 21–22.
  14. ^ Ван Гастерен 1990, с. 45.
  15. ^ «Функциональная связь — Математическая энциклопедия» . энциклопедияofmath.org . Проверено 13 июня 2024 г.
  16. ^ «функциональная связь в nLab» . ncatlab.org . Проверено 13 июня 2024 г.
  17. ^ Мас 2007
  18. ^ Яо и Вонг 1995
  19. ^ Розенштейн 1982 , с. 4
  20. ^ Шмидт и Стрёлейн, 1993 г.
  21. ^ Эндертон 1977 , глава 3. с. 40
  22. ^ Мюллер 2012 , с. 22
  23. ^ Пал и Дамрат 2001 , с. 496

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 1926b9f4e393429a2f2cedad9adb52f5__1721396280
URL1:https://arc.ask3.ru/arc/aa/19/f5/1926b9f4e393429a2f2cedad9adb52f5.html
Заголовок, (Title) документа по адресу, URL1:
Relation (mathematics) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)