1: Both the evens and primes are countably infinite.
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.
2: Any set made from pairing elements of a countably infinite set is also countably infinite.
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.
3: There is only one cardinality which is countably infinite.
Yes. $\aleph_0$, the infinity of countable infinity, is the smallest in our hierarchy. Hence there is no "smaller-yet-countable" infinity.
4: Therefore the evens and primes pairs have the same cardinality.
Yes. By the previous, both are countably infinite, and hence have cardinality $\aleph_0$.
"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."
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
- $\binom n 1$ kinds of paints without mixing
- $\binom n 2$ kinds of paints that result from mixing two
- $\binom n 3$ kinds of paints that result from mixing three
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.
"Even in dealing with the infinities, the combinations of paired primes are infinitely greater than theircounterparts in the infinite set of even numbers"
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:
- $(0,1)$ and $[0,10]$ have equal cardinalities, but different Lebesgue measures ($1$ versus $10$).
- $\Bbb Q$ is countable and the Cantor set is uncountable, but they have equal measure of zero.
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.
Best Answer
Your reasoning is correct. How to write it up nicely depends on what results you already have available to use. It might be enough to write something like this: