Упорядоченная пара - Ordered pair

В математика, упорядоченная пара (а, б) - пара объектов. Порядок, в котором объекты появляются в паре, имеет значение: упорядоченная пара (а, б) отличается от упорядоченной пары (б, а) пока не а = б. (Напротив, неупорядоченная пара {а, б} равно неупорядоченной паре {б, а}.)

Заказанные пары также называются 2-кортежи, или же последовательности (иногда списки в контексте информатики) длины 2. Упорядоченные пары скаляры иногда называют двумерными векторов. (Технически это злоупотребление обозначениями, поскольку упорядоченная пара не обязательно должна быть элементом векторное пространство.) Записи упорядоченной пары могут быть другими упорядоченными парами, что позволяет рекурсивное определение упорядоченного п- пары (упорядоченные списки п объекты). Например, упорядоченная тройка (а,б,c) можно определить как (а, (б,c)), т.е.как одна пара вложена в другую.

В заказанной паре (а, б), предмет а называется первая запись, а объект б то вторая запись пары. Как вариант, объекты называют первым и вторым. составные части, первый и второй координаты, или влево и вправо прогнозы заказанной пары.

Декартовы произведения и бинарные отношения (и поэтому функции ) определены в терминах упорядоченных пар.

Общие

Позволять ${displaystyle (a_{1},b_{1})}$ и ${displaystyle (a_{2},b_{2})}$ быть заказанными парами. Тогда характеристика (или же определение) свойство заказанной пары:

${displaystyle (a_{1},b_{1})=(a_{2},b_{2}){ ext{ if and only if }}a_{1}=a_{2}{ ext{ and }}b_{1}=b_{2}.}$

В набор всех упорядоченных пар, первая запись которых находится в некотором наборе А и чья вторая запись находится в некотором наборе B называется Декартово произведение из А и B, и написано А × B. А бинарное отношение между сетами А и B это подмножество из А × B.

В (а, б) обозначение может использоваться для других целей, в первую очередь для обозначения открытые интервалы на действительная числовая линия. В таких ситуациях контекст обычно дает понять, какое значение имеется в виду.^[1][2] Для дополнительного пояснения упорядоченную пару можно обозначить обозначением варианта ${ extstyle langle a,bangle }$, но это обозначение имеет и другие применения.

Левая и правая проекция пары п обычно обозначается π₁(п) и π₂(п) или π_ℓ(п) и π_р(п) соответственно. в контекстах, где произвольно п-считываются пары, π^п
_я(т) - общее обозначение я-й компонент ппара т.

Неформальные и формальные определения

В некоторых вводных учебниках математики дается неформальное (или интуитивно понятное) определение упорядоченной пары, например

Для любых двух объектов а и б, заказанная пара (а, б) обозначение, определяющее два объекта а и б, в этой последовательности.^[3]

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

Это «определение» неудовлетворительно, потому что оно носит только описательный характер и основано на интуитивном понимании порядок. Однако, как иногда отмечают, использование этого описания не причинит вреда, и почти каждый думает об упорядоченных парах таким образом.^[4]

Более удовлетворительный подход состоит в том, чтобы заметить, что приведенное выше характерное свойство упорядоченных пар - это все, что требуется для понимания роли упорядоченных пар в математике. Следовательно, упорядоченную пару можно рассматривать как примитивное понятие, ассоциированная аксиома которого является характеристическим свойством. Такой подход использовали Н. Бурбаки группа в своем Теория множеств, опубликовано в 1954 году. Однако этот подход также имеет свои недостатки, поскольку необходимо аксиоматически допустить как существование упорядоченных пар, так и их характеристические свойства.^[3]

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

Определение упорядоченной пары с помощью теории множеств

Если согласиться, что теория множеств привлекательный основа математики, то все математические объекты должны быть определены как наборы какой-то. Следовательно, если упорядоченная пара не считается примитивной, она должна быть определена как набор.^[5] Ниже приводится несколько теоретико-множественных определений упорядоченной пары.

Определение Винера

Норберт Винер предложил первое теоретическое определение упорядоченной пары в 1914 году:^[6]

${displaystyle left(a,bight):=left{left{left{aight},,emptyset ight},,left{left{bight}ight}ight}.}$

Он заметил, что это определение позволило определить типы из Principia Mathematica ресурсы. Principia Mathematica взял типы, и, следовательно, связи всех арностей, как примитивный.

Винер использовал {{б}} вместо {б}, чтобы сделать определение совместимым с теория типов где все элементы в классе должны быть одного «типа». С б вложенный в дополнительный набор, его тип равен ${displaystyle {{a},emptyset }}$с.

Определение Хаусдорфа

Примерно в то же время, что и Винер (1914), Феликс Хаусдорф предложил свое определение:

${displaystyle (a,b):=left{{a,1},{b,2}ight}}$

«где 1 и 2 - два разных объекта, отличных от a и b».^[7]

Определение Куратовского

В 1921 г. Казимеж Куратовски предложил ныне принятое определение^[8][9]заказанной пары (а, б):

${displaystyle (a, b)_{K};:= {{a}, {a, b}}.}$

Обратите внимание, что это определение используется, даже если первая и вторая координаты идентичны:

${displaystyle (x, x)_{K}={{x},{x, x}}={{x}, {x}}={{x}}}$

Учитывая некоторую упорядоченную пару п, недвижимость "Икс первая координата п"можно сформулировать как:

${displaystyle forall Yin p:xin Y.}$

Недвижимость "Икс вторая координата п"можно сформулировать как:

${displaystyle (exists Yin p:xin Y)land (forall Y_{1},Y_{2}in p:Y_{1}eq Y_{2}ightarrow (xotin Y_{1}lor xotin Y_{2})).}$

Если левая и правая координаты совпадают, правая соединяться ${displaystyle (forall Y_{1},Y_{2}in p:Y_{1}eq Y_{2}ightarrow (xotin Y_{1}lor xotin Y_{2}))}$ тривиально верно, поскольку Y₁ ≠ Y₂ никогда не бывает.

Вот как мы можем извлечь первую координату пары (используя обозначение для произвольное пересечение и произвольный союз ):

${displaystyle pi _{1}(p)=igcup igcap p.}$

Вот как можно извлечь вторую координату:

${displaystyle pi _{2}(p)=igcup left{left.xin igcup p,ight|,igcup peq igcap pightarrow xotin igcap pight}.}$

Варианты

Приведенное выше определение Куратовского упорядоченной пары «адекватно» в том смысле, что оно удовлетворяет характеристическому свойству, которому должна удовлетворять упорядоченная пара, а именно тому, что ${displaystyle (a,b)=(x,y)leftrightarrow (a=x)land (b=y)}$. В частности, он адекватно выражает «порядок» в том смысле, что ${displaystyle (a,b)=(b,a)}$ ложно, если ${displaystyle b=a}$. Существуют и другие определения аналогичной или меньшей сложности, которые в равной степени адекватны:

• ${displaystyle (a,b)_{ ext{reverse}}:={{b},{a,b}};}$
• ${displaystyle (a,b)_{ ext{short}}:={a,{a,b}};}$
• ${displaystyle (a,b)_{ ext{01}}:={{0,a},{1,b}}.}$^[10]

В обеспечить регресс Определение - всего лишь тривиальный вариант определения Куратовского и как таковое не представляет самостоятельного интереса. Определение короткая называется так, потому что для этого требуется две, а не три пары подтяжки. Доказывая, что короткая удовлетворяет характеристическому свойству, требует Теория множеств Цермело – Френкеля аксиома регулярности.^[11] Более того, если использовать Теоретико-множественная конструкция фон Неймана натуральных чисел, то 2 определяется как набор {0, 1} = {0, {0}}, который неотличим от пары (0, 0)_{короткая}. Еще один недостаток короткая пара - это факт, что даже если а и б однотипны, элементы короткая пара нет. (Однако если а = б затем короткая версия продолжает иметь мощность 2, чего можно ожидать от любой «пары», включая любую «упорядоченную пару». Также обратите внимание, что короткая версия используется в Теория множеств Тарского – Гротендика, на котором Система Мицар основан.)

Доказательство того, что определения удовлетворяют характеристическому свойству

Доказывать: (а, б) = (c, d) если и только если а = c и б = d.

Куратовски:
Если. Если а = с и б = г, тогда {{а}, {а, б}} = {{c}, {CD}}. Таким образом (а, б)_K = (CD)_K.

Только если. Два случая: а = б, и а ≠ б.

Если а = б:

(а, б)_K = {{а}, {а, б}} = {{а}, {а, а}} = {{а}}.

(CD)_K = {{c}, {CD}} = {{а}}.

Таким образом {c} = {CD} = {а}, что означает а = c и а = d. По предположению, а = б. Следовательно б = d.

Если а ≠ б, тогда (а, б)_K = (CD)_K подразумевает {{а}, {а, б}} = {{c}, {CD}}.

Предполагать {CD} = {а}. потом с = d = а, и так {{c}, {CD}} = {{а}, {а, а}} = {{а}, {а}} = {{а}}. Но потом {{а}, {а, б}} также будет равно {{а}}, так что б = а что противоречит а ≠ б.

Предполагать {c} = {а, б}. потом а = б = с, что также противоречит а ≠ б.

Следовательно {c} = {а}, так что с = а и {CD} = {а, б}.

Если d = а были правдой, то {CD} = {а, а} = {а} ≠ {а, б}; противоречие. Таким образом d = b это так, так что а = с и б = г.

Обеспечить регресс:
(а, б)_{обеспечить регресс} = {{б}, {а, б}} = {{б}, {б, а}} = (б, а)_K.

Если. Если (а, б)_{обеспечить регресс} = (CD)_{обеспечить регресс},(б, а)_K = (Округ Колумбия)_K. Следовательно, б = г и а = с.

Только если. Если а = с и б = г, тогда {{б}, {а, б}} = {{d}, {CD}}.Таким образом (а, б)_{обеспечить регресс} = (CD)_{обеспечить регресс}.

Короткий:^[12]

Если: Если а = с и б = г, тогда {а, {а, б}} = {c, {CD}}. Таким образом (а, б)_{короткая} = (CD)_{короткая}.

Только если: Предполагать {а, {а, б}} = {c, {CD}}.Потом а находится в левой части и, следовательно, в правой части. Поскольку равные множества имеют равные элементы, один из а = с или же а = {CD} должно быть так.

Если а = {CD}, то по аналогичным рассуждениям, указанным выше, {а, б} находится в правой части, поэтому {а, б} = c или же {а, б} = {CD}.

Если {а, б} = c тогда c в {CD} = а и а в c, и эта комбинация противоречит аксиоме регулярности, так как {а, в} не имеет минимального элемента в отношении "element of."

Если {а, б} = {CD}, тогда а является элементом а, из а = {CD} = {а, б}, что снова противоречит закономерности.

Следовательно а = с должен держать.

Снова мы видим, что {а, б} = c или же {а, б} = {CD}.

Опция {а, б} = c и а = с подразумевает, что c является элементом c, что противоречит закономерности.

Итак, у нас есть а = с и {а, б} = {CD}, и так: {б} = {а, б} {а} = {CD} {c} = {d}, так б = d.

Определение Куайна – Россера

Россер (1953)^[13] использовал определение упорядоченной пары из-за Куайн что требует предварительного определения натуральные числа. Позволять ${displaystyle mathbb {N} }$ быть набором натуральных чисел и определить сначала

${displaystyle sigma (x):={egin{cases}x,&{ ext{if }}xot in mathbb {N} ,x+1,&{ ext{if }}xin mathbb {N} .end{cases}}}$

Функция ${displaystyle sigma }$ увеличивает свой аргумент, если это натуральное число, и оставляет его как есть в противном случае; число 0 не является функциональным значением ${displaystyle sigma }$.В качестве ${displaystyle xsmallsetminus mathbb {N} }$ это набор элементов ${displaystyle x}$ не в ${displaystyle mathbb {N} }$ продолжать с

${displaystyle varphi (x):=sigma [x]={sigma (alpha )mid alpha in x}=(xsmallsetminus mathbb {N} )cup {n+1:nin (xcap mathbb {N} )}.}$

Это установить изображение набора ${displaystyle x}$ под ${displaystyle sigma }$, иногда обозначается к ${displaystyle sigma ''x}$ также. Применение функции ${displaystyle varphi }$ к набору Икс просто увеличивает каждое натуральное число в нем. Особенно, ${displaystyle varphi (x)}$ никогда не содержит числа 0, так что для любых наборов Икс и у,

${displaystyle varphi (x)eq {0}cup varphi (y).}$

Далее, определим

${displaystyle psi (x):=sigma [x]cup {0}=varphi (x)cup {0}.}$

Этим, ${displaystyle psi (x)}$ всегда содержит число 0.

Наконец, определите упорядоченную пару (А, B) как несвязное объединение

${displaystyle (A,B):=varphi [A]cup psi [B]={varphi (a):ain A}cup {varphi (b)cup {0}:bin B}.}$

(который ${displaystyle varphi ''Acup psi ''B}$ в альтернативных обозначениях).

Извлечение всех элементов пары, не содержащих 0, и отмена ${displaystyle varphi }$ дает А. Так же, B можно восстановить из элементов пары, содержащих 0.^[14]

Например, пара ${displaystyle ({{a,0},{b,c,1}},{{d,2},{e,f,3}})}$ кодируется как ${displaystyle {{a,1},{b,c,2},{d,3,0},{e,f,4,0}}}$ при условии ${displaystyle a,b,c,d,e,fotin mathbb {N} }$.

В теория типов и в ее продуктах, таких как аксиоматическая теория множеств NF пара Куайна – Россера имеет тот же тип, что и ее проекции, и поэтому называется упорядоченной парой «уровня типа». Следовательно, это определение имеет то преимущество, что позволяет функция, определенный как набор упорядоченных пар, чтобы иметь тип только на 1 выше, чем тип его аргументов. Это определение работает, только если набор натуральных чисел бесконечен. Так обстоит дело в NF, но не в теория типов или в НФУ. Дж. Баркли Россер показали, что существование такой упорядоченной пары на уровне типов (или даже упорядоченной пары «повышение типов на 1») влечет аксиома бесконечности. Подробное обсуждение упорядоченной пары в контексте теории множеств Квиниана см. В Holmes (1998).^[15]

Определение Кантора – Фреге

В начале развития теории множеств, до того, как были обнаружены парадоксы, Кантор вслед за Фреге определил упорядоченную пару из двух множеств как класс всех отношений, которые выполняются между этими множествами, предполагая, что понятие отношения является примитивным:^[16]

${displaystyle (x,y)={R:xRy}.}$

Это определение недопустимо в большинстве современных формализованных теорий множеств и методологически аналогично определению кардинал множества как класс всех множеств, равнодействующих данному множеству.^[17]

Определение Морзе

Теория множеств Морса – Келли бесплатно использует правильные классы.^[18] Морс определила упорядоченную пару так, чтобы ее проекции могли быть как собственными классами, так и наборами. (Определение Куратовского не допускает этого.) Сначала он определил упорядоченные пары, проекции которых являются множествами в манере Куратовского. Затем он переопределенный пара

${displaystyle (x,y)=({0} imes s(x))cup ({1} imes s(y))}$

где компонентные декартовы произведения - это пары множеств Куратовского, а

${displaystyle s(x)={emptyset }cup {{t}mid tin x}}$

Это отображает возможные пары, проекции которых являются собственными классами. Приведенное выше определение Куайна – Россера также допускает правильные классы как прогнозы. Точно так же тройка определяется как тройка следующим образом:

${displaystyle (x,y,z)=({0} imes s(x))cup ({1} imes s(y))cup ({2} imes s(z))}$

Использование одноэлементного набора ${displaystyle s(x)}$ который имеет вставленный пустой набор, позволяет кортежам иметь свойство уникальности, которое, если а является п-набор и b м-часть и а = б тогда п = м. Упорядоченные тройки, которые определены как упорядоченные пары, не обладают этим свойством по отношению к упорядоченным парам.

Теория категорий

Коммутативная диаграмма для установленного продукта Икс₁×Икс₂.

Теоретико-категориальный товар А × B в категория наборов представляет собой набор упорядоченных пар, причем первый элемент происходит из А и второй исходящий от B. В этом контексте указанное выше характерное свойство является следствием универсальная собственность продукта и того факта, что элементы набора Икс можно отождествить с морфизмами от 1 (одноэлементное множество) до Икс. Хотя разные объекты могут обладать универсальным свойством, все они естественно изоморфный.

Рекомендации

1. Лэй, Стивен Р. (2005), Анализ / Введение в доказательство (4-е изд.), Пирсон / Прентис Холл, стр. 50, ISBN  978-0-13-148101-5
2. Девлин, Кейт (2004), Множества, функции и логика / Введение в абстрактную математику (3-е изд.), Chapman & Hall / CRC, стр. 79, ISBN  978-1-58488-449-1
3. Вольф, Роберт С. (1998), Доказательство, логика и гипотеза / The Mathematician's Toolbox, W.H. Freeman and Co., p. 164, г. ISBN  978-0-7167-3050-7
4. Флетчер, Питер; Пэтти, К. Уэйн (1988), Основы высшей математики, PWS-Kent, стр. 80, ISBN  0-87150-164-3
5. Куайн утверждал, что теоретико-множественные реализации концепции упорядоченной пары представляют собой парадигму для разъяснения философских идей (см. "Слово и объект ", раздел 53). Общее понятие таких определений или реализаций обсуждается в Томасе Форстере" Рассуждения о теоретических объектах ".
6. Статья Винера «Упрощение логики отношений» перепечатана вместе с ценным комментарием на страницах 224ff в van Heijenoort, Jean (1967), От Фреге до Гёделя: Справочник по математической логике, 1979–1931 гг., Издательство Гарвардского университета, Кембридж, Массачусетс, ISBN  0-674-32449-8 (пбк.). Ван Хейеноорт формулирует это упрощение следующим образом: «Дав определение упорядоченной пары из двух элементов в терминах операций классов, примечание сводило теорию отношений к теории классов».
7. см. введение в статью Винера в van Heijenoort 1967: 224
8. см. введение к статье Винера в van Heijenoort 1967: 224. ван Хейеноорт замечает, что результирующее множество, представляющее упорядоченную пару, «имеет тип на 2 выше, чем элементы (когда они одного типа)»; он предлагает ссылки, которые показывают, как при определенных обстоятельствах тип может быть уменьшен до 1 или 0.
9. Куратовски, Казимир (1921). "Sur la notion de l'ordre dans la Théorie des Ensembles" (PDF). Fundamenta Mathematicae. 2 (1): 161–171. Архивировано из оригинал (PDF) на 2019-04-29. Получено 2013-05-29.
10. Это отличается от определения Хаусдорфа тем, что не требует, чтобы два элемента 0 и 1 были отличны от а и б.
11. Турлакис, Джордж (2003) Лекции по логике и теории множеств. Vol. 2: Теория множеств. Cambridge Univ. Нажмите. Предложение III.10.1.
12. Для официального Метамат доказательство адекватности короткая, видеть здесь (opthreg). Также см. Tourlakis (2003), предложение III.10.1.
13. Дж. Баркли Россер, 1953. Логика для математиков. Макгроу – Хилл.
14. Холмс, М. Рэндалл: По заказанным парам, on: Boise State, 29 марта 2009 г. Автор использует ${displaystyle sigma _{1}}$ за ${displaystyle varphi }$ и ${displaystyle sigma _{2}}$ за ${displaystyle psi }$.
15. Холмс, М. Рэндалл (1998) Элементарная теория множеств с универсальным множеством В архиве 2011-04-11 на Wayback Machine. Academia-Bruylant. Издатель любезно согласился разрешить распространение этой монографии через Интернет.
16. Фреге, Готтлоб (1893). Grundgesetze der Arithmetik (PDF). Йена: Verlag Hermann Pohle. §144
17. Канамори, Акихиро (2007). Установить теорию от Кантора до Коэна (PDF). Elsevier BV. п. 22, сноска 59
18. Морс, Энтони П. (1965). Теория множеств. Академическая пресса.