수학 에서 순서쌍 (順序雙, 영어 : ordered pair )이란 두 개의 수학적 대상 을 순서를 정하여 짝지어 나타낸 쌍이다. 두 대상 a , b 로부터 순서를 생각하여 만든 쌍을 흔히 (a , b )로 적는다. 이는 a 와 b 가 같지 않는 한, (b , a )와 다른 순서쌍이다.
순서쌍은 2-튜플 , 또는 두짝 (영어 : 2-tuple )이라고도 불린다. 순서쌍 (a , b )에서의 a , b 를 각각 첫 번째, 두 번째 성분 (영어 : first (second) entry )이라고 한다. 때로는 첫 번째, 두 번째 좌표 (영어 : first (second) coordinate )라고도 한다.
두 순서쌍이 같을 필요충분조건 은, 두 순서쌍의 첫째와 둘째 성분이 각각 같은 것이다. 집합론 에서는 이 성질을 구현하기 위해 (a , b ) := {{a }, {a , b }}와 같은 정의를 자주 사용한다.
순서쌍의 성분은 스칼라 이거나(2 차원 벡터 ), 다른 순서쌍일 수 있다. 이로써, 순서쌍을 이용해 순서있는 n-튜플 을 귀납적으로 정의하는 것이 가능하다. 예를 들어, 순서쌍 (a , b , c )는 (a , (b , c ))로 정의할 수 있다.
곱집합 , 함수 를 비롯한 이항관계 와 같은 수학 개념은 순서쌍을 이용하여 정의되었다.
순서쌍의 가장 기본적인 성질은, 두 순서쌍이 같을 필요충분조건이 두 성분이 각각 같은 것이라는 것이다. 즉,
(
a
,
b
)
=
(
c
,
d
)
⟺
a
=
c
∧
b
=
d
{\displaystyle (a,b)=(c,d)\ \iff \ a=c\wedge b=d}
이러한 성질을 순서쌍을 정의내리는 데에 사용할 수 있다.
첫 번째 성분을 집합
A
{\displaystyle A}
, 두 번째 성분을 집합
B
{\displaystyle B}
에서 취한 모든 순서쌍의 집합을 곱집합 이라고 하고
A
×
B
{\displaystyle A\times B}
로 표기한다. 집합
A
{\displaystyle A}
와
B
{\displaystyle B}
사이의 이항 관계 는
A
×
B
{\displaystyle A\times B}
의 부분집합 이다.
순서쌍의 통상적인 표기법은
(
a
,
b
)
{\displaystyle (a,b)}
꼴이지만, 개구간 등의 표기와 혼동하지 않기 위해
⟨
a
,
b
⟩
{\displaystyle \langle a,b\rangle }
로 나타내기도 한다.
집합론적 정의 [ 편집 ]
순서쌍의 위 성질은 순서쌍의 본질을 보여주고 있다. 이 본질적인 성질을 공리 로 두어 순서쌍을 무정의 용어 로 취급할 수 있다. 이는 니콜라 부르바키 단체의 1954년 출간된 《집합론》에서 사용된 처리법이다. 1970년 출간된 2 판에서 쿠라토프스키 의 정의가 추가되었다.
수학기초론 의 일원인 공리적 집합론 에서는 모든 개념을 집합으로서 정의한다.[1] [2] 순서쌍의 집합론적 정의의 예로는 다음의 것들이 있다.
위너의 정의 [ 편집 ]
순서쌍의 최초 집합론적 정의는 1914년 노버트 위너 에 의해 제안되었다.[3]
(
a
,
b
)
:=
{
{
{
a
}
,
∅
}
,
{
{
b
}
}
}
{\displaystyle (a,\,b):=\{\{\{a\},\,\emptyset \},\,\{\{b\}\}\}}
그에 의하면 이러한 정의는 《수학 원리 》의 모든 유형 을 집합으로 정의될 수 있게 한다. (《수학 원리》의 관계 를 비롯한 유형들은 본래 모두 정의내리지 않는 원시 개념 이다.)
그는 정의와 유형 이론 이 양립하게 하기 위해(즉, 집합의 원소가 모두 같은 유형이어야 한다),
{
b
}
{\displaystyle \{b\}}
가 아닌
{
{
b
}
}
{\displaystyle \{\{b\}\}}
를 사용하였다, 이렇게 하면
{
{
b
}
}
{\displaystyle \{\{b\}\}}
는
{
{
a
}
,
∅
}
{\displaystyle \{\{a\},\,\emptyset \}}
와 같은 유형이 된다.
하우스도르프의 정의 [ 편집 ]
위너와 비슷한 시기에(1914), 펠릭스 하우스도르프 는 다른 정의를 제안하였다.
(
a
,
b
)
:=
{
{
a
,
1
}
,
{
b
,
2
}
}
{\displaystyle (a,\,b):=\{\{a,\,1\},\,\{b,\,2\}\}}
여기서 1, 2(1 ≠ 2)는 a , b 와 다른 대상이다.[3]
쿠라토프스키의 정의 [ 편집 ]
오늘날에 쓰이는 정의는 카지미에시 쿠라토프스키 가 1912년에 제시하였다.[3] [4]
(
a
,
b
)
K
=
{
{
a
}
,
{
a
,
b
}
}
{\displaystyle (a,\ b)_{K}=\{\{a\},\ \{a,\ b\}\}}
이 정의는 두 성분이 같은 경우에 쓰여도 무방하다.
(
x
,
x
)
K
=
{
{
x
}
,
{
x
,
x
}
=
{
{
x
}
,
{
x
}
}
=
{
{
x
}
}
{\displaystyle (x,\ x)_{K}=\{\{x\},\ \{x,\ x\}=\{\{x\},\ \{x\}\}=\{\{x\}\}}
임의의 순서쌍
p
{\displaystyle p}
의 첫 번째 성분은 다음 조건들의 동치성 에 의해 추출할 수 있다.
a
{\displaystyle a}
는 순서쌍
p
{\displaystyle p}
의 첫 번째 성분이다.
∀
Y
∈
p
:
a
∈
Y
{\displaystyle \forall Y\in p:a\in Y}
a
=
⋃
⋂
p
{\displaystyle a=\bigcup \bigcap p}
비슷한 결론이 두 번째 성분에 대해서도 존재한다.
b
{\displaystyle b}
는 순서쌍
p
{\displaystyle p}
의 두 번째 성분이다.
(
∃
Y
∈
p
:
b
∈
Y
)
∧
(
∀
Y
1
,
Y
2
∈
p
:
(
Y
1
≠
Y
2
)
→
(
b
∉
Y
1
∨
b
∉
Y
2
)
)
{\displaystyle (\exists Y\in p:b\in Y)\wedge (\forall Y_{1},Y_{2}\in p:(Y_{1}\neq Y_{2})\rightarrow (b\notin Y_{1}\vee b\notin Y_{2}))}
b
=
⋃
{
x
∈
⋃
p
|
⋃
p
≠
⋂
p
→
x
∉
⋃
p
}
{\displaystyle b=\bigcup \{x\in \bigcup p|\bigcup p\neq \bigcap p\rightarrow x\notin \bigcup p\}}
변형 정의 [ 편집 ]
위 정의는 순서쌍의 기본 성질을 반영하기에 충분하다, 즉
(
a
,
b
)
=
(
x
,
y
)
↔
(
a
=
x
)
∧
(
b
=
y
)
{\displaystyle (a,\,b)=(x,\,y)\leftrightarrow (a=x)\wedge (b=y)}
. 순서성을 반영하는 데에도 충분하다, 즉
a
≠
b
→
(
a
,
b
)
≠
(
b
,
a
)
{\displaystyle a\neq b\rightarrow (a,\,b)\neq (b,\,a)}
. 아래의 비슷한 정의들도 순서쌍을 구성하기에 충분하다.
(
a
,
b
)
reverse
:=
{
{
b
}
,
{
a
,
b
}
}
{\displaystyle (a,\,b)_{\text{reverse}}:=\{\{b\},\,\{a,\,b\}\}}
(
a
,
b
)
short
:=
{
a
,
{
a
,
b
}
}
{\displaystyle (a,\,b)_{\text{short}}:=\{a,\,\{a,\,b\}\}}
(
a
,
b
)
01
:=
{
{
0
,
a
}
,
{
1
,
b
}
}
{\displaystyle (a,\,b)_{01}:=\{\{0,\,a\},\,\{1,\,b\}\}}
[5]
reverse 정의는 쿠라토프스키의 정의의 자명한 변형이며, 따로 논할 가치가 없다. short 정의는 괄호 를 두 쌍만 사용한다는 점에서 이름을 땄다. short 정의는 몇가지 결점을 가진다. 첫째, 기본 성질을 만족함을 증명하기 위해 체르멜로-프렝켈 집합론 의 정칙성 공리 를 사용해야 한다. 둘째, 자연수 의 폰 노이만 정의 를 채용했을 때,
2
=
{
0
,
1
}
=
{
0
,
{
0
}
}
=
(
0
,
0
)
short
{\displaystyle 2=\{0,\,1\}=\{0,\,\{0\}\}=(0,\,0)_{\text{short}}}
와 같은 부자연스러운 결과를 낳는다. 셋째, short 순서쌍의 원소는 항상 유형이 다르다. 그러나 short 정의에서의 순서쌍은 모두 2를 기수로 한다는 점, 또 미자르 시스템 의 기초인 타르스키-그로텐디크 집합론 에서 사용된다는 점에 주의할 필요 있다.
기본 성질 성립 증명 [ 편집 ]
다음은
(
a
,
b
)
=
(
c
,
d
)
⟺
a
=
c
∧
b
=
d
{\displaystyle (a,b)=(c,d)\iff a=c\wedge b=d}
성질의 증명이다.
쿠라토프스키
먼저,
a
=
c
∧
b
=
d
{\displaystyle a=c\wedge b=d}
이면,
(
a
,
b
)
K
=
{
{
a
}
,
{
a
,
b
}
}
=
{
{
c
}
,
{
c
,
d
}
}
=
(
c
,
d
)
K
{\displaystyle (a,b)_{K}=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=(c,d)_{K}}
또한
(
a
,
b
)
K
=
(
c
,
d
)
K
⇒
{
{
a
}
,
{
a
,
b
}
}
=
{
{
c
}
,
{
c
,
d
}
}
⇒
(
{
a
}
=
{
c
}
)
∨
(
{
a
}
=
{
c
,
d
}
)
⇒
(
a
=
c
)
∨
(
c
=
a
∧
d
=
a
)
⇒
a
=
c
{\displaystyle {\begin{array}{cl}&(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}}}
그리고
(
a
,
b
)
K
=
(
c
,
d
)
K
⇒
⋃
(
a
,
b
)
K
=
⋃
(
c
,
d
)
K
⇒
{
a
,
b
}
=
{
a
,
d
}
⇒
(
b
=
a
∨
b
=
d
)
∧
(
d
=
a
∨
d
=
b
)
⇒
(
b
=
d
)
∨
(
b
=
a
∧
d
=
a
)
⇒
b
=
d
{\displaystyle {\begin{array}{cl}&(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 정의. 아래에서
(
∗
)
{\displaystyle (*)}
표기를 한 과정은 정칙성 공리 를 사용하였다.[6]
a
=
c
∧
b
=
d
⇒
{
a
,
{
a
,
b
}
}
=
{
c
,
{
c
,
d
}
}
⇒
(
a
,
b
)
short
=
(
c
,
d
)
short
{\displaystyle a=c\wedge b=d\Rightarrow \{a,\{a,b\}\}=\{c,\{c,d\}\}\Rightarrow (a,b)_{\text{short}}=(c,d)_{\text{short}}}
순서쌍의 같음 ⇒ a = c
(
a
,
b
)
short
=
(
c
,
d
)
short
⇒
{
a
,
{
a
,
b
}
}
=
{
c
,
{
c
,
d
}
}
⇒
(
a
=
c
∨
a
=
{
c
,
d
}
)
∧
(
c
=
a
∨
c
=
{
a
,
b
}
)
⇒
(
a
=
c
)
∨
(
a
=
{
c
,
d
}
∧
c
=
{
a
,
b
}
)
⇒
(
a
=
c
)
∨
(
c
∈
a
∧
a
∈
c
)
⇒
a
=
c
(
∗
)
{\displaystyle {\begin{array}{clc}&(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}}}
순서쌍의 같음 ⇒ b = d
(
a
,
b
)
short
=
(
c
,
d
)
short
⇒
{
a
,
{
a
,
b
}
}
=
{
a
,
{
a
,
d
}
}
⇒
a
∪
{
a
,
b
}
=
a
∪
{
a
,
d
}
⇒
(
b
∈
a
∨
b
=
a
∨
b
=
d
)
∧
(
d
∈
a
∨
d
=
a
∨
d
=
b
)
⇒
(
b
=
a
∨
b
=
d
)
∧
(
d
=
a
∨
d
=
b
)
(
∗
)
⇒
(
b
=
d
)
∨
(
b
=
a
∧
d
=
a
)
⇒
b
=
d
{\displaystyle {\begin{array}{clc}&(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년 로서 는 콰인 의 정의를 확장하였다. 로서-콰인 정의는 자연수 의 선결적 정의를 필요로 한다.
N
{\displaystyle \mathbb {N} }
을 자연수의 집합으로 두고,
x
∖
N
{\displaystyle x\setminus \mathbb {N} }
을
N
{\displaystyle \mathbb {N} }
에 속하지 않는
x
{\displaystyle x}
의 원소들의 집합 이라고 하자. 먼저 함수
φ
{\displaystyle \varphi }
를 정의한다.
φ
(
x
)
=
(
x
∖
N
)
∪
{
n
+
1
:
n
∈
(
x
∩
N
)
}
{\displaystyle \varphi (x)=(x\setminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}}
이 변환은
x
{\displaystyle x}
안의 모든 자연수를 1 증가시킨다. 또한
φ
(
x
)
{\displaystyle \varphi (x)}
는 0을 포함하지 않는다. 그러므로 모든 집합
x
{\displaystyle x}
,
y
{\displaystyle y}
에 대해 다음이 성립한다.
φ
(
x
)
≠
{
0
}
∪
φ
(
y
)
{\displaystyle \varphi (x)\neq \{0\}\cup \varphi (y)}
이제 순서쌍
(
A
,
B
)
{\displaystyle (A,B)}
를 정의한다.
(
A
,
B
)
=
{
φ
(
a
)
:
a
∈
A
}
∪
{
0
∪
φ
(
b
)
:
b
∈
B
}
{\displaystyle (A,B)=\{\varphi (a):a\in A\}\cup \{0\cup \varphi (b):b\in B\}}
이렇게 정의된 순서쌍에서도 첫째, 둘째 성분을 추출할 수 있다. 첫째 성분
A
{\displaystyle A}
는 순서쌍의 원소 중, 0을 원소로 포함하지 않는 모든 집합들에
φ
{\displaystyle \varphi }
변환을 벗겨서 이루어진 집합이다. 둘째 성분
B
{\displaystyle B}
는 순서쌍의 원소 중, 0을 원소로 포함하는 모든 집합들에 적당한 변환을 가하여 이루어진 집합이다. 아래는 이의 공식화이다.
A
=
{
φ
−
1
(
α
)
:
α
∈
(
A
,
B
)
,
0
∉
α
}
{\displaystyle A=\{\varphi ^{-1}(\alpha ):\alpha \in (A,B),0\notin \alpha \}}
B
=
{
φ
−
1
(
β
∖
{
0
}
)
:
β
∈
(
A
,
B
)
,
0
∈
β
}
{\displaystyle B=\{\varphi ^{-1}(\beta \setminus \{0\}):\beta \in (A,B),0\in \beta \}}
유형 이론 과 그의 갈래(새기초 집합론 등)에서, 콰인-로서 순서쌍은 두 성분과 유형이 같다. 그렇기에 이 정의는 (일정 조건을 만족하는 순서쌍들로 이루어진 집합으로 정의된) 함수 가 변수보다 유형이 1 만큼만 크다는 장점이 있다. 이 정의는 자연수 집합이 무한할 때만 의미가 있다. NF 는 그러하지만, 유형 이론이나 NFU 는 그렇지 않다. 로서는 이러한 두 성분과 유형이 같은 순서쌍의 존재성으로부터 무한 공리 를 유추할 수 있음을 증명하였다.
모스의 정의 [ 편집 ]
모스-켈리 집합론 에서는 고유 모임 을 자유로이 사용할 수 있다. 모스 의 정의는 순서쌍의 성분이 고유 모임일 수도 있게끔한다. 이는 쿠라토프스키 정의에서 허용되지 않는다. 그는 우선 집합을 성분으로 하는 순서쌍을 쿠라토프스키의 방식으로 정의한 뒤, 순서쌍을 다음과 같이 재정의하였다.
(
x
,
y
)
=
(
{
0
}
×
s
(
x
)
)
∪
(
{
1
}
×
s
(
y
)
)
{\displaystyle (x,y)=(\{0\}\times s(x))\cup (\{1\}\times s(y))}
여기서의 곱집합은 쿠라토프스키 순서쌍의 집합이고,
s
(
x
)
=
{
∅
}
∪
{
{
t
}
:
t
∈
x
}
{\displaystyle s(x)=\{\emptyset \}\cup \{\{t\}:t\in x\}}
이다.
이는 고유 모임을 성분으로 하는 순서쌍을 허용케 한다. 이는 위의 콰인-로서 정의도 마찬가지이다. 이와 비슷하게 세짝 (영어 : 3-tuple, triple )을 다음과 같이 정의할 수 있다.
(
x
,
y
,
z
)
=
(
{
0
}
×
s
(
x
)
)
∪
(
{
1
}
×
s
(
y
)
)
∪
(
{
2
}
×
s
(
z
)
)
{\displaystyle (x,y,z)=(\{0\}\times s(x))\cup (\{1\}\times s(y))\cup (\{2\}\times s(z))}
한원소 집합 으로 이루어진 집합
s
(
x
)
{\displaystyle s(x)}
의 사용하여 정의한 튜플 은 일종의 유일성을 부여받는다. 즉, 임의의 n -튜플 a 와 m -튜플 b 에 대해, 만약 a = b 이면, n = m 이다. 이는 순서쌍을 이용해 재귀적으로 정의한 튜플에게는 없는 성질이다, (a , b , c ) = (a , (b , c ))는 2-튜플이기도, 3-튜플이기도 하다.
범주론 [ 편집 ]
이 문단은 비어 있습니다. 내용을 추가해 주세요.
같이 보기 [ 편집 ]
↑ Willard Van Orman Quine . 〈53〉. 《Word and Object》 (영어).
↑ Thomas Forster. 《Reasoning about theoretical entities》 (영어).
↑ 가 나 다 Wiener, Norbert (1967). 〈A Simplification of the logic of relations〉. van Heijenoort, Jean. 《From Frege to Gödel: A Source Book in Mathematical Logic》 (학위논문) (영어) 재판. Harvard University Press, Cambridge MA. ISBN 0-674-32449-8 .
↑ Kuratowski, Casimir (1921). “Sur la notion de l'ordre dans la Théorie des Ensembles” (PDF) . 《Fundamenta Mathematicae》 (프랑스어) 2 (1): 161–171. 2013년 10월 21일에 원본 문서 (PDF) 에서 보존된 문서. 2015년 8월 10일에 확인함 .
↑ 이는 0, 1(0 ≠ 1)이 a , b 와 다를 것을 요구하지 않는다는 점에서 하우스도르프의 정의와 다른 정의이다.
↑ 가 나 첫 번째 별표에서, 정칙성 공리에 의해
c
∈
a
,
a
∈
c
{\displaystyle c\in a,\,a\in c}
인 두 집합
a
,
c
{\displaystyle a,c}
는 존재하지 않는다. 두 번째 별표에서, 정칙성 공리에 의해
b
,
d
{\displaystyle b,d}
모두
a
{\displaystyle a}
에 속하지 않는다.