Reference no: EM132248576

Set Theory Questions - Order Relations and Functions

The following exercises should be solved using only first-order logic and the first six axioms of Zermelo-Fraenkel set theory.

Q1. Let (A, ≤_A) and (B, ≤_B) be posets and define the relation ≤ on A x B by (x₁, y₁) ≤ (x₂, y₂) :⇔ x₁ <_A x₂ or (x₁ = x₂ and y₁ ≤_B y₂).

a) Prove that ≤ is a partial order (known as the lexicographical order) on A x B.

b) Prove that if ≤_A is a total order on A and ≤_B is a total order on B, then ≤ is a total order on A x B.

c) Describe (e.g., by drawing the Hasse diagram) the poset (A x B, ≤), when (A, ≤_A) = (P({a}), ⊆) and (B, ≤_B) = (P({a, b}), ⊆).

Q2. For the poset ({∅, {a}, {b}, {c}, {d}, {a, b, c}, {a, b, d}}, ⊆), determine (when they exist) the upper bounds, least upper bound, lower bounds, and greatest lower bound of the following sets:

(i) {{a}, {b}}

(ii) {{a}, {c}}

(iii) {{a, b, c}, {a, b, d}}

(iv) ∅

(v) {∅}.

Q3. Prove that for any functions F and G:

(i) F ο G is a function.

(ii) dom (F ο G) = {x ∈ dom (G) : G(x) ∈ dom (F)}.

(iii) (F ο G)(x) = F(G(x)) for all x ∈ dom (F ο G).

Q4. Let A be a set of functions such that for all F, G ∈ A, either F ⊆ G or G ⊆ F.

a) Prove that ∪A is a function.

b) Prove that if every F ∈ A is injective, then ∪A is injective.

Q5. Let F : A → B be a function and define the relation ∼ on A by

x ∼ y :⇔ F(x) = F(y).

Prove that ∼ is an equivalence relation on A and describe its equivalence classes.

Instructions: "It's Set Theory on a university level".

Attachment:- Assignment File.rar