Читать книгу Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory - Douglas Cenzer - Страница 10

In naive set theory, there is a universe U of all elements. For example, this may be the set of real numbers or the set = {0, 1, 2, . . . } of natural numbers, or perhaps some finite set. The fundamental relation of set theory is that of membership. For a subset A of U and an element a of A, we write a ∈ A to mean that a belongs to A, or is an element of A. The family (U) of subsets of U has the natural Boolean operations of union, intersection, and complement, as follows.

Definition 2.1.1. For any element a of U and any subsets A and B of U,

(1) a ∈ A ∪ B if and only if a ∈ A ∨ a ∈ B;

(2) a ∈ A ∩ B if and only if a ∈ A ∧ a ∈ B;

(3) a ∈ A^∁ if and only if ¬ a ∈ A.

Here we use the symbols ∨, ∧, and ¬ to denote the logical connectives or, and, and not. We will frequently write x ∉ A as an abbreviation for ¬ x ∈ A.

The convention is that two sets A and B are equal if they contain the same elements, that is

This is codified in the Axiom of Extensionality, one of the axioms of Zermelo–Fraenkel set theory which will be presented in detail in Chapter 3. The family of subsets of U composes a Boolean algebra, that is, it satisfies certain properties such as the associative, commutative, and distributive laws. We will consider some of these now, and leave others to the exercises. We will put in all of the details at first, and later on leave some of them to the reader.

Proposition 2.1.2 (Commutative Laws). For any sets A and B,

(1) A ∪ B = B ∪ A;

(2) A ∩ B = B ∩ A.

Proof. (1) Let x be an arbitrary element of U. We want to show that, for any x ∈ U, x ∈ A ∪ B x ∈ B ∪ A. By propositional logic, this means we need to show that x ∈ A ∪ B → x ∈ B ∪ A and that x ∈ B ∪ A → x ∈ A ∪ B. To prove the first implication, we need to suppose that x ∈ A∪B and then deduce that x ∈ B∪A. We now proceed as follows. Suppose that x ∈ A ∪ B. Then by Definition 2.1.1, x ∈ A or x ∈ B. It follows by propositional logic that x ∈ B ∨ x ∈ A. Hence by Definition 2.1.1, x ∈ B ∪ A. Thus we have shown x ∈ A ∪ B → x ∈ B ∪ A. A similar argument shows that x ∈ B ∪ A → x ∈ A ∪ B. Then x ∈ A ∪ B x ∈ B ∪ A. Since x was arbitrary, we have (∀x)[x ∈ A ∪ B x ∈ B ∪ A]. It then follows by Extensionality that A ∪ B = B ∪ A.

Part (2) is left to the exercises.

The notion of subset, or inclusion, is fundamental.

Definition 2.1.3. For any sets A and B, we have the following conditions:

(1) A ⊆ B (∀x)[x ∈ A → x ∈ B]. We say that A is included in B if A ⊆ B.

(2) A ⊊ B A ⊆ B ∧ A ≠ B.

Proposition 2.1.4 (Associative Laws).

(1) A ∩ (B ∩ C) = (A ∩ B) ∩ C;

(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. 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 ∩ A.

Exercise 2.1.2. Prove the Associative Law for union, that is, for any sets A, B, and C, A ∪ (B ∪ C) = (A ∪ B) ∪ C.

Exercise 2.1.3. Prove the Distributive Laws, that is, for any sets A, B, and C, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Exercise 2.1.4. Show that, for any set A, ⊆ A and A ⊆ U.

Exercise 2.1.5. Show that, for any set A, (A^∁)^∁ = A.

Exercise 2.1.6. Show that, for any set A, A ∪ = A and A ∩ U = A.

Exercise 2.1.7. Show that, for any set A, A ∩ = and A ∪ U = U.

Exercise 2.1.8. Complete the argument that the relation ⊆ is a partial ordering by showing that it is transitive, that is, if A ⊆ B and B ⊆ C then A ⊆ C.

Exercise 2.1.9. Show that, for any sets A and B, A ⊆ B if and only if A ∪ B = B.

Exercise 2.1.10. Show that the following conditions are equivalent:

(1) A ⊆ B;

(2) B^∁ ⊆ A^∁;

(3) A \ B = .

Exercise 2.1.11. Show that, for any sets A, B, and C, A ⊆ B and A ⊆ C imply that A ⊆ B ∩ C.