Book of Proof

Home > Other > Book of Proof > Page 3
Book of Proof Page 3

by Richard Hammack


  18. Z × Z

  13. ©1, 1.5, 2ª × [1,2]

  19. [0, 1] × [0,1] × [0,1]

  14. [1, 2] × ©1,1.5,2ª

  20. ©(x, y) ∈ R2 : x2 + y2 ≤ 1ª × [0,1]

  Subsets

  11

  1.3 Subsets

  It can happen that every element of some set A is also an element of

  another set B. For example, each element of A = ©0, 2, 4ª is also an element

  of B = ©0, 1, 2, 3, 4ª. When A and B are related this way we say that A is a

  subset of B.

  Definition 1.3

  Suppose A and B are sets. If every element of A is also

  an element of B, then we say A is a subset of B, and we denote this as

  A ⊆ B. We write A 6⊆ B if A is not a subset of B, that is, if it is not true

  that every element of A is also an element of B. Thus A 6⊆ B means that

  there is at least one element of A that is not an element of B.

  Example 1.2

  Be sure you understand why each of the following is true.

  ©

  1.

  2, 3, 7ª ⊆ ©2,3,4,5,6,7ª

  ©

  2.

  2, 3, 7ª 6⊆ ©2,4,5,6,7ª

  ©

  3.

  2, 3, 7ª ⊆ ©2,3,7ª

  ©

  4.

  2n : n ∈ Zª ⊆ Z

  ©

  5.

  (x, sin(x)) : x ∈ Rª ⊆ R2

  ©

  6.

  2, 3, 5, 7, 11, 13, 17, . . . ª ⊆ N

  7. N ⊆ Z ⊆ Q ⊆ R

  8. R × N ⊆ R × R

  This brings us to a significant fact: If B is any set whatsoever, then

  ; ⊆ B. To see why this is true, look at the last sentence of Definition 1.3.

  It says that ; 6⊆ B would mean that there is at least one element of ;

  that is not an element of B. But this cannot be so because ; contains no

  elements! Thus it is not the case that ; 6⊆ B, so it must be that ; ⊆ B.

  Fact 1.2

  The empty set is a subset of every set, that is, ; ⊆ B for any set B.

  Here is another way to look at it. Imagine a subset of B as a thing you

  ©ª

  make by starting with braces

  , then filling them with selections from B.

  ©ª

  For example, to make one particular subset of B = ©a, b, cª, start with

  ,

  ©ª

  ©

  select b and c from B and insert them into

  to form the subset

  b, cª.

  ©

  Alternatively, you could have chosen just a to make aª, and so on. But

  one option is to simply select nothing from B. This leaves you with the

  ©ª

  ©ª

  subset

  . Thus

  ⊆ B. More often we write it as ; ⊆ B.

  12

  Sets

  This idea of “making” a subset can help us list out all the subsets of

  a given set B. As an example, let B = ©a, b, cª. Let’s list all of its subsets.

  One way of approaching this is to make a tree-like structure. Begin with

  ©ª

  the subset

  , which is shown on the left of Figure 1.3. Considering the

  ©ª

  element a of B, we have a choice: insert it or not. The lines from

  point

  ©ª

  ©

  to what we get depending whether or not we insert a, either

  or aª. Now

  move on to the element b of B. For each of the sets just formed we can

  either insert or not insert b, and the lines on the diagram point to the

  ©ª

  ©

  ©

  ©

  resulting sets

  , bª, aª, or a, bª. Finally, to each of these sets, we can

  either insert c or not insert it, and this gives us, on the far right-hand

  ©ª

  ©

  ©

  ©

  ©

  ©

  ©

  ©

  column, the sets

  , cª, bª, b, cª, aª, a, cª, a, bª and a, b, cª. These are

  the eight subsets of B = ©a, b, cª.

  Insert a ?

  Insert b ?

  Insert c ?

  ©ª

  ©ª

  No

  Yes

  ©

  No

  cª

  ©ª

  ©

  Yes

  bª

  ©

  No

  No

  bª

  Yes

  ©b, cª

  ©ª

  ©aª

  ©

  No

  Yes

  aª

  Yes

  ©

  No

  a, cª

  ©aª

  ©

  Yes

  a, bª

  ©

  No

  a, bª

  Yes

  ©a, b, cª

  Figure 1.3. A “tree” for listing subsets

  We can see from the way this tree branches out that if it happened that

  B = ©aª, then B would have just two subsets, those in the second column

  of the diagram. If it happened that B = ©a, bª, then B would have four

  subsets, those listed in the third column, and so on. At each branching of

  the tree, the number of subsets doubles. Thus in general, if |B| = n, then

  B must have 2n subsets.

  Fact 1.3

  If a finite set has n elements, then it has 2n subsets.

  Subsets

  13

  For a slightly more complex example, consider listing the subsets of

  B = ©1,2,©1,3ªª

  ©

  . This B has just three elements: 1, 2 and 1, 3ª. At this

  point you probably don’t even have to draw a tree to list out B’s subsets.

  You just make all the possible selections from B and put them between

  braces to get

  ©ª, ©1ª, ©2ª, ©©1,3ªª, ©1,2ª, ©1,©1,3ªª, ©2,©1,3ªª, ©1,2,©1,3ªª.

  These are the eight subsets of B. Exercises like this help you identify what

  ©

  is and isn’t a subset. You know immediately that a set such as 1, 3ª is not

  a subset of B because it can’t be made by selecting elements from B, as

  the 3 is not an element of B and thus is not a valid selection. Notice that

  ©

  ©

  ©©

  although 1, 3ª 6⊆ B, it is true that 1, 3ª ∈ B. Also,

  1, 3ªª ⊆ B.

  Example 1.3

  Be sure you understand why the following statements are

  true. Each illustrates an aspect of set theory that you’ve learned so far.

  ©

  1. 1 ∈ ©1, ©1ªª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 is the first element listed in 1, ©1ªª

  2. 1 6⊆ ©1, ©1ªª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because 1 is not a set

  ©

  ©

  ©

  3.

  1ª ∈ ©1,©1ªª . . . . . . . . . . . . . . . . . . . . . . . . . 1ª is the second element listed in 1,©1ªª

  ©

  ©

  ©

  4.

  1ª ⊆ ©1,©1ªª . . . . . . . . . . . . . . . . . . . . . . . make subset 1ª by selecting 1 from 1,©1ªª

  ©©

  ©

  ©

  ©©

  5.

  1ªª ∉ ©1,©1ªª . . . . . . . . . . . because 1,©1ªª contains only 1 and 1ª, and not

  1ªª

  ©©

 
©©

  ©

  ©

  6.

  1ªª ⊆ ©1,©1ªª. . . . . . . . . . . . . . . . . .make subset

  1ªª by selecting 1ª from 1,©1ªª

  7. N ∉ N . . . . . . . . . because N is a set (not a number) and N contains only numbers

  8. N ⊆ N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because X ⊆ X for every set X

  9. ; ∉ N . . . . . . . . . . . . . . . . . . . . because the set N contains only numbers and no sets

  10. ; ⊆ N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because ; is a subset of every set

  ©

  11. N ∈ ©Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . because Nª has just one element, the set N

  12. N 6⊆ ©Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because, for instance, 1 ∈ N but 1 ∉ ©Nª

  ©

  13. ; ∉ ©Nª . . . . . . . . . . . . . . . . . . . . . note that the only element of Nª is N, and N 6= ;

  14. ; ⊆ ©Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because ; is a subset of every set

  ©

  15. ; ∈ ©;, Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ; is the first element listed in ;, Nª

  16. ; ⊆ ©;, Nª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because ; is a subset of every set

  ©

  ©

  ©

  17.

  Nª ⊆ ©;,Nª . . . . . . . . . . . . . . . . . . . . . . . make subset Nª by selecting N from ;,Nª

  ©

  18.

  Nª 6⊆ ©;,©Nªª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . because N ∉ ©;,©Nªª

  ©

  ©

  ©

  19.

  Nª ∈ ©;,©Nªª. . . . . . . . . . . . . . . . . . . . . . Nª is the second element listed in ;,©Nªª

  ©

  20.

  (1, 2), (2, 2), (7, 1)ª ⊆ N × N . . . . . . . . . . . . . . . . . . . each of (1,2), (2,2), (7,1) is in N × N

  Though they should help you understand the concept of subset, the

  above examples are somewhat artificial. But in general, subsets arise very

  14

  Sets

  naturally. For instance, consider the unit circle C = ©(x, y) ∈ R2 : x2 + y2 = 1ª.

  This is a subset C ⊆ R2. Likewise the graph of a function y = f (x) is a set

  of points G = ©(x, f (x)) : x ∈ Rª, and G ⊆ R2. Surely sets such as C and G

  are more easily understood or visualized when regarded as subsets of R2.

  Mathematics is filled with such instances where it is important to regard

  one set as a subset of another.

  Exercises for Section 1.3

  A. List all the subsets of the following sets.

  1. ©1, 2, 3, 4ª

  5. ©;ª

  2. ©1, 2, ;ª

  6. ©R,Q,Nª

  3. ©©Rªª

  7. ©R,©Q,Nªª

  4. ;

  8. © ©0, 1ª, ©0, 1, ©2ªª, ©0ª ª

  B. Write out the following sets by listing their elements between braces.

  9. ©X : X ⊆ ©3,2, aª and |X | = 2ª

  11. ©X : X ⊆ ©3,2, aª and |X | = 4ª

  10. ©X ⊆ N : |X | ≤ 1ª

  12. ©X : X ⊆ ©3,2, aª and |X | = 1ª

  C. Decide if the following statements are true or false. Explain.

  13. R3 ⊆ R3

  15. ©(x, y) : x − 1 = 0ª ⊆ ©(x, y) : x2 − x = 0ª

  14. R2 ⊆ R3

  16. ©(x, y) : x2 − x = 0ª ⊆ ©(x, y) : x − 1 = 0ª

  1.4 Power Sets

  Given a set, you can form a new set with the power set operation, defined

  as follows.

  Definition 1.4

  If A is a set, the power set of A is another set, denoted

  as P(A) and defined to be the set of all subsets of A. In symbols, P(A) =

  © X : X ⊆ Aª.

  For example, suppose A = ©1, 2, 3ª. The power set of A is the set of all

  subsets of A. We learned how to find these subsets in the previous section,

  ©ª

  ©

  ©

  ©

  ©

  ©

  ©

  ©

  and they are

  , 1ª, 2ª, 3ª, 1, 2ª, 1, 3ª, 2, 3ª and 1, 2, 3ª. Therefore the

  power set of A is

  P(A) = © ;, ©1ª, ©2ª, ©3ª, ©1,2ª, ©1,3ª, ©2,3ª, ©1,2,3ª ª.

  As we saw in the previous section, if a finite set A has n elements, then

  it has 2n subsets, and thus its power set has 2n elements.

  Power Sets

  15

  Fact 1.4

  If A is a finite set, then |P(A)| = 2|A|.

  Example 1.4

  You should examine the following statements and make

  sure you understand how the answers were obtained. In particular, notice

  that in each instance the equation |P(A)| = 2|A| is true.

  1. P ¡©0, 1, 3ª¢ = © ;, ©0ª, ©1ª, ©3ª, ©0, 1ª, ©0, 3ª, ©1, 3ª, ©0, 1, 3ª ª

  2. P ¡©1, 2ª¢ = © ;, ©1ª, ©2ª, ©1, 2ª ª

  3. P ¡©1ª¢ = © ;, ©1ª ª

  4. P (;) = © ; ª

  5. P ¡©aª¢ = © ;, ©aª ª

  6. P ¡©;ª¢ = © ;, ©;ª ª

  7. P ¡©aª¢ × P ¡©;ª¢ = © (;, ;), ¡;, ©;ª¢ , ¡©aª, ;¢ , ¡©aª, ©;ª¢ ª

  8. P ¡P ¡©;ª¢¢ = © ;, ©;ª, ©©;ªª, ©;, ©;ªª ª

  9. P ¡©1, ©1, 2ªª¢ = © ;, ©1ª, ©©1, 2ªª, ©1, ©1, 2ªª ª

  10. P ¡©Z, Nª¢ = © ;, ©Zª, ©Nª, ©Z, Nª ª

  Next are some that are wrong. See if you can determine why they are wrong

  and make sure you understand the explanation on the right.

  11. P(1) = © ;, ©1ª ª . . . . . . . . . . . . . . . . . . . . . . . . . . . meaningless because 1 is not a set

  ©

  12. P ¡©1, ©1, 2ªª¢ = ©;, ©1ª, ©1, 2ª, ©1, ©1, 2ªªª . . . . . . . . wrong because 1, 2ª 6⊆ ©1, ©1, 2ªª

  ©©

  13. P ¡©1, ©1, 2ªª¢ = ©;, ©©1ªª, ©©1, 2ªª, ©;, ©1, 2ªªª . . . . . wrong because

  1ªª 6⊆ ©1,©1,2ªª

  If A is finite, it is possible (though maybe not practical) to list out P(A)

  between braces as was done in the above example. That is not possible if

  A is infinite. For example, consider P(N). If you start listing its elements

  you quickly discover that N has infinitely many subsets, and it’s not clear

  how (or if) they could be arranged as a list with a definite pattern:

  P(N) = ©;,©1ª,©2ª,...,©1,2ª,©1,3ª,...,©39,47ª,

  . . . , ©3, 87, 131ª, . . . , ©2, 4, 6, 8, . . . ª, . . . ? . . . ª.

  The set P(R2) is mind boggling. Think of R2 = ©(x, y) : x, y ∈ Rª as the set

  of all points on the Cartesian plane. A subset of R2 (that is, an element

  of P(R2)) is a set of points in the plane. Let’s look at some of these sets.

  ©

  ©

  Since (0, 0), (1, 1)ª ⊆ R2, we know that (0, 0), (1, 1)ª ∈ P(R2). We can even

  draw a picture of this subset, as in Figure 1.4(a). For another example, the

  graph of the equation y = x2 is the set of points G = ©(x, x2) : x ∈ Rª and this

  is a subset of R2, so G ∈ P(R2). Figure 1.4(b) is a picture of G. Because

  this can be done for any function, the graph of any imaginable function

  f : R → R is an element of P(R2).

  16

  Sets

  y

  y

  y

  x

  x

  x

  (a)

  (b)

  (c)


  Figure 1.4. Three of the many, many sets in P(R2)

  In fact, any black-and-white image on the plane can be thought of as a

  subset of R2, where the black points belong to the subset and the white

  points do not. So the text “INFINITE” in Figure 1.4(c) is a subset of R2

  and therefore an element of P(R2). By that token, P(R2) contains a copy

  of the page you are reading now.

  Thus in addition to containing every imaginable function and every

  imaginable black-and-white image, P(R2) also contains the full text of

  every book that was ever written, those that are yet to be written and

  those that will never be written. Inside of P(R2) is a detailed biography of

  your life, from beginning to end, as well as the biographies of all of your

  unborn descendants. It is startling that the five symbols used to write

  P(R2) can express such an incomprehensibly large set.

  Homework: Think about P(P(R2)).

  Exercises for Section 1.4

  A. Find the indicated sets.

  1. P ¡©©a, bª,©cªª¢

  7. P ¡©a, bª¢ × P ¡©0,1ª¢

  2. P ¡©1,2,3,4ª¢

  8. P ¡©1,2ª × ©3ª¢

  3. P ¡©©;ª,5ª¢

  9. P ¡©a, bª × ©0ª¢

  4. P ¡©R,Qª¢

  10. ©X ∈ P ¡©1,2,3ª¢ : |X | ≤ 1ª

  5. P ¡P ¡©2ª¢¢

  11. ©X ⊆ P ¡©1,2,3ª¢ : |X | ≤ 1ª

  6. P ¡©1,2ª¢ × P ¡©3ª¢

  12. ©X ∈ P ¡©1,2,3ª¢ : 2 ∈ X ª

  B. Suppose that |A| = m and |B| = n. Find the following cardinalities.

  13. |P(P(P(A)))|

  17. ¯©

  ¯

  X ∈ P(A) : |X | ≤ 1ª¯¯

  14. |P(P(A))|

  18. |P(A × P(B))|

  15. |P(A × B)|

  19. |P(P(P(A × ;)))|

  16. |P(A) × P(B)|

  20. ¯©

  ¯

  X ⊆ P(A) : |X | ≤ 1ª¯¯

  Union, Intersection, Difference

  17

  1.5 Union, Intersection, Difference

  Just as numbers are combined with operations such as addition, subtrac-

  tion and multiplication, there are various operations that can be applied to

  sets. The Cartesian product (defined in Section 1.2) is one such operation;

  given sets A and B, we can combine them with × to get a new set A × B.

  Here are three new operations called union, intersection and difference.

  Definition 1.5

  Suppose A and B are sets.

  The union of A and B is the set

  A ∪ B = ©x : x ∈ A or x ∈ Bª.

  The intersection of A and B is the set

  A ∩ B = ©x : x ∈ A and x ∈ Bª.

  The difference of A and B is the set

  A − B = ©x : x ∈ A and x ∉ Bª.

  In words, the union A ∪ B is the set of all things that are in A or in B

  (or in both). The intersection A ∩ B is the set of all things in both A and B.

 

‹ Prev