Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory. Douglas Cenzer

Скачать книгу

      (2) A ∪ (B ∪ C) = (A ∪ B) ∪ C.

      Proof. (1) A ∩ (B ∩ C) = (A ∩ B) ∩ C. Let x be an arbitrary element of U and suppose that x ∈ A ∩ (B ∩ C). Then by Definition 2.1.1, we have x ∈ A and x ∈ B ∩ C and therefore x ∈ B and x ∈ C. It follows by propositional logic that x ∈ A ∧ x ∈ B, and thus x ∈ A ∩ B. Then by propositional logic, (x ∈ A ∩ B) ∧ x ∈ C. Thus by Definition 2.1.1, x ∈ (A ∩ B) ∩ C. Thus x ∈ A ∩ (B ∩ C) → x ∈ (A ∩ B) ∩ C. A similar argument shows that x ∈ (A ∩ B) ∩ C → x ∈ (A ∩ (B ∩ C)). Since x was arbitrary, we have (∀x)[x ∈ A ∩ (B ∩ C) → x ∈ (A ∩ B) ∩ C]. It now follows by Extensionality that A ∩ (B ∩ C) = (A ∩ B) ∩ C.

      Part (2) is left to the exercises.

      

      The following proposition can help simplify a proof that two sets are equal.

      Proposition 2.1.5. For any sets A and B, A = B

A ⊆ B ∧ B ⊆ A.

      Proof. Suppose first that A = B. This means that (∀x)[x ∈ A

x ∈ B]. Now let x ∈ U be arbitrary. Then x ∈ A

x ∈ B. It follows from propositional logic that x ∈ A → x ∈ B and also x ∈ B → x ∈ A. Since x was arbitrary we have (∀x)[x ∈ A → x ∈ B] and (∀x)[x ∈ B → x ∈ A]. Then by Definition 2.1.3, it follows that A ⊆ B and B ⊆ A.

      Next suppose that A ⊆ B and B ⊆ A. The steps above can be reversed to deduce that A = B.

      The empty set

is defined by the following property:

      It is easy to see that

= U^∁ and that

^∁ = U. This is left as an exercise.

      Proposition 2.1.6 (DeMorgan’s Laws). For any sets A and B,

      (1) (A ∪ B)^∁ = A^∁ ∩ B^∁;

      (2) (A ∩ B)^∁ = A^∁ ∪ B^∁.

      Proof. (1) We will prove this by a sequence of equivalent statements. Let x ∈ U be arbitrary. Then x ∈ (A ∪ B)^∁ if and only if x ∉ A ∪ B if and only if ¬(x ∈ A ∨ x ∈ B) if and only if x ∉ A ∧ x ∉ B if and only if x ∈ A^∁ ∧ x ∈ B^∁ if and only if x ∈ A^∁ ∩ B^∁.

      Part (2) is left to the exercises.

      The universal set U and the empty set are the identities of the Boolean algebra

(U). This is spelled out in the following proposition.

      

      Proposition 2.1.7 (Identity Laws). For any set A,

      (1) A ∪ A^∁ = U;

      (2) A ∩ A^∁ =

.

      Proof. (1) One inclusion follows from the fact that B ⊆ U for all sets B. For the other inclusion, let x ∈ U be arbitrary. It follows from propositional logic (the so-called law of excluded middle) that x ∈ A ∨ ¬x ∈ A. Then by Definition 2.1.1, x ∈ A ∨ x ∈ A^∁ and then x ∈ A ∪ A^∁. Thus U ⊆ A ∪ A^∁.

      (2) This follows from (1) using DeMorgan’s laws. Given part (1) that A ∪ A^∁ = U, we obtain

= U^∁ = (A ∪ A^∁)^∁ = A^∁ ∩ (A^∁)^∁ = A^∁ ∩ A = A ∩ A^∁.

      The inclusion relation may be seen to be a partial ordering. We have just seen above that it is antisymmetric, that is A ⊆ B and B ⊆ A imply A = B. Certainly this relation is reflexive, that is, A ⊆ A. Transitivity is left to the exercises.

      Inclusion may be defined from the Boolean operations in several ways.

      Proposition 2.1.8. The following conditions are equivalent:

      (1) A ⊆ B;

      (2) A ∩ B = A;

      (3) A ∪ B = B.

      Proof. We will show that (1) and (2) are equivalent and leave the other equivalence to the exercises.

      (1)

(2): Assume that A ⊆ B.

Скачать книгу