Now that we have developed the framework for sets, we can finally use it to discover things about the nature of some very special sets (those that you and I work with on a daily basis). In this post I will cover some oddities surrounding infinite sets. You already know of one infinite set: the integers. Of course there are subsets of this set and there are other infinite sets, but I will focus on this one as it is quite familiar to you. For now, consider the following questions. Are there more integers than even integers? Why or why not? The answer to these two questions will be given later in the post.
Before we get to the weird results, we first need some more dreaded definitions and explanations behind the definitions. The upcoming definitions will, again, be a little strange and you might wonder why we define them as so, but once you see some examples you should be convinced.
Definition: The cardinality of a set is a measure of the elements in the set.
There are two possibilities: either a set is finite or it is infinite. We can easily see how to determine if there are the same number of elements in two finite sets: write the sets out and count the elements. Take for example the following sets:
$ A = \{ 1, 3, 5, 7 \} $ and $ B = \{ 2, 4, 6 \} $. We see that $A$ has four elements, whereas $B$ has three elements and conclude that $A$ and $B$ do not have the same number of elements, i.e. do not have the same cardinality. So far, so good. Unfortunately we cannot count (try as we might!) the amount of elements in an infinite set, so this approach seems less than satisfactory. We may need a shift in paradigm in order to approach the case of infinite sets. You might wonder why we even care; if two sets have an infinite amount of elements, then they have the same number of elements! However by that logic, infinity/infinity should equal one! But we know from calculus that isn't necessarily so. Initial intuition often fails when dealing with infinities, which is often caused by conceptions on shaky foundation.
To create a proper paradigm, we will imagine mathematics without the concept of numbers (it will turn out thinking about numbers is somewhat misleading). How would we then determine if two sets were the same size? We can't make a reference to the number of elements since we don't even know what numbers are, so that is out.
(I will try to avoid using numeric quantifiers so I don't contradict myself.) Imagine a basket with apples in it and imagine a basket with oranges in it. If we were told to determine if there were the same amount of each, we could reach a hand into each basket and pull out a single unit of each. We'll keep them paired when we place them on the ground: an orange with an apple. If we happen to run out of oranges at the same time that we run out of apples, we would be assured that we have the same amount of apples and oranges. Each individual apple is paired with an orange and each orange is paired with an apple. If we have an excess of either apple or oranges, we would have an empty basket and a basket with objects inside it.
This seems logical, but does it reduce down to what we devised before? It turns out that it does. Remember, we can't state how many elements there are since we don't know what numbers are, but we can say whether two collections have the same number of elements.
It turns out that this is the proper way of thinking about cardinality and this notion works wonderfully for infinite sets. We no longer talk about the actual size of the set, but whether or not we can form a proper pairing. If we have an infinite number of oranges and apples, yet we are able to pair one orange with one apple (and vice versa) we would undoubtedly have to say that they have the same cardinality. But if we have an excess of apples when pairing them with oranges, then we would be forced to say that the set of apples is larger than that of the oranges.
Before I continue and make this more concrete, I must define one term which will come up a lot in future discussion. You have undoubtedly heard the term or know what it is without knowing it by name.
Definition: A function $f$ is a bijection from the set $A$ into the set $B$ if $f$ is both one-to-one and onto. (Note: the range of $f$ must be contained in $B$.)
(Muffled groans) You might be thinking: Greaaat. Now what does that mean?
Well, if $f$ were an onto function, it would mean that nothing in our set $B$ is left out. In mathematical jargon, we say that every element in $B$ gets mapped to. See the picture below.
In this diagram, our function's domain is the set $\{a_1, a_2, a_3, a_4 \} $ and its codomain is the set $\{1, 2, 3\}$. The arrow represents what acting our function does to each element. So $f(a_1) = 1$, $f(a_2) = 1$, $f(a_3) = 2$ and $ f(a_4) = 3 $. As you can see, every element of our set $B$ gets mapped to. If an element were left out, it would not have an arrow going to it and our function would not be onto. Since this is not the case, it must be onto.
Okay so now what does one-to-one mean?
You're also familiar with one-to-one, though maybe not this term exactly. Colloquially, a one-to-one function is a function that passes the horizontal line test. An example of a function that is not one-to-one would be the function $f:\Bbb R\to\Bbb R$ given by $f(x) = x^2$. Take for example $x = \pm 1$. For both of these values $f(x) = 1$ so we conclude that $f$ is not one-to-one (two different $x$ values map to the same $y$ value!).
You might be wondering what functions are both one-to-one and onto? Well first we have to define a domain and codomain (our $A$ and $B$ as mentioned in the definition, respectively).
We'll work with what you're used to: the real numbers. We'll use the real numbers for both the domain and codomain. The function $f(x) = x$ is a bijection. The proof of this is left to the reader. (Hint: to show a function is one-to-one amounts to the following. If $f(x) = f(y)$, then $x = y$ - meaning that the only way $f$ can have the same value for two values in its domain is if the two values are in fact the same. To show it is onto, you want to make sure every element in the codomain gets mapped to. Pick $y$ in codomain. Try to find an $x$ such that $f(x) = y$. If no such $x$ exists, then the function is not onto.)
Okay, you've survived the definition of a bijective function (mark that off on your bucket list!). With this definition and the apples and oranges thought experiment from before, we can now give the formal concept behind equating cardinalities.
Concept: Two sets have the same cardinality if there exists a bijective function from one set into the other.
This concept is succinct and quite exact. There is no wiggle room to speak of. But you may not be convinced that this definition works. We'll test it out for our set of apples and oranges from before. The tricky part of showing two sets have the same cardinality is devising the function you need. While you may not be convinced, but we will rig our function to work properly.
Returning to out example of the apples and oranges, suppose $O = \{o_1, o_2, o_3\}$ and $A = \{a_1,a_2,a_3\}$ represent the set of oranges and apples, respectively. We will define $f$ by the following: $f:O\to A$ ($f$ is a mapping from the set of oranges into the set of apples) and
$$ f(o_1) = a_1,\quad f(o_2) = a_2,\quad f(o_3) = a_3.$$
As you can see, each orange is paired with a single apple and each apple is paired with a single orange, so by our previous concept we should have the same amount of each. Now we will show that this is the case within the new paradigm we have created. Is this function onto? The answer is obviously yes. We only had three apples and each one is mapped to by our function (the $ a_1$, $a_2$ and $a_3$). Now is it one-to-one? The answer is also yes. Each apple is paired with one and only one orange (no two oranges map to the same apple; recall the hint to the problem). We have successfully created a bijective function from the set of oranges into the set of apples and therefore they have the same number of elements.
Of course that was somewhat a waste of time since we already knew they had the same number of elements; we could just count them! The utility of this definition really only comes into play when discussing infinite sets and it is this very definition that causes all kinds of conceptual headaches as we are about to see.
Now that we have a proper framework, we can finally answer the question I asked at the beginning of the post, i.e. whether or not the integers and even integers have the same number of elements, i.e. have the same cardinality. We can now very easily answer this question, but first I will appeal to your intuition.
Imagine the finite set $\{1, 2, 3, 4, 5, 6\}$. The set of even integers within this set is $\{2, 4, 6\}$. Of course we would say that these two sets do not have the same number of elements; one has six elements, the other has three. What if there are an infinite amount of both? Well our sets look like the following: $\{\ldots, -4, -3, -2, -1, 0, 1, 2, 3, 4,\ldots\}$ and $\{\ldots, -4, -2, 0, 2, 4,\ldots\}$. Of course we know that the set of even integers are a subset of the integers, but also that there are numbers in the integers that are not in the set of even integers. Our intuition would tell us that the even integers and and the integers do not have the same number of elements. And of course our intuition is never wrong.
We'll check that our intuition is right with our hot-off-the-presses definition. Let's let $f : \Bbb Z\to \Bbb Z_e $, where the [; \Bbb Z_e ;] represents the even integers, and let $f(n) = 2n$, for the sake of argument.
Now, if $n$ is an integer, we know that $2n$ must be an even integer, so we are on the right track (our function's range is inside the codomain). We'll check if $f$ is onto.
Let $y\in \Bbb Z_e$, then $y$ is even. If $y$ is even, then it can be written in the form $2m$, where $m$ is some integer. But our domain is the entire set of integers, so surely $m$ must be in there somewhere! So we must conclude $f$ is onto. Now we'll check that it isn't one-to-one. (Otherwise if it is, our intuition was wrong. And our intuition cannot be wrong. Our intuition is infallible.)
Let $x$ and $y$ be in $\Bbb Z$ and suppose $f(x) = f(y)$. Then $f(x) = 2x$ and $f(y) = 2y$. However if $f(x) = f(y)$, then $2x = 2y$. We then obtain that $x = y$. So $f$ is also one-to-one.
We have created a function from the integers into the even integers that is one-to-one and onto. But one-to-one and onto functions are bijective functions and by our concept concerning cardinalities, we must conclude that $\Bbb Z$ and $\Bbb Z_e$ have the same number of elements. But our intuition says that they can't. What are we to do? Well the answer lies in the fact that we aren't built to understand infinite sets of objects intuitively. When was the last time you came across an infinite collection of apples (much less an infinite collection of both apples and oranges)? The answer is, of course, never. In mathematics we are often led astray by our intuition which leads us to something a professor once told me: Our intuition is never wrong. Except when it is.
Again, for the sake of brevity, I will cut this post short. If these ideas seem weird or mysterious, it is because they are - at least at first. A lot of early work in set theory was accomplished by a man named Gregory Cantor. A man whose ideas shook the foundations of modern mathematics. Many mathematicians believed his work to be factually incorrect purely because they disagreed with its premises. But the best - or worst, depending on which camp you are in - is yet to come. In the next post I will explore the real numbers and the supreme strangeness surrounding these incredible numbers.
Before we get to the weird results, we first need some more dreaded definitions and explanations behind the definitions. The upcoming definitions will, again, be a little strange and you might wonder why we define them as so, but once you see some examples you should be convinced.
Definition: The cardinality of a set is a measure of the elements in the set.
There are two possibilities: either a set is finite or it is infinite. We can easily see how to determine if there are the same number of elements in two finite sets: write the sets out and count the elements. Take for example the following sets:
$ A = \{ 1, 3, 5, 7 \} $ and $ B = \{ 2, 4, 6 \} $. We see that $A$ has four elements, whereas $B$ has three elements and conclude that $A$ and $B$ do not have the same number of elements, i.e. do not have the same cardinality. So far, so good. Unfortunately we cannot count (try as we might!) the amount of elements in an infinite set, so this approach seems less than satisfactory. We may need a shift in paradigm in order to approach the case of infinite sets. You might wonder why we even care; if two sets have an infinite amount of elements, then they have the same number of elements! However by that logic, infinity/infinity should equal one! But we know from calculus that isn't necessarily so. Initial intuition often fails when dealing with infinities, which is often caused by conceptions on shaky foundation.
To create a proper paradigm, we will imagine mathematics without the concept of numbers (it will turn out thinking about numbers is somewhat misleading). How would we then determine if two sets were the same size? We can't make a reference to the number of elements since we don't even know what numbers are, so that is out.
(I will try to avoid using numeric quantifiers so I don't contradict myself.) Imagine a basket with apples in it and imagine a basket with oranges in it. If we were told to determine if there were the same amount of each, we could reach a hand into each basket and pull out a single unit of each. We'll keep them paired when we place them on the ground: an orange with an apple. If we happen to run out of oranges at the same time that we run out of apples, we would be assured that we have the same amount of apples and oranges. Each individual apple is paired with an orange and each orange is paired with an apple. If we have an excess of either apple or oranges, we would have an empty basket and a basket with objects inside it.
This seems logical, but does it reduce down to what we devised before? It turns out that it does. Remember, we can't state how many elements there are since we don't know what numbers are, but we can say whether two collections have the same number of elements.
It turns out that this is the proper way of thinking about cardinality and this notion works wonderfully for infinite sets. We no longer talk about the actual size of the set, but whether or not we can form a proper pairing. If we have an infinite number of oranges and apples, yet we are able to pair one orange with one apple (and vice versa) we would undoubtedly have to say that they have the same cardinality. But if we have an excess of apples when pairing them with oranges, then we would be forced to say that the set of apples is larger than that of the oranges.
Before I continue and make this more concrete, I must define one term which will come up a lot in future discussion. You have undoubtedly heard the term or know what it is without knowing it by name.
Definition: A function $f$ is a bijection from the set $A$ into the set $B$ if $f$ is both one-to-one and onto. (Note: the range of $f$ must be contained in $B$.)
(Muffled groans) You might be thinking: Greaaat. Now what does that mean?
Well, if $f$ were an onto function, it would mean that nothing in our set $B$ is left out. In mathematical jargon, we say that every element in $B$ gets mapped to. See the picture below.
In this diagram, our function's domain is the set $\{a_1, a_2, a_3, a_4 \} $ and its codomain is the set $\{1, 2, 3\}$. The arrow represents what acting our function does to each element. So $f(a_1) = 1$, $f(a_2) = 1$, $f(a_3) = 2$ and $ f(a_4) = 3 $. As you can see, every element of our set $B$ gets mapped to. If an element were left out, it would not have an arrow going to it and our function would not be onto. Since this is not the case, it must be onto.
Okay so now what does one-to-one mean?
You're also familiar with one-to-one, though maybe not this term exactly. Colloquially, a one-to-one function is a function that passes the horizontal line test. An example of a function that is not one-to-one would be the function $f:\Bbb R\to\Bbb R$ given by $f(x) = x^2$. Take for example $x = \pm 1$. For both of these values $f(x) = 1$ so we conclude that $f$ is not one-to-one (two different $x$ values map to the same $y$ value!).
You might be wondering what functions are both one-to-one and onto? Well first we have to define a domain and codomain (our $A$ and $B$ as mentioned in the definition, respectively).
We'll work with what you're used to: the real numbers. We'll use the real numbers for both the domain and codomain. The function $f(x) = x$ is a bijection. The proof of this is left to the reader. (Hint: to show a function is one-to-one amounts to the following. If $f(x) = f(y)$, then $x = y$ - meaning that the only way $f$ can have the same value for two values in its domain is if the two values are in fact the same. To show it is onto, you want to make sure every element in the codomain gets mapped to. Pick $y$ in codomain. Try to find an $x$ such that $f(x) = y$. If no such $x$ exists, then the function is not onto.)
Okay, you've survived the definition of a bijective function (mark that off on your bucket list!). With this definition and the apples and oranges thought experiment from before, we can now give the formal concept behind equating cardinalities.
Concept: Two sets have the same cardinality if there exists a bijective function from one set into the other.
This concept is succinct and quite exact. There is no wiggle room to speak of. But you may not be convinced that this definition works. We'll test it out for our set of apples and oranges from before. The tricky part of showing two sets have the same cardinality is devising the function you need. While you may not be convinced, but we will rig our function to work properly.
Returning to out example of the apples and oranges, suppose $O = \{o_1, o_2, o_3\}$ and $A = \{a_1,a_2,a_3\}$ represent the set of oranges and apples, respectively. We will define $f$ by the following: $f:O\to A$ ($f$ is a mapping from the set of oranges into the set of apples) and
$$ f(o_1) = a_1,\quad f(o_2) = a_2,\quad f(o_3) = a_3.$$
As you can see, each orange is paired with a single apple and each apple is paired with a single orange, so by our previous concept we should have the same amount of each. Now we will show that this is the case within the new paradigm we have created. Is this function onto? The answer is obviously yes. We only had three apples and each one is mapped to by our function (the $ a_1$, $a_2$ and $a_3$). Now is it one-to-one? The answer is also yes. Each apple is paired with one and only one orange (no two oranges map to the same apple; recall the hint to the problem). We have successfully created a bijective function from the set of oranges into the set of apples and therefore they have the same number of elements.
Of course that was somewhat a waste of time since we already knew they had the same number of elements; we could just count them! The utility of this definition really only comes into play when discussing infinite sets and it is this very definition that causes all kinds of conceptual headaches as we are about to see.
Now that we have a proper framework, we can finally answer the question I asked at the beginning of the post, i.e. whether or not the integers and even integers have the same number of elements, i.e. have the same cardinality. We can now very easily answer this question, but first I will appeal to your intuition.
Imagine the finite set $\{1, 2, 3, 4, 5, 6\}$. The set of even integers within this set is $\{2, 4, 6\}$. Of course we would say that these two sets do not have the same number of elements; one has six elements, the other has three. What if there are an infinite amount of both? Well our sets look like the following: $\{\ldots, -4, -3, -2, -1, 0, 1, 2, 3, 4,\ldots\}$ and $\{\ldots, -4, -2, 0, 2, 4,\ldots\}$. Of course we know that the set of even integers are a subset of the integers, but also that there are numbers in the integers that are not in the set of even integers. Our intuition would tell us that the even integers and and the integers do not have the same number of elements. And of course our intuition is never wrong.
We'll check that our intuition is right with our hot-off-the-presses definition. Let's let $f : \Bbb Z\to \Bbb Z_e $, where the [; \Bbb Z_e ;] represents the even integers, and let $f(n) = 2n$, for the sake of argument.
Now, if $n$ is an integer, we know that $2n$ must be an even integer, so we are on the right track (our function's range is inside the codomain). We'll check if $f$ is onto.
Let $y\in \Bbb Z_e$, then $y$ is even. If $y$ is even, then it can be written in the form $2m$, where $m$ is some integer. But our domain is the entire set of integers, so surely $m$ must be in there somewhere! So we must conclude $f$ is onto. Now we'll check that it isn't one-to-one. (Otherwise if it is, our intuition was wrong. And our intuition cannot be wrong. Our intuition is infallible.)
Let $x$ and $y$ be in $\Bbb Z$ and suppose $f(x) = f(y)$. Then $f(x) = 2x$ and $f(y) = 2y$. However if $f(x) = f(y)$, then $2x = 2y$. We then obtain that $x = y$. So $f$ is also one-to-one.
We have created a function from the integers into the even integers that is one-to-one and onto. But one-to-one and onto functions are bijective functions and by our concept concerning cardinalities, we must conclude that $\Bbb Z$ and $\Bbb Z_e$ have the same number of elements. But our intuition says that they can't. What are we to do? Well the answer lies in the fact that we aren't built to understand infinite sets of objects intuitively. When was the last time you came across an infinite collection of apples (much less an infinite collection of both apples and oranges)? The answer is, of course, never. In mathematics we are often led astray by our intuition which leads us to something a professor once told me: Our intuition is never wrong. Except when it is.
Again, for the sake of brevity, I will cut this post short. If these ideas seem weird or mysterious, it is because they are - at least at first. A lot of early work in set theory was accomplished by a man named Gregory Cantor. A man whose ideas shook the foundations of modern mathematics. Many mathematicians believed his work to be factually incorrect purely because they disagreed with its premises. But the best - or worst, depending on which camp you are in - is yet to come. In the next post I will explore the real numbers and the supreme strangeness surrounding these incredible numbers.
