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

Пара математических объектов

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

В математике упорядоченная пара ( a , b ) — это пара объектов. Порядок, в котором объекты появляются в паре, имеет значение: упорядоченная пара ( 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 (a_{1},b_{1})}$ ${\displaystyle (a_{2},b_{2})}$

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

Набор всех упорядоченных пар, первая запись которых находится в некотором множестве A , а вторая запись находится в некотором множестве B , называется декартовым произведением A и 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] Ниже приведены несколько теоретико-множественных определений упорядоченной пары (см. также ^[6] ).

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

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

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

типыMathematicaPrincipia Mathematicaотношенияпримитивные

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

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

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

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

^[8]

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

В 1921 году Казимеж Куратовский предложил ныне принятое определение ^{[9] [10]} упорядоченной пары ( 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.}$$

xp

$${\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\}\}.}$^[11]

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

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

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

Если : Если 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) ^[14] использовал определение упорядоченной пары, данное Куайном , которое требует предварительного определения натуральных чисел . Пусть - набор натуральных чисел и определите сначала ${\displaystyle \mathbb {N} }$

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

${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle x\setminus \mathbb {N} }$ ${\displaystyle x}$ ${\displaystyle \mathbb {N} }$

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

образ множестватакжеxxy ${\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\}.}$$

${\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. ^[15] ${\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 выше типа ее аргументов. Это определение работает только в том случае, если множество натуральных чисел бесконечно. Это имеет место в НФ , но не в теории типов или НФУ . Дж. Баркли Россер показал, что существование такой упорядоченной пары на уровне типа (или даже упорядоченной пары с повышением типа на 1) подразумевает аксиому бесконечности . Подробное обсуждение упорядоченной пары в контексте теорий множеств Квиниана см. в Holmes (1998). ^[16]

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

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

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

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

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

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

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

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

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

$${\displaystyle 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 } })

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

1. Лэй, Стивен Р. (2005), Анализ / С введением в доказательство (4-е изд.), Пирсон / Прентис Холл, стр. 50, ISBN 978-0-13-148101-5
2. Девлин, Кейт (2004), Множества, функции и логика / Введение в абстрактную математику (3-е изд.), Чепмен и Холл / CRC, стр. 79, ISBN 978-1-58488-449-1
3. Вольф, Роберт С. (1998), Доказательство, логика и гипотеза / Набор инструментов математика , WH Freeman and Co., p. 164, ISBN 978-0-7167-3050-7
4. Флетчер, Питер; Пэтти, К. Уэйн (1988), Основы высшей математики , PWS-Кент, с. 80, ISBN 0-87150-164-3
5. Куайн утверждал, что теоретико-множественная реализация концепции упорядоченной пары является парадигмой для разъяснения философских идей (см. « Слово и объект », раздел 53). Общее понятие таких определений или реализаций обсуждается в книге Томаса Форстера «Рассуждения о теоретических сущностях».
6. Диперт, Рэндалл. «Теоретико-множественные представления упорядоченных пар и их адекватность логике отношений».
7. Статья Винера «Упрощение логики отношений» переиздана вместе с ценным комментарием на страницах 224 и далее в книге Ван Хейеноорт, Жан (1967), От Фреге до Гёделя: Справочник по математической логике, 1979–1931 , Гарвардский университет. Press, Кембридж, Массачусетс, ISBN 0-674-32449-8 (pbk.). Ван Хейеноорт формулирует упрощение следующим образом: «Давая определение упорядоченной пары двух элементов в терминах классовых операций, заметка свела теорию отношений к теории классов». 
8. см. введение к статье Винера в van Heijenoort 1967: 224.
9. см. введение к статье Винера в van Heijenoort 1967: 224. ван Хейеноорт отмечает, что результирующий набор, представляющий упорядоченную пару, «имеет тип на 2 выше, чем элементы (когда они одного типа)»; он предлагает ссылки, которые показывают, как при определенных обстоятельствах тип может быть уменьшен до 1 или 0.
10. Куратовский, Казимир (1921). «Сюр-ла-понятия о порядке в теории ансамблей». Фундамента Математика . 2 (1): 161–171. дои : 10.4064/fm-2-1-161-171 .
11. Это отличается от определения Хаусдорфа тем, что не требует, чтобы два элемента 0 и 1 отличались от a и b .
12. Турлакис, Джордж (2003) Лекции по логике и теории множеств. Том. 2: Теория множеств . Кембриджский университет. Нажимать. Предложение III.10.1.
13. Формальное метаматематическое доказательство адекватности short см. здесь (opthreg). См. также Турлакис (2003), Предложение III.10.1.
14. Дж. Баркли Россер , 1953. Логика для математиков . МакГроу-Хилл.
15. Холмс, М. Рэндалл: Об упорядоченных парах , по: Штат Бойсе, 29 марта 2009 г. Автор использует for и for . ${\displaystyle \sigma _{1}}$ ${\displaystyle \varphi }$ ${\displaystyle \sigma _{2}}$ ${\displaystyle \psi }$
16. Холмс, М. Рэндалл (1998) Элементарная теория множеств с универсальным набором. Архивировано 11 апреля 2011 г. в Wayback Machine . Академия-Брюйлан. Издатель любезно согласился разрешить распространение этой монографии через Интернет.
17. Фреге, Готтлоб (1893). «144». Основные сведения об арифметике (PDF) . Йена: Верлаг Герман Поле.
18. Канамори, Акихиро (2007). Теория множеств от Кантора до Коэна (PDF) . Эльзевир Б.В.п. 22, сноска 59
19. Морс, Энтони П. (1965). Теория множеств . Академическая пресса.