집합과 함수

집합의 연산 A∪BA \cup B, A∩BA \cap B, AcA^c와 드모르간 법칙, 그리고 단사·전사·전단사를 그림으로 확인합니다.

(A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c
f bijective  ⟺  ∃g:g∘f=idf \text{ bijective} \iff \exists g: g \circ f = \mathrm{id}

이 씬이 포함된 학습 경로

예제

(A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c임을 원소로 직접 증명하세요.

x∈(A∪B)c  ⟺  x∉A∪B  ⟺  x∉A and x∉B  ⟺  x∈Ac∩Bcx \in (A \cup B)^c \iff x \notin A \cup B \iff x \notin A \text{ and } x \notin B \iff x \in A^c \cap B^c
합집합이 켜진 벤 다이어그램 — 여집합을 씌우면 바깥 영역만 남습니다.
증명 보기
  1. 원소 xx를 잡습니다. 여집합의 정의에 의해 x∈(A∪B)c  ⟺  x∉A∪Bx \in (A \cup B)^c \iff x \notin A \cup B입니다.
  2. x∉A∪B  ⟺  ¬(x∈A∨x∈B)x \notin A \cup B \iff \lnot(x \in A \lor x \in B)입니다. 명제논리의 드모르간 법칙에 의해 이는 ¬(x∈A)∧¬(x∈B)\lnot(x \in A) \land \lnot(x \in B), 즉 (x∉A)∧(x∉B)(x \notin A) \land (x \notin B)와 동치입니다.
  3. (x∉A)∧(x∉B)  ⟺  x∈Ac∧x∈Bc  ⟺  x∈Ac∩Bc(x \notin A) \land (x \notin B) \iff x \in A^c \land x \in B^c \iff x \in A^c \cap B^c입니다. xx가 임의였으므로 (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c입니다.

f:A→Bf: A \to B가 전단사   ⟺  \iff 양쪽 역함수 g:B→Ag: B \to A (g∘f=idAg \circ f = \mathrm{id}_A, f∘g=idBf \circ g = \mathrm{id}_B)가 존재함을 증명하세요.

전단사 모드 — 모든 점이 정확히 한 번씩 연결됩니다.
증명 보기
  1. (⇒) b∈Bb \in B마다 f(a)=bf(a) = b인 aa가 존재합니다(전사). 단사이므로 그 aa는 유일합니다. 이를 g(b)g(b)라 정의하면 g:B→Ag: B \to A입니다.
  2. g(f(a))=ag(f(a)) = a인 이유는 f(a)f(a)에 대응하는 유일한 원소가 aa 자신이므로, 그리고 f(g(b))=bf(g(b)) = b인 이유는 g(b)g(b)의 정의 그대로입니다.
  3. (⇐) 그런 gg가 존재한다고 하자. f(a1)=f(a2)f(a_1) = f(a_2)이면 양변에 gg를 적용해 a1=g(f(a1))=g(f(a2))=a2a_1 = g(f(a_1)) = g(f(a_2)) = a_2 — 단사입니다. 한편 b∈Bb \in B에 대해 a=g(b)a = g(b)라 두면 f(a)=f(g(b))=bf(a) = f(g(b)) = b — 전사입니다. 따라서 ff는 전단사입니다.

유한집합에 대해 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A \cap B\rvert임을 증명하고, ∣A∣=5\lvert A\rvert=5, ∣B∣=4\lvert B\rvert=4, ∣A∩B∣=2\lvert A\cap B\rvert=2일 때를 계산하세요.

∣A∪B∣=5+4−2=7\lvert A \cup B\rvert = 5 + 4 - 2 = 7
∣A∣=5\lvert A\rvert=5, ∣B∣=4\lvert B\rvert=4, 겹치는 부분 22 — 합집합은 77.
증명 보기
  1. A∪BA \cup B는 서로소인 세 조각 A∖BA \setminus B, B∖AB \setminus A, A∩BA \cap B의 분리합집합입니다.
  2. ∣A∣=∣A∖B∣+∣A∩B∣\lvert A \rvert = \lvert A \setminus B \rvert + \lvert A \cap B \rvert, ∣B∣=∣B∖A∣+∣A∩B∣\lvert B \rvert = \lvert B \setminus A \rvert + \lvert A \cap B \rvert입니다 (둘 다 분리합집합).
  3. 두 식을 더하면 ∣A∣+∣B∣=∣A∪B∣+∣A∩B∣\lvert A \rvert + \lvert B \rvert = \lvert A \cup B \rvert + \lvert A \cap B \rvert — 겹치는 부분이 두 번 세어졌습니다. 정리하면 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert입니다.
  4. ∣A∣=5\lvert A \rvert = 5, ∣B∣=4\lvert B \rvert = 4, ∣A∩B∣=2\lvert A \cap B \rvert = 2를 대입하면 ∣A∪B∣=5+4−2=7\lvert A \cup B \rvert = 5 + 4 - 2 = 7입니다.

1. 수의 체계