2. Basic Structures: Sets, Functions, Sequences and Sums

2.1. Sets

Sets

Set(집합)은 순서가 없는 Object들의 모음이다.
Set의 구성요소를 Element라고 하고 Member라고 표현하기도 한다.
Set은 Element를 포함한다.
Notation으로 Set $A$의 $a$라는 Element가 포함됨을 나타낼 때 $a\in A$라고 표현하며 Set $A$에 포함되지 않을 시 $a\notin A$로 표현한다.

Set을 설명하기 위해 Element들을 나열하거나, Set builder로 표현할 수 있다.

정보

Example

• Element들을 나열
  • $A=\{a,b,c,d,e\}, B=\{1,2,3,4,...\}$
• Set builder
  • C=\{x \in \mathbf{Z^+}\mid x \ is\ odd\ positive\ integer\ less\ than\ 10\}$$$$C=\{x\in a \mid x is odd positive integer less than 10}

Set notation	Description	List of elements
$\mathbf{N}$	The set of natural numbers	$\mathbf{N}=\{0,1,2,3,\ldots\}$
$\mathbf{Z}$	The set of integers	$\mathbf{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$
$\mathbf{Z^+}$	The set of positive integers	$\mathbf{Z^+}=\{1,2,3,\ldots\}$
$\mathbf{Q}$	The set of rational numbers	$\mathbf{Q}=\{p/q \mid p\in \mathbf{Z},q\in \mathbf{Z}\ and\ q \not =0\}$
$\mathbf{R}$	The set of real numbers

Computer science에서 Datatype, Type의 개념은 Set의 개념을 기반으로 한다.
Datatype은 Set의 이름, 해당 Element에 대해 수행 가능한 Operation의 Set으로 구성된다.

정보

Example

Boolean's Elements = $\{0,1\}$, Boolean's Operation= AND, OR, NOT

두 Set이 같다는 표현은 Set $A$, $B$에 대해 $\forall x(x\in A \leftrightarrow x\in B)$가 성립할 때 Notation $A=B$로 표현한다.

Element가 없는 Set을 Empty set(공집합)이나 Null이라고 부르며 Notation으로 $\{\ \}$나 $\empty$로 표현한다.

Element가 하나만 있는 Set을 Singleton set(한원소 집합)이라고 부른다.

Set $A$, $B$에 대해 $\forall x(x\in A\to x\in B)$가 성립할 때 $A$는 $B$의 Subset(부분 집합)이라고 하며 Notation $A\subseteq B$로 표현한다.

Empty set이 아닌 Set은 적어도 두 개의 Subset(Set 본인과 $\empty$)을 가진다.

• $\forall x(x\in \empty \to x\in S)$, 즉 $\empty$은 어떤 Element도 가지지 않기에 $x\in \empty$는 항상 False이므로 Vacuous Truth로 인해 Conditional statement $x\in \empty \to x\in S$는 항상 True로 증명할 수 있다.
• $\forall x(x\in S\to x\in S)$는 $x\in S$를 Proposition $P$라고 가정할 때 Domain $x$에 대해 $P\to P$는 항상 True이므로 True로 증명할 수 있다.

Set $A$, $B$에 대해 $\forall x(x\in A\to x\in B)\land \exists x(x\in B \land x\not =A)$가 성립할 때, 즉 $A$가 $B$의 $B$ 자신을 제외한 Subset일 때 $A$는 $B$의 Proper subset(진부분 집합)이며 Notation으로 $A\subset B\land A\not =B$로 표현한다.

Set은 Element로 다른 Set을 가질 수 있다.

정보

Example

$A=\{\empty, \{a\},\{b\},\{a, b\}\}=\{x\ \mid\ x\ is\ subset\ of\ set \{a,b\}\}$
$\{a\}\in A,a\notin A$

Set $S$에 대해 서로 다른 Element가 정확히 $n$개 존재할 때 $n$이 Nonnegative integer라면 $S$를 Finite set(유한 집합)이라고 하며 $n$을 $S$의 Cardinality(기수)라고 하며 Notation $|S|=n$으로 표현한다.

Power set

Set $S$의 모든 Subset을 Element로 갖는 Set을 $S$의 Power set(멱집합)이라고 하며 Notation $P(S)$로 표현한다.
Cardinality가 $n$인 Set $S$의 Power set의 Cardinality는 $2^n$이다.

정보

Example

$\{0, 1, 2\}$의 Powerset
$P(\{0,1,2\})=\{\empty , \{0\} ,\{1\} ,\{2\} ,\{0,1\} ,\{0,2\} ,\{1,2\} ,\{0,1,2\}\}$
$P(\{0,1,2\})=8=2^3$\

Cartesian Products

Collection은 Set과 달리 Element의 순서가 유의미하다.
Collection을 표현하기 위해 Set과 다른 표현 방법이 필요해 Ordered n-tuple로 표현하며 Ordered 2-tuple을 Ordered pair라고 한다.

Ordered n-tuple인 $(a_1,a_2,\cdots , a_n)$은 $a_1$을 첫 Element, $a_2$를 두 번째 Element, $a_n$을 n번째 Element로 갖는 Collection을 뜻한다.

두 Ordered n-tuple이 같다는 것은 각 Ordered n-tuple의 Element가 순서대로 모두 동일하다는 것이다.

정보

Example

Ordered pair $(a,b)=(c,d)$는 $a=c$이고 $b=d$라는 뜻이다.

Set $A$, $B$에 대해 $A$, $B$의 Cartesian product는 Notation $A\times B$로 표현한다.
$A\times B=\{(a,b)\ \mid\ a\in A\land b\in B\}$이며 $(a, b)$는 Ordered pair이다.

정보

Example

$A=\{1,2\},\ B=\{a,b,c\}$일 때 $A\times B$

$A\times B=\{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$

Set $A$, $B$에 대한 Cartesian product의 Subset $R$을 Set $A$에서 Set $B$로의 Relation이라고 한다.
$A\times B=B\times A$이기 위해 $A=B \lor A=\empty \lor B=\empty$여야 한다.
Set $A_1,A_2,\cdots ,A_n$의 Cartesian product는 $A_1\times A_2\times \cdots \times A_n$으로 표기되며 Ordered n-tuple $(a_1,a_2,\cdots ,a_n)$으로 구성되며$A_1\times A_2\times \cdots \times A_n=\{(a_1,a_2,\cdots ,a_n)\ \mid\ a_i\in A_i, i=1,2,\cdots,n\}$로 표현할 수 있다.

Using Set Notation with Quantifiers

Quantifier를 사용하여 Set Notation을 표현할 수 있다.

정보

Example

Set $S$에 대한 모든 Element에 대해 $P(x)$의 Universal quantification은 $\forall x\in S(P(x))=\forall x(x\in S\to P(x))$이고, Existential quantification은 $\exists x\in S(P(x))=\exists x(x\in S\land P(x))$이다.

Truth Sets of Quantifiers

Predicate $P$와 Domain $D$가 주어질 때 $P$의 Truth set은 $P(x)$가 True인 $D$의 Element인 x에 대한 Set $P(x)$이며 Notation $P's\ Truth\ set=\{x\in D\ \mid\ P(x)\}$이다.

2.2. Set Operations

Set Operations

Union

Union은Set $A$, $B$에 대해 $\{x\ \mid\ x\in A\lor x\in B\}$일 때 Notation $A\cup B$로 표현한다.

Section

Section은 Set $A$, $B$에 대해 $\{x\ \mid\ x\in A\land x\in B\}$일 때 Notation $A\cap B$로 표현한다.

Disjoint

Set $A$, $B$에 대해 $A\cap B=\empty$일 때 Disjoint라고 한다.

두 Finite Set $A$, $B$의 Cardinality를 구할 때 $|A\cup B| =|A|+|B|-|A\cap B|$로 구하는데 이를 임의의 수의 Set의 Union으로 일반화한 것을 Principle of inclusion-exclusion이라고 한다.

Difference

두 Finite set $A, B$에 대해 $\{x\mid x\in A\land x\notin B\}$일 때 Notation $A-B$로 표현한다.

Complement

Set $U$(Universal set), $A$에 대해 $U-A=\{x\mid x\notin A\}$일 때 Notation $A^C$로 표현한다.

Set Identities

Identity	Name
$A\cup \empty = A\\A\cap U=A$	Identity laws
$A\cup A=A\\A\cap A=A$	Idempotent laws
$A\cup B= B\cup A\\A\cap B= B\cap A$	Commutative laws
$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\\A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$	Distributive laws
$A\cup(A\cap B)=A\\A\cap(A\cap B)=A$	Absorption laws
$A\cup U=U\\A\cap \empty = \empty$	Domination laws
$(A^C)^C = A$	Complementation laws
$A\cup(B\cup C)=(A\cup B)\cup C\\A\cap(B\cap C)=(A\cap B)\cap C$	Associative laws
$(A\cup B)^C = A^C\cap B^C\\(A\cap B)^C=A^C\cup B^C$	De Morgan's laws
$A\cup A^C=U\\A\cap A^C= \empty$	Complement laws

Generalized Unions and Intersections

Union과 Intersection은 Associative law를 만족하기에 순서가 상관이 없다.

팁

Example

여러 Set의 Union은 해당 Set 중 적어도 하나의 Set에 포함된 Element를 포함하는 Set이다.
Set $A_1, A_2, \dots, A_n$에 대한 Union의 Collection은 $A_1\cup A_2\cup \cdots \cup A_n=\bigcup_{i=1}^n A_i$이다.

여러 Set의 Intersection은 해당 Set에 모두 포함된 Element를 포함하는 Set이다.
Set $A_1,A_2,\dots,A_n$에 대항 Intersection의 Collection은 $A_1\cap \cdots \cap A_n=\bigcap_{i=1}^nA_i$이다.

Computer Representation of Sets

Computer에서 Set을 표현하는 방법 중 하나는 Set의 Element를 순서 없이 저장하는 것이다.
Union과 Intersection, Difference Operation이 오래걸릴 수 있다.

Computer에서 Universal set $U$가 Finite set(Memory size보다 작을 때)일 때 $U$의 Element를 임의의 순서대로 저장하는 방법은 Cardinality가 $n$인 $U$의 임의의 Element $a_1,a_2,\dots,a_n$으로 나열한 후 길이가 $n$인 Bit string($1=T,0=F$)로 나타내며 이를 통해 Union, Intersection, Difference를 쉽게 찾을 수 있다.

2.3. Functions

Set Functions

Set $A,B$가 Nonempty set일 때 $A$에서 $B$로의 Functrion $f$는 $A$의 각 Element $a$에 대해 $B$에 정확히 하나의 Element인 $b$를 할당하는 것이며 Notation으로 $f(a)=b$로 표현한다.

만약 $f(a)=b$가 성립할 때 $f:A\to B$로 표현하며 Function은 Mapping이나 Transformation이라고도 불린다.
$f(a)=b$일 때 Pair $(a,b)$는 Relation에서 $a$를 첫 Element로 가지는 Unique ordered pair가 된다.

Function $f$가 Set $A, B$에 대해 $A$에서 $B$로의 Function일 경우 $f$가 $A$를 $B$로 Mapping한다고 표현하며 $A$는 $f$의 Domain, $B$는 $f$의 Codomain이 되며 $b$는 $a$의 Image, $a$는 $b$의 Preimage라고 한다.

Function을 정의할 때 Function의 Domain, Codomain, Domain의 Element를 Codomain의 Element에 Mapping하는 방식을 지정한다.
만약 두 Function이 동일한 Domain, Codomain, Domain의 Element를 Codomain의 Element에 Mapping하는 결과가 같다면 두 Function은 같다고 하며 Domain이나 Codomain만이 바뀌더라도 두 Function은 같지 않다고 한다.

$(f_1+f_2)(x)=f_1(x)+f_2(x), (f_1f_2)(x)=f_1(x)f_2(x)$이다.

Function $f$가 Set $A, B$에 대해 $A$에서 $B$로의 Function일 때 $A$의 Subset $S$가 존재할 때 Function $f$에 의한 $S$의 Image는 $S$의 Element들의 Image로 구성된 $B$의 Subset이다.
$S$의 Image는 $f(S)$로 표현하며 $f(S)=\{t\mid\exists s\in S(t=f(s))\}=\{f(s)\mid s\in S\}$이다.

One-to-One and Onto Functions

Injection

One-to-one(=Injective) function은 두 개의 서로 다른 Domain element에 동일한 Value를 할당하지 않는다.
One-to-one function $f$에 대해 $a\not=b$일 때 $f(a)\not=f(b)$이며 $a=b$일 때 $f(a)=f(b)$이다.
$f$가 One-to-one임을 표시하는 방식은 Definition의 Implication의 Contrapositive를 취함으로 구할 수 있다.

Function $f$가 One-to-one이라는 것을 Quantifier를 통해 $\forall a\forall b(f(a)=f(b)\to a=b)$나 $\forall a\forall b(a\not=b \to f(a)\not = f(b))$로 나타낼 수 있다.
위 Statement들의 Universe of discourse는 Function의 Domain과 같다.

Function $f$가 $\forall a\forall b(a<b\to f(a)\leq f(b))$이면 Increasing function, $\forall a\forall b(a<b\to f(a)\geq f(b))$이면 Decreasing function이라고 하며 각 Statement에 Equal이 빠질 경우 Strictly increasing(decreasing) function이라고 한다.
Strictly increasing function의 경우 One-to-one function이여야 한다.

Surjection

Onto(=Surjective) function은 Range와 Codomain이 같은 Function을 의미한다.
Function $f$가 Set $A$에서 $B$로 가는 경우 $f$가 Surjection이기 위해 $B$의 모든 Element에 대해 $f(a)=b$인 Element $a$가 존재해야 한다.

Bijection

One-to-one correspondence function은 모든 Element가 One-to-one이며 Onto임을 의미하며 Bijection이라고 한다.

Inverse Functions and Compositions of Functions

Set $A, B$에 대해 $A$에서 $B$로 가는 One-to-one correspondence function $f$가 존재할 때 $f$의 Inverse function은 $B$에 속하는 Element $b$에 대해 $f(a)=b$를 만족하는 $A$의 유일한 Element $a$를 할당하는 Function이며 Notation으로 $f^{-1}$로 표기하며 즉, $f(a)=b$일 때 $f^{-1}(b)=a$가 성립한다.

One-to-one correspondence를 Invertible이라고 하며 Inverse function을 정의할 수 있다는 의미이다.
Not invertible의 경우 One-to-one correspondence이지 않음을 의미한다.

Set $A,B,C$에 대해 Function $g$는 $A$에서 $B$로, $f$를 $B$에서 $C$로 가는 Function이라고 할 때 Function $f, g$의 Composite function은 Notation $f\cdot g$로 표기하며 $f\cdot g(a)=f(g(a))$를 의미한다.

Composition $f\cdot g$는 $g$의 Range가 $f$의 Domain의 Subset인 경우에만 정의 가능하다.

The graphs of Functions

Set $A,B$에 대해 $A$에서 $B$로의 각 Function에 대해 $A\times B$의 Pair set을 Function의 Graph라고 한다.
보통 Function의 동작을 이해하는 데 도움이 되도록 그림으로 표현한다.

Function $f$를 Set $A,B$에 대해 $A$에서 $B$로의 Function이라고 할 때 $f$의 Graph는 $\{(a,b)\mid a\in A \land f(a)=b\}$와 같은 Pair의 Set이며 $A\times B$의 Subset으로 첫 Entry에 의해 $f$가 할당한 $B$의 Element와 두 번째 Entry가 같은 Ordered pair를 포함한다.

Some Important Functions

Floor function은 Real number $x$에 대해 $x$보다 작거나 같은 가장 큰 Integer를 할당하며 Notation $\lfloor x\rfloor$로 표현한다.

Ceiling function은 Real number $x$에 대해 $x$보다 크거나 같은 가장 작은 Integer를 할당하며 Notation $\lceil x\rceil$로 표현한다.

Floor and ceiling function's Properties
$\lfloor x\rfloor = n\text{ if and only if } n\leq x<n+1$
$\lfloor x\rfloor = n\text{ if and only if } x-1 < n \leq x$
$\lceil x\rceil = n\text{ if and only if } n-1 < x \leq n$
$\lceil x\rceil = n\text{ if and only if } x \leq n < x+1$
$x-1<\lfloor x\rfloor \leq x\leq \lceil x \rceil < x+1$
$\lfloor x+n \rfloor = \lfloor x\rfloor + n$
$\lceil x+n \rceil = \lceil x \rceil + n$

2.4. Sequences and Summations

Sequences

Sequence는 Ordered list를 나타내기 위해 사용되는 Discrete structure이다.
Sequence는 Integer의 Subset에서 Set $S$로의 Function으로 나타내며 Sequence의 특정 Element를 Term이라고 한다.

Geometric progression은 $a, ar, ar^2, \cdots, ar^n,\cdots$와 같으며 Inital term은 $a$, Common ratio는 $r$이다.

Arithmetic progression은 $a, a+d, a+2d,\cdots,a+nd,\cdots$와 같으며 Initail term은 $a$, Common difference는 $d$이다.

Finite sequence는 String으로도 표현되며, String $S$의 길이가 0일 경우 Empty string, Notation $\lambda$로 표현한다.

Special Integer Sequences

Sequence의 Term을 구성하는 Formula를 찾는 데 여러 Term들을 확인하여 추측하는 데 도움이 될 수 있다.
패턴을 찾는 것이 유용한데 아래의 사항들을 고려하는 것이 좋다.

• 같은 Value가 여러번 연속되는가?
• 이전 Term에서 같은 Value나 위치에 따라 달라지는 Value를 더하여 Term을 얻는가?
• 특정한 Value의 수를 Product하여 이전의 Term에서 Term을 얻는가?
• 이전의 Term을 특정한 방식으로 결합하여 Term을 얻는가?
• Term 사이에 주기가 존재하는가?

nth Term	First 10 Terms
n^2	1, 4, 9, 16, 25, 36, 49, 64, 81, 100, …
n^3	1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, …
n^4	1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, …
2^n	2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …
3^n	3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, …
n!	1, 2, 6, 120, 720, 5040, 40320, 362880, 3628800, …

Summations

$am,am+1,\cdots,an$의 Summation은 Notation $\sum_{j=m}^n a_j$로 표현한다.
위 Variable $j$를 Index of summation, $m$을 Lower limit, $n$을 Upper limit이라고 한다.

정보

Theorem

Real number $a, r$에 대해 $r\not= 0$일 때 $\sum_{j=0}^nar^j=\begin{cases}\frac{ar^{n+1}-a}{r-1}&\text{if }r\not=1\\(n+1)a&\text{if }r=1\end{cases}$이다.

• Proof
  $S=\sum_{j=0}^nar^j$로 치환하여 아래의 식을 전개한다.
  $rS =r\sum_{j=0}^nar^j\\ =\sum_{j=0}^nar^{j+1}\\ =\sum_{k=1}^{n+1}ar^k\\ =(sum_{k=0}^nar^k)+(ar^{n+1}-a)\\ =S+(ar^{n+1}-a)$

Sum	Closed Form
$\sum_{k=0}^nar^k(r\not=0)$	$\frac{ar^n+1-a}{r-1},r\not=1$
$sum_{k=1}^nk$	$\frac{n(n+1)}{2}$
$\sum_{k=1}^nk^2$	$\frac{n(n+1)(2n+1)}{6}$
$\sum_{k=1}^nk^3$	$\frac{n^2(n+1)^2}{4}$
$\sum_{k=0}^\infin x^k,\|x\|\lt 1$	$\frac{1}{1-x}$
$\sum_{k=1}kx^{k-1},\|x\|\lt 1$	$\frac{1}{(1-x)^2}$

Cardinality

Set $A, B$가 $A$에서 $B$로의 One-to-one coresspondence가 존재할 때만 같은 Cardinality를 가진다.
Infinite set을 Natural number set과 같은 Cardinality를 가진 Set과 다른 Set으로 나누게 되는데 이 때 Finite set이거나 Positive integer와 같은 Cardinality를 가진 Set을 Countable, 그렇지 않은 Set을 Uncountable set이라고 부른다.
Infinite set $S$가 Countable일 때 $S$의 Cardinality를 $\aleph_0$로 표현하며 즉, Notation으로 $|S|=\aleph_0$로 표기하고 $S$의 Cardinality가 Aleph null이라고 한다.

Infinite set은 Set의 Element를 순서대로 나열할 수 있는 경우 Countable이라고 한다.
Uncountable set의 예시로는 Real number set이 존재한다.