A friend and I have been engaged in a lively discussion on prime numbers. I'll cut to the chase right away. They ask:
If you were to write out all of the even numbers and then all of the pairs of primes, you believe they would correspond one-to-one?
Clearly, they are referring to a bijection, which is from my understanding the definition for equal cardinality. Furthermore, I believe that the evens and pairs of primes have the same cardinality. Mind you, in this case we are referring to a set of two primes $\{p, q\}$ rather than an ordered pair, or twin primes, for that matter.
Set-theoretically, my reasoning is as follows:
- 1: Both the evens and primes are countably infinite.
- 2: Any set made from pairing elements of a countably infinite set is also countably infinite.
- 3: There is only one cardinality which is countably infinite.
- 4: Therefore the evens and primes pairs have the same cardinality.
Is my reasoning valid? If not, I'd be grateful for corrections. If so, I'd be grateful for any elaboration which may aid in a convincing argument to end the discussion.
I find my reason quite sound, but I shall give them the benefit of the doubt as they have a higher education on mathematics. Hence, perhaps they are referring to something more abstract, of which you may enlighten me.
Edit: I should also add some of their points too, for context:
"Are you suggesting that if we have 5 objects, and consider how many ways we can combine them into two objects that we will have five such combinations?"
"The number of combinations is not equal to the number of objects."
"Even in dealing with the infinities, the combinations of paired primes are infinitely greater than theircounterparts in the infinite set of even numbers"
Edit 2: The previous title was regarding a 'formal' debate. I realize now I was using 'formally' informally! In fact, the opposite may be more appropriate. An intuitive argument in mostly plain language or with aid of some visualization is optimal, as those are the kind they appreciate the most.
Best Answer
Yes, this is well-known. A simple argument for this fact can come from the fact they're both infinite subsets of $\Bbb Z$, but the cardinality of $\Bbb Z$ is the smallest infinite one, and thus they must share that cardinality.
Ultimately, what this amounts to, more precisely, is this: suppose we have a countable set $\newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\AA}{\mathcal{A}} \mathcal{A} := \set{a_i}^\infty_{i=1}$. Define the collection of its two-member subsets $\mathcal{A}_2 := \{ \{a_i,a_j\} \mid a_i,a_j \in \mathcal{A} \}$.
We ask: is it true that $\abs{\AA_2} = \aleph_0 = \abs{\AA}$?
We can use an argument much in the vein of the countability of $\Bbb Q$ to establish a bijection. Make a table like below:
Here, each dot represents the set $\set{a_{\text{row #}}, a_{\text{col#}}}$. Notice how each set is represented only once.
Draw a line according to this scheme:
Let $f : \AA \to \AA_2$ have $$f(a_i) = i\text{th set touched by this scheme}$$ Clearly, this is a bijection, giving countability.
Of course, replacing $a_i$ with the $i$th prime, and mapping the $i$th even integer instead according to this pattern yields the desired result.
Yes. $\aleph_0$, the infinity of countable infinity, is the smallest in our hierarchy. Hence there is no "smaller-yet-countable" infinity.
Yes. By the previous, both are countably infinite, and hence have cardinality $\aleph_0$.
I assume this is framed in the vein of something like this...
Suppose I have $n$ kinds of paint in equal amounts. I consider a combination of these paints to be pouring two kinds (or more), in their entirety, into a larger container, and thoroughly mixing the result. How many distinct colors can I make (on the assumption each combination is a unique color)?
Well in that case we know that order does not matter, so we have
and so on. It is well known, in fact, that
$$\sum_{i=0}^n \binom n i = 2^n$$
Of course, as one would expect, $n < 2^n$.
So no, taking all possible combinations will not result in as many combinations as there are original objects. Similarly, or even more relevantly, even the number of possible pairs will not necessarily be the same, as
$$\binom n 2 = \frac{n(n-1)}{2} > n$$
However, what is key is that this all is stuck in the realm of finite arithmetic.
Infinity simply behaves weirdly like that.
One issue with all of this is how we define "greater." Greater in what sense?
There are three common ways to define "greater" or how to "order" sets in terms of their "size" (or I guess more concisely -- how to define the "size" of a set).
Set Inclusion: Is $A \subseteq B$? Then we say $B$ is bigger than $A$.
Bijections & Cardinalities: What you're familiar with. $A$ and $B$ are equally "big" in this sense if and only if there is a bijection between them.
(Lebesgue) Measure: Essentially how much volume or area these sets take up, usually limited to subsets of $\Bbb R^n$ or $\Bbb C^n$ for appropriate $n$.
Each have their uses and advantages, and some will satisfy one case but not the others, somewhat. (Trivially, if $A \subseteq B$, then $|A| \le |B|$ and $A$ will have measure at most equal to $B$, so usually the latter two end up being more useful concerns.) For instance:
Another issue is the framing your friend may be using. They may have the intuition to grasp that "if there is an injection $A \to B$, then $|A| \le |B|$" -- but perhaps they're not used to seeing some weird injections like that I used previously (which was a bijection). Part of this is simply exposure.
I'm inclined to agree with them on an intuitive sense: it "feels" like there are far more pairs of primes, than even integers, even when we accept there are equally many primes and even integers to start with. In fact, even we took all possible finite groupings of primes, it would have be countable. We would need sequences or countable sets of prime numbers to begin broaching on uncountable infinity -- I suppose you could look it the gap between countable and uncountable being so big as to need to describe it with infinitely-many, infinitely-big sets of numbers to even touch it. (A countable union of countable sets is still countable, even - so this broaching is not as clear as it sounds!)
In the end, we need to codify this notion of size somehow. Here, cardinality is the best method (they're measure-zero sets and neither are contained in each other), and it's nice in that it works as one would hope for finite sets. It's just that once you hit infinite examples, you have to be willing to open your mind a little bit.
Experience certainly helps with that. (For instance without seeing the usual proof of the countability of $\Bbb Q$, I would not have gone for the above bijection.)
In summary though (as I feel I'm rambling but have lost track of my main point):
It all comes down to how you define the "size" of a set. Sure, it might "feel" bigger: but that's just a feeling. We want cold, hard, unambiguous mathematics to describe that. Cardinality is one way to do so, and the most relevant here. And sadly, infinity just sometimes leads to counterintuitive results like these.