Math for CS | Part One
ZFC is the standard foundation of modern mathematics
Axioms
Axioms are taken for granted, being so fundamental.
Set
A set is a well defined collection of distinct objects.
Implication
Dhaka-dweller → Bangladesh-dweller
A → B is just A ⊆ B
Equivalence A ←> B
A or B both mean the same thing
For example, x + 60–30 = 0 is equivalent to x = -30
We often want to make things simpler
Size | Lebesgue measure
Length in 1D, Area in 2D, Volume in 3D. Single point has size zero. A collection of points also has size 0.
What does it mean to have equal number of items in two sets?
Ans: Pair each item with an item from the other set. If for each item, an item from the other set always exists, they have the same item. (One-to-one mapping)
Russel’s paradox
R = {x | x is a set and x ∉ x}
Zermelo–Fraenkel set theory | Most widely used axioms with “C” added — ZFC
- Empty set axiom | There exists an empty set | {} is a set
- Axiom of extensionality |
Axiom of choice
Given a collection of non-empty set, there exists a sequence where each term belongs to a corresponding set. The existence of such a set is certain
Countable set
When an infinite set can be indexed by natural numbers
Naive set theory stuff
A = { {a, 2, 3}, 5} B = { {a, 2}, 3, 5} C = { {a, 3, 2}, 5}
A != B as 3 ∈ B and 3 ∉ A
A = C; A and C are the same
{3, 5} ⊆ B as every element of {3, 5} is also an element of B
For any set A, A ⊆ A as every element of the first set is also in the second set. ∅⊆∅ . For every set, ∅ ⊆ P(A). ∅⊆A
∅⊆A is vacuously true as there’s no element inside ∅ to check for its existence in A, Empty string is contained in every string
First order logic notation
