수학(mathematics)에서, 순서쌍(ordered pair) (a, b)는 한 쌍의 대상입니다. 쌍에 나타나는 대상의 순서는 중요합니다: 만약 a = b가 아닌 한, 순서쌍 (a, b)는 순서쌍 (b, a)와 다릅니다. (대조적으로, 비순서 쌍(unordered pair) {a, b}는 비순서 쌍 {b, a}와 같습니다.)
순서쌍은 역시 2-튜플(2-tuples), 또는 길이 2의 수열 (때때로, 컴퓨터 과학 문맥에서 목록)이라고 불립니다; 스칼라(scalars)의 순서쌍은 때때로 2-차원 벡터(vectors)라고 불립니다. (기술적으로 이것은 순서쌍이 벡터 공간의 원소일 필요가 없기 때문에 용어의 남용입니다.) 순서쌍의 엔트리는 다른 순서쌍이 될 수 있으며, 순서화된 n-튜플(n-tuple) (n 대상의 순서화된 목록)의 재귀적 정의를 활성화합니다. 예를 들어, 순서화된 세-쌍 (a,b,c)는 (a, (b,c)), 즉 또 다른 쌍으로 중첩된 한 쌍으로 정의될 수 있습니다.
순서쌍 (a, b)에서, 대상 a는 쌍의 첫 번째 엔트리라고 불리고, 대상 b는 두 번째 엔트리라고 불립니다. 대안적으로, 그 대상은 첫 번째와 두 번째 성분(components), 첫 번째와 두 번째 좌표(coordinates), 또는 순서쌍의 왼쪽과 오른쪽 투영(projections)이라고 불립니다.
데카르트 곱(Cartesian product)과 이항 관계(binary relations) (및 따라서 함수(functions))는 순서쌍의 관점에서 정의됩니다.
Generalities
\(\displaystyle (a_1, b_1)\)와 \(\displaystyle (a_2, b_2)\)를 순서쌍으로 놓습니다. 그런-다음 순서쌍의 특성 (또는 정의하는) 속성은 다음입니다:
\(\quad\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에 있는 모든 순서 쌍의 집합(set)은 A와 B의 데카르트 곱(Cartesian product)이라고 불리고, A × B로 쓰입니다. 집합 A와 B 사이의 이항 관계(binary relation)는 A × B의 부분집합(subset)입니다.
(a, b) 표기법이 다른 목적, 특히 실수 직선(real number line)에서 열린 구간(open interval)을 나타내는 것으로 사용될 수 있습니다. 그러한 상황에서, 그 문맥은 보통 어떤 의미가 의도된 것인지 명확하게 할 것입니다. 추가 설명을 위해, 순서 쌍은 변형 표기법 \(\displaystyle \langle a,b\rangle\)에 의해 표시될 수 있지만, 이 표기법은 역시 다른 용도를 가집니다.
쌍 p의 왼쪽과 오른쪽 투영은 보통 각각 \(\pi_1(p)\)과 \(\pi_2(p)\)에 의해, 또는 \(\pi_{l}(p)\)와 \(\pi_r(p)\)에 의해 표시됩니다. 임의적인 n-튜플이 고려되는 문맥에서, \(\pi_i^n (t)\)가 n-튜플 t의 i-번째 성분에 대해 공통적인 표기법입니다.
Informal and formal definitions
일부 입문 수학 교과서에서, 다음과 같이 순서쌍의 비공식적 (또는 직관적인) 정의가 제공됩니다:
임의의 두 대상 a와 b에 대해, 순서쌍 (a, b)는 해당 순서에서 두 대상 a와 b를 지정하는 표기법입니다.
이것은 보통 두 원소의 집합에 대한 비교로 이어집니다; 집합 a와 b가 반드시 달라야 하지만, 순서쌍에서 그것들이 같을 수 있고 집합의 원소를 나열하는 순서는 중요하지 않지만, 순서쌍에서 고유한 엔트리의 순서를 변경하는 것은 순서쌍을 변경하는 것으로 지적합니다.
이 "정의"는 불만족스러운데 왜냐하면 그것은 오직 설명적이고 순서의 직관적인 이해를 기반으로 하기 때문입니다. 어쨌든, 때때로 지적되는 것처럼, 이 설명에 의존해도 해가 되지 않고 거의 모든 사람이 이러한 방식으로 순서쌍을 생각합니다.
더 만족스러운 접근 방식은 위에 주어진 순서쌍의 특질 속성이 수학에서 순서쌍의 역할을 이해하기 위해 요구되는 전부라는 것을 관찰하는 것입니다. 따라서 순서 쌍은 결합된 공리가 특질 속성인 원시적 개념(primitive notion)으로 취해질 수 있습니다. 이것은 니콜라 부르바키(Nicolas Bourbaki) 그룹에 의해 1954년에 출판한 집합의 이론(Theory of Sets)에서 취해진 접근 방식이었습니다. 어쨌든, 이 접근 방식은 역시 순서쌍의 존재와 그것의 특질 속성 둘 다가 공리적으로 가정되어야 하는 단점이 있습니다.
순서쌍을 엄격하게 다루는 또 다른 방법은 집합 이론의 문맥에서 형식적으로 정의하는 것입니다. 이것은 여러 가지 방법으로 수행될 수 있고 존재와 특질 속성이 집합 이론을 정의하는 공리로부터 증명될 수 있다는 장점을 가집니다. 이 정의의 가장 많이 인용된 버전 중 하나는 쿠라토프스키 (아래 참조)에 기인하고 그의 정의는 1970년에 출판된 부르바키의 집합의 이론의 두 번째 판에서 사용되었습니다. 심지어 순서쌍의 비공식적인 정의를 제공하는 수학 교과서조차도 종종 연습에서 쿠라토프스키의 공식적인 정의를 언급합니다.
Defining the ordered pair using set theory
만약 우리가 집합 이론(set theory)이 매력적인 수학의 토대(foundation of mathematics)임을 동의한다면, 모든 수학적 대상은 일종의 집합(sets)으로 정의되어야 합니다. 따라서 만약 순서 쌍이 원시적으로 취해지지 않으면, 그것은 집합으로 정의되어야 합니다. 순서쌍의 몇 가지 집합-이론적 정의가 아래에 나와 있습니다.
Wiener's definition
노버트 위너(Norbert Wiener)는 1914년에 순서쌍의 첫 번째 집합 이론적 정의를 제안했습니다:
\(\quad\displaystyle \left( a, b \right) :=
\left\{\left\{ \left\{a\right\},\, \emptyset \right\},\, \left\{\left\{b\right\}\right\}\right\}.\)
그는 이 정의가 Principia Mathematica의 유형(types)을 집합으로 정의하는 것을 가능하게 한다는 것을 관찰했습니다. Principia Mathematica는 유형과 따라서 모든 애리티의 관계(relations)를 원시적(primitive)인 것으로 취해져 왔습니다.
위너는 클래스에서 모든 원소가 같은 "유형"이어야 하는 유형 이론(type theory)과 호환되는 정의를 만들기 위해 {b} 대신 {{b}}를 사용했습니다. 추가적 집합 내에 중첩된 b와 함께, 그것의 유형은 \(\displaystyle \{\{a\}, \emptyset\}\)의 것과 같습니다.
Hausdorff's definition
위너 (1914)와 거의 같은 시기에, 펠릭스 하우스도르프(Felix Hausdorff)는 다음과 같은 그의 정의를 제안했습니다:
\(\quad\displaystyle (a, b) := \left\{ \{a, 1\}, \{b, 2\} \right\}\)
"여기서 1과 2는 a와 b와 다른 둘의 별개의 대상입니다."
Kuratowski's definition
1921년 카지미에시 쿠라토프스키(Kazimierz Kuratowski)는 순서쌍 (a, b)의 현재-받아들여지는 정의를 제안했습니다:
\(\quad\displaystyle (a, \ b)_K \; := \ \{ \{ a \}, \ \{ a, \ b \} \}.\)
이 정의는 심지어 첫 번째 좌표와 두 번째 좌표가 동일할 때 사용됨을 주목하십시오:
\(\quad\displaystyle (x,\ x)_K = \{\{x\},\{x, \ x\}\} = \{\{x\},\ \{x\}\} = \{\{x\}\}\)
어떤 순서쌍 p가 주어지면, 속성 "x는 p의 첫 번째 좌표입니다"는 다음과 같이 공식화될 수 있습니다:
\(\quad\displaystyle \forall Y\in p:x\in Y.\)
속성 "x는 p의 두 번째 좌표입니다"는 다음과 같이 공식화될 수 있습니다:
\(\quad\displaystyle (\exists Y\in p:x\in Y)\land(\forall Y_1,Y_2\in p:Y_1\ne Y_2\rightarrow (x\notin Y_1\lor x \notin Y_2)).\)
왼쪽과 오른쪽 좌표가 동일한 경우에서, 오른쪽 conjunct \(\displaystyle (\forall Y_1,Y_2\in p:Y_1\ne Y_2\rightarrow (x\notin Y_1 \lor x \notin Y_2))\)는 자명하게 참인데, 왜냐하면 \(Y_1 \neq Y_2\)는 그 결코 그 경우가 아니기 때문입니다.
이것은 우리가 (임의적인 교집합(arbitrary intersection)과 임의적인 합집합(arbitrary union)에 대해 표기법을 사용하여) 쌍의 첫 번째 좌표를 추출할 수 있는 방법입니다:
\(\quad\displaystyle \pi_1(p) = \bigcup\bigcap p.\)
이것은 두 번째 좌표가 추출될 수 있는 방법입니다:
\(\quad\displaystyle \pi_2(p) = \bigcup\left\{\left. x \in \bigcup p\,\right|\,\bigcup p \neq \bigcap p \rarr x \notin \bigcap p \right\}.\)
Variants
순서쌍의 위의 쿠라토프스키 정의는 순서쌍이 반드시 만족시켜야 하는, 즉, \(\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 \}\}.\)
뒤집은(reverse) 정의는 쿠라토프스키 정의의 단지 자명한 변형일 뿐이고 이를테면 독립적인 관심 대상이 아닙니다. 그 정의 짧은(short) 것은 소위 세 쌍이 아닌 두 쌍의 중괄호(braces)가 필요하기 때문입니다. 짧은 것이 특질 속성을 만족시킨다는 것을 증명하려면 체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory) 규칙성의 공리(axiom of regularity)를 요구합니다. 게다가, 만약 우리가 자연수의 폰 노이만의 집합-이론적 구성을 사용하면, 2는 집합 {0, 1} = {0, {0}}으로 정의되며, 쌍 \((0,0)_{\rm short}\)와 구별할 수 없습니다. 게다가 짧은 쌍의 또 다른 단점은 심지어 a와 b가 같은 유형일지라도, 짧은 쌍의 원소가 아니라는 사실입니다. (어쨌든, 만약 a = b이면 짧은 버전은 카디널리티 2를 가짐을 유지하며, 이것은 임의의 "순서쌍"을 포함하여 임의의 "쌍"에 대해 기대할 수 있는 것입니다. 역시 짧은 버전은 미자르 시스템(Mizar system)이 기반이 되는 타르스키–그로텐디크 집합 이론(Tarski–Grothendieck set theory)에서 사용된다는 점에 유의하십시오. Mizar 시스템의 기반이 됩니다.)
Proving that definitions satisfy the characteristic property
증명: (a, b) = (c, d)인 것과 a = c와 b = d이 것은 필요충분(iff) 조건입니다.
쿠라토프스키:
If. 만약 a = c와 b = d이면, {{a}, {a, b}} = {{c}, {c, d}}입니다. 따라서 \((a,b)_{\rm K} = (c,d)_{\rm K}\)입니다.
Only if. 두 경우: a = b, 및 a ≠ b.
만약 a = b이면:
- \((a,b)_{\rm K} = \{\{a\}, \{a,b\}\} = \{\{a\}, \{a,b\}\}\).
- \((c,d)_{\rm K} = \{\{c\},\{c,d\}\} = \{\{a\}\}\).
- 따라서 {c} = {c, d} = {a}이며, 이는 a = c 및 a = d를 의미합니다. 가설에 의해, a = b입니다. 그러므로 b = d.
만약 a ≠ b이면, \((a,b)_{\rm K} = (c,d)_{\rm 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인 경우입니다.
뒤집은:
\((a,b)_{\text{reverse}} = \{\{b\}, \{a,b\}\} = \{\{b\}, \{b,a\}\} = (b,a)_{\rm K}\).
If. 만약 \((a,b)_{\text{reverse}} = (c,d)_{\text{reverse}}\), \((b,a)_{\rm K} = (c,d)_{\rm K}\). 그러므로, b = d 및 a = c.
Only if. 만약 a = c 및 b = d이면, {{b}, {a, b}} = {{d}, {c, d}}입니다. 따라서 \((a,b)_{\text{reverse}} = (c,d)_{\text{reverse}}\).
짧은:
If: 만약 a = c 및 b = d이면, {a, {a, b}} = {c, {c, d}}입니다. 따라서 \((a,b)_{\text{short}} = (c,d)_{\text{short}}\).
Only if: {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 = {c, d} = {a, b}로부터 a의 원소이며, 다시 규칙성과 모순됩니다.
- 따라서 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.
Quine–Rosser definition
로서(Rosser) (1953)는 자연수(natural number)의 앞선 정의를 요구하는 과인(Quine)에 기인한 순서쌍의 정의를 사용했습니다. \(\mathbb{N}\)를 자연수의 집합으로 놓고 먼저 다음을 정의합니다:
\(\quad\displaystyle \sigma(x) := \begin{cases}
x, & \text{if }x \not\in \mathbf{N}, \\
x+1, & \text{if }x \in \mathbf{N}.
\end{cases}\)
함수 \(\displaystyle \sigma\)는 만약 그것이 인수가 자연수이면 인수를 증가시키고 그렇지 않으면 그대로 둡니다; 숫자 0은 \(\displaystyle \sigma\)의 함수형 값으로 나타나지 않습니다.
\(\displaystyle x \smallsetminus \mathbf{N}\)는 \(\displaystyle \mathbf{N}\)에 있지 앟은 \(\displaystyle x\)의 원소의 집합이므로 다음과 같이 계속됩니다:
\(\quad\displaystyle \varphi(x) := \sigma[x] = \{\sigma(\alpha)\mid\alpha \in x\} = (x \smallsetminus \mathbf{N}) \cup \{n+1 : n \in (x \cap \mathbf{N}) \}.\)
이것은 \(\displaystyle \sigma\) 아래에서 집합 \(\displaystyle x\)의 집합 이미지(set image)이며, 마찬가지로 \(\displaystyle \sigma''x\)에 의해 때때로 표시됩니다. 함수 \(\displaystyle \varphi\)를 집합 x에 적용하는 것은 단순히 그것에서 모든 각 자연수를 증가시킵니다. 특히, \(\displaystyle \varphi(x)\)는 임의의 집합 x와 y에 대해, 다음이 되도록 숫자 0을 결코 포함하지 않습니다:
\(\quad\displaystyle \varphi(x) \neq \{0\} \cup \varphi(y).\)
게다가, 다음을 정의합니다:
\(\quad\displaystyle \psi(x) := \sigma[x] \cup \{0\} = \varphi(x) \cup \{0\}.\)
이것에 의해, \(\displaystyle \psi(x)\)는 항상 숫자 0을 포함합니다.
마지막으로, 순서쌍 (A, B)를 다음 서로소 합집합으로 정의합니다:
\(\quad\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을 포함하지 않는 쌍의 모든 쌍의 원소를 추출하고 \(\displaystyle \varphi\)를 실행취소하면 A를 산출합니다. 마찬가지로, B는 0를 포함하는 쌍의 원소로부터 복구될 수 있습니다.
예를 들어, 쌍 \(\displaystyle ( \{\{a,0\},\{b,c,1\}\} , \{\{d,2\},\{e,f,3\}\} )\)은 \(\displaystyle a,b,c,d,e,f\notin \mathbf{N}\)에서 제공된 \(\displaystyle \{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\}\)로 인코딩됩니다.
유형 이론(type theory)과 공리적 집합 이론 NF와 같은 그것의 부산물에서, 콰인–로서 쌍은 그것의 투영과 같은 유형을 가지고 따라서 "유형-수준" 순서쌍이라고 이름-짓습니다. 따라서 이 정의는 순서쌍의 집합으로 정의된 함수(function)를 그것의 인수 유형보다 오직 1 더 높은 유형을 가지기 위해 활성화하는 이점을 가집니다. 이 정의는 오직 만약 자연수의 집합이 무한이면 작동합니다. 이것은 NF에서 경우이지만, 유형 이론이나 NFU에서는 그렇지 않습니다. 로서는 그러한 유형-수준 순서쌍 (또는 심지어 "1에 의해 올려지는-유형" 순서쌍)의 존재가 무한대의 공리(axiom of infinity)를 의미한다는 것을 보여주었습니다. 콰인 집합 이론의 맥락에서 순서쌍의 광범위한 논의에 대해 Holmes(1998)를 참조하십시오.
Cantor–Frege definition
집합 이론의 발전 초기에, 역설이 발견되기 전에, 칸토어는 관계의 개념이 원시적이라고 가정하여 두 집합의 순서쌍을 이들 집합 사이에 유지되는 모든 관계의 클래스로 정의함으로써 프레게를 따랐습니다:
\(\quad\displaystyle (x, y) = \{R : x R y \}.\)
이 정의는 대부분의 현대의 형식화된 집합 이론에서 허용되지 않고 주어진 집합과 동등한 효과의 모든 집합의 클래스로 집합의 세는-숫자(cardinal)를 정의하는 것과 방법론적으로 유사합니다.
Morse definition
모스-켈리 집합 이론(Morse–Kelley set theory)은 적절한 클래스(proper class)의 자유로운 사용을 만듭니다. 모스(Morse)는 그것의 투영이 집합뿐만 아니라 적절한 클래스가 될 수 있도록 순서쌍을 정의했습니다. (쿠라토프스키 정의는 이것을 허용하지 않습니다.) 그는 먼저 그것의 투영이 쿠라토프스키의 방식으로 집합인 순서쌍을 정의했습니다. 그는 그런-다음 쌍을 재정의했습니다.
\(\quad\displaystyle (x, y) = (\{0\} \times s(x)) \cup (\{1\} \times s(y))\)
여기서 성분 데카르트 곱은 집합의 쿠라토프스키 쌍이고 다음입니다:
\(\quad\displaystyle s(x) = \{\emptyset \} \cup \{\{t\} \mid t \in x\} \)
이것은 그것의 투영이 적절한 클래스인 가능한 쌍을 렌더링합니다. 위의 콰인–로서 정의는 역시 적절한 클래스(proper class)를 투영으로 인정합니다. 유사하게 세-쌍은 다음과 같이 3-튜플로 정의됩니다:
\(\quad\displaystyle (x, y, z) = (\{0\} \times s(x)) \cup (\{1\} \times s(y)) \cup (\{2\} \times s(z))\)
삽입된 빈 집합을 가지는 한원소 집합 \(\displaystyle s(x) \)의 사용은 튜플에게 만약 a가 n-튜플이고 b가 m-튜플이고 a = b이면 n = m이라는 고유성 속성을 가지는 것을 허용합니다. 순서 쌍으로 정의된 순서 세-쌍은 순서 쌍에 관한 이 속성을 가지지 않습니다.
Axiomatic definition
순서쌍은 역시 단지 ZF에 애리티 2 (보통 생략됨)의 새로운 함수 기호 \(\displaystyle f\)에 더하고 \(\displaystyle f\)에 대해 공리를 정의함으로써 체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory)(ZF)에서 공리적으로 도입될 수 있습니다:
\(\quad\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의 이 확장은 보존적 확장(conservative extension)이기 때문에 허용됩니다.
그 정의는 만약 쿠라토프스키의 정의 (a,b) = {{a}, {a,b}}가 사용되었으면 (a,a) = {{a}}, {a} ∈ (a,b)와 같은 소위 우발적 정리를 피하는 데 도움이 됩니다.
Category theory
집합의 카테고리(category of sets)에서 카테고리-이론적 곱(product) A × B는 순서쌍의 집합을 나타내며, 첫 번째 원소는 A에서 오고, 두 번째 원소는 B에서 옵니다. 이러한 문맥에서 위의 특질 속성은 곱의 보편적 속성(universal property)과 집합 X의 원소가 1 (하나의 원소 집합)에서 X로의 사상으로 식별될 수 있다는 사실의 결과입니다. 다른 대상이 보편적 속성을 가질 수 있지만, 그것들은 모두 자연적으로 동형(naturally isomorphic)입니다.
