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]
AX3. sup { a + b | a∈A, b∈B } ≤ sup A + sup B
Proof
∀ a ∈ A, b ∈ B
⇒ a ≤ sup A
b ≤ sup B
⇒ a + b ≤ sup A + sup B
⇒ a + b ≤ sup{ a + b | a∈A, b∈B } ≤ sup A + sup B
AX4. ∀c∈ℝ and c>0, sup { c·a | a∈A } = c·sup A
Proof
∀ a ∈ A
⇒ a ≤ sup A
⇒ c·a ≤ c·sup A
Suppose c·sup A is not the least upper bound of c·a
⇒ ∃ L∈ℝ s.t. c·a ≤ L < c·sup A
⇒ a ≤ L/c
⇒ sup A ≤ L/c
⇒ c·sup A ≤ L < c·sup A
⇒ contradiction
⇒ sup { c·a | a∈A } = c·sup A
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.
ARM. ∀ 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
To be continued…
