Set Theory — Part 1 (Sup and Inf)
In this article, I will list out some more advanced concepts in the set theory. I assumed that you have studied the basic set theory before, you know what is “union” & “intersection”, what is a function, its domain, pre-image and range.
First, let’s review some propositions from the Set Theory that will be frequently used.
Basic Set Theory Review
Proposition 1: For any universe X and subsets A, B, and C of X, the following identities hold:
Ac = X\A
A\B = A∩Bc
A\B = A\(A∩B)
A\A\B = A∩B
(A\B)c = Ac ∪ B
A∩B ⊆ A
A∩B ⊆ B
A ⊆ A∪B
B ⊆ A∪B
A\(B∪C) = (A\B)∩(A\C)
A\(B∪C) = A∩(B∪C)c
A\(B∩C) = (A\B)∪(A\C)
(A\B)∩C = (A∩C)\(B∩C)
A∩(B\C) = (A∩B)\C
(A∩B)c =Ac ∪ Bc
(A∪B)c =Ac ∩ Bc
A∩(B∪C) = (A∩B)∪(A∩C)
A∪(B∩C) = (A∪B)∩(A∪C)
Proposition 2: For any two sets A and B:
A⊆B ⇒ A\B=ø
A∩B=ø ⇒ A⊆Bc
A∩B=ø ⇒ B⊆Ac
A∩B=ø ⇒ A\B = A
A⊆B ⇒Bc⊆Ac
A⊆B ⇒[x∉B ⇒x∉A]
Proposition 3: For any function f:A→B, f-1:B→A, A0, A1 ⊂ A, B0, B1 ⊂ B [ f-1 means pre-image of B under f ]:
B0⊆B1 ⇒ f-1(B0)⊆f-1(B1)
f-1(B0∪B1) = f-1(B0)∪f-1(B1)
f-1(B0∩B1) = f-1(B0)∩f-1(B1)
f-1(B0\B1) = f-1(B0)\f-1(B1)
A0⊆A1 ⇒ f(A0)⊆f(A1)
f(A0∪A1) = f(A0)∪f(A1)
f(A0∩A1) ⊂ f(A0)∩f(A1)
f(A0)\f(A1) ⊂ f(A0\A1)
f(f-1(B)) ⊆ B
A ⊆ f-1(f(A))
if f is injective:
f(A0∩A1) = f(A0)∩f(A1)
f(A0)\f(A1) = f(A0\A1)
A = f-1(f(A))
if f is surjective:
f(f-1(B)) = B
Bound, Sup and Inf of Set ℝ
Let S be a non-empty set of real numbers ℝ.
A real number x is called an upper bound for S if x ≥ s for all s ∈ S.
Least-upper-bound property — Any non-empty set of real numbers that has an upper bound must have a least upper bound in real numbers.
A real number x is the least upper bound (or supremum) for S if x is an upper bound for S and x ≤ y for every upper bound y of S. The least upper bound of the set S will be denoted by sup S.
A real number x is called an lower bound for S if x ≤ s for all s ∈ S.
Greatest-lower-bound property — Any non-empty set of real numbers that has an lower bound must have a greatest lower bound in real numbers.
A real number x is the greatest lower bound (or infimum) for S if x is an lower bound for S and x ≥ y for every lower bound y of S. The greatest lower bound of the set S will be denoted by inf S.
Let A and B be the non-empty set of real numbers ℝ and both have upper bound. So, both sup A and sup B exists. Below are the properties of sup and inf.
AX1. If A ⊆ B, then sup A ≤ sup B and inf A ≥ inf B
Proof
∀ a ∈ A ⊆ B
⇒ a ∈ B
⇒ a ≤ sup B, a ≥ inf B
⇒ sup A ≤ sup B and inf A ≥ inf B [ Since sup B is a upper bound of A and sup A is the least upper bound of A ]
AX2. ∀ a∈A, b∈B, a ≤ b ⇒ sup A ≤ sup B
Proof
∀ a ∈ A, b ∈ B
⇒ a ≤ sup A
a ≤ b ≤ sup B
⇒ sup A ≤ sup B [ Since sup B is a upper bound of A and sup A is the least upper bound of A]
Denote
A+B = { a+b | a∈A and b∈B }
cA = { c·a | a∈A } where c∈ℝ
AX3. sup A+B = sup A + sup B
Proof
∀ a ∈ A, b ∈ B
⇒ a ≤ sup A, b ≤ sup B, a+b ∈ A+B
⇒ a + b ≤ sup A + sup B
⇒ sup A+B ≤ sup A + sup B [ Since sup A + sup B is an upper bound of A+B ]
∀a ∈ A, a+b ≤ sup A+B [ Since a+b ∈ A+B ]
⇒ a ≤ sup A+B — b
⇒ sup A ≤ sup A+B — b [ Since sup A+B — b is an upper bound of A ]
⇒ ∀b ∈ B, b ≤ sup A+B — sup A
⇒ sup B ≤ sup A+B — sup A [ Since sup A+B — sup A is an upper bound of B ]
⇒ sup A + sup B ≤ sup A+B
Thus, sup A+B = sup A + sup B
AX4. ∀c∈ℝand c ≥ 0, sup cA = c·sup A
Proof
if c = 0 ⇒ cA = {0}, 0*sup A = sup cA = 0
if c > 0,
∀s ∈ cA,
s = ca ≤ c·sup A [ Since ∀a ∈ A, a ≤ sup A ]
⇒ sup cA ≤ c·sup A [ Since c·supA is a upper bound of cA ]
∀a ∈ A,
a = 1/c · ca ≤ 1/c · sup cA [ Since ca ∈ cA ]
⇒ sup A ≤ 1/c · sup cA [ Since 1/c · sup cA is a upper bound of A ]
⇒ c·sup A ≤ sup cA [ Since c > 0 ]
⇒ c·sup A = sup cA
AX5. sup A = inf { M ∈ ℝ | a ≤ M ∀a ∈ A }
Proof
Let UA = { M ∈ ℝ | a ≤ M ∀a ∈ A }
∀a ∈ A
⇒ a ≤ sup A
⇒ sup A ∈ UA
⇒ inf UA ≤ sup A [ Since inf UA is a greatest lower bound for set UA ]
∀M ∈ UA
⇒ a ≤ M ∀a ∈ A
⇒ sup A ≤ M
⇒ sup A is a lower bound for set UA
⇒ sup A ≤ inf UA [ Since inf UA is a greatest lower bound for set UA ]
⇒ sup A = inf UA
AX6. ∀c∈ℝ, sup A > c iff ∃ a ∈ A s.t. a > c
Proof
(only if)
Suppose ∀a ∈ A, a ≤ c
⇒ c is a upper bound of A
⇒ sup A ≤ c [ Since sup A is the least upper bound of A ]
⇒ contradict sup A > c
(if)
∃ a ∈ A s.t. a > c
⇒ c < a ≤ sup A
⇒ sup A > c
Archimedean Property of Set ℝ
The Archimedean Property is a fundamental concept in mathematics. This property implies that no matter how small the positive number xxx is, you can always find a large enough multiple of xxx that exceeds any given positive number yyy.
AX7. ∀ x, y∈ℝ, x, y > 0, ∃ n∈ℕ s.t. nx > y where ℕ is the natural number set
Proof
Suppose ∄ n∈ℕ s.t. nx > y
⇒ ∀n∈ℕ, nx ≤ y ⇒ n ≤ y/x
⇒ ℕ has upper bound y/x
⇒ ℕ has least upper bound M [ By Least-upper-bound property ]
⇒ M-1 is not a upper bound of ℕ
⇒ M-1 < K for some K∈ℕ
⇒ M < K+1, M is not an upper bound ⇒ Contradict M is an upper bound
Here is the application of Archimedean Property:
AX8. Q is Dense in ℝ
Proof
For any x, y ∈ℝ with x < y
Let d=y-x > 0,
⇒ ∃ n∈ℕ s.t. 1 < nd = ny-nx [ By AX7 ]
⇒ 1+nx < ny
∃ z∈ℕ s.t. z-1 < nx < z [ Since nx ∈ ℝ ]
⇒ nx < z < nx+1 < ny
⇒ x < z/n < y where z/n ∈ ℝ
To be continued…
