[01] Sets and Propositions

개념적인 이야기가 많아서 그냥 나열해서 설명한다.

• $X$와 $Y$가 disjoint면, $X \cap Y = \emptyset$

 

Combinations of sets

• $P-Q$ : difference
  $\{a,b,c\}-\{a,b,d\} = \{c\}$
• $P \oplus Q$ : symmetric difference
  $\{a,b,c\} \oplus \{a,c,d\} = \{b,d\}$
  P와 Q에 동시에 속하지 않는 element이다.
• $\overline{Q}$ : complement
  Q의 여집합
• Power set
  $P(\{a,b\}) = \{\{\}, \{a\}, \{b\}, \{a,b\}\}$
  집합의 크기가 $k$이면, $2^k$의 elements를 가짐

Power set

 

Properties of Sets

 

Finite and Infinite Sets

Cardinality를 정의한다. Set의 크기이다. 서로 다른 element의 수를 세면 된다.

• $\{a,b,c\}$ = 3
• $\emptyset$ = 0
• $\{a,\emptyset, b\}$ = 3

 

Finite와 infinite set을 정의하기 위해서 successor 개념도 필요하다.

$$successor: A^+ = A \cup \{A\}$$

 

Successor의 정의에 따라 cardinality를 만들어가면 다음처럼 나온다.

 

그렇다면, cardinality of successor는 다음처럼 증가하게 된다.

$0^+=1,$

$1^+=2,$

$2^+=3,...$

 

다음으로는 set $N$을 다음처럼 정의해볼 수 있다.

1. $N$은 0을 element로 가진다.
2. $n$이 $N$의 element이면, $n^+$도 element이다.
3. $N$에 다른 set은 없다.

정의에 따라 $N$은 infinite set이 된다.

 

Finite set을 정의하기 위해 one-to-one correspondence 개념을 알아야 한다. One-to-one correspondence는 두 집합 $P$와 $Q$의 모든 element가 서로 일대일 대응인 경우이다.

 

Finite set은 집합 $N$의 element $n$과 one-to-one correspondence로 매칭할 수 있는 집합으로 정의할 수 있다. 그럼 이제 반대로 infinite set은 finite set이 아니면 infinite set으로 정의되게 된다.

 

Infinite set의 크기는 집합 $N$과 1-1 correspondence로 대응되면 countably infinite가 된다. 예를 들어서 $\{0,1,2,...\}$는 countably infinite set이지만, [0,1] 사이의 정수는 uncountably infinite set이 된다.

 

Principle of Inclusion and Exclusion

$|P|$를 cardinality of P라고 하자. 그럼 다음의 관계들을 얻는다.

 

조금 생각해보면 다 맞다.

 

Multiset

Set과는 조금 다르게 중복이 허용되는 set이다. 즉 element의 순서가 존재하는 set이다. 가령 $S=\{a,a,a,a,b,b,b\}$이다.

 

Set의 cardinality와 비슷하게 multiset에서는 multiplicity가 사용된다. Multiplicity는 multiset에서 element가 존재하는 수라고 생각하면 된다. 가령 $S$의 multiplicity of $a$는 4이다.

 

Multiset의 cardinality는 모든 element의 수이다. 중복이 있어도 다 다른 element로 본다.

 

• $P \cup Q$ : union
  Multiplicity가 큰 친구를 따라간다.
  $\{a,a,b,b\} \cup \{a,b,c,c,d\}$ = $\{a,a,b,b,c,c,d\}$
• $P \cap Q$ : intersection
  Multiplicity가 작은 친구를 따라간다.
  $\{a,a,b,b\} \cap \{a,b,c,c,d\}$ = $\{a,b\}$
• $P-Q$ : difference
  Multiplicity의 차이이다.
  $\{a,a,b,b\} - \{a,b,c,c,d\}$ = $\{a, b\}$
•  $P+Q$ : sum
  Multiplicity의 합이다.
  $\{a,a,b,b\} + \{a,b,c,c,d\}$ = $\{a,a,a,b,b,b,c,c,d\}$

 

$n$-Tuple

우리가 아는 그 tuple이다. $(x,y)$로 표기한다.

 

$X×Y$는 cartesian product를 의미한다. 모든 ordered pair라고 생각하면 된다.

$X=\{1,2,3\}$, $Y=\{a,b\}$인 경우,

• $X×Y=\{ (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) \}$ (tuple)

 

그래서 $n$-tuple은 finite ordered list를 의미한다. $(a_1, a_2, ..., a_n)$

 

Propositions

True나 false인 선언문, 명제를 의미한다. True인지 false인지 모르지만, 둘 중에 하나인 것이 명확하면 명제이기도 하다. 예를 들어 "생명체는 지구에만 산다" 역시 명제이다.

 

명제가 항상 True이면 Tautology라 한다.

명제가 항상 False면 Contradiction이라 한다.

 

두 명제 $p$와 $q$에 대해서 $p$가 true면 $q$가 true고 $p$가 false면 $q$도 false인 관계를 equivalent하다고 한다.

 

명제의 관계는 다음처럼 나타낼 수 있다.

• $P \vee Q$ : disjunction
  or와 같다. 진리표는 다음과 같다.

Disjunction

 

• $P \wedge Q$ : conjunction
  and와 같다.

Conjunction

 

• $\overline{P}$ : negation
  not과 같다.

Negation

 

• $P \rightarrow Q$ : implies
  확실하게 틀린 경우에만, false를 가진다.

If $P$ then $Q$

 

• $P \leftrightarrow Q$ : if and only if
  P와 Q는 logically equivalent함을 의미한다.

Iff

 

위의 관계를 잘 조합하면 서로 다른 명제가 logically equivalent함을 알 수 있다.

 

Quantifier

$P(x)$에 대해서 $P$는 propositional function이나 predicate라 하며, $D$는 domain of discourse of $P(x)$라 한다. 예를 들어서 $P(x)$에 대해 $x$가 odd integer이면, $D$는 positive integer의 집합이 된다.

 

Mathematical Induction

Basis에 대해 statement를 증명하고, $n=k$일 때 성립함을 가정하여 $n=k+1$인 경우에도 성립함을 보이면, inductive step에 의해서 주어진 statement가 성립함을 알 수 있다.