Experience Mathematics # 15 : OR and AND

Suppose that your mom says that you can have either an Apple or a Banana. Can you have both? One of the most fundamental rules of logic says that the expression either $A$ or $B$ is true only if one of $A$ or $B$ is true. That is to say, you cannot have both the Apple and the Banana (assuming you wish to obey your mom.)

What if your mom says you can have an Apple or a Banana? In this case, you can have both.

Suppose your mom asks you if you have had an Apple or a Banana. Can you honestly say yes if you have had an Apple and an Orange? The answer is yes. If she asks you if you have had an Apple and a Banana, you can answer yes only if you have had both.

Suppose your mom insists that you should not have an Apple. Is it OK to have a Banana? How about Baked Beans? It depends. The alternatives to an Apple allowed by your mom depend on the context. For example, if the alternatives allowed consist of the other fruits in the house, you cannot have baked beans instead of the Apple, but you could have a Banana. However, if the context of discussion is the five servings of fruits and vegetables that you must have every day, then Baked Beans are allowed. In Mathematics, when we refer to a set $A$, then we must specify the universal set $U$ from where the elements of $A$ are picked. Then the complement of $A$ is the set of all the elements that are in $U$ but not in $A$. Then there is no confusion when we claim: $a$ is not an element of $A$. By this statement we mean that $a$ is an element of the complement of $A$.

Experience Mathematics #14 - Uncountable sets

Many of the infinite sets we have encountered are countable. Even numbers, the set of prime numbers, integers and rational numbers, all have the same number of elements as $N$, the set of natural numbers. Are there any infinite sets that have more elements than the natural numbers?

This question was answered by Cantor, who showed that the real numbers outnumber the natural numbers. All the real numbers between $0$ and $1$ have a decimal expansion such as $x=0.13212987\dots$. Cantor showed that all numbers of this form cannot be put into one-to-one correspondence with the set of natural numbers. To be able to understand his proof, find a number that differs from $x$ in the first decimal place. Take any number $y$ with $2$ in the first decimal place. Since $2$ is different from $1$, $y$ differs from $x$ in the first decimal place.

To return to Cantor’s proof, suppose that you are able to find a one-to-one correspondence between the natural numbers and all the real numbers in the interval $(0,1)$. Let us denote by $x_1$ the number corresponding to $1$; $x_2$, the number corresponding to $2$, and so on. Now consider a number $y$ (between $0$ and $1$) that is different from $x_1$ in the first place after the decimal; different from $x_2$ in the second place after the decimal; and so on. Clearly, $y$ cannot appear in the list, since it is different from all the $x$’s. Thus we have found a real number between $0$ and $1$ that is not in the above correspondence. This contradiction shows that no such correspondence is possible. In other words, the real numbers are uncountable in number.

Are there any infinite sets that have more elements than $N$ but less elements than the set of real numbers?

Experience Mathematics #13 - The cartesian society in Hilbert Hotel


A set S is countable if it can be put in one-to-one correspondence with $N$. Suppose that you are the manager of the Hilbert Hotel, a hotel with a countable number of rooms. Now, even though the hotel is full, when $200$ new guests arrive after lunch at the Restaurant at the End of the Universe, you can accommodate them. All you have to do is to move the guests in Room $1$ to Room $201$, the guests in Room $2$ to Room $202$, etc. In other words, you will move the guests in Room $n$ to Room $200+n$.

Now, suppose the hotel is empty. The members of the Cartesian Society (Motto: We Think, Therefore We Exist!) decide to have a convention. Each member of the Cartesian Society has an identification mark of the form $(a, b)$, where $a$ and $b$ are natural numbers. The chairman of the society is $(1,1)$ and for any two numbers $a$ and $b$, there is a member corresponding to the ordered pair $(a, b)$. Don’t confuse $(2,3)$ with $(3,2)$: they are quite different people. There are many, many members in this society. But all of them can be accommodated in the Hilbert Hotel. Can you find a one-to-one correspondence of the members of the Cartesian Society with the natural numbers?

First write down the ID numbers of all the members of the Cartesian Society in the form of a table. For example, put $(3,5)$ in the third row and the fifth column of the table. Now find a way to “count” them. In other words, assign a natural number to each of them in a systematic fashion.

Experience Mathematics #12 -- A part can be equal to the whole!

A set S is countable if it can be put in one-to-one correspondence with $N$. For example, if we take the set of even numbers, we can establish a one-to-one correspondence as follows. $1$ corresponds to $2$, $2$ to $4$, $3$ to $6$, and so on. This shows that the number of even numbers is equal to the number of natural numbers.

This contradictory idea—that a part of an object is equal to the whole—troubled many philosophers. But they got over it, and began to compare the concept of infinity with the concept of God. However, when Biologists made it possible to clone human beings, they have stopped approving of the idea.

The famous mathematician Hilbert told the story of a hotel with an infinite number of rooms. Suppose the Hilbert Hotel is full, but the hotel manager wants to accommodate a guest who arrives suddenly. How does he manage that? Well, he asks the guest in room number $1$ to move to Room $2$, the guest in Room $2$ to move to Room $3$, and so on. Room $1$ becomes empty and is readied for the new guest. Can you figure out how to accommodate $30$ guests, even if the hotel is full? 

What if a travel agent calls the manager, and says she is sending groups of tourists to the hotel. The numbers of people in the groups are: $3$, $7$, $11$, $15$, and so on. Help the manager come up with the required one-to-one correspondence in these cases, so that he can accommodate all the guests.