Enderton.Set.Chapter_2

Axioms and Operations

Commutative Laws

For any sets A and B,

A ∪ B = B ∪ A
A ∩ B = B ∩ A

theorem Enderton.Set.Chapter_2.commutative_law_i {α : Type u_1} (A : Set α) (B : Set α) : A ∪ B = B ∪ A

theorem Enderton.Set.Chapter_2.commutative_law_ii {α : Type u_1} (A : Set α) (B : Set α) : A ∩ B = B ∩ A

Associative Laws

For any sets A, B, and C,

A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C

theorem Enderton.Set.Chapter_2.associative_law_i {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∪ (B ∪ C) = A ∪ B ∪ C

theorem Enderton.Set.Chapter_2.associative_law_ii {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∩ (B ∩ C) = A ∩ B ∩ C

Distributive Laws

For any sets A, B, and C,

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

theorem Enderton.Set.Chapter_2.distributive_law_i {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∩ (B ∪ C) = A ∩ B ∪ A ∩ C

theorem Enderton.Set.Chapter_2.distributive_law_ii {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∪ B ∩ C = (A ∪ B) ∩ (A ∪ C)

De Morgan's Laws

For any sets A, B, and C,

C - (A ∪ B) = (C - A) ∩ (C - B)
C - (A ∩ B) = (C - A) ∪ (C - B)

theorem Enderton.Set.Chapter_2.de_morgans_law_i {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : C \ (A ∪ B) = C \ A ∩ (C \ B)

theorem Enderton.Set.Chapter_2.de_morgans_law_ii {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : C \ (A ∩ B) = C \ A ∪ C \ B

Identities Involving ∅

For any set A,

A ∪ ∅ = A
A ∩ ∅ = ∅
A ∩ (C - A) = ∅

theorem Enderton.Set.Chapter_2.emptyset_identity_i {α : Type u_1} (A : Set α) : A ∪ ∅ = A

theorem Enderton.Set.Chapter_2.emptyset_identity_ii {α : Type u_1} (A : Set α) : A ∩ ∅ = ∅

theorem Enderton.Set.Chapter_2.emptyset_identity_iii {α : Type u_1} (A : Set α) (C : Set α) : A ∩ (C \ A) = ∅

Monotonicity

For any sets A, B, and C,

A ⊆ B ⇒ A ∪ C ⊆ B ∪ C
A ⊆ B ⇒ A ∩ C ⊆ B ∩ C
A ⊆ B ⇒ ⋃ A ⊆ ⋃ B

theorem Enderton.Set.Chapter_2.monotonicity_i {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) (h : A ⊆ B) : A ∪ C ⊆ B ∪ C

theorem Enderton.Set.Chapter_2.monotonicity_ii {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) (h : A ⊆ B) : A ∩ C ⊆ B ∩ C

theorem Enderton.Set.Chapter_2.monotonicity_iii {α : Type u_1} (A : Set (Set α)) (B : Set (Set α)) (h : A ⊆ B) : ⋃₀ A ⊆ ⋃₀ B

Anti-monotonicity

For any sets A, B, and C,

A ⊆ B ⇒ C - B ⊆ C - A
∅ ≠ A ⊆ B ⇒ ⋂ B ⊆ ⋂ A

theorem Enderton.Set.Chapter_2.anti_monotonicity_i {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) (h : A ⊆ B) : C \ B ⊆ C \ A

theorem Enderton.Set.Chapter_2.anti_monotonicity_ii {α : Type u_1} (A : Set (Set α)) (B : Set (Set α)) (h : A ⊆ B) : ⋂₀ B ⊆ ⋂₀ A

theorem Enderton.Set.Chapter_2.inter_diff_assoc {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∩ (B \ C) = (A ∩ B) \ C

Intersection/Difference Associativity

Let A, B, and C be sets. Then A ∩ (B - C) = (A ∩ B) - C.

theorem Enderton.Set.Chapter_2.exercise_2_1 {A : Set ℤ} {B : Set ℤ} {C : Set ℤ} (hA : A = {x : ℤ | 4 ∣ x}) (hB : B = {x : ℤ | 9 ∣ x}) (hC : C = {x : ℤ | 10 ∣ x}) (x : ℤ) : x ∈ A ∩ B ∩ C → 4 ∣ x ∧ 9 ∣ x ∧ 10 ∣ x

Exercise 2.1

Assume that A is the set of integers divisible by 4. Similarly assume that B and C are the sets of integers divisible by 9 and 10, respectively. What is in A ∩ B ∩ C?

theorem Enderton.Set.Chapter_2.exercise_2_2 {A : Set (Set ℕ)} {B : Set (Set ℕ)} (hA : A = {{1}, {2}}) (hB : B = {{1, 2}}) : ⋃₀ A = ⋃₀ B ∧ A ≠ B

Exercise 2.2

Give an example of sets A and B for which ⋃ A = ⋃ B but A ≠ B.

theorem Enderton.Set.Chapter_2.exercise_2_3 {α : Type u_1} {A : Set (Set α)} (x : Set α) : x ∈ A → x ⊆ ⋃₀ A

Exercise 2.3

Show that every member of a set A is a subset of U A. (This was stated as an example in this section.)

theorem Enderton.Set.Chapter_2.exercise_2_4 {α : Type u_1} {A : Set (Set α)} {B : Set (Set α)} (h : A ⊆ B) : ⋃₀ A ⊆ ⋃₀ B

Exercise 2.4

Show that if A ⊆ B, then ⋃ A ⊆ ⋃ B.

theorem Enderton.Set.Chapter_2.exercise_2_5 {α : Type u_1} {B : Set α} {𝓐 : Set (Set α)} (h : ∀ x ∈ 𝓐, x ⊆ B) : ⋃₀ 𝓐 ⊆ B

Exercise 2.5

Assume that every member of 𝓐 is a subset of B. Show that ⋃ 𝓐 ⊆ B.

theorem Enderton.Set.Chapter_2.exercise_2_6a : ∀ {α : Type u_1} {A : Set α}, ⋃₀ (𝒫 A) = A

Exercise 2.6a

Show that for any set A, ⋃ 𝓟 A = A.

theorem Enderton.Set.Chapter_2.exercise_2_6b : ∀ {α : Type u_1} {A : Set (Set α)}, A ⊆ 𝒫⋃₀ A ∧ (A = 𝒫⋃₀ A ↔ ∃ (B : Set α), A = 𝒫 B)

Exercise 2.6b

Show that A ⊆ 𝓟 ⋃ A. Under what conditions does equality hold?

theorem Enderton.Set.Chapter_2.exercise_2_7A : ∀ {α : Type u_1} {A B : Set α}, 𝒫 A ∩ 𝒫 B = 𝒫(A ∩ B)

Exercise 2.7a

Show that for any sets A and B, 𝓟 A ∩ 𝓟 B = 𝓟 (A ∩ B).

theorem Enderton.Set.Chapter_2.exercise_2_7b_i : ∀ {α : Type u_1} {A B : Set α}, 𝒫 A ∪ 𝒫 B ⊆ 𝒫(A ∪ B)

Exercise 2.7b (i)

Show that 𝓟 A ∪ 𝓟 B ⊆ 𝓟 (A ∪ B).

theorem Enderton.Set.Chapter_2.exercise_2_7b_ii : ∀ {α : Type u_1} {A B : Set α}, 𝒫 A ∪ 𝒫 B = 𝒫(A ∪ B) ↔ A ⊆ B ∨ B ⊆ A

Exercise 2.7b (ii)

Under what conditions does 𝓟 A ∪ 𝓟 B = 𝓟 (A ∪ B).?

theorem Enderton.Set.Chapter_2.exercise_2_9 {a : Set ℕ} {B : Set (Set ℕ)} (ha : a = {1}) (hB : B = {{1}}) : a ∈ B ∧ 𝒫 a ∉ 𝒫 B

Exercise 2.9

Give an example of sets a and B for which a ∈ B but 𝓟 a ∉ 𝓟 B.

theorem Enderton.Set.Chapter_2.exercise_2_10 {α : Type u_1} {a : Set α} {B : Set (Set α)} (ha : a ∈ B) : 𝒫 a ∈ 𝒫 𝒫⋃₀ B

Exercise 2.10

Show that if a ∈ B, then 𝓟 a ∈ 𝓟 𝓟 ⋃ B.

theorem Enderton.Set.Chapter_2.exercise_2_11_i {α : Type u_1} {A : Set α} {B : Set α} : A = A ∩ B ∪ A \ B

Exercise 2.11 (i)

Show that for any sets A and B, A = (A ∩ B) ∪ (A - B).

theorem Enderton.Set.Chapter_2.exercise_2_11_ii {α : Type u_1} {A : Set α} {B : Set α} : A ∪ B \ A = A ∪ B

Exercise 2.11 (ii)

Show that for any sets A and B, A ∪ (B - A) = A ∪ B.

theorem Enderton.Set.Chapter_2.right_diff_eq_insert_one_three {A : Set ℕ} {B : Set ℕ} {C : Set ℕ} {hA : A = {1, 2, 3}} {hB : B = {2, 3, 4}} {hC : C = {3, 4, 5}} : A \ (B \ C) = {1, 3}

theorem Enderton.Set.Chapter_2.left_diff_eq_singleton_one {A : Set ℕ} {B : Set ℕ} {C : Set ℕ} {hA : A = {1, 2, 3}} {hB : B = {2, 3, 4}} {hC : C = {3, 4, 5}} : (A \ B) \ C = {1}

theorem Enderton.Set.Chapter_2.exercise_2_14 {A : Set ℕ} {B : Set ℕ} {C : Set ℕ} {hA : A = {1, 2, 3}} {hB : B = {2, 3, 4}} {hC : C = {3, 4, 5}} : A \ (B \ C) ≠ (A \ B) \ C

Exercise 2.14

Show by example that for some sets A, B, and C, the set A - (B - C) is different from (A - B) - C.

theorem Enderton.Set.Chapter_2.exercise_2_15a {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∩ B ∆ C = (A ∩ B) ∆ (A ∩ C)

Exercise 2.15 (a)

Show that A ∩ (B + C) = (A ∩ B) + (A ∩ C).

theorem Enderton.Set.Chapter_2.exercise_2_15b {α : Type u_1} (A : Set α) (B : Set α) (C : Set α) : A ∆ (B ∆ C) = A ∆ B ∆ C

Exercise 2.15 (b)

Show that A + (B + C) = (A + B) + C.

theorem Enderton.Set.Chapter_2.exercise_2_16 {α : Type u_1} {A : Set α} {B : Set α} {C : Set α} : ((A ∪ B ∪ C) ∩ (A ∪ B)) \ ((A ∪ B \ C) ∩ A) = B \ A

Exercise 2.16

Simplify: [(A ∪ B ∪ C) ∩ (A ∪ B)] - [(A ∪ (B - C)) ∩ A]

Exercise 2.17

Show that the following four conditions are equivalent.

(a) A ⊆ B (b) A - B = ∅ (c) A ∪ B = B (d) A ∩ B = A

theorem Enderton.Set.Chapter_2.exercise_2_17_i {α : Type u_1} {A : Set α} {B : Set α} (h : A ⊆ B) : A \ B = ∅

theorem Enderton.Set.Chapter_2.exercise_2_17_ii {α : Type u_1} {A : Set α} {B : Set α} (h : A \ B = ∅) : A ∪ B = B

theorem Enderton.Set.Chapter_2.exercise_2_17_iii {α : Type u_1} {A : Set α} {B : Set α} (h : A ∪ B = B) : A ∩ B = A

theorem Enderton.Set.Chapter_2.exercise_2_17_iv {α : Type u_1} {A : Set α} {B : Set α} (h : A ∩ B = A) : A ⊆ B

theorem Enderton.Set.Chapter_2.exercise_2_19 {α : Type u_1} {A : Set α} {B : Set α} : 𝒫(A \ B) ≠ 𝒫 A \ 𝒫 B

Exercise 2.19

Is 𝒫 (A - B) always equal to 𝒫 A - 𝒫 B? Is it ever equal to 𝒫 A - 𝒫 B?

theorem Enderton.Set.Chapter_2.exercise_2_20 {α : Type u_1} {A : Set α} {B : Set α} {C : Set α} (hu : A ∪ B = A ∪ C) (hi : A ∩ B = A ∩ C) : B = C

Exercise 2.20

Let A, B, and C be sets such that A ∪ B = A ∪ C and A ∩ B = A ∩ C. Show that B = C.

theorem Enderton.Set.Chapter_2.exercise_2_21 {α : Type u_1} {A : Set (Set α)} {B : Set (Set α)} : ⋃₀ (A ∪ B) = ⋃₀ A ∪ ⋃₀ B

Exercise 2.21

Show that ⋃ (A ∪ B) = (⋃ A) ∪ (⋃ B).

theorem Enderton.Set.Chapter_2.exercise_2_22 {α : Type u_1} {A : Set (Set α)} {B : Set (Set α)} : ⋂₀ (A ∪ B) = ⋂₀ A ∩ ⋂₀ B

Exercise 2.22

Show that if A and B are nonempty sets, then ⋂ (A ∪ B) = ⋂ A ∩ ⋂ B.

theorem Enderton.Set.Chapter_2.exercise_2_24a {α : Type u_1} {𝓐 : Set (Set α)} : 𝒫⋂₀ 𝓐 = ⋂₀ {x : Set (Set α) | ∃ X ∈ 𝓐, 𝒫 X = x}

Exercise 2.24a

Show that is 𝓐 is nonempty, then 𝒫 (⋂ 𝓐) = ⋂ { 𝒫 X | X ∈ 𝓐 }.

theorem Enderton.Set.Chapter_2.exercise_2_24b {α : Type u_1} {𝓐 : Set (Set α)} : ⋃₀ {x : Set (Set α) | ∃ X ∈ 𝓐, 𝒫 X = x} ⊆ 𝒫⋃₀ 𝓐 ∧ (⋃₀ {x : Set (Set α) | ∃ X ∈ 𝓐, 𝒫 X = x} = 𝒫⋃₀ 𝓐 ↔ ⋃₀ 𝓐 ∈ 𝓐)

Exercise 2.24b

Show that

⋃ {𝒫 X | X ∈ 𝓐} ⊆ 𝒫 ⋃ 𝓐.

Under what conditions does equality hold?

theorem Enderton.Set.Chapter_2.exercise_2_25 {α : Type u_1} {A : Set α} (𝓑 : Set (Set α)) : A ∪ ⋃₀ 𝓑 = ⋃₀ {x : Set α | ∃ X ∈ 𝓑, A ∪ X = x} ↔ A = ∅ ∨ Set.Nonempty 𝓑

Exercise 2.25

Is A ∪ (⋃ 𝓑) always the same as ⋃ { A ∪ X | X ∈ 𝓑 }? If not, then under what conditions does equality hold?