집합, 관계, 함수

과정의 언어

다음 수업은 한 함수, 곧 후자 함수로 자연수를 정의하는데, 이 함수는 단사이며 $1$의 값을 취하지 않는다. 다음 단원은 정수와 유리수를 동치 관계의 동치류로 구성한다. 조합론 수업은 원소의 개수를 전단사 함수로 정의한다. 자연수의 순서는 순서 관계이며, 셋째 단원은 실함수를 합성하고 그 역을 구한다. 이 모든 낱말은 같은 언어에 속하므로, 과정이 앞으로 인용할 첫 정리들과 함께 쓰기 전에 정해 두는 것이 좋다.

무엇을 미리 쓰는지 밝혀 둘 필요가 있다. 예에서는 작은 자연수와 그 순서, 덧셈, 곱셈, 나누어떨어짐, 나눗셈의 나머지를 학교에서 배운 대로 쓴다. 다음 수업은 페아노 공리로 자연수를 정의하고, 이 단원의 수업들은 이 연산들을 정의하고 그 성질을 증명하지만 이 수업의 예는 하나도 쓰지 않으므로 순환은 없다. 이 수업의 어떤 정리도 예에 의존하지 않는다. 수는 정리가 어떻게 작동하는지 보기 위해서만 쓰인다.

받아들이는 것

집합은 대상들의 모임이며, 그 대상을 원소라고 한다. $a \in A$이라고 써서 $a$가 $A$에 속한다는 것을 나타내고, $a \notin A$라고 써서 이를 부정한다. 집합과 속함은 정의하지 않는다. 이들은 산술에서의 $1$과 후자처럼 원시 개념이다. 그러나 모든 성질이 집합을 정하는 것은 아니다. 자기 자신에 속하지 않는 집합들로 이루어진 집합 $R$이 있다면, 「$R$이 $R$에 속하는가」라는 물음에는 답이 없다. $R$의 정의에서 $R \in R \leftrightarrow R \notin R$이 나오기 때문이다. 이 모순은 러셀이 1901년에 발견한 것으로, 집합을 만드는 방법을 제한하게 한다. 성질은 이미 주어진 집합에서 원소를 골라낼 수 있을 뿐이다.

증명 없이 받아들이는 사실 (소박한 집합론의 규칙). 이 수업에서 쓰는 소박한 집합론의 규칙을 증명 없이 받아들인다. 같은 원소를 갖는 두 집합은 같다. 주어진 집합 $A$와 성질 $P$로부터 집합 $\{ x \in A : P(x) \}$, 곧 $A$의 원소 가운데 그 성질을 만족하는 것들의 집합을 만들 수 있다. 또한 공집합, 집합 $\{a, b\}$(원소가 $a$와 $b$뿐인 집합), 집합들의 집합의 원소들의 합집합, 그리고 한 집합의 모든 부분집합의 집합이 존재한다. 자연수 집합의 성질을 갖는 집합의 존재는 다음 수업에서 받아들인다.

이 규칙들은 체르멜로와 프렝켈의 공리에 속하며, 그 연구는 집합론의 몫으로 이 과정의 범위를 넘는다. 그래서 여기서는 받아들이되, 무엇을 쓰는지 정확히 알 수 있도록 명시해 둔다.

양화사의 논리

증명은 연결사 $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$로 진술을 결합한다. 이 연결사들의 법칙은 보조 과정 수리논리학 I: 명제 논리에서 그 언어부터 다룬다. 여기서는 다음을 떠올리는 것으로 충분하다. 함의 $p \rightarrow q$는 $p$가 참이고 $q$가 거짓일 때에만 거짓이며, 그 대우 $\neg q \rightarrow \neg p$와 동치이다. 그리고 드모르간 법칙은 연언과 선언의 부정을 준다.

그러나 집합에 대해 말하려면 모든 원소에 대한 진술이나 어떤 원소에 대한 진술도 필요하다. $P(x)$가 $A$의 원소들의 성질일 때, 진술 $(\forall x \in A)\,P(x)$는 「모든 $x$($A$의 원소)에 대하여 $P(x)$」라고 읽으며, $A$의 모든 원소가 그 성질을 만족한다고 주장한다. 진술 $(\exists x \in A)\,P(x)$는 「어떤 $x$($A$의 원소)가 존재하여 $P(x)$」라고 읽으며, 적어도 한 원소가 그 성질을 만족한다고 주장한다. 그리고 $(\exists! x \in A)\,P(x)$는 그 성질을 만족하는 원소가 정확히 하나 있다고 주장한다. 기호 $\forall$와 $\exists$를 양화사라고 하며, 각각 전칭 양화사와 존재 양화사이다.

증명 없이 받아들이는 사실 (양화사의 부정). 모든 원소가 어떤 성질을 만족한다는 것을 부정하는 것은 어떤 원소가 그것을 만족하지 않는다고 주장하는 것이고, 어떤 원소가 그것을 만족한다는 것을 부정하는 것은 어떤 원소도 그것을 만족하지 않는다고 주장하는 것이다.

이 규칙들은 일계 논리에 속하며 여기서는 받아들인다. 이들은 드모르간 법칙을 일반화한다. $A = \{a, b\}$이면 전칭 진술은 $P(a) \wedge P(b)$이고 존재 진술은 $P(a) \vee P(b)$이기 때문이다. 양화사의 순서는 중요하다. 진술 $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$는 모든 자연수에 대해 그보다 큰 다른 자연수가 있다고 말하며 참이다. 진술 $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$는 모든 자연수보다, 자기 자신보다도 큰 자연수가 있다고 말하며 거짓이다.

진술의 논리적 형식이 그것을 증명하는 방법을 정한다. 이 수업에서 쓰는 전략은 다음과 같으며, 그 논리적 근거는 연역 기법 수업에서 다룬다.

• $(\forall x \in A)\,P(x)$를 증명하려면 임의의 원소 $x$($A$의 원소)를 잡아, $A$에 속한다는 것 말고는 아무것도 가정하지 않고 $P(x)$를 증명한다.
• $(\exists x \in A)\,P(x)$를 증명하려면 $A$의 구체적인 원소 가운데 $P$를 만족하는 것을 보인다. $(\forall x \in A)\,P(x)$를 부정하려면 반례, 곧 그것을 만족하지 않는 원소 하나로 충분하다.
• $p \rightarrow q$를 증명하려면 $p$를 가정하여 $q$를 이끌어 내거나, 대우 $\neg q \rightarrow \neg p$를 증명하거나, $p \wedge \neg q$를 가정하여 모순을 이끌어 낸다.
• $p \leftrightarrow q$를 증명하려면 두 함의 $p \rightarrow q$와 $q \rightarrow p$를 증명한다.

집합

속함, 상등, 포함

집합은 중괄호 안에 원소를 늘어놓는 원소나열법, 예를 들어 $\{1, 2, 3\}$으로 나타낼 수도 있고, 성질을 이용하는 조건제시법, 예를 들어 $\{ n \in \mathbb{N} : n \leq 3 \}$(같은 집합이다)로 나타낼 수도 있다. 외연성 규칙은 집합이 그 원소로 정해진다고 말한다.

여기서 원소나열법에서는 순서도 중복도 상관없다는 것을 알 수 있다. $\{1, 2, 2\}$와 $\{2, 1\}$은 같은 원소를 가지므로 같은 집합이다. 또한 원소가 없는 집합은 하나뿐이며, 그것이 공집합 $\emptyset$이라는 것도 알 수 있다. 원소가 없는 두 집합은 같은 원소를 가지기 때문이다. 곧 둘 다 원소가 없다.

정의 (포함). 집합 $A$가 집합 $B$에 포함된다, 또는 $B$의 부분집합이라는 것은 $A$의 모든 원소가 $B$의 원소라는 것이다.

또한 $A \neq B$이면, $A$를 $B$의 진부분집합이라고 한다.

공집합은 모든 집합 $A$에 포함된다. 함의 $x \in \emptyset \rightarrow x \in A$는 전건이 언제나 거짓이므로 참이기 때문이다. 속함과 포함은 구별해야 한다. $1 \in \{1, 2\}$와 $\{1\} \subseteq \{1, 2\}$는 참이지만 $\{1\} \in \{1, 2\}$는 거짓이다. $\{1, 2\}$의 원소는 $1$과 $2$뿐이고, 집합 $\{1\}$은 그 어느 것과도 같지 않기 때문이다. $\{1\} \neq 1$인데, $1$을 유일한 원소로 갖는 집합은 $1$과 다르기 때문이며, 또 $\{1\} \neq 2$이다.

합집합, 교집합, 차집합

정의 (집합의 연산). $A$와 $B$의 합집합은 적어도 한쪽에 속하는 원소들의 집합이고, 교집합은 양쪽에 다 속하는 원소들의 집합이며, 차집합 $A \setminus B$는 $A$에 속하고 $B$에 속하지 않는 원소들의 집합이다.

$B \subseteq A$일 때, 차집합 $A \setminus B$를 $B$의 $A$에 대한 여집합이라고 한다. 두 집합은 교집합이 공집합일 때 만나지 않는다고 한다.

각 연산은 하나의 연결사에 대응한다. 합집합은 선언에, 교집합은 연언에, 차집합은 연언과 부정에 대응한다. 그렇다면 논리의 각 법칙은 집합의 법칙을 낳는다. 합집합과 교집합은 교환적이고 결합적이며 서로에 대해 분배적이다. 연결사가 그렇기 때문이다. 이 모든 법칙은 다음 정리처럼 증명된다. 여집합은 언제나 어떤 기준 집합에 대해 취한다. $B$에 없는 모든 것의 집합은 러셀 역설을 다시 낳기 때문이다.

멱집합

한 집합의 부분집합들은 그 자체로 다시 집합을 이루며, 그 존재는 처음에 받아들였다. $A$의 멱집합은 $\mathcal{P}(A)$로 나타내며, $A$의 부분집합들을 원소로 갖는 집합이다.

예를 들어 $\{1, 2, 3\}$의 멱집합은 여덟 개의 원소를 갖는다. 공집합, 세 개의 한원소 집합, 세 개의 두원소 집합, 그리고 $\{1, 2, 3\}$ 자신이다.

임의의 집합 $A$에 대하여, 공집합과 $A$ 자신은 $\mathcal{P}(A)$의 원소이며, 각 $a$($A$의 원소)에 대하여 $\{a\} \in \mathcal{P}(A)$이지만, $a$는 일반적으로 $\mathcal{P}(A)$의 원소가 아니다. 조합론 수업에서는 $n$개의 원소를 갖는 집합이 $2^n$개의 부분집합을 갖는다는 것을 증명한다.

순서쌍과 곱집합

평면의 점, 분수, 아직 하지 않은 뺄셈은 정해진 순서로 놓인 두 대상으로 기술된다. 쌍 $(3, 5)$는 쌍 $(5, 3)$이 아니다. 집합 $\{3, 5\}$는 이를 나타내는 데 쓸 수 없다. $\{5, 3\}$과 같기 때문이다. 순서쌍에 요구하는 것은 하나뿐인데, 그것이 특성 성질이다. 두 쌍이 같을 필요충분조건은 첫째 성분이 일치하고 둘째 성분이 일치하는 것이다. 쿠라토프스키는 1921년에 이 성질을 갖는 대상을 구성하는 데 집합의 개념만으로 충분하다는 것을 보였다.

정의 (순서쌍). 첫째 성분이 $a$이고 둘째 성분이 $b$인 순서쌍은 다음 집합이다.

특성 성질이 증명되면 쿠라토프스키의 구성은 잊어도 된다. 과정이 쌍에 대해 말하는 모든 것은 이 성질에서 나온다.

정의 (곱집합). $A$와 $B$의 곱집합은 첫째 성분이 $A$에 속하고 둘째 성분이 $B$에 속하는 쌍들의 집합이다.

표기 $\{ (a, b) : a \in A \wedge b \in B \}$ 자체는 받아들인 규칙 가운데 하나가 아니다. 그 규칙들은 이미 만들어진 집합에서 원소를 분리하는 것만 허용한다. 그러나 이 집합은 존재한다. $a \in A$이고 $b \in B$이면 집합 $\{a\}$와 $\{a, b\}$는 $A \cup B$에 포함되므로 $\mathcal{P}(A \cup B)$의 원소이다. 여기서 쌍 $(a, b) = \{ \{a\}, \{a, b\} \}$이 $\mathcal{P}(A \cup B)$에 포함된다는 것, 곧 $\mathcal{P}(\mathcal{P}(A \cup B))$의 원소라는 것을 알 수 있다. 따라서 곱집합은 받아들인 규칙이 존재를 보장하는 집합 안에서 분리로 만들어진다. $A \cup B$는 $\{A, B\}$의 원소들의 합집합이며, 거기서 멱집합을 두 번 취한다.

이 이름은 데카르트를 떠올리게 한다. 해석기하의 평면이 $\mathbb{R} \times \mathbb{R}$이다. 곱은 교환적이지 않다. $\{1\} \times \{2\}$는 $(1, 2)$만을 포함하고 $\{2\} \times \{1\}$은 $(2, 1)$만을 포함하는데, 특성 성질에 의해 뒤의 것은 앞의 것과 다르다.

관계

$2$가 $6$을 나눈다, $3$이 $5$보다 작다, 또는 두 날짜가 같은 요일이라고 말하는 것은 어떤 대상들의 쌍이 관계되어 있다고 주장하는 것이다. 그렇다면 관계는 그것이 묶는 쌍들로 정해지며, 쌍들의 집합으로 정의할 수 있다.

정의 (관계). $A$에서 $B$로의 관계는 부분집합 $R$(곱 $A \times B$에 포함되는 것)이다. $A$ 위의 관계는 $A$에서 $A$로의 관계이다. $(a, b) \in R$일 때, $a$는 $b$와 $R$에 의해 관계되어 있다고 한다.

예를 들어 $\{1, 2, 3\}$ 위의 관계 「작거나 같다」는 쌍들의 집합 $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$이다. 자주 쓰는 관계에서는 두 항 사이에 $a \leq b$나 $a \mid b$ 같은 기호를 쓰며, $(a, b) \in R$라고 쓰지 않는다. 집합 위의 관계의 네 성질이 과정 전체에 걸쳐 되풀이된다.

정의 (관계의 성질). 관계 $R$($A$ 위의 관계)는 각각 다음 조건을 만족할 때 반사적, 대칭적, 반대칭적, 추이적이라고 한다.

• 각 원소가 자기 자신과 관계되어 있으면 반사적이다: $(\forall a \in A)\,((a, a) \in R)$.
• $a$가 $b$와 관계되어 있으면 $b$도 $a$와 관계되어 있을 때 대칭적이다: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$.
• 양방향으로 관계된 두 원소가 같을 때 반대칭적이다: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$.
• $a$가 $b$와 관계되어 있고 $b$가 $c$와 관계되어 있으면 $a$도 $c$와 관계되어 있을 때 추이적이다: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

$A \times A$의 격자에서 관계는 점들의 집합이다. 쌍 $(a, a)$로 이루어진 대각선 전체를 포함하면 반사적이고, 그 그림이 대각선에 대해 대칭이면 대칭적이며, 대각선 밖의 어떤 점도 그 대칭점이 관계에 들어 있지 않으면 반대칭적이다. 반대칭은 「대칭이 아님」을 뜻하지 않는다. 상등 관계는 두 성질을 다 가지며, 연습 문제 1은 둘 다 갖지 않는 관계를 요구한다.

동치 관계

관계 「홀짝이 같다」는 부분적인 상등처럼 행동한다. 한 측면, 곧 홀짝에서 일치하는 수들을 같은 것으로 보고 나머지 측면은 무시한다. 이렇게 행동하게 하는 세 성질에는 이름이 있다.

정의 (동치 관계). $A$ 위의 관계가 반사적, 대칭적, 추이적일 때 동치 관계라고 한다. 이때 $a \sim b$라고 쓰고, $a$는 $b$와 동치라고 한다. $a$의 동치류는 $a$와 동치인 원소들의 집합이며, 그 각 원소는 그 동치류의 대표원이다.

모든 동치류의 집합을 몫집합이라 하고 $A/{\sim}$로 나타낸다.

동치 관계의 예로는 각 동치류가 원소 하나만 갖는 상등 관계, 동치류가 둘인 「홀짝이 같다」, 동치류가 셋인 「$3$으로 나눈 나머지가 같다」, 그리고 예제 3에서 다루는, 동치류가 일곱인 「같은 요일이다」가 있다. 일반적으로 $g$가 $A$ 위에서 정의된 함수이면 관계 $g(x) = g(y)$는 상등 관계로부터 세 성질을 물려받으며, 예제 5는 모든 동치 관계가 이런 꼴임을 보인다.

따라서 동치류는 집합을 겹치지 않는 블록으로 나눈다. 집합을 나누는 이 방식은 따로 정의할 만하다.

정의 (분할). 집합 $A$의 분할은 $A$의 부분집합들의 집합으로서, 그 부분집합들(블록이라 한다)이 공집합이 아니고, 어느 둘도 만나지 않으며, 그 합집합이 $A$인 것이다. 동치인 말로 하면, $A$의 각 원소가 정확히 한 블록에 속한다.

따라서 $A$ 위의 동치 관계를 주는 것과 $A$의 분할을 주는 것은 같은 것을 말하는 두 방식이다. 예제 4는 이를 이용하여 동치 관계를 센다. 몫집합은 새로운 집합으로 본 분할이다. $A$에서 $A/{\sim}$로 옮겨 가면 동치인 원소들이 하나로 합쳐진다.

마찬가지로 유리수 수업에서는 두 분수 $(p, q)$와 $(r, s)$가 $ps = qr$일 때 동치이고 유리수는 하나의 동치류이며, 합동식 수업에서는 $n$을 법으로 하는 잉여류가 정수 사이의 한 동치 관계의 동치류이다.

순서 관계

앞의 예의 나누어떨어짐 관계는 대칭적이지 않고 반대칭적이었다. 원소들을 같은 것으로 보는 것이 아니라 순서를 매긴다. 이런 관계에는 고유한 이름이 있다.

정의 (순서). $A$ 위의 관계가 반사적, 반대칭적, 추이적일 때 순서 관계 또는 부분 순서라고 한다. 이때 $a \preceq b$라고 쓰고, $a$가 $b$에 앞선다고 한다. 두 원소가 언제나 비교 가능할 때, 곧 임의의 $a$와 $b$에 대하여 $a \preceq b$이거나 $b \preceq a$일 때 그 순서는 전순서이다.

순서의 예로는 자연수 사이의 관계 $\leq$(자연수의 연산 수업에서 증명하는 삼분법에 의해 전순서이다), 포함 관계(그 성질의 정리에 의해 순서이지만, $\{1\}$과 $\{2\}$가 비교 가능하지 않으므로 전순서가 아니다), 그리고 자연수 사이의 나누어떨어짐 관계(그 반대칭성은 나누어떨어짐 수업에서 증명하며, $2 \mid 3$도 $3 \mid 2$도 성립하지 않으므로 전순서가 아니다)가 있다. 유한 순서는 하세 도표로 그린다. 각 원소마다 점을 하나 두고, $b$를 $a$보다 위에 두는 것은 $a$가 $b$에 앞설 때이며, 둘 사이에 다른 원소가 없을 때 선분으로 잇는다. 추이성 덕분에 나머지 선분은 생략할 수 있다.

정의 (한계와 극단적인 원소). $\preceq$를 $A$ 위의 순서, $X$를 $A$의 부분집합이라 하자. $X$의 한계와 극단적인 원소를 다음과 같이 정의한다.

• 원소 $c$($A$의 원소)가 $X$의 하계라는 것은 $X$의 모든 원소에 앞서는 것이고, 상계라는 것은 $X$의 모든 원소가 그것에 앞서는 것이다.
• $X$의 최소원은 $X$의 하계로서 $X$에 속하는 것이고, 최대원은 상계로서 $X$에 속하는 것이다.
• 원소 $m$($X$의 원소)는 $X$의 원소 가운데 그것과 다른 어떤 것도 그것에 앞서지 않을 때 극소원이고, 그것이 $X$의 원소 가운데 자기와 다른 어떤 것에도 앞서지 않을 때 극대원이다.
• $X$의 하한은 그 하계들의 집합의 최대원이고, 상한은 그 상계들의 집합의 최소원이다. 단, 존재할 때에 한한다.