Финитарное соотношение

В математике финитное отношение над последовательностью множеств X ₁ , ..., X _n является подмножеством декартова произведения X ₁ × ... × X _n ; то есть это набор из n кортежей ( x ₁ , ..., x _n ) , каждый из которых представляет собой последовательность элементов x _i в соответствующем X _i . Обычно отношение описывает возможную связь между элементами n -кортежа. Например, отношение « x делится на y и z » состоит из набора троек, замена которых на x , y и z соответственно делает предложение истинным.

Неотрицательное целое число n , которое дает количество «мест» в отношении, называется арностью , адичностью или степенью отношения . Отношение с n «местами» по-разному называется n -арным отношением , n -адическим отношением или отношением степени n . Отношения с конечным числом мест называются финитными отношениями (или просто отношениями, если контекст ясен). Также возможно обобщить эту концепцию на бесконечные отношения с бесконечными последовательностями .

Определения

Когда два объекта, качества, класса или атрибута, рассматриваемые умом вместе, рассматриваются в некоторой связи, эта связь называется отношением.

— Огастес Де Морган

Определение

R — n -арное отношение на множествах X ₁ , ..., X _n задается подмножеством декартова произведения X ₁ × ... × X _n .

Поскольку определение основано на базовых множествах X ₁ , ..., X _n , R может быть более формально определен как ( n + 1 )-кортеж ( X ₁ , ..., X _n , G ) , где G , называемый графиком R × , является подмножеством декартова произведения X ₁ ... × X _n .

Как это часто бывает в математике, один и тот же символ используется для обозначения математического объекта и лежащего в его основе набора, поэтому утверждение ( x ₁ , ..., x _n ) ∈ R часто используется для обозначения ( x ₁ , . .., x _n ) ∈ G читается как « 1 _, ..., n _R » -родственны и обозначаются с использованием префиксной записи Rx x ₁ ⋯ x _n и с использованием постфиксной записи x x ₁ ⋯ x _n R . В случае, когда является бинарным отношением, эти утверждения также обозначаются с использованием инфиксной записи x R ₁ Rx ₂ .

Применяются следующие соображения:

• Множество X _i называется i й областью R - . В случае, когда R является бинарным отношением, X ₁ называется просто областью или множеством отправления R , а X ₂ также называется кодоменом или множеством назначения R также .
• Когда элементы X _i отношениями, X _i называется непростой областью R являются .
• Множество ∀ x _i ∈ X _i таких, что Rx ₁ ⋯ x _{i −1} x _i x _{i +1} ⋯ x _n хотя бы для одного ( x ₁ , ..., x _n ), называется i -й областью определения. или активный домен R. ​ В случае, когда R является бинарным отношением, его первая область определения также называется просто областью или активной областью определения R , а вторая область определения также называется кодоменом определения или активной коденом R определения .
• Когда i -я область определения R равна X _i , R называется тотальной на своей i- й области (или на X _i , если это не является двусмысленным). В случае, когда R является бинарным отношением, когда R тотально на X ₁ , его также называют левототальным или серийным , а когда R тотально на X ₂ , его также называют правототальным или сюръективным. .
• Когда ∀ x ∀ y ∈ X _i . ∀ z ∈ Икс _j . xR _ij z ∧ yR _ij z ⇒ x = y , где i ∈ I , j ∈ J , R _ij = π _ij R , и { I , J } { — разбиение 1 , ..., n } , R — Говорят, что он уникален на { X _i } _{i ∈ I} , а { X _i } _{i ∈ J} называется первичным ключом. Р. ​ ​В случае, когда R является бинарным отношением, когда R уникально на { X ₁ }, оно также называется единственным слева или инъективным , а когда R уникально на { X ₂ }, оно также называется однолистным. или право-единственное .
• Когда все Xi _{представляют собой} одно и то же множество X , проще называть R -арным отношением n над X , называемым однородным отношением . Без этого ограничения R называется гетерогенным отношением .
• Когда любой из X _i пуст, определяющее декартово произведение пусто, и единственным отношением над такой последовательностью областей является пустое отношение R = ∅ .

Пусть логическая область B представляет собой набор из двух элементов, скажем, B = {0, 1} , элементы которого можно интерпретировать как логические значения, обычно 0 = false и 1 = true . Характеристическая функция R χ , обозначаемая χ _R , является булевозначной функцией χ _R : X ₁ × ... × X _n → B , определяемой R ₍ ( x 1 _, ..., x _n ) ) = 1, если Rx ₁ ⋯ x _n и χ _R ( ( x ₁ , ..., x _n ) ) = 0 в противном случае.

В прикладной математике, информатике и статистике булевозначную функцию принято называть n -арным предикатом . С более абстрактной точки зрения формальной логики и теории моделей отношение R представляет собой логическую модель или реляционную структуру , которая служит одной из многих возможных интерпретаций некоторого n -арного символа-предиката.

Поскольку отношения возникают во многих научных дисциплинах, а также во многих разделах математики и логики , существуют значительные различия в терминологии. Помимо теоретико-множественного расширения реляционного понятия или термина, термин «отношение» также может использоваться для обозначения соответствующей логической сущности, либо логического понимания , которое представляет собой совокупность интенсионалов , либо абстрактных свойств, общих для всех элементов в отношение или, иначе говоря, символы, обозначающие эти элементы и интенсионалы. Кроме того, некоторые авторы последнего убеждения вводят термины с более конкретным значением (например, «реляционная структура» для теоретико-множественного расширения данной реляционной концепции).

Конкретные значения n

Нуллари

Нульарные (0-арные) отношения насчитывают только два члена: пустое нулевое отношение, которое никогда не выполняется, и универсальное нулевое отношение, которое выполняется всегда. Это связано с тем, что существует только один 0-кортеж, пустой кортеж (), и существует ровно два подмножества (одиночного) набора всех 0-кортежей. Иногда они полезны для построения базового случая индукционного аргумента.

Унарный

Унарные (1-арные) отношения можно рассматривать как совокупность членов (например, совокупность нобелевских лауреатов ), обладающих некоторым свойством (например, обладанием Нобелевской премией ).

Любая нулевая функция является унарным отношением.

Двоичный

Бинарные (2-арные) отношения — наиболее часто изучаемая форма финитных отношений. К однородным бинарным отношениям (где X ₁ = X ₂ ) относятся

• Равенство и неравенство , обозначаемые такими знаками, как = и < в таких утверждениях, как « 5 <12 », или
• Делимость , обозначается знаком | в таких утверждениях, как « 13 | 143 ».

Гетерогенные бинарные отношения включают в себя

• Членство во множестве , обозначается знаком ∈ в таких утверждениях, как « 1 ∈ N ».

тройной

Тернарные (3-арные) отношения включают, например, бинарные функции , которые связывают два входа и выход. Все три области однородного тернарного отношения представляют собой один и тот же набор.

Пример

Рассмотрим троичное отношение R " x думает, что y любит z " над множеством людей P = { Алиса, Боб, Чарльз, Дениз } , определяемое формулой:

R = { (Алиса, Боб, Дениз), (Чарльз, Алиса, Боб), (Чарльз, Чарльз, Алиса), (Дениз, Дениз, Дениз) } .

R можно эквивалентно представить следующей таблицей:

Отношение R " x думает, что y любит z "

х	и	С
Алиса	Боб	Дениз
Чарльз	Алиса	Боб
Чарльз	Чарльз	Алиса
Дениз	Дениз	Дениз

Здесь каждая строка представляет собой тройку R , то есть содержит утверждение вида « x думает, что y любит z ». Например, в первой строке говорится: «Алиса думает, что Бобу нравится Дениз». Все строки различны. Порядок строк незначителен, но порядок столбцов важен.

Приведенная выше таблица также является простым примером реляционной базы данных , области теории, основанной на реляционной алгебре и приложениях в управлении данными. Однако ученые-компьютерщики, логики и математики склонны иметь разные представления о том, что такое общее отношение и из чего оно состоит. Например, базы данных предназначены для работы с эмпирическими данными, которые по определению конечны, тогда как в математике также рассматриваются отношения с бесконечной арностью (т. е. бесконечные отношения).

История

Смотрите также: Алгебраическая логика § История

Логик Огастес Де Морган в работе, опубликованной около 1860 года, был первым, кто сформулировал понятие отношения в чем-то похожем на его нынешний смысл. Он также изложил первые формальные результаты в теории отношений (о Де Моргане и отношениях см. Merrill 1990).

Чарльз Пирс , Готтлоб Фреге , Георг Кантор , Ричард Дедекинд и другие выдвинули теорию отношений. Многие из их идей, особенно об отношениях, называемых порядками , были обобщены в «Принципах математики» (1903), где Бертран Рассел свободно использовал эти результаты.

В 1970 году Эдгар Кодд предложил реляционную модель баз данных , предвосхитив тем самым развитие систем управления базами данных .

См. также

• Структура заболеваемости
• Гиперграф
• Логика родственников
• Логическая матрица
• Частичный заказ
• Предикат (математическая логика)
• Проекция (теория множеств)
• Рефлексивное отношение
• Алгебра отношений
• Реляционная алгебра
• Реляционная модель
• Отношения (философия)

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

• Бурбаки, Н. (1994), Элементы истории математики , перевод Джона Мелдрама , Springer-Verlag
• Карнап, Рудольф (1958), Введение в символическую логику с приложениями , Dover Publications
• Кодд, Эдгар Франк (июнь 1970 г.). «Реляционная модель данных для больших общих банков данных» (PDF) . Коммуникации АКМ . 13 (6): 377–387. дои : 10.1145/362384.362685 . S2CID   207549016 . Проверено 29 апреля 2020 г.
• Кодд, Эдгар Франк (1990). Реляционная модель управления базами данных: версия 2 (PDF) . Бостон: Аддисон-Уэсли . ISBN  978-0201141924 .
• Де Морган, А. (1966) [1858], «О силлогизме, часть 3», в Хит, П. (редактор), « О силлогизме и других логических трудах» , Routledge, p. 119
• Халмос, PR (1960), Наивная теория множеств , Принстон, штат Нью-Джерси: Компания Д. Ван Ностранда
• Ловере, ФРВ ; Роузбру, Р. (2003), Наборы для математики , Кембриджский университет. Нажимать
• Льюис, CI (1918) Обзор символической логики , Глава 3: Приложения алгебры Буля – Шредера, через Интернет-архив
• Лукас, младший (1999), Концептуальные корни математики , Routledge
• Мэддукс, Р.Д. (2006), Алгебры отношений , Исследования по логике и основам математики, том. 150, Эльзевир Наука
• Меррилл, Дэн Д. (1990), Огастес Де Морган и логика отношений , Клювер
• Ниват, М. (1981). «Бесконечные отношения» . В Астезиано, Эджидио; Бём, Коррадо (ред.). Каап '81 . Конспекты лекций по информатике. Том. 112. Шпрингер Берлин Гейдельберг. стр. 46–75. дои : 10.1007/3-540-10828-9_54 . ISBN  978-3-540-38716-9 .
• Пирс, CS (1870), «Описание обозначения логики относительностей, возникающее в результате расширения концепций логического исчисления Буля», Мемуары Американской академии искусств и наук 9, 317–78, 1870. Переиздано. , Сборник статей CP 3.45–149, Хронологическое издание CE 2, 359–429.
• Пирс, CS (1984) Сочинения Чарльза С. Пирса: хронологическое издание, том 2, 1867–1871 гг . Проект Peirce Edition, ред. Издательство Университета Индианы.
• Рассел, Б. (1938) [1903], Принципы математики (2-е изд.), Cambridge Univ. Нажимать.
• Суппес, П. (1972) [1960], Аксиоматическая теория множеств , Dover Publications
• Тарский, А. (1983) [1956], Логика, семантика, метаматематика, статьи с 1923 по 1938 год , перевод Дж. Х. Вудгера (1-е изд.), Oxford University Press, 2-е издание, Дж. Коркоран, изд. Индианаполис, Индиана: Hackett Publishing.
• Улам, С.М. и Беднарек, А.Р. (1990), «О теории реляционных структур и схем для параллельных вычислений», стр. 477–508 в А.Р. Беднареке и Франсуазе Улам (ред.), Аналогии между аналогиями: математические отчеты SM Улам и его сотрудники из Лос-Аламоса , Калифорнийский университет Press, Беркли, Калифорния.
• Улам, С.М. (1990), А.Р. Беднарек; Франсуаза Улам (ред.), Аналогии между аналогиями: математические отчеты С.М. Улама и его коллег из Лос-Аламоса , University of California Press
• Фрэссе, Р. (2000) [1986], Теория отношений , Северная Голландия.