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

Аналитическая геометрия связывает каждой точке евклидовой плоскости упорядоченную пару. Красный эллипс связан с набором всех пар ( x , y ) таких, что Икс ² / 4 + и ² = 1 .

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

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

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

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

Общие сведения

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

$$(a_{1},b_{1})=(a_{2},b_{2}){\text{ if and only if }}a_{1}=a_{2}{\text{ and }}b_{1}=b_{2}.$$

Набор называется первая запись которых находится в некотором множестве A, а вторая запись находится в некотором множестве , декартовым произведением A A и B и пишется как всех упорядоченных пар , × B. B Бинарное отношение множествами A и B является подмножеством A . × B между

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Куратовского

В 1921 году Казимеж Куратовский предложил ныне принятое определение. упорядоченной пары ( a , b ):

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

Когда первая и вторая координаты идентичны, определение получается:

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

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

$$\forall Y\in p:x\in Y.$$

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

$$(\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})).$$

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

Если $p=(x,y)=\{\{x\},\{x,y\}\}$ затем:

$\bigcap p=\bigcap {\bigg \{}\{x\},\{x,y\}{\bigg \}}=\{x\}\cap \{x,y\}=\{x\},$

$\bigcup p=\bigcup {\bigg \{}\{x\},\{x,y\}{\bigg \}}=\{x\}\cup \{x,y\}=\{x,y\}.$

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

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

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

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

(если $x\neq y$, то набор {y} можно получить проще: $\{y\}=\{\left.a\in \{x,y\}\,\right|\,a\notin \{x\}\}$, но предыдущая формула учитывает и случай, когда x=y)

Варианты

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

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

Обратное определение представляет собой всего лишь тривиальный вариант определения Куратовского и как таковое не представляет самостоятельного интереса. Определение «короткое» названо так потому, что оно требует двух, а не трех пар фигурных скобок . Для доказательства того, что short удовлетворяет характеристическому свойству, требуется теории множеств Цермело – Френкеля аксиома регулярности . Более того, если использовать теоретико-множественную конструкцию натуральных чисел фон Неймана , то 2 определяется как набор {0, 1} = {0, {0}}, который неотличим от пары (0, 0) _short . Еще одним недостатком короткой пары является тот факт, что, даже если 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 ) _K знак равно ( c , d ) _K .

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

Если а = б :

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

{{ c }, { c , d }} знак равно ( c , d ) _K знак равно ( а , б ) _K знак равно {{ а }}.

Таким образом, { c } = { c , d } = { a }, что подразумевает a = c и a = d . По условию a = 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 .

Обеспечить регресс :
( а, б ) _{обратный знак равно} {{ б }, { а, б }} знак равно {{ б }, { б, а }} = ( б, а ) _K .

Если . Если ( a, b ) _реверс = ( c, d ) _реверс , ( б, а ) _K знак равно ( d, c ) _K . Следовательно, b = d и a = c .

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

Короткий:

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

Только если : Предположим, { 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 } не имеет минимального элемента при отношении «элемент ."

Если { 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 }, так что б = d .

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

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

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

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

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

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

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

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

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

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

Наконец, определите упорядоченную пару ( A , B ) как непересекающийся союз

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

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

Извлечение всех элементов пары, не содержащих 0, и отмена $\varphi$дает А. ​ Аналогично, B можно восстановить из элементов пары, которые содержат 0.

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

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

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

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

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

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

Определение Морса

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

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

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

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

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

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

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

Аксиоматическое определение

Упорядоченные пары также можно аксиоматически ввести в теорию множеств Цермело – Френкеля (ZF), просто добавив к ZF новый функциональный символ. $f$ арности 2 (обычно ее опускают) и определяющую аксиому для $f$:

$$f(a_{1},b_{1})=f(a_{2},b_{2}){\text{ if and only if }}a_{1}=a_{2}{\text{ and }}b_{1}=b_{2}.$$

Это определение приемлемо, поскольку это расширение ZF является консервативным расширением .

Определение помогает избежать так называемых случайных теорем типа (a,a) = {{a}} и {a} ∈ (a,b), если определение Куратовского (a,b) = {{a}, {a, b}} использовался.

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

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

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

См. также

• Декартово произведение
• Теория множеств Тарского – Гротендика
• Трибулец, Анджей, 1989, « Теория множеств Тарского – Гротендика », Журнал формализованной математики (определение Def5 «упорядоченных пар» как { { x, y }, { x } })