Mathematical Thinking

Due November 28

3:2; 1-8, 13-19, 28

1. Au Natural. Describe the set of natural numbers. It’s the set, usually denoted by N of counting numbers, 1,2,3,4….

1. Au not-so-natural. Describe each of the sets given below in words.

{3, 6, 12, 15, 18, ….} It’s the set of multiples of 3 except that the multiple 9 is missing. This may or may not be intented.

{1, 2, 3, 4, 5} This is the five element set consisting of the first five counting numbers.

{1/2, 1/4, 1/8, 1/16, ….} This is the set of positive integer powers of ½.

{-1, -2, -3, -4, ….} This is the set of negatives of counting numbers.

{1, 4, 9, 16, 25, 36, 49, 64, 81, 100} This is the set of squares of the first ten positive integers.

1. Set setup. We can denote the natural numbers symbolically as { 1, 2, 3, 4, …} Use this notation to express each of the sets described below.
• The set of natural numbers less than 10. {1,2,3,4,5,6,7,8,9}
• The set of all even natural numbers.  {2,4,6,8,10,…}
• The set of solutions to the equation x² - 4 = 0 {-2, 2}
• The set of all reciprocals of the natural numbers. {1, ½. 1/3, ¼, …}

1. Little or large. Which of the sets in Mindscape I.3 are infinite sets? Which are finite?

The second and fourth are infinite. The first and third are finite.

1. A word you can count on. Define the cardinality of the set.

This is a hard idea. For finite sets, it means the number of elements. For infinite sets, it means roughly speaking, the types of sets which can be put into a one-to-one correspondence with. Those that can be put in one-to-one correspondence with N are called countable. Two sets that have the same cardinality are sometimes called equinumerous. In class we proved that the set of real numbers has a greater cardinality than N.

1. Even odds. Let E stand for the set of all even natural numbers

(so E = {2,4,6,8,….}) and O stand for the set of all odd natural numbers

(so O = {1,3,5,7,….}). Show that the sets E and O have the same cardinality by describing an explicit one-o-one correspondence between the two sets.

The mapping that sends each number to the one that is one bigger is one-to-one from the set O to the set E.

1. Naturally even. Let E stand for the set of all even natural numbers

(so E = {2,4,6,8,….}). Show that the set E and the set of all natural numbers have the same cardinality by describing an explicit one-to-one correspondence between the two sets.

The mapping that sends each number to its double is one-to-one from the set N to the set E.

1. Five takes over. Let EIF be the set of al natural numbers ending in 5 (EIF stands

for “ends in five”). That is, EIF = {5, 15, 25, 35, 45, 55, 65, 75,….}. Describe a

one-to-one correspondence between the set of natural numbers and the set of EIF.

The mapping that sends each number n to 10n-5 is one-to-one from the set N to the set EIF.

13. Squaring off. Let S stand for the set of all natural numbers that are perfect             squares, so S = {1, 4, 9, 16, 25, 36, 49, 64, ….}. Show that the set S and the set of all natural numbers have the same cardinality by describing an explicit one-to-one correspondence between the two sets.

The mapping that sends each number n to n^2 is one-to-one from the set N to the set S.

14. Counting cubes (formerly crows). Let C stand for the set of all natural numbers     that are perfect cubes, so C = {1, 8, 27, 64, 125, 216, 343, 512, ….}. Show that the set C and the set of all natural numbers have the same cardinality by describing an explicit one-to-one correspondence between the two sets.

The mapping that sends each number n to n^3 is one-to-one from the set N to the set C.

15. Reciprocals.  Suppose R is the set defined by

R = {1/1, 1/2, 1/3, 1/4,1/5, 1/6, ….}

Describe the set R in words. Show that it has the same cardinality as the set of         natural numbers.

The mapping that sends each number n to its reciprocal 1/n is one-to-one from the set N to the set R.

1. Hotel Cardinality (formerly California) (H). It is the stranded traveler’s fantasy. The Hotel Cardinality is a full-service luxury hotel with bar and restaurant. It has as many rooms as there are natural numbers. The room numbers are 1, 2, 3, 4, 5, ….You can see why stranded travelers love Hotel Cardinality. There appears to be no need for the sad sign: No Vacancy. Suppose, however, that every room is occupied. Now it appears that the night manager must flash the No Vacancy sign. What if a weary traveler were to arrive late at night looking for a place to stay? Could the night manager figure out a way to provide the traveler with a private room (no sharing) without evicting another guest? The answer is yes. Describe how this accommodation can be made; of course, some guests will have to move to other rooms.

The manager simply sends each guest to the room that has a number one bigger.

1. Hotel Cardinality continued. Given the scenario in Mindscape II.16, suppose now that two more travelers arrive, each wanting his or her own private room. Is it possible for the night manager to make room for these folks without pushing anyone onto the streets?

The manager simply sends each guest to the room that has a number two bigger, leaving rooms 1 and 2 vacant for the new arrivals.

1. More Hotel C. Given the scenario in Mindscape II.16—that is, the hotel starts full—suppose now that the Infinite Life Insurance Company, which has lots of employees—in fact, there are as many employees as there are natural numbers—decides to provide each of its employees with a private room. Is it possible for the night manager to give each of the infinitely many employees his or her own room without kicking any of the other guests onto the streets? By the way, as you may have guessed, after this busy evening, the night manager quit and got a job as the night manager of a nearby Motel 6 (it only had 56 rooms).

The manager simply sends each guest to the room that has a number twice as big as his original room. This leave all the odd numbered rooms for the new arrivals.

1. So much sand. Prove that there cannot be an infinite number of grains of sand on Earth.

I do not know how to do this without begging the question. My method originally was to assume the universe had finite weight, and that the average grain of sand has a positive weight, so the maximum number of grains is the fraction (weight of universe/average weight of a grain), however, this assume a lot about our universe.

1. Bowling ball barrel. Suppose you have infinitely many bowling balls and two huge barrels. You take the bowling balls and put each ball in one of the two barrels. What can you conclude about the cardinality of at least one of the barrel? Prove your answer.

If both barrels ended up finite, say with m and n ball respectively, then the original set had only m+n balls, a contradiction.