순서쌍

수학에서 순서쌍(順序雙, 틀:Llang)이란 두 개의 수학적 대상을 순서를 정하여 짝지어 나타낸 쌍이다. 두 대상 a, b로부터 순서를 생각하여 만든 쌍을 흔히 (a, b)로 적는다. 이는 a와 b가 같지 않는 한, (b, a)와 다른 순서쌍이다. 순서쌍은 2-튜플, 또는 두짝(틀:Llang)이라고도 불린다. 순서쌍 (a, b)에서의 a, b를 각각 첫 번째, 두 번째 성분(틀:Llang)이라고 한다. 때로는 첫 번째, 두 번째 좌표(틀:Llang)라고도 한다.

두 순서쌍이 같을 필요충분조건은, 두 순서쌍의 첫째와 둘째 성분이 각각 같은 것이다. 집합론에서는 이 성질을 구현하기 위해 (a, b) := {{a}, {a, b}}와 같은 정의를 자주 사용한다.

순서쌍의 성분은 스칼라이거나(2 차원 벡터), 다른 순서쌍일 수 있다. 이로써, 순서쌍을 이용해 순서있는 n-튜플을 귀납적으로 정의하는 것이 가능하다. 예를 들어, 순서쌍 (a, b, c)는 (a, (b, c))로 정의할 수 있다.

곱집합, 함수를 비롯한 이항관계와 같은 수학 개념은 순서쌍을 이용하여 정의되었다.

성질

순서쌍의 가장 기본적인 성질은, 두 순서쌍이 같을 필요충분조건이 두 성분이 각각 같은 것이라는 것이다. 즉,

$(a,b)=(c,d)⟺a=c\wedge b=d$

이러한 성질을 순서쌍을 정의내리는 데에 사용할 수 있다.

첫 번째 성분을 집합 $A$, 두 번째 성분을 집합 $B$에서 취한 모든 순서쌍의 집합을 곱집합이라고 하고 $A\times B$로 표기한다. 집합 $A$와 $B$ 사이의 이항 관계는 $A\times B$의 부분집합이다.

순서쌍의 통상적인 표기법은 $(a,b)$ 꼴이지만, 개구간 등의 표기와 혼동하지 않기 위해 $⟨a,b⟩$로 나타내기도 한다.

집합론적 정의

순서쌍의 위 성질은 순서쌍의 본질을 보여주고 있다. 이 본질적인 성질을 공리로 두어 순서쌍을 무정의 용어로 취급할 수 있다. 이는 니콜라 부르바키 단체의 1954년 출간된 《집합론》에서 사용된 처리법이다. 1970년 출간된 2 판에서 쿠라토프스키의 정의가 추가되었다.

수학기초론의 일원인 공리적 집합론에서는 모든 개념을 집합으로서 정의한다. 순서쌍의 집합론적 정의의 예로는 다음의 것들이 있다.

위너의 정의

순서쌍의 최초 집합론적 정의는 1914년 노버트 위너에 의해 제안되었다.

$(a,b):=\{\{\{a\},\mathrm{\varnothing }\},\{\{b\}\}\}$

그에 의하면 이러한 정의는 《수학 원리》의 모든 유형을 집합으로 정의될 수 있게 한다. (《수학 원리》의 관계를 비롯한 유형들은 본래 모두 정의내리지 않는 원시 개념이다.)

그는 정의와 유형 이론이 양립하게 하기 위해(즉, 집합의 원소가 모두 같은 유형이어야 한다), $\{b\}$가 아닌 $\{\{b\}\}$를 사용하였다, 이렇게 하면 $\{\{b\}\}$는 $\{\{a\},\mathrm{\varnothing }\}$와 같은 유형이 된다.

하우스도르프의 정의

위너와 비슷한 시기에(1914), 펠릭스 하우스도르프는 다른 정의를 제안하였다.

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

여기서 1, 2(1 ≠ 2)는 a, b와 다른 대상이다.

쿠라토프스키의 정의

오늘날에 쓰이는 정의는 카지미에시 쿠라토프스키가 1912년에 제시하였다.

$(a,b{)}_K=\{\{a\},\{a,b\}\}$

이 정의는 두 성분이 같은 경우에 쓰여도 무방하다.

$(x,x{)}_K=\{\{x\},\{x,x\}=\{\{x\},\{x\}\}=\{\{x\}\}$

임의의 순서쌍 $p$의 첫 번째 성분은 다음 조건들의 동치성에 의해 추출할 수 있다.

• $a$는 순서쌍 $p$의 첫 번째 성분이다.
• $\mathrm{\forall }Y\in p:a\in Y$
• $a=\bigcup \bigcap p$

비슷한 결론이 두 번째 성분에 대해서도 존재한다.

• $b$는 순서쌍 $p$의 두 번째 성분이다.
• $(\mathrm{\exists }Y\in p:b\in Y)\wedge (\mathrm{\forall }{Y}_1,Y_2\in p:(Y_1\ne Y_2)\to (b\notin Y_1\vee b\notin Y_2))$
• $b=\bigcup \{x\in \bigcup p|\bigcup p\ne \bigcap p\to x\notin \bigcup p\}$

변형 정의

위 정의는 순서쌍의 기본 성질을 반영하기에 충분하다, 즉 $(a,b)=(x,y)\leftrightarrow (a=x)\wedge (b=y)$. 순서성을 반영하는 데에도 충분하다, 즉 $a\ne b\to (a,b)\ne (b,a)$. 아래의 비슷한 정의들도 순서쌍을 구성하기에 충분하다.

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

reverse 정의는 쿠라토프스키의 정의의 자명한 변형이며, 따로 논할 가치가 없다. short 정의는 괄호를 두 쌍만 사용한다는 점에서 이름을 땄다. short 정의는 몇가지 결점을 가진다. 첫째, 기본 성질을 만족함을 증명하기 위해 체르멜로-프렝켈 집합론의 정칙성 공리를 사용해야 한다. 둘째, 자연수의 폰 노이만 정의를 채용했을 때, $2=\{0,1\}=\{0,\{0\}\}=(0,0{)}_{\text{short}}$와 같은 부자연스러운 결과를 낳는다. 셋째, short 순서쌍의 원소는 항상 유형이 다르다. 그러나 short 정의에서의 순서쌍은 모두 2를 기수로 한다는 점, 또 미자르 시스템의 기초인 타르스키-그로텐디크 집합론에서 사용된다는 점에 주의할 필요 있다.

기본 성질 성립 증명

다음은 $(a,b)=(c,d)⟺a=c\wedge b=d$ 성질의 증명이다.

• 쿠라토프스키
  1. 먼저, $a=c\wedge b=d$이면,

     $(a,b{)}_K=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=(c,d{)}_K$

  2. 또한

     $\begin{array}{cc}& (a,b{)}_K=(c,d{)}_K\\ \Rightarrow & \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}\\ \Rightarrow & (\{a\}=\{c\})\vee (\{a\}=\{c,d\})\\ \Rightarrow & (a=c)\vee (c=a\wedge d=a)\\ \Rightarrow & a=c\end{array}$

  3. 그리고

     $\begin{array}{cc}& (a,b{)}_K=(c,d{)}_K\\ \Rightarrow & \bigcup (a,b{)}_K=\bigcup (c,d{)}_K\\ \Rightarrow & \{a,b\}=\{a,d\}\\ \Rightarrow & (b=a\vee b=d)\wedge (d=a\vee d=b)\\ \Rightarrow & (b=d)\vee (b=a\wedge d=a)\\ \Rightarrow & b=d\end{array}$

• reverse 정의도 위와 비슷하게 기본 성질을 만족한다는 것을 보일 수 있다.
• short 정의. 아래에서 $(*)$ 표기를 한 과정은 정칙성 공리를 사용하였다.
  1. $a=c\wedge b=d\Rightarrow \{a,\{a,b\}\}=\{c,\{c,d\}\}\Rightarrow (a,b{)}_{\text{short}}=(c,d{)}_{\text{short}}$
  2. 순서쌍의 같음 ⇒ a = c

     $\begin{array}{ccc}& (a,b{)}_{\text{short}}=(c,d{)}_{\text{short}}& \\ \Rightarrow & \{a,\{a,b\}\}=\{c,\{c,d\}\}& \\ \Rightarrow & (a=c\vee a=\{c,d\})\wedge (c=a\vee c=\{a,b\})& \\ \Rightarrow & (a=c)\vee (a=\{c,d\}\wedge c=\{a,b\})& \\ \Rightarrow & (a=c)\vee (c\in a\wedge a\in c)& \\ \Rightarrow & a=c& (*)\end{array}$

  3. 순서쌍의 같음 ⇒ b = d

     $\begin{array}{ccc}& (a,b{)}_{\text{short}}=(c,d{)}_{\text{short}}& \\ \Rightarrow & \{a,\{a,b\}\}=\{a,\{a,d\}\}& \\ \Rightarrow & a\cup \{a,b\}=a\cup \{a,d\}& \\ \Rightarrow & (b\in a\vee b=a\vee b=d)\wedge (d\in a\vee d=a\vee d=b)& \\ \Rightarrow & (b=a\vee b=d)\wedge (d=a\vee d=b)& (*)\\ \Rightarrow & (b=d)\vee (b=a\wedge d=a)& \\ \Rightarrow & b=d& \end{array}$

콰인-로서의 정의

1953년 로서는 콰인의 정의를 확장하였다. 로서-콰인 정의는 자연수의 선결적 정의를 필요로 한다. $\mathbb{N}$을 자연수의 집합으로 두고, $x\setminus \mathbb{N}$을 $\mathbb{N}$에 속하지 않는 $x$의 원소들의 집합이라고 하자. 먼저 함수 $\phi$를 정의한다.

$\phi (x)=(x\setminus \mathbb{N})\cup \{n+1:n\in (x\cap \mathbb{N})\}$

이 변환은 $x$ 안의 모든 자연수를 1 증가시킨다. 또한 $\phi (x)$는 0을 포함하지 않는다. 그러므로 모든 집합 $x$, $y$에 대해 다음이 성립한다.

$\phi (x)\ne \{0\}\cup \phi (y)$

이제 순서쌍 $(A,B)$를 정의한다.

$(A,B)=\{\phi (a):a\in A\}\cup \{0\cup \phi (b):b\in B\}$

이렇게 정의된 순서쌍에서도 첫째, 둘째 성분을 추출할 수 있다. 첫째 성분 $A$는 순서쌍의 원소 중, 0을 원소로 포함하지 않는 모든 집합들에 $\phi$ 변환을 벗겨서 이루어진 집합이다. 둘째 성분 $B$는 순서쌍의 원소 중, 0을 원소로 포함하는 모든 집합들에 적당한 변환을 가하여 이루어진 집합이다. 아래는 이의 공식화이다.

$A=\{{\phi }^{-1}(\alpha ):\alpha \in (A,B),0\notin \alpha \}$

$B=\{{\phi }^{-1}(\beta \setminus \{0\}):\beta \in (A,B),0\in \beta \}$

유형 이론과 그의 갈래(새기초 집합론 등)에서, 콰인-로서 순서쌍은 두 성분과 유형이 같다. 그렇기에 이 정의는 (일정 조건을 만족하는 순서쌍들로 이루어진 집합으로 정의된) 함수가 변수보다 유형이 1 만큼만 크다는 장점이 있다. 이 정의는 자연수 집합이 무한할 때만 의미가 있다. NF는 그러하지만, 유형 이론이나 NFU는 그렇지 않다. 로서는 이러한 두 성분과 유형이 같은 순서쌍의 존재성으로부터 무한 공리를 유추할 수 있음을 증명하였다.

모스의 정의

모스-켈리 집합론에서는 고유 모임을 자유로이 사용할 수 있다. 모스의 정의는 순서쌍의 성분이 고유 모임일 수도 있게끔한다. 이는 쿠라토프스키 정의에서 허용되지 않는다. 그는 우선 집합을 성분으로 하는 순서쌍을 쿠라토프스키의 방식으로 정의한 뒤, 순서쌍을 다음과 같이 재정의하였다.

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

여기서의 곱집합은 쿠라토프스키 순서쌍의 집합이고,

$s(x)=\{\mathrm{\varnothing }\}\cup \{\{t\}:t\in x\}$

이다.

이는 고유 모임을 성분으로 하는 순서쌍을 허용케 한다. 이는 위의 콰인-로서 정의도 마찬가지이다. 이와 비슷하게 세짝(틀:Llang)을 다음과 같이 정의할 수 있다.

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

한원소 집합으로 이루어진 집합 $s(x)$의 사용하여 정의한 튜플은 일종의 유일성을 부여받는다. 즉, 임의의 n-튜플 a와 m-튜플 b에 대해, 만약 a = b 이면, n = m이다. 이는 순서쌍을 이용해 재귀적으로 정의한 튜플에게는 없는 성질이다, (a, b, c) = (a, (b, c))는 2-튜플이기도, 3-튜플이기도 하다.

같이 보기

• 튜플
• 곱집합
• 이항관계
• 함수