Упорядоченная пара

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

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

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

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

Общие [ править ]

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

${\ displaystyle (a_ {1}, b_ {1}) = (a_ {2}, b_ {2}) {\ text {тогда и только тогда, когда}} a_ {1} = a_ {2} {\ text {и }} b_ {1} = b_ {2}.}$

Множество всех упорядоченных пар, первый элемент которого в некотором множестве А и чей второй элемент находится в некотором множестве B называется декартово произведение из A и B , и записывается A × B . Бинарное отношение между множествами A и B является подмножеством из A × B .

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

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

Неформальные и формальные определения [ править ]

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

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

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

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

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

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

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

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

Определение Винера [ править ]

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

${\displaystyle \left(a,b\right):=\left\{\left\{\left\{a\right\},\,\emptyset \right\},\,\left\{\left\{b\right\}\right\}\right\}.}$

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

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

Определение Хаусдорфа [ править ]

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

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

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

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

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

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

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

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

Для некоторой упорядоченной пары p свойство « x является первой координатой p » можно сформулировать как:

${\displaystyle \forall Y\in p:x\in Y.}$

Свойство « x - вторая координата p » можно сформулировать как:

${\displaystyle (\exists Y\in p:x\in Y)\land (\forall Y_{1},Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2})).}$

В случае, когда левая и правая координаты идентичны, правый конъюнкт тривиально верен, поскольку Y ₁ ≠ Y ₂ никогда не бывает.${\displaystyle (\forall Y_{1},Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2}))}$

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

${\displaystyle \pi _{1}(p)=\bigcup \bigcap p.}$

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

${\displaystyle \pi _{2}(p)=\bigcup \left\{\left.x\in \bigcup p\,\right|\,\bigcup p\neq \bigcap p\rightarrow x\notin \bigcap p\right\}.}$

Варианты [ править ]

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

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

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

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

Докажите: ( a , b ) = ( c , d ) тогда и только тогда, когда a = c и b = d .

Куратовский :
Если . Если a = c и b = d , то {{ a }, { a, b }} = {{ c }, { c, d }}. Таким образом , ( а, б ) _К = ( в, г ) _К .

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

Если a = b :

( a, b ) _K = {{ a }, { a, b }} = {{ a }, { a, a }} = {{ a }}.

( c, d ) _K = {{ c }, { c, d }} = {{ a }}.

Таким образом, { c } = { c, d } = { a }, откуда a = c и a = d . По условию a = b . Следовательно, b = d .

Если a ≠ b , то ( a, b ) _K = ( c, d ) _K влечет {{ a }, { a, b }} = {{ c }, { c, d }}.

Предположим, что { c, d } = { a }. Тогда c = d = a , и поэтому {{ c }, { c, d }} = {{ a }, { a, a }} = {{ a }, { a }} = {{ a }}. Но тогда {{ a }, { a, b }} также будут равны {{ a }}, так что b = a, что противоречит a ≠ b .

Предположим, что { c } = { a, b }. Тогда a = b = c , что также противоречит a ≠ b .

Следовательно, { c } = { a }, так что c = a и { c, d } = { a, b }.

Если d = a истинно, то { c, d } = { a, a } = { a } ≠ { a, b }; противоречие. Таким образом, d = b , так что a = c и b = d .

Реверс :
( а, б ) _{обратные} = {{ Ь }, { а, Ь }} = {{ Ь }, { Ь, а }} = ( Ь, а ) _К .

Если . Если ( а, б ) _{обратный} = ( с, d ) _{обратный} , ( Ь, а ) _К = ( D, C ) _K . Следовательно, b = d и a = c .

Только если . Если a = c и b = d , то {{ b }, { a, b }} = {{ d }, { c, d }}. Таким образом, ( a, b ) _reverse = ( c, d ) _reverse .

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

Если : Если a = c и b = d , то { a , { a, b }} = { c , { c, d }}. Таким образом, ( a, b ) _short = ( c, d ) _short .

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

Если a = { c, d }, то по тем же рассуждениям, что и выше, { a, b } находится в правой части, поэтому { a, b } = c или { a, b } = { c, d }.

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

Если { a, b } = { c, d }, то a является элементом a , из a = { c, d } = { a, b }, что снова противоречит регулярности.

Следовательно , должно выполняться a = c .

Снова мы видим, что { a, b } = c или { a, b } = { c, d }.

Вариант { a, b } = c и a = c подразумевает, что c является элементом c , что противоречит регулярности.

Итак, у нас есть a = c и { a, b } = { c, d }, и поэтому: { b } = { a, b } \ { a } = { c, d } \ { c } = { d }, так что b = d .

Определение Куайна – Россера [ править ]

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

${\displaystyle \sigma (x):={\begin{cases}x,&{\text{if }}x\not \in \mathbb {N} ,\\x+1,&{\text{if }}x\in \mathbb {N} .\end{cases}}}$

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

${\displaystyle \varphi (x):=\sigma [x]=\{\sigma (\alpha )\mid \alpha \in x\}=(x\smallsetminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}.}$

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

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

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

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

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

Наконец, определим упорядоченную пару ( A , B ) как непересекающееся объединение

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

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

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

Например, пара кодируется, как указано .${\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,f\notin \mathbb {N} }$

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

Определение Кантора – Фреге [ править ]

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

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

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

Определение Морзе [ править ]

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

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

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

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

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

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

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

Теория категорий [ править ]

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

Ссылки [ править ]