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

theorems. Topics here will include functions and relations, in particular, orderings and equivalence relations, presented at an informal level. We will return to these topics in a more formal way once we begin to study the axiomatic foundation of set theory. Students who have had a transition course to higher mathematics, such as a course in sets and logic, should be able to go right to the next chapter.

2.1. The Algebra of Sets

      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