순서쌍

ordered pair

$x in A$와 $y in B$에 대해 $(x, y)$ 꼴로 나타낸 수학적 객체를 말한다.

중딩때부터 함수에서 볼 수 있다.

동치 관계가 $(x_1, y_1) = (x_2, y_2) iff x_1 = x_2 land y_1 = y_2$와 같이 정의되는데, 쉽게 말해서 괄호의 양쪽에 들어가는 숫자가 전부 같아야만 같다고 쳐준다는 소리이다.

쉽게 말해서 $(a, b) neq (b, a)$이다. 이 작은 차이가 이항 관계에서 반사성(symmetricity)을 조건으로 두느냐 두지 않느냐의 차이를 발생시킨다.

이러한 순서쌍을 모은 집합을 곱집합이라고 하고, 곱하는 연산을 set-product라고 한다. 엄밀하게는 집합 $A$와 $B$에 대해

로 정의된다.

교재나 맥락에 따라 set-product라고 하지 않고 카티전 곱(Cartesian product)이라고 하는 경우도 많은데, 보통 조합론이나 이산수학에서 그렇게 부른다. 조금만 생각해 봐도 $A times B$의 원소가 $A$와 $B$가 독립적으로 발생하는 경우를 모두 나열한 것임을 알 수 있다. 때문에 유한집합에서는 $|A times B| = |A| times |B|$라는 등식이 성립한다.

한편, 공집합과 곱하면 항상 공집합이 된다. 공집합에서는 $forall x in$가 항상 부정되기 때문.

곱하는 집합이 같은 경우, 거듭제곱으로 표현할 수도 있다.

이를 Cartesian power라 부른다.

분배법칙이 깔끔하게 성립하는데, 조금만 고민해보면 알겠지만 이는 $land$가 분배법칙을 성립시키기 때문이다.

tuple

위 곱의 정의를 사용해 일반화해서 포장하면 $(x_1, x_2, x_3, dots, x_n)$ 형태의 $n$-tuple이란 $prod A_n$의 원소로 정의할 수 있다. 이런 고차항 튜플은 $mathbb R^n$ 유클리드 공간이나 $n$차 관계가 등장할 때마다 지겹게 나오니 그런가보다 하자.

나중에 n차 튜플 대수(NTA)를 배우면 더 기상천외한 성질을 볼 수 있다.

그냥 '동치관계를 만족하는 어떤 것' 정도만으로도 충분히 well-defined되지만, 집합론에 심취한 퍼거 학자들은 순서쌍 및 n차 튜플을 집합으로 환원시키는 여러 구성적 정의들을 떠올리기도 했다. 제안된 방법이 한두가지가 아니지만 학계에서 가장 널리 쓰이는 방법은 1921년 쿠라토프스키(Kuratowski)가 제시한 방식[1]으로, 다음과 같다.

우선 비가환성을 만족하는지 확인해 보자. $(x, y) = {{x}, {x, y}}$이고 $(y, x) = {{y}, {x, y}}$이므로 두 집합이 상등일 필요충분조건은 $x = y$인 것이다. 이는 우리가 순서쌍에서 기대하는 결과와 정확히 일치한다.

또한 $x_1 = x_2, y_1 = y_2$일 때 $(x_1, y_1) = (x_2, y_2)$를 만족함을 직관적으로 확인할 수 있다.

이어서 역, 즉 ${{x_1}, {x_1, y_1}} = {{x_2}, {x_2, y_2}}$ 일때 $x_1 = x_2 land y_1 = y_2$ 또한 성립하는지 살펴보자. 상등식을 전개하면

아오시발
대충 눈에 들어오겠지만 이따위로 장황하게 전개되는 이유는 $x_1, y_1$에 대한 전제가 없기 때문으로, 뇌절을 막기 위해 세 case로 나눠서 해결하자. 우선 $x_1 = y_1 land x_2 = y_2$인 경우는 그냥 ${{x_1}} = {{x_2}}$이므로 자명하다. 이어서 $x_1 = y_1$라고 가정하자. 참고로 이는 $x_2 = y_2$인 경우의 가정과 순서가 동일하므로 생략한다.

우선 ${x_1, y_1} = {x_1}$이 되므로 ${x_2} = {x_1} iff x_1 = x_2$는 쉽게 보여진다. 이를 대입하면 ${x_1, y_2} = {x_1} iff x_1 = y_2$가 되는데, 가정에 의해 $x_1 = y_1$이므로 이를 대입하면 $y_1 = y_2$임이 보여진다.

다음으로 $x_1 neq y_1$인 경우을 살펴보자. 이 전제가 있으면 ${x_1, y_1}$ 등은 원소가 하나인 ${x_2}$의 부분집합이 될 수 없으며, 따라서 선언 제거가 가능하다. 같은 방식으로 위 식을 정리하면 이번에도 ${x_2} = {x_1} iff x_1 = x_2$가 드러나고, ${x_1, y_1} = {x_2, y_2}$도 도출된다. 이에 따르면 $y_1 in {x_2, y_2}$ 이므로 $y_1 = x_2 lor y_1 = y_2$일 것이다.

앞서 보인 대로 $x_1 = x_2$이고 가정에 의해 $x_1 neq y_1$ 따러서 $x_2 neq y_1$ 을 대입하면 선언 제거로 $y_1 = y_2$이다.