Advanced Calculus Single Variable

3.4 Exercises

1. The Barber of Seville is a man and he shaves exactly those men who do not shave themselves. Who shaves the Barber?
2. Do you believe each person who has ever lived on this earth has the right to do whatever he or she wants? (Note the use of the universal quantifier with no set in sight.) If you believe this, do you really believe what you say you believe? What of those people who want to deprive others their right to do what they want? Do people often use quantifiers this way? (This is not hypothetical. Tyrants usually seek to deprive others of their agency to do what they want. Do they have a right to do this?)
3. President Bush, when he found there were no weapons of mass destruction said we would give the Iraqi’s “freedom”. He is protecting our “freedom”. What is freedom? Is there an implied quantifier involved? Is there a set mentioned? What is the meaning of the statement? Could it mean different things to different people?
4. DeMorgan’s laws are very useful in mathematics. Let S be a set of sets each of which is contained in some universal set, U. Show

   { } ∪ AC : A ∈ S = (∩ {A : A ∈ S })C

   and

   ∩ {AC : A ∈ S} = (∪{A : A ∈ S})C .

5. Let S be a set of sets show

   B ∪∪ {A : A ∈ S} = ∪{B ∪ A : A ∈ S }.

6. Let S be a set of sets show

   B ∩∪ {A : A ∈ S} = ∪{B ∩ A : A ∈ S }.

7. Show the rational numbers are countable, this is in spite of the fact that between any two integers there are infinitely many rational numbers. What does this show about the usefulness of common sense and instinct in mathematics? 
8. Show the set of all subsets of ℕ, the natural numbers, which have 3 elements, is countable. Is the set of all subsets of ℕ which have finitely many elements countable? How about the set of all subsets of ℕ?
9. We say a number is an algebraic number if it is the solution of an equation of the form

   anxn + ⋅⋅⋅+ a1x+ a0 = 0

   where all the a_j are integers and all exponents are also integers. Thus

   √ - 2
   is an algebraic number because it is a solution of the equation x² − 2 = 0. Using the observation that any such equation has at most n solutions, show the set of all algebraic numbers is countable.

10. Let A be a nonempty set and let P
    (A)
    be its power set, the set of all subsets of A. Show there does not exist any function f, which maps A onto P
    (A )
    . Thus the power set is always strictly larger than the set from which it came. Hint: Suppose f is onto. Consider S ≡{x ∈ A : x
    ∕∈
    f
    (x)
    }. If f is onto, then f
    (y)
    = S for some y ∈ A. Is y ∈ f
    (y)
    ? Note this argument holds for sets of any size.
11. The empty set is said to be a subset of every set. Why? Consider the statement: If pigs had wings, then they could fly. Is this statement true or false?
12. If S =
    {1,⋅⋅⋅,n}
    , show P
    (S)
    has exactly 2ⁿ elements in it. Hint: You might try a few cases first.
13. Let S denote the set of all sequences which have either 0 or 1 in every entry. You have seen sequences in calculus. They will be discussed more formally later. Show that the set of all such sequences cannot be countable. Hint: Such a sequence can be thought of as an ordered list a₁a₂a₃
    ⋅⋅⋅
    where each a_i is either 0 or 1. Suppose you could list them all as follows.

    a1 = a11a12a13⋅⋅⋅ a2 = a21a22a23⋅⋅⋅ a3 = a31a32a33⋅⋅⋅ .. .

    Then consider the sequence a₁₁a₂₂a₃₃

    ⋅⋅⋅
    . Obtain a sequence which can’t be in the list by considering the sequence b₁b₂b₃
    ⋅⋅⋅
    where b_k is obtained by changing a_kk. Explain why this sequence can’t be any of the ones which are listed.

14. Show that the collection of sequences a₁a₂
    ⋅⋅⋅
    a_n such that each a_k is either 0 or 1 such that a_k = 0 for all k larger than n is countable. Now show that the collection of sequences consisting of either 0 or 1 such that a_k is 0 for all k larger than some n is also countable. However, the set of all sequences of 0 and 1 is not countable.
15. Prove Theorem 3.3.3.
16. Let S be a set and consider a function f which maps P
    (S)
    to P
    (S)
    which satisfies the following. If A ⊆ B, then f
    (A)
    ⊆ f
    (B)
    . Show there exists A such that f
    (A)
    = A. Hint: You might consider the following subset of P
    (S)
    .

    C ≡ {B ∈ P (S ) : B ⊆ f (B )}

    Then consider A ≡∪C. Argue A is the “largest” set in C which implies A cannot be a proper subset of f

    (A )
    .