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 - 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.

      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 aA 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.

      (1) aAB if and only if aAaB;

      (2) aAB if and only if aAaB;

      (3) aA if and only if ¬ aA.

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

      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) AB = BA;

      (2) AB = BA.

      Proof. (1) Let x be an arbitrary element of U. We want to show that, for any xU, xAB

xBA. By propositional logic, this means we need to show that xABxBA and that xBAxAB. To prove the first implication, we need to suppose that xAB and then deduce that xBA. We now proceed as follows. Suppose that xAB. Then by Definition 2.1.1, xA or xB. It follows by propositional logic that xBxA. Hence by Definition 2.1.1, xBA. Thus we have shown xABxBA. A similar argument shows that xBAxAB. Then xAB
xBA. Since x was arbitrary, we have (∀x)[xAB
xBA]. It then follows by Extensionality that AB = BA.

      Part (2) is left to the exercises.

      The notion of subset, or inclusion, is fundamental.

      (1) AB

(∀x)[xAxB]. We say that A is included in B if AB.

      (2) AB

ABAB.

       Proposition 2.1.4 (Associative Laws).

      (1) A ∩ (BC) = (AB) ∩ C;

      (2) A ∪ (BC) = (AB) ∪ C.

      Proof. (1) A ∩ (BC) = (AB) ∩ C. Let x be an arbitrary element of U and suppose that xA ∩ (BC). Then by Definition 2.1.1, we have xA and xBC and therefore xB and xC. It follows by propositional logic that xAxB, and thus xAB. Then by propositional logic, (xAB) ∧ xC. Thus by Definition 2.1.1, x ∈ (AB) ∩ C. Thus xA ∩ (BC) → x ∈ (AB) ∩ C. A similar argument shows that x ∈ (AB) ∩ Cx ∈ (A ∩ (BC)). Since x was arbitrary, we have (∀x)[xA ∩ (BC) → x ∈ (AB) ∩ C]. It now follows by Extensionality that A ∩ (BC) = (AB) ∩ 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

ABBA.

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

xB]. Now let xU be arbitrary. Then xA
xB. It follows from propositional
Скачать книгу