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


Скачать книгу
href="#ulink_149d6af8-abfc-53ba-8599-fcc1cad06030">Definition 2.1.3, it follows that AB and BA.

      Next suppose that AB and BA. 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) (AB) = AB;

      (2) (AB) = AB.

      Proof. (1) We will prove this by a sequence of equivalent statements. Let xU be arbitrary. Then x ∈ (AB) if and only if xAB if and only if ¬(xAxB) if and only if xAxB if and only if xAxB if and only if xAB.

      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) AA = U;

      (2) AA =

.

      Proof. (1) One inclusion follows from the fact that BU for all sets B. For the other inclusion, let xU be arbitrary. It follows from propositional logic (the so-called law of excluded middle) that xA ∨ ¬xA. Then by Definition 2.1.1, xAxA and then xAA. Thus UAA.

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

= U = (AA) = A ∩ (A) = AA = AA.

      The inclusion relation may be seen to be a partial ordering. We have just seen above that it is antisymmetric, that is AB and BA imply A = B. Certainly this relation is reflexive, that is, AA. 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) AB;

      (2) AB = A;

      (3) AB = B.

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

      (1)

(2): Assume that AB. Let x be arbitrary. Then xAxB. Now suppose that xA. Then xB and hence xAxB, so that xAB. Thus AAB. Next suppose that xAB. Then xAxB, so certainly xA. Thus ABA. It follows that AB = A, as desired.

      (2)

(1): Suppose that AB = A. Let x be arbitrary and suppose that xA. Since AB = A, it follows that xAB. That is, xAxB, so that xB. Hence AB.

      

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

      Proposition 2.1.9. The following conditions are equivalent:

      (1) AB;

      (2) BA;

      (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 BA and CA, then BCA.

      (2) If AB and AC, then ABC.

      Proof. (1) Assume that BA and CA. Let x be arbitrary and suppose that xBC. This means that xBxC. There are two cases. Suppose first that xB. Since BA, it follows that xA. Suppose next that xC. Since CA, it follows again that xA. Hence xBCxA. Since x was arbitrary, we have BCA, 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, AB = B


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