DOC PREVIEW
UCR MATH 144 - Elementary constructions on sets

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

I I I : Elementary constructions on setsIn this unit we cover the some fundamental constructions of set theory that are used throughout the mathematical sciences.Much of this material is probably extremely familiar, but we shall start at the beginning for several reasons, including the following:1. To ensure that the discussion is complete.2. To emphasize the more abstract perspective on the material.3. To state some subtle but important differences in terminology between these notes and more elementary treatments of the material.In the final section of this unit we shall indicate how one expresses everything in more formal and axiomatic terms. Numbering conventions. In mathematics it is often necessary to use results that were previously established. Throughout these notes we shall refer to results from earlier sections by notation like Proposition I I .4.6, which will denote Proposition 6 from SectionI I.4 (this particular example does not actually exist, but it should illustrate the key points adequately). I I I .1 : Boolean operations(Halmos, §§ 4 – 5; Lipschutz, §§ 1.6 – 1.7)We shall begin with a discussion of unions, intersections and complements. In order to keep the discussion simple and familiar at the beginning, we shall begin by considering only those sets which are subsets of some fixed set S. Definitions. Let A and B be subsets of some set S. The standard Boolean operations on these sets are defined as follows:- The intersection of A and B is the set of all elements common to both sets. It is symbolized by A  B or { x  S | x  A and a  B }. - The union of two sets A and B is the set of elements which are in A or B or both.It is symbolized by A  B or { x  S | x  A or x  B }. - The relative complement of A in S is the set of all elements in S that do not belong to A. It is symbolized by S – A or { x  S | x  A }.Numerous other symbols are also used for the relative complement of A, including 36and A  and Ac and also by an A with a long horizontal line over it ( Ā ). We shall now review and prove the standard relationships between these three operations on subsets of S. The first group describes the class of algebraic identities involving unions and intersections which appear in the writings of G. Boole.Theorem 1. Let A, B and C be subsets of some fixed set S. Then the union and intersection defined as above satisfy the following Boolean algebra identities:(Idempotent Law for unions.) A  A = A. (Idempotent Law for intersections.) A  A = A. (Commutative Law for unions.) A  B = B  A. (Commutative Law for intersections.) A  B = B  A. (Associative Law for unions.) A  (B  C) = (A  B)  C. (Associative Law for intersections.) A  (B  C) = (A  B)  C.(Distributive Law 1.) A  (B  C) = (A  B)  (A  C).(Distributive Law 2.) A  (B  C) = (A  B)  (A  C).(Zero Law.) A  Ø = A.(Unit Law.) A  S = A.The second group of relations also involves complementation.Theorem 2. Let A and B be subsets of some fixed set S. Then the union, intersection and relative complement satisfy the following identities:(Double negative Law.) (A)  = A. (Complementation Law 1.) A  A  = S.(Complementation Law 2.) A  A  = Ø.(De Morgan’s Law 1.) (A  B)  = A   B .(De Morgan’s Law 2.) (A  B)  = A   B .37Most if not all the verifications of these rules are fairly straightforward, and they essentially follow from the formulas for propositional calculus listed in Section I I.0. We shall fill in the details atfter the next heading. Some ideitities are more obvious than others (in particular, the distributive laws and De Morgan’s laws are probably less intuitive than the commutative and associative laws), and in these cases we shall also give alternate arguments that are more detailed Boolean operations and subsetsThere are simple but important characterizations of the relationship A  B in terms of unions and intersections.Theorem 3. Let A and B be subsets of some fixed set S. Then the following are equivalent:(i) A  B = B(ii) A  B(iii) A  B = AProof. There are four parts to the argument.(i)  (ii) If x  A, then x  A or x  B, and hence x  A  B, which is B. Hence we have A  B.(ii)  (i) If A  B and x  A  B, then x  A or x  B, and in either case we have x  B. Hence we have A  B  B. Conversely, if x  B, then we must have x  A or x  B, so that B  A  B. Combining these, we have A  B = B.(ii)  (iii) If A  B and x  A, then x  B and hence x  A  B, so that we have A  A  B. Conversely, if x  A  B, then x  A and x  B, and the latter means that A  B  A. Combining these, we have A  B = A.(iii)  (ii) If x  A, then A  B = A implies that x  A and x  B, and the secondof these means we must have A  B.Verifications of the standard identitiesWe shall derive the identities of Theorems 1 and 2 roughly in the order they were stated.Idempotent laws. The law for unions is true because x  A  x  A or x  A, while the law for intersections is true because x  A  x  A and x  A.Commutative laws. The law for unions is true because 38x  A  B  x  A or x  B  x  B or x  A  x  B  A,while the law for intersections is true because x  A  B  x  A and x  B  x  B and x  A  x  B  A.In symbolic terms, the preceding arguments are just special cases of the more general propositional equivalencesP  Q  Q  P and P  Q  Q  Pand we shall use other such equivalences freely in deriving the remaining assertions in the theorem.Associative laws. The argument is similar, depending upon the general propositional equivalences [P  (Q  R)]  [(P  Q)  R] and [P  (Q  R)]  [(P  Q)  R]where P, Q and R are the statements x  A, x  B and x  C respectively.Distributive laws. The argument is again similar, depending upon the general propositional …


View Full Document

UCR MATH 144 - Elementary constructions on sets

Download Elementary constructions on sets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Elementary constructions on sets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Elementary constructions on sets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?