Search
Duplicate

데코수학/ 집합론/ 집합

(유튜브 동영상인데 현재는 삭제되어서 내용만 남김)

1

개념

순진한 정의
집합: 구별 가능한 것들의 모임
원소: 집합에 들어 있는 대상들
공집합: aa \neq \emptyset
원소 나열법
A={a,b,c}A = \{ a, b, c \}
조건 제시법
a{p(x)q(x)}a \in \{ p(x) | q(x) \}
상등
A=Bz,zAzBA = B \Leftrightarrow \forall z, z \in A \Leftrightarrow z \in B
{a,a,b}={a,b}\{ a, a, b \} = \{ a, b \}
부분집합
ABzAzBA \subseteq B \Leftrightarrow \forall z \in A \Rightarrow z \in B
집합의 크기
A|A| : AA의 원소의 개수 (AA는 유한집합)
멱집합(power set)
P(A):AP(A) : A의 부분집합들을 모은 집합
{xxA}\{ x | x \in A \}
A=2P(A)=2n|A| = 2 \Rightarrow |P(A)| = 2^{n}
합집합
AB={xxAxB}A \cup B = \{ x | x \in A \vee x \in B \}
교집합
AB={xxAxB}A \cap B = \{ x | x \in A \wedge x \in B \}
차집합
AB={xxBxB}A \setminus B = \{ x | x \in B \wedge x \notin B \}
여집합
Ac=UAA^{c} = U \setminus A
공집합은 모든 집합의 부분집합
공집합은 unique 하다

집합식

ABBAA=BA \subseteq B \wedge B \subseteq A \Leftrightarrow A = B
ABBCACA \subseteq B \wedge B \subseteq C \Rightarrow A \subseteq C
AA=AA \cup A = A
AA=AA \cap A = A
AB=BAA \cup B = B \cup A
AB=BAA \cap B = B \cap A
A(BC)=(AB)CA \cup (B \cup C) = (A \cup B) \cup C
A(BC)=(AB)CA \cap (B \cap C) = (A \cap B) \cap C
A(BC)=(AB)(AC)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
(Ac)c=A(A^{c})^{c} = A
c=U,Uc=\emptyset^{c} = U, U^{c} = \emptyset
(AB)c=AcBc(A \cup B)^{c} = A^{c} \cap B^{c}
(AB)c=AcBc(A \cap B)^{c} = A^{c} \cup B^{c}
ABAB=BA \subseteq B \Leftrightarrow A \cup B = B
ABAB=AA \subseteq B \Leftrightarrow A \cap B = A
ABAB=A \subseteq B \Leftrightarrow A \setminus B = \emptyset
ABBcAcA \subseteq B \Leftrightarrow B^{c} \cup A^{c}
AU=UA \cup U = U
AU=AA \cap U = A
A=AA \cup \emptyset = A
A=A \cap \emptyset = \emptyset

2

개념

대칭차집합
AB:=(AB)(BA)=(AB)(AB)A \bigtriangleup B := (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)
서로소
A,BA, B = 서로소 AB=\Leftrightarrow A \cap B = \emptyset
A,BA, B가 서로소이면 ABc,BAcA \subseteq B^{c}, B \subseteq A^{c}
비둘기집 원리
a1,a2,...,an+1U,U=Uk=1nAk,Ak=각각 서로소k,Ak2a_{1}, a_{2}, ... , a_{n+1} \in U, U = U_{k=1}^{n} A_{k}, A_{k} = \text{각각 서로소} \Rightarrow \exists k, |A_{k}| \geq 2
n+1n + 1개의 물건을 nn개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다
집합족
집합을 원소로 가지는 집합
F={{...},{...},{...}}F = \{\{...\}, \{...\}, \{...\}\}
첨수집합족
집합을 첨수로 표기하는 집합 족
F={AγγR}F = \{ A_{\gamma} | \gamma \in \mathbb{R}\}
집합족의 합집합
F={xXF,xX}\cup F = \{ x | \exists X \in F, x \in X \}
xFAF,xAx \in \cup F \Leftrightarrow \exists A \in F, x \in A
F={AγγΓ},F={xγΓ,xAγ}F = \{ A_{\gamma} | \gamma \in \Gamma \}, \cup F = \{ x | \exists \gamma \in \Gamma, x \in A_{\gamma} \}
F=k=1Ak\cup F = \cup_{k=1}^{\infty} A_{k} (k=1k = 1부터 무한대, 무한개의 원소)
F=k=1nAk\cup F = \cup_{k=1}^{n} A_{k} (k=1k = 1부터 nn까지, 유한개의 원소)
집합족의 교집합 표현
F={xxF,xX}\cap F = \{ x | \forall x \in F, x \in X \}
k=1Ak\cap_{k=1}^{\infty} A_{k}
k=1nAk\cap_{k=1}^{n} A_{k}
kNAk\cap_{k \in \mathbb{N}} A_{k}

집합식

xABxAxBx \in A \bigtriangleup B \Leftrightarrow x \in A \veebar x \in B
AB=BAA \bigtriangleup B = B \bigtriangleup A
A(BC)=(AB)CA \bigtriangleup (B \bigtriangleup C) = (A \bigtriangleup B) \bigtriangleup C
AB=A+BAB|A \cup B| = |A| + |B| - |A \cap B|
ABC=A+B+CABBCCA+ABC|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|
=\cup \emptyset = \emptyset
=U,U\cap \emptyset = U, U는 전체집합
(F)c=AFAc(\cup F)^{c} = \cap_{A \in F} A^{c}
(F)c=AFAc(\cap F)^{c} = \cup_{A \in F} A^{c}
S(AFA)=AF(SA)S \cap (\cup_{A \in F} A) = \cup_{A \in F} (S \cap A)
S(AFA)=AF(SA)S \cup (\cap_{A \in F} A) = \cap_{A \in F} (S \cup A)