- The Barber of Seville is a man and he shaves exactly those men who do not shave themselves. Who shaves the Barber?
- 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?)
- 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?
- 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
and

- Let S be a set of sets show
- Let S be a set of sets show
- 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?
- 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 ℕ?
- We say a number is an algebraic number if it is the solution of an equation of the
form
where all the a

_{j}are integers and all exponents are also integers. Thusis an algebraic number because it is a solution of the equation x^{2}− 2 = 0. Using the observation that any such equation has at most n solutions, show the set of all algebraic numbers is countable. - Let A be a nonempty set and let Pbe its power set, the set of all subsets of A. Show there does not exist any function f, which maps A onto P. Thus the power set is always strictly larger than the set from which it came. Hint: Suppose f is onto. Consider S ≡{x ∈ A : xf}. If f is onto, then f= S for some y ∈ A. Is y ∈ f? Note this argument holds for sets of any size.
- 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?
- If S = , show Phas exactly 2
^{n}elements in it. Hint: You might try a few cases first. - 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
_{1}a_{2}a_{3}where each a_{i}is either 0 or 1. Suppose you could list them all as follows.Then consider the sequence a

_{11}a_{22}a_{33}. Obtain a sequence which can’t be in the list by considering the sequence b_{1}b_{2}b_{3}where b_{k}is obtained by changing a_{kk}. Explain why this sequence can’t be any of the ones which are listed. - Show that the collection of sequences a
_{1}a_{2}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. - Prove Theorem 3.3.3.
- Let S be a set and consider a function f which maps Pto Pwhich satisfies the following. If A ⊆ B, then f⊆ f. Show there exists A such that f= A. Hint: You might consider the following subset of P.
Then consider A ≡∪C. Argue A is the “largest” set in C which implies A cannot be a proper subset of f

.

Download PDFView PDF