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

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

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

href="#ulink_149d6af8-abfc-53ba-8599-fcc1cad06030">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. Let x be arbitrary. Then x ∈ A → x ∈ B. Now suppose that x ∈ A. Then x ∈ B and hence x ∈ A ∧ x ∈ B, so that x ∈ A ∩ B. Thus A ⊆ A ∩ B. Next suppose that x ∈ A∩B. Then x ∈ A ∧ x ∈ B, so certainly x ∈ A. Thus A ∩ B ⊆ A. It follows that A ∩ B = A, as desired.

(2)

(1): Suppose that A ∩ B = A. Let x be arbitrary and suppose that x ∈ A. Since A ∩ B = A, it follows that x ∈ A ∩ B. That is, x ∈ A ∧ x ∈ B, so that x ∈ B. Hence A ⊆ B.

We will sometimes write A \ B for A ∩ B^∁. The proof of the following is left as an exercise.

Proposition 2.1.9. The following conditions are equivalent:

(1) A ⊆ B;

(2) B^∁ ⊆ A^∁;

(3) A \ B =

There are some interactions between the inclusion relation and the Boolean operations, in the same way that inequality for numbers interacts with the addition and multiplication operations.

Proposition 2.1.10. For any sets A, B, and C, we have the following properties:

(1) If B ⊆ A and C ⊆ A, then B ∪ C ⊆ A.

(2) If A ⊆ B and A ⊆ C, then A ⊆ B ∩ C.

Proof. (1) Assume that B ⊆ A and C ⊆ A. Let x be arbitrary and suppose that x ∈ B ∪ C. This means that x ∈ B ∨ x ∈ C. There are two cases. Suppose first that x ∈ B. Since B ⊆ A, it follows that x ∈ A. Suppose next that x ∈ C. Since C ⊆ A, it follows again that x ∈ A. Hence x ∈ B ∪ C → x ∈ A. Since x was arbitrary, we have B ∪ C ⊆ A, as desired.

The proof of part (2) is left to the exercises.

Exercises for Section 2.1

Exercise 2.1.1. Prove the Commutative Law for intersection, that is, for any sets A and B, A ∩ B = B

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