Sets

4 분 소요

Introduction

S={a,b,c,d}
- 순서는 중요하지 않음
  - S = {a,b,c,d} = {b,c,a,d}
- 같은 원소를 한번이상 나열해도 집합은 변하지 않음
  - S = {a,b,c,d} = {a,b,c,b,c,d}
- Elipses (…): 생략
  - S = {a,b,c,d,…..,z}
Some Important Sets
- N = natural numbers = {0,1,2,3,…}
- Z = integers = {…, -3, -2, -1, 0, 1, 2, 3…}
- Z+ = positive integers = { 1, 2, 3…}
- R = set of real numbers
- R+ = set of positive real numbers
- C = set of complex numbers
- Q = set of rational numbers
Set-Builder Notation
- Specify the property(ies) (description)
  - S = { x | x is a positive integer less than 100}
  - O = { x | x is an odd positive integer less than 10}
  - O = { x∈Z+ | x is odd and x<10}
Interval Notation
- closed interval [a,b]
- open interval (a, b)
  - [a,b] = { x | a ≤ x ≤ b }
  - [a,b) = { x | a ≤ x < b }
  - (a,b] = { x | a < x ≤ b }
  - (a,b) = { x | a < x < b }
Sets can be elements of sets
- {{1,2,3}, a, {b/c}}
- {N,Z,Q,R}

Universal Set (U)
- the set containing everything
Empty Set (∅ or {})
- the set with no elements
- The empty set is different from a set containing the empty set
  - ∅(empty set) ≠ {∅}(a set containing the empty set)

The set A is a subset of B, iff every element of A is also an element of B
- A⊆B ↔︎ ∀x(x∈A → x∈B)
- IF) ∀x(x∈A ∧ x∉B), A cannot be a subset of B
Showing that A is a Subset of B
- if x belongs to A, then x also belongs to B
Showing that A is not a Subset of B
- find an element x ∈ A with x ∉ B (counterexample)
- Ex)
  The set of integers with squares less than 100 is not a subset of the set of nonnegative integers
  counterexample: -1, -4 …

Two sets are equal iff they have the same elements
- A, B: Sets, A=B ↔︎ ∀(x∈A ↔︎ x∈B)
- Ex)
  {1,3,5} = {3,5,1}
  {1,5,5,5,3,3,1} = {1,3,5}
Logical equivalences
- A↔︎B ≡ (A→B) ∧ (B→A)
- ∀x[(x∈A → x∈B) ∧ (x∈B → x∈A)]
- ≡ A⊆B and B⊆A
∴A=B iff A⊆B and B⊆A

The Cardinality of a finite set A

A × B = {(a,b) | a∈A ∧ b∈B}
Ex)
- A = {a,b} B = {1,2,3} C = {c, d}
- A × B = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}
- A × B × C = {(a, 1, c), (a, 1, d), (a, 2, c), … , (b,3,c), (b,3,d)}
  - |A × B × C| = 12

The truth set of P

Union
- A ∪ B
- {x | x∈A ∨ x∈B}
Intersection
- A ∩ B
- {x | x∈A ∧ x∈B}
- intersection is empty(∅) -> disjoint
  - is not independent (컨셉이 다름)
Complement
- Ā or A^c
- {x∈U | x∉A} : U-A
Difference
- A - B
- {x | x∈A ∧ x∉B}
The Cardinality(||) of the Union of Two Sets
- |A ∪ B| = |A| + |B| - |A ∩ B|

Identity laws
- A ∪ ∅ = A
- A ∩ U = A
Domination laws
- A ∪ U = U
- A ∩ ∅ = ∅
Idempotent laws
- A ∪ A = A
- A ∩ A = A
Complementation law
- (Ẫ) = A
Commutative laws
- A ∪ B = B ∪ A
- A ∩ B = B ∩ A
Associative laws
- A ∪ (B ∪ C) = (A ∪ B) ∪ C
- A ∩ (B ∩ C) = (A ∩ B) ∩ C
Distributive laws
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Absorption laws
- A ∪ (A ∩ B) = A
- A ∩ (A ∪ B) = A
Complement laws
- A ∪ Ā = U
- A ∩ Ā = ∅
De Morgan’s laws