집합은 어떤 대상이 포함되는지를, 함수는 한 대상이 다른 대상으로 어떻게 대응되는지를 표현한다. 원소와 부분집합, 공역과 치역처럼 비슷해 보이는 말을 구별해야 이후의 계산과 증명도 정확해진다. 집합 연산을 논리식으로 풀어 보고, 함수의 성질을 정의역과 공역까지 포함해 판단해 보자.
연습문제로 바로 가기 · 먼저 풀어 본 뒤 각 문제의 해설 보기를 눌러 확인할 수 있다.
1. 집합을 표현하는 방법
집합은 서로 구별되는 대상들의 순서 없는 모임이다. 는 가 의 원소라는 뜻이고, 는 원소가 아니라는 뜻이다. 순서와 중복은 집합을 바꾸지 않으므로
원소나열법은 처럼 원소를 직접 쓰는 방식이다. 조건제시법은 처럼 조건으로 정한다. 말줄임표를 사용할 때도 원소를 결정하는 규칙이 분명해야 한다.
이 글에서는 , 로 쓴다. 는 정수, 는 유리수, 는 실수, 는 복소수 집합이다.
실수 구간의 표기는 끝점을 포함하는지에 따라 달라진다.
| 구간 | 조건 |
|---|---|
현재 논의하는 모든 대상을 담은 집합은 전체집합 다. 원소가 하나도 없는 집합은 공집합 이다. 집합 자체도 다른 집합의 원소가 될 수 있으므로
벤 다이어그램은 전체집합 안에서 각 집합의 영역과 겹침을 보여 주는 방법이다. 그림을 읽을 때도 결국 판정하는 것은 “이 원소가 어느 집합에 속하는가”다.
아무 조건이나 집합을 만드는 것은 아니다
“자기 자신을 원소로 갖지 않는 모든 집합의 집합” 를 허용한다고 하자. 이면 정의에 의해 이고, 이면 다시 정의에 의해 여야 한다. 이것이 러셀의 역설이다. 따라서 임의의 성질을 적었다고 항상 집합이 존재한다고 생각해서는 안 된다. 보통의 조건제시법은 이미 주어진 집합에서 조건을 만족하는 원소를 고르는 방식으로 사용한다.
2. 원소, 부분집합, 멱집합
집합의 상등과 포함 관계는 논리식으로 정의한다.
이면서 이면 진부분집합이다. 여기서는 로 표기한다. 예를 들어 이다.
모든 집합 에 대해 와 가 성립한다. 후자는 이 항상 거짓이라 조건문이 공허하게 참이기 때문이다. 가 아님을 보이려면 에는 있지만 에는 없는 원소 하나를 찾는다. 예를 들어 은 제곱이 100보다 작지만 음이 아닌 정수는 아니다.
과 는 다른 질문이다. 다음을 하나씩 풀어 보면 차이가 분명하다.
| 주장 | 진리값 | 이유 |
|---|---|---|
| F | 유일한 원소는 수 0 | |
| T | 공집합은 부분집합이고 두 집합은 다름 | |
| F | 오른쪽의 원소는 | |
| T | 왼쪽의 원소 가 오른쪽에 있음 | |
| T | 오른쪽의 유일한 원소가 |
크기와 멱집합
유한집합의 크기 는 서로 다른 원소의 수다. 의 모든 부분집합을 모은 집합을 멱집합 라고 한다.
원소마다 넣거나 넣지 않는 두 선택이 있으므로 이면 이다. 예를 들어 원소가 다섯 개이면 부분집합은 32개다. 공집합도 자기 자신의 부분집합이므로
는 원소가 두 개여서 멱집합의 원소가 네 개다.
3. 순서쌍, 데카르트 곱, 관계
집합과 달리 튜플은 순서가 있다. 인 것은 이면서 일 때다.
, 이면
일반적으로 다. 첫 좌표와 둘째 좌표의 역할이 다르기 때문이다. 유한집합에서 이면 각 첫 좌표에 둘째 좌표를 가지로 붙이므로 이다. 여러 집합도 같은 방식으로
로 정의한다. 에는 12개의 삼중쌍이 있다.
관계는 데카르트 곱의 부분집합이다. 에서 인 쌍을 모으면
곱집합의 상등에서 얻는 결론
이고 이면 다. 하나를 고정한다. 임의의 에 대해 이므로 다. 따라서 이고, 반대 방향도 같아서 상등이 성립한다. 이면 두 곱집합이 항상 공집합이라 가 달라도 같아진다. 비어 있지 않다는 조건을 실제로 사용하는 지점은 를 고르는 단계다.
4. 한정 기호와 진리집합
집합을 사용해 한정 기호의 정의역을 제한할 수 있다.
술어 의 진리집합은 다. 전칭 명제는 진리집합이 정의역 전체일 때 참이고, 존재 명제는 진리집합이 비어 있지 않을 때 참이다.
| 정수 정의역의 조건 | 진리집합 |
|---|---|
| 또는 | |
마지막은 을 풀면 또는 이기 때문이다. 실수에서는 이 참이고, 정수에서는 가 거짓이다. 은 0이 반례이고, 은 이 증인이다.
5. 집합 연산과 포함·배제
| 연산 | 정의 |
|---|---|
| 합집합 | |
| 교집합 | |
| 여집합 | |
| 차집합 | |
| 대칭차집합 |
교집합이 공집합인 두 집합을 서로소라고 한다. 대칭차는 두 집합 중 정확히 하나에만 속하는 원소를 모으므로 배타적 논리합에 대응한다.
, , 이면
| 연산 | 결과 |
|---|---|
유한집합의 합집합 크기는
다. 교집합의 원소를 두 번 세었으므로 한 번 빼는 것이다. 수학 전공 40명, 컴퓨터공학 전공 35명, 두 전공 모두인 학생 10명이면 적어도 하나에 속한 학생은 명이다.
6. 집합 항등식과 증명
| 법칙 | 항등식 |
|---|---|
| 항등 | , |
| 지배 | , |
| 멱등 | , |
| 이중여집합 | |
| 교환 | , |
| 결합 | , |
| 분배 | , |
| 드모르간 | , |
| 흡수 | , |
| 여집합 | , |
이들은 명제 논리의 동치와 대응한다. 원소 를 고정하면 합집합은 OR, 교집합은 AND, 여집합은 NOT이다.
서로 부분집합임을 보이기
를 보이자. 왼쪽의 원소 는 에 동시에 속하지 않으므로 둘 중 적어도 하나에 속하지 않는다. 따라서 오른쪽에 속한다. 반대로 오른쪽의 원소 는 또는 중 하나에 속하지 않으므로 교집합에 속하지 않는다. 따라서 왼쪽에도 속한다.
이를 동치의 연쇄로 쓰면 더 짧다.
다른 드모르간 법칙도 로 증명한다.
구성원 표로 확인하기
| 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 |
마지막 두 열이 같으므로 항등식이 성립한다. 집합이 세 개면 소속 여부의 조합은 개다. 에서는 괄호 안이 항상 1이므로 결과가 와 같다.
알려진 항등식을 적용하기
또 이다. 흡수법칙 는 라는 사실에서 바로 나온다.
대칭차의 다른 표현도 유용하다.
오른쪽에 속하려면 적어도 하나에 속하면서 동시에 둘 모두에 속하지 않아야 한다. 이는 정확히 하나에 속한다는 대칭차의 정의다.
7. 여러 집합과 컴퓨터에서의 표현
색인이 붙은 집합족 에 대해
라면 유한한 에 대해 합집합은 , 교집합은 이다. 무한히 모두 교집합하면 공집합이 된다. 어떤 양의 정수 도 에는 들어 있지 않기 때문이다.
비트 문자열
의 순서를 고정하고 왼쪽부터 번째 비트가 1이면 를 원소로 넣는다. 여집합은 비트별 NOT, 합집합은 OR, 교집합은 AND, 대칭차는 XOR로 계산된다.
| 집합 | 비트 문자열 |
|---|---|
| 홀수 | 1010101010 |
| 짝수 | 0101010101 |
1111100000 | |
0110101000 | |
| 의 여집합 | 1001010111 |
와 을 계산하면
A 0011100000
B 1010010001
A OR B 1011110001
A AND B 0010000000
따라서 합집합은 , 교집합은 이다. 1111001111은 을 나타낸다. 1100001111과 0101010101의 OR는 1101011111, AND는 0100000101이다.
다중집합
다중집합은 원소별 중복도를 기록한다. 의 크기는 5다. 원소 의 중복도를 라고 하면 연산은 다음과 같다.
, 처럼 중복도를 줄여 쓰면
| 연산 | 결과 |
|---|---|
합집합과 합의 중복도 계산이 다르다는 점에 주의한다.
8. 함수와 상
함수 는 의 각 원소에 의 원소를 정확히 하나씩 대응시킨다. 관계로 보면 모든 에 대해 꼴의 쌍이 정확히 하나 존재하는 의 부분집합이다.
는 정의역, 는 공역이다. 실제 출력의 집합 는 치역이며 공역의 부분집합이다. 이면 는 의 상이고 는 의 원상이다. 원상은 없거나 여러 개일 수 있지만 입력 하나의 출력이 여러 개일 수는 없다.
이면 치역은 이고, 의 원상들은 다. 공역의 원소 에는 원상이 없다. 부분집합 의 상은
이다. 이면 로 중복 출력을 한 번만 센다.
두 함수가 같으려면 정의역·공역이 같고 모든 입력에서 출력이 같아야 한다. 함수의 그래프도 순서쌍 집합 다.
같은 정의역에서 실숫값을 갖는 함수의 합과 곱은 입력별로 계산한다. 이면
9. 단사, 전사, 전단사
단사는 서로 다른 입력이 서로 다른 출력을 갖는다는 뜻이고, 전사는 공역의 모든 원소가 출력으로 나온다는 뜻이다.
둘 다 만족하면 전단사다. 단사가 아님을 보일 때는 출력이 같은 서로 다른 입력 둘을 찾는다. 전사가 아님을 보일 때는 원상이 없는 공역 원소 하나를 찾는다.
| 함수 | 단사 | 전사 | 근거 |
|---|---|---|---|
| , | O | O | 의 원상은 |
| , | O | X | 1의 원상이 없음 |
| , | X | X | 의 출력이 같고 이 출력되지 않음 |
| , | O | X | 양수에서 순증가하지만 2의 원상이 없음 |
| , | O | O | 각 의 원상은 |
함수 가 를 3, 를 2, 를 1로 보내면 전사이지만 단사는 아니다. 공역에 4를 추가하면 전사도 아니게 된다. 공식을 보고만 판단할 수 없는 이유다.
실수의 부분집합에서 일 때 이면 비감소, 이면 순증가다. 부등호를 반대로 하면 비증가와 순감소다. 순증가·순감소 함수는 단사다. 서로 다른 두 입력은 대소관계가 있고, 순단조성에 의해 출력이 같을 수 없기 때문이다. 은 양의 실수에서는 순증가지만 실수 전체에서는 그렇지 않다.
항등함수 는 전단사다. 유한집합 에서 는 단사와 전사가 동치지만, 무한집합에서는 위의 예처럼 다를 수 있다.
10. 역함수와 합성
전단사 의 역함수 는
로 정의한다. 단사가 아니면 원상이 여러 개라 출력이 하나로 정해지지 않고, 전사가 아니면 공역 전체에서 역함수를 정의할 수 없다. 치역으로 공역을 제한한 뒤 역함수를 생각하는 것과 처음 지정한 공역 전체에서 역함수를 갖는 것은 구별한다.
, 일 때 다. 오른쪽 함수부터 적용한다. , 이면
따라서 합성은 일반적으로 교환되지 않는다. 가 이고 가 이면 는 이다. 반대 합성은 의 출력이 의 정의역에 없어서 정의되지 않는다.
역함수와 합성하면
예를 들어 를 실수에서 실수로 가는 함수로 잡고 이라고 하면 를 풀어
를 얻는다. 두 방향으로 합성하면 각각 원래 입력이 나온다.
11. 연습문제
문제를 읽고 풀이를 적어 본 뒤 해설을 펼쳐 비교해 보자. 계산 결과뿐 아니라 사용한 정의와 추론 근거까지 설명하는 연습을 한다.
01. 집합의 표현과 공집합
- 10보다 작은 양의 짝수 집합을 원소나열법으로, 양의 홀수 집합을 조건제시법으로 쓰자.
- 와 는 같은가?
- 와 는 같은가?
- 이면 와 는 성립하는가?
- 모든 집합 에 대해 인 이유는?
해설 보기
- , 다. 후자는 와 같다.
- 같다. 집합은 순서와 중복을 구별하지 않는다.
- 다르다. 앞은 원소 0개, 뒤는 공집합을 원소로 갖는 원소 1개의 집합이다.
- 모두 성립한다. 1과 2는 에도 있고, 3은 에만 있으므로 두 집합은 같지 않다.
- 의 전건이 항상 거짓이므로 참이다.
02. 원소와 부분집합 판별
여기서 는 진부분집합이다. 다음의 참·거짓과 이유를 쓰자.
- .
- .
- .
- .
- .
해설 보기
- F. 오른쪽의 원소는 수 0 하나다. 여기서는 수 0과 공집합을 구별하는 기초 집합 표기를 사용한다.
- T. 공집합은 모든 집합의 부분집합이며 와 다르다.
- F. 오른쪽의 원소는 이지 가 아니다.
- T. 왼쪽의 유일한 원소 가 오른쪽에 있다. 오른쪽에는 도 있으므로 두 집합은 다르다.
- T. 오른쪽의 유일한 원소가 바로 다. 중괄호 한 겹마다 집합의 층위가 바뀐다.
03. 멱집합과 집합의 크기
- 의 멱집합을 나열하자.
- 의 크기와 멱집합의 크기는?
- 의 크기와 멱집합의 크기는?
- 이면 임을 설명하자.
해설 보기
- 크기별로 나누면 공집합 , 한 원소 집합 , 두 원소 집합 , 세 원소 집합 다. 이 8개 집합을 원소로 모은 것이 다.
- , 다. 두 원소는 와 로 서로 다르다.
- , 다. 각 원소마다 포함/제외 두 선택이 있다.
- 임의의 에 대해 와 가 모두 참이다. 따라서 두 집합은 정확히 같은 원소를 가지며 같다.
04. 곱집합과 곱의 법칙
- 를 나열하자.
- 이면 는?
- 일반적으로 인 유한집합에서 를 구하고 이유를 설명하자.
해설 보기
- 다. 첫 좌표는 앞 집합, 둘째는 뒤 집합에서 고른다.
- 이다.
- 이다. 첫 좌표 선택 가지마다 둘째 좌표 선택이 가지씩 있다. 순서쌍의 상등은 두 좌표가 모두 같은 경우이므로 서로 다른 선택은 서로 다른 원소를 준다.
05. 곱집합의 상등
가 공집합이 아니고 일 때 임을 증명하자. 조건을 빼도 되는가?
해설 보기
이므로 를 하나 고정한다.
임의의 에 대해 이므로 다. 따라서 .
반대로 임의의 에 대해 이므로 다. 따라서 . 두 포함 관계를 합하면 다.
이면 예를 들어 에서도 두 곱집합은 모두 공집합이다. 그러므로 가 비어 있지 않다는 조건은 필요하다. 실제 증명에는 가 비어 있지 않다는 조건까지는 필요하지 않다.
06. 진리집합 계산
정의역은 정수다. 다음 술어의 진리집합을 구하자.
- .
- .
- .
- .
- .
이를 이용해 도 판정하자.
해설 보기
- . 인 정수다.
- .
- . 세제곱은 증가하므로 과 같다.
- . 실수해 는 정수가 아니다.
- 이므로 또는 . 정수에서는 다.
마지막 존재 명제는 진리집합이 비어 있으므로 거짓이다.
07. 한정 명제를 문장으로 읽기
다음을 자연어로 옮기고 참·거짓을 근거와 함께 판정하자.
- .
- .
- .
- .
해설 보기
- “모든 실수의 제곱은 -1과 다르다.” 참이다. 제곱은 0 이상이다.
- “제곱이 2인 정수가 존재한다.” 거짓이다. 이면 제곱이 1 이하, 이면 4 이상이라 2가 될 수 없다.
- “모든 정수의 제곱은 양수다.” 거짓이며 0이 반례다.
- “세제곱이 -1인 실수가 존재한다.” 참이며 이 증인이다.
08. 합집합·교집합·여집합
- 과 의 합집합과 교집합을 구하자.
- 과 의 관계를 무엇이라고 하는가?
- 에서 의 여집합은?
- 일 때 를 구하자.
해설 보기
- 합집합은 , 교집합은 이다. 합집합에서도 중복 원소 3을 한 번만 쓴다.
- 교집합이 공집합이므로 서로소다.
- 전체집합에서 짝수를 제외한 다.
- 차례로 , , , 이다.
09. 차집합과 대칭차
- , , 의 합집합·교집합·각 여집합·양방향 차집합·대칭차를 구하자.
- 일반적인 집합에서 임을 증명하자.
해설 보기
- 정의에 따라 양쪽/한쪽 소속 여부를 나누어 센다.
| 연산 | 결과 |
|---|---|
- 가 오른쪽에 속한다는 것은 이면서 라는 뜻이다. 즉 적어도 한쪽에 속하지만 양쪽 모두에는 속하지 않는다. 이는 정확히 한쪽에만 속한다는 대칭차의 정의다. 역방향도 같은 조건이므로 모든 원소의 소속 여부가 일치한다.
10. 합집합의 여집합: 세 가지 증명
전체집합 의 부분집합 에 대해 를 다음 방법으로 보이자.
- 양쪽이 서로의 부분집합임을 보이기.
- 소속표로 확인하기.
- 조건제시법과 논리적 동치로 쓰기.
해설 보기
1. 서로 포함됨을 보인다.
라고 하자. 이며 에는 속하지 않는다. 따라서 이고 이므로 다. 이로써 다.
반대로 라면 이면서 다. 따라서 에 속하지 않아 다. 이로써 다. 두 포함 관계에서 상등이 나온다.
2. 1은 소속, 0은 비소속으로 놓는다.
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
왼쪽과 오른쪽을 나타내는 두 열이 네 경우 모두 같다.
3. 조건제시법으로 쓴다.
여집합을 취하는 전체집합은 모든 줄에서 같은 다.
11. 교집합의 여집합과 분배법칙
- 를 원소 논증으로 보이자.
- 를 소속표로 보이자.
- 세 집합의 소속표에는 몇 행이 필요한가?
- 에서 를 계산으로 확인하자.
해설 보기
- 모든 에 대해
따라서 같은 원소를 갖는다.
- 표는 다음과 같다.
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 |
마지막 열이 첫 열과 같다.
- 각 집합에 소속/비소속 2가지씩이므로 행이다.
- 이므로 왼쪽은 . 오른쪽은 다. 이 계산은 주어진 집합에 대한 확인이며, 일반 항등식의 증명은 원소 논증이나 8행 소속표로 할 수 있다.
12. 집합을 비트로 표현하기
이며 왼쪽부터 번째 비트가 원소 의 소속을 나타낸다.
- 과 그 여집합을 비트로 쓰자.
11 0000 1111과01 0101 0101의 합집합·교집합을 비트로 쓰자.- 를 비트로 쓰고 합집합·교집합을 비트 연산 및 집합으로 구하자.
11 1100 1111은 어떤 집합인가?
해설 보기
- 는
01 1010 1000, 여집합은 비트를 뒤집은10 0101 0111이다. - 합집합은 OR하여
11 0101 1111, 교집합은 AND하여01 0000 0101이다. - 각 원소 위치를 1로 표시한 뒤 자리별로 계산한다.
A 0011100000
B 1010010001
A OR B 1011110001
A AND B 0010000000
합집합은 , 교집합은 이다. 4. 1인 위치를 읽으면 이다. 문자열을 이진수의 자리값으로 해석하는 문제가 아니다.
13. 공역·치역·원상
- 함수의 공역과 치역은 어떻게 다른가?
- 가 로 주어졌다. 의 원상을 모두 구하자.
- 가 으로 주어졌다. 단사·전사를 판정하자.
해설 보기
- 공역은 출력이 속하도록 정한 집합, 치역은 실제 출력들의 집합이다. 치역은 공역의 부분집합이지만 항상 같지는 않다.
- 다. 출력이 가 되는 입력을 전부 고른다.
- 인데 이므로 단사가 아니다. 공역의 1, 2, 3은 각각 의 상이므로 전사다.
14. 정의역을 바꾸면 함수의 성질도 바뀐다
- 을 와 에서 각각 단사·전사 판정하자.
- 가 전사가 아님을 보이자.
- 의 역함수를 구하자.
- 가 역함수를 갖지 않는 이유는?
해설 보기
- 두 정의역에서 모두 이면 , 따라서 이므로 단사다. 정수 전체에서는 각 에 가 있어 전사다. 양의 정수에서는 공역의 1을 만드는 입력 0이 정의역에 없으므로 전사가 아니다.
- 은 정수의 제곱이 아니므로 공역의 모든 값을 만들지 못한다.
- 이다. 와 를 모두 만족한다.
- 이라 단사가 아니며 음수는 출력되지 않아 전사도 아니다. 역함수를 얻으려면 정의역·공역을 알맞게 제한해야 한다.
15. 합성과 역함수의 조건
- 를 정의할 수 있으려면 어떤 조건이 필요한가?
- 전단사와 역함수의 존재가 동치인 이유를 설명하자.
- 가 전단사임을 보이고 역함수를 구하자.
- 인 실수 에 대해 가 가역임을 보이고 역함수를 구하자.
해설 보기
- 의 모든 출력이 의 정의역에 들어가야 한다. 라면 자동으로 만족한다. 더 일반적으로 면 충분하다.
- 단사이면 각 출력의 원상이 많아야 하나, 전사이면 공역의 각 값의 원상이 적어도 하나다. 둘을 합하면 정확히 하나여서 역함수가 정의된다. 역함수가 존재한다면 두 입력이 같은 출력으로 갈 수 없고 공역에 원상 없는 값도 있을 수 없다.
- 이면 여서 단사다. 임의의 정수 의 원상 가 있으므로 전사다. 따라서 다.
- 이면 이고 이므로 . 모든 실수 에는 가 있으므로 전사다. 따라서
, 로 확인된다.
Comments