[군론]Section0 - SETS AND RELATIONS(2)

목차

 

기수(Cardinality, 원소의 개수)

 

집합 $X$내의 원소의 수를 $X$의 기수(카디널리티)라고 하며, 종종 $|X|$로 표시한다.

 

예를 들면 $|\{ 2,5,7 \}| = 3$이다.

 

두 집합이 같은 카디널리티를 가지고 있는지 알아내는 것은 수학적으로 뿐 아니라 응용의 측면에서도 중요한데, 

 

두 집합이 모두 유한한 경우에는 문제가 없다; 집합의 원소를 세면 되기 때문이다.

 

하지만 $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$은 같은 카디널리티를 가지고 있을까?

 

두 집합 $X$와 $Y$가 같은 카디널리티를 가진다는 것을 확신하기 위해

 

$X$의 $x$를 $Y$의 단 하나의 $y$와 짝지어 보여주려 시도할 수 있다.

 

예를 들어 집합 $X = \{ 2,5,7 \}$과 $Y = \{ ?,!,\# \} $ 에 대해

 

$$2 \leftrightarrow ?, 5 \leftrightarrow \#, 7 \leftrightarrow !$$

 

와 같은 순서쌍은 두 집합이 같은 카디널리티를 가진다는 것을 보여준다.

 

또한 이 순서쌍을 $\{ (2,?), (5, \# ), (7,!) \}$로 나타낼 수 있는데,

 

이는 $X \times Y$의 부분집합으로서, $X$와 $Y$의 관계로 볼 수 있다.

 

계속해서 다음의 순서쌍

은 $\mathbb{Z}$와 $\mathbb{Z}^+$가 같은 카디널리티를 가진다는 것을 보여준다.

 

이러한 순서쌍 혹은 짝지음, 즉 $X$와 $Y$가 같은 카디널리티를 가진다는 것을 보여주는 것을

 

$X$와 $Y$ 사이의 특별한 유형의 관계인 일대일 대응(one-to-one correspondence) $\leftrightarrow$이라고 부른다.

 

이 관계에서 $X$의 각 원소 $x$는 정확히 한 번만 나타나므로, 이 일대일 대응을 정의역이 $X$인 함수로 간주할 수 있다.

 

함수의 치역은 $Y$인데, $Y$의 모든 원소 $y$가 모든 짝지음 $x \leftrightarrow y$에 등장하기 때문이다.

 

이를 정의로 명확히 하자.

 

0.12 Definition

 

함수 $\phi : X \rightarrow Y$가 일대일(one-to-one)이라 함은

 

$\phi(x_1) = \phi(x_2)$가 $x_1 = x_2$일 때만 성립하는 경우를 가리킨다.

 

함수 $\phi$가 $Y$에 대해 전사(onto)라 함은, $\phi$의 치역(range)이 $Y$가 되는 경우를 의미한다.■

 

Another Terminology

• 주입(injection)
  모든 서로 다른 입력 $x_1$과$x_2$에 대해 서로 다른 출력 $\phi (x_1)$과 $\phi (x_2)$를 가지는 함수.
  즉, 다른 입력값이 같은 출력값으로 매핑되지 않는다.
• 전사(surjection)
  함수의 치역이 공역$Y$와 정확히 일치할 때, 즉 $Y$의 모든 원소가 적어도 하나의 $X$의 원소에 의해 매핑될 때.
• 전단사(bijection)
  함수가 주입이면서 전사인 경우, 즉 $X$의 모든 원소가 $Y$의 유일한 원소에 대응되고
  $Y$의 모든 원소가 $X$의 모든 원소에 의해 매핑될 때 해당된다.

 

집합 $X \times Y$의 부분집합이 $X$에서 $Y$로의 일대일 함수 $\phi$인 경우,

 

모든 $x \in X$는 $\phi$ 내에서 정확히 하나의 순서쌍의 첫 번째 구성원으로 나타나고,

 

모든 $y \in Y$역시 정확히 하나의 순서쌍의 두 번째 구성원으로 나타난다.

 

따라서 모든 순서쌍 $(x, y)$에서 첫 번째와 두 번째 구성원을 교환하여 얻은 순서쌍의 집합 $(y, x)$는

 

$Y \times X$의 부분집합을 형성하며, 이는 $Y$에서 $X$로의 일대일 전사함수를 제공한다.

 

이 함수를 $\phi$의 역함수라고 하며, $\phi ^{-1}$로 표기한다.

 

요약하자면 $\phi$가 $X$를 $Y$로 일대일 전사로 매핑하고 $\phi (x) = y$인 경우,

 

$\phi ^{-1}$은 $Y$를 $X$로 일대일 전사로 매핑하며, $\phi ^{-1}(y) = x$이다.

 

0.13 Definition

 

두 집합 $X$와 $Y$가 같은 카디널리티를 가진다는 것은 $X$에서 $Y$로의 일대일 함수가 존재한다는 것을 의미한다.

 

즉, $X$와 $Y$ 사이에 일대일 대응이 존재한다는 뜻이다.■

 

0.14 Example

 

함수 $f: \mathbb{R} \rightarrow \mathbb{R}$는 $f(x) = x^2$일 때 일대일 함수가 아니다.

 

왜냐하면 $f(2)=f(-2)=4$이지만 $2 \neq -2$이기 때문이다.

 

또한 이 한수는 $\mathbb{R}$에 대해 전사 함수도 아니다.

 

왜냐하면 치역이 $\mathbb{R}$ 내의 모든 음이 아닌 숫자들의 적절한 부분집합이기 때문이다.

 

그러나 $g: \mathbb{R} \rightarrow \mathbb{R}$로 정의된 $g(x) = x^3$은 일대일이면서도 $\mathbb{R}$에 대해 전사 함수이다.▲

 

위에서 $\mathbb{Z}$와 $\mathbb{Z}^+$가 같은 카디널리티를 가진다는 것을 보였다.

 

이 카디널 수를 $ℵ_0$(알레프 제로)라 표기하며, $|Z| = |Z^+| = ℵ_0$라고 한다.

 

무한 집합의 적절한 부분집합이 전체 집합과 같은 카디널리티를 가진다는 것은 무척 흥미로운 사실이다;

 

무한 집합은 이와 같은 성질을 가지는 집합으로 정의될 수 있다.

 

계속해서 자연스러운 질문은 모든 무한 집합이 $\mathbb{Z}$와 같은 카디널리티를 가지는가 하는 것이다.

 

어떤 집합이 카디널리티 $ℵ_0$를 가지려면 해당 집합의 모든 원소를 무한히 긴 열에 나열할 수 있어야 하며,

 

그렇게 함으로써 $\mathbb{Z}^+$를 사용해 "번호를 매길"수 있어야 한다.

 

아래의 그림은 이 방식이 $\mathbb{Q}$에 대해 가능함을 보여준다.

 

분수의 정사각형 배열은 오른쪽과 아래로 무한히 확장되며 $\mathbb{Q}$의 모든 멤버를 포함한다.

 

계속해서 이 배열을 통해 길을 만들며 멤버를 감아가는 문자열을 그릴 수 있다.

 

분수들이 이 문자열에 붙어있다고 상상하고 문자열의 시작 부분을 잡고 화살표 방향으로 당기면,

 

문자열이 펴지고 $\mathbb{Q}$의 모든 원소들이 $0, 1, -1, \frac{1}{2}, -\frac{1}{2}, \frac{1}{3}, ...$과 같이 무한히 긴 열에 놓인다.

 

따라서 $|\mathbb{Q} |$ 역시 $ℵ_0$이다.

 

계속해서 이번에는 집합 $S = \{ x \in \mathbb{R} | 0 < x < 1 \}$이 카디널리티 $ℵ_0$을 가진다고 가정해보자.

 

이는 $S$의 원소를 무한히 내려가는 열에 무한소수로 나열할 수 있다는 의미이다. 예를 들면 아래와 같다.

 

0.3659663426 ···
0.7103958453 ···
0.0358493553 ···
0.9968452214 ···
...

하지만 이와 같은 배열은 $S$내의 어떤 숫자를 반드시 누락시키게 된다.

 

왜냐하면 임의의 무한소수 사이에는 반드시 또 다른 무한소수가 존재하기 때문이다(이 부분은 책의 예시와 다르다).

 

심지어 그 무한소수 역시 무한히 많이 존재하기 때문에, $S$는 $\mathbb{Z}^+$와 짝짓기에는 원소가 너무 많다.

 

즉, $S$의 카디널리티는 $ℵ_0$보다 큰데, 여기서 더 나가 연습문제 15는 $S$와 $\mathbb{R}$이 같은 수의 원소를 가진다는 것을 증명한다.

 

이때 단순히 $\mathbb{R}$의 카디널리티는 $|\mathbb{R} |$이라고 표시한다.

 

분할과 동치 관계(Partitions and Equivalence Relations)

 

집합이 서로소(disjoint)라는 것은 그 중 어떤 두 집합도 공통의 원소를 가지고 있지 않을 때를 의미한다.

 

나중엔 대수적 구조(예를 들어, 덧셈의 개념)를 가진 집합을 서로소인 부분집합으로 나누어,

 

관련된 대수적 구조에서 원소가 되도록 하는 경우를 다룰 것이다.

 

이 섹션을 집합의 이러한 분산, 또는 분할에 대한 공부로 마무리한다.

 

0.16 Definition

 

집합 $S$의 분할은 $S$의 비어 있지 않은 부분집합들의 모음으로서, 

$S$의 모든 원소가 정확히 하나의 부분집합에 속하는 것을 말한다. 이러한 부분집합들을 분할의 셀(cells)이라고 한다. ■

 

집합 S의 분할을 논할 때, $S$의 원소 $x$를 포함하는 셀을 $\overline{x}$로 표시한다.

 

0.17 Example

 

양의 정수 집합 $\mathbb{Z}^+$를 2로 나누어질 수 있는 짝수 양의 정수들의 부분집합과

 

2로 나누었을 때 1의 나머지를 가지는 홀수 양의 정수들의 부분집합으로 나누면,

 

$\mathbb{Z}^+$의 두 셀로 이루어진 분할을 얻을 수 있습니다. 예를 들어, 우리는 다음과 같이 쓸 수 있다:

 

$$\overline{14} = \{2, 4, 6, 8, 10, 12, 14, 16, 18, ...\}$$

 

또한, $\mathbb{Z}^+$를 3개의 셀로 분할할 수도 있다.

 

하나는 3으로 나누어질 수 있는 양의 정수들로 구성되고,

 

다른 하나는 3으로 나누었을 때 1의 나머지를 가지는 모든 양의 정수들을 포함하며,

 

마지막 셀은 3으로 나누었을 때 2의 나머지를 가지는 양의 정수들을 포함한다.

 

일반화하자면, 각 양의 정수 $n$에 대해, 우리는 양의 정수를 $n$으로 나누었을 때 나머지가 $0, 1, 2, ..., n−1$이 되는지에 따라

 

$\mathbb{Z}^+$를 n개의 셀로 분할할 수 있다.

 

이 셀들은 $\mathbb{Z}^+$에서 modulo n에 대한 residue이다.

 

연습문제 35는 $n=2,3,5$인 경우에 대한 이러한 분할을 보여주도록 요청한다. ▲

 

집합 $S$의 각 분할은 자연스럽게 $S$에 대한 관계 $\mathfrak{R}$을 생성한다.

 

즉, $x,y∈S$에 대해, $x$와 $y$가 분할의 같은 셀 안에 있을 경우에만 $x\mathfrak{R} y$로 정의한다.

 

집합 표기법에서, $x\mathfrak{R} y$를 $(x,y)∈\mathfrak{R}$로 쓴다(정의 0.7 참조).

 

조금 생각해보면, 이 관계 R은 다음 정의에서 동치 관계의 세 가지 성질을 만족함을 알 수 있다.

 

Modulo and Residue

 

모듈로(modulo)와 잉여류(residue)는 수학, 특히 정수론과 대수학에서 중요한 개념이다. 

 

이 개념들은 정수를 특정 수로 나누었을 때의 나머지를 다루는 연산과 관련이 있다.

 

• 모듈로(modulo)
  모듈로 연산은 두 정수의 나눗셈에 대한 나머지를 구하는 연산이다.
  예를 들어, "8 모듈로 3"은 8을 3으로 나누었을 때의 나머지인 2를 의미하며, 이를 수학적으로 표현하면, $8 mod3=2$입니다.
  모듈로 연산은 주기적인 패턴이나 순환하는 구조를 다룰 때 특히 유용하다.
  예를 들어, 시계는 12시간 또는 24시간 주기로 순환하기 때문에 모듈로 12 또는 모듈로 24 연산으로 표현할 수 있다.
• 잉여류(Residue)
  잉여류는 모듈로 $n$에 대해 나머지가 같은 정수들의 집합을 의미한다.
  예를 들어, 모듈로 3에 대한 잉여류는 나머지가 0, 1, 2인 세 개의 집합으로 구분될 수 있다.
  나머지가 0인 모든 정수들은 하나의 잉여류를 형성하고,
  나머지가 1인 모든 정수들은 또 다른 잉여류를,
  나머지가 2인 모든 정수들은 세 번째 잉여류를 형성하는 식이다.
  예를 들어, 모듈로 4에 대한 잉여류를 고려해보면, 
  나머지가 0인 정수들의 집합(4의 배수), 
  나머지가 1인 정수들의 집합(4로 나누었을 때 나머지가 1인 수), 
  나머지가 2인 정수들의 집합, 
  그리고 나머지가 3인 정수들의 집합으로 나뉜다.

모듈로와 잉여류의 개념은 암호학, 컴퓨터 과학, 음악 이론, 그리고 다양한 수학적 증명과 이론에서 널리 사용된다. 

 

이 개념들은 특정 범위 내에서 숫자들의 동등성을 다루며, 

 

이를 통해 복잡한 문제를 더 단순한 형태로 변환하고 해결하는 데 도움을 준다.

 

0.18 Definition

 

집합 $S$의 동치 관계 $\mathfrak{R}$은 $S$의 모든 $x, y, z$에 대해 다음 세 가지 성질을 만족한다.

 

1. (반사성) $x\mathfrak{R} x$
2. (대칭성) $x\mathfrak{R} y$ 라면 $y\mathfrak{R} x$
3. (추이성) $x\mathfrak{R} y$ 이고 $y\mathfrak{R} z$라면 $x\mathfrak{R} z$

$S$의 분할에 해당하는 관계 $\mathfrak{R}$이 정의에서 대칭성 조건을 만족하는 이유를 설명하려면

 

$y$와 $x$가 같은 셀 안에 있다면(즉 $x\mathfrak{R} y$이면), $x$도 $y$와 같은 셀 안에 있다는 것($y\mathfrak{R} x$)

을 관찰하기만 하면 된다. 반사성과 추이성에 대한 관찰은 연습문제 28로 남겨둔다.

 

0.19 Example

 

어떤 비어있지 않은 집합 $S$에 대해서도 $S \times S$의 부분집합 $\{(x, x)|x\in S\}$에 의해 정의된

 

등가 관계인 동등 관계($=$)는 동치관계이다.▲

 

0.20 Example

 

(n에 대한 합동) $n \in \mathbb{Z}^+$일 때, $\mathbb{Z}^+$를 모듈로 n에 따른 잉여류로 분할하는 것에

 

대응하는 동치관계는 모듈로 n에 대한 합동이다. 이는 때때로 $\equiv _n$로 표시되기도 한다.

 

$a \equiv _n b$라고 쓰는 대신, 일반적으로 $a \equiv b (mod n)$ 이라고 쓰며, 이는

 

"a 모듈로 n에 대해 b와 합동이다." 라고 읽는다.

 

예를 들어, 15와 27은 4로 나누었을 때 나머지가 3이기 때문에, $15 \equiv 27 (mod 4)$가 성립한다.▲

 

0.21 Example

 

집합 $\mathbb{Z}$에 대한 관계 $\mathfrak{R}$을 $n\mathfrak{R} m$은 $nm \geq 0$일 때만 성립한다고 정의하고,

 

$\mathfrak{R}$이 동치 관계인지 결정해보자.

 

• 반사성: $a\mathfrak{R} a$, 왜냐하면 모든 $a \in \mathbb{Z}$에 대해 $a^2 \geq 0$ 이기 때문이다.
• 대칭성: 만약 $a\mathfrak{R} b$라면 $ab \geq 0$이므로 $ba \geq 0$이므로 $b\mathfrak{R} a$이다.
• 추이성: 만약 $a\mathfrak{R} b$이고 $b\mathfrak{R} c$라면 $ab \geq 0$이고 $bc \geq 0$이다.

만약 $b^2 > 0$임을 알았다면 $bc \geq 0$이므로 $a\mathfrak{R} c$를 추론할 수 있다.

 

하지만 $b=0$인 경우는 따로 검토해야 하는데,

 

잠시 생각해보면 $-3\mathfrak{R} 0$과 $0\mathfrak{R} 5$는 성립하지만 $-3\mathfrak{R} 5$는 성립하지 않는다.

 

따라서 관계 $\mathfrak{R}$은 추이성이 없으므로 동치 관계가 아니다.▲

 

위에서 본 것처럼, 분할은 자연스러운 동치 관계를 제공한다.

 

이제 집합에 대한 동치 관계가 집합의 자연스러운 분할을 제공한다는 것을 알 수 있다.

 

다음의 정리는 두 결과를 참고용으로 기술한다.

 

0.22 Theorem

 

(동치 관계와 분할)$S$가 비어있지 않은 집합이라 하고, $S$에 대한 동치 관계를 $\sim$라 하면 $\sim$은 $S$의 분할을 만든다.

 

그렇다면 여기서

 

$$\overline{a} = \{x\in S | x \sim a\}$$

 

이다.

 

또한 $S$의 각 분할은 $S$에 대한 동치관계 $\sim$을 생성하는데, $a\sim b$는 a와 b가 분할의 같은 셀 안에 있을 때만 성립한다.

 

Proof

 

다른 셀 $\overline{a} = \{x\in S | x \sim a\}$들이 $S$의 분할을 이룬다는 것을 보여야 한다.

 

즉 $S$의 모든 원소가 어떤 셀에 속하고, 만약 $a \in \overline{b}$ 라면 $\overline{a} = \overline{b}$가 된다.

 

$a \in S$라 하자. 반사성 조건에 의해 $a \in \overline{a}$이므로 $a$는 적어도 하나의 셀에 속한다.

 

이어서 $a$가 또 다른 셀 $\overline{b}$에도 속한다고 가정하자.

 

$\overline{a} = \overline{b}$가 집합으로서 같다는 것을 보여야 하며,

 

이것은 $a$가 하나 이상의 셀에 속할 수 없다는 것을 보여줄 것이다.

 

두 집합이 같다는 것을 보이는 표준적인 방법은 다음과 같다:

 

각 집합이 다른 집합의 부분집합임을 보인다.

 

$x \in \overline{a}$라고 하자. 그러면 $x \sim a$이다. 하지만 $a \in \overline{b}$이므로 $a \sim b$이다.

 

그러면 추이성 조건에 따라 $x \sim b$이므로 $x \in \overline{b}$이다.

 

계속해서 $y \in \overline{b}$라고 하자. 그러면 $y \sim b$이다. 하지만 $a \in \overline{b}$이므로 $a \sim b$이고,

 

대칭성에 의해 $b \sim a$이다. 그러면 추이성에 의해 $y \sim a$이므로 $y \in \overline{a}$이다.

 

따라서 $\overline{b} = \overline{a}$가 되고, 증명은 완료된다.◆

 

동치 관계에서 비롯된 분할의 각 셀은 동치류이다.