# Is it proper to say that two infinite sets are the “same size” if there is a bijection between them?

I get the fact that a set can be called countably infinite if it can be bijected with $\mathbb{N}$, but it feels wrong on many levels to say that they are the same size.

Example: $A=\{x \in \mathbb{N} \mid \exists k\in\mathbb{N}\, (x=2k)\}$ is intuitively smaller than $\mathbb{N}$ because it is $50\%$ in size of $\mathbb{N}$. But it is countably infinite.

-
Usually we use the term cardinality instead of size - but the answer to your question is yes. – L. F. Feb 5 '13 at 14:46
Do you mean $A=\{x\in \mathbb N: \exists k\in\mathbb N: x=2k\}$? That is, $A$ is the even natural numbers? – Thomas Andrews Feb 5 '13 at 14:49
Part of it is just your intuition. Your intuition, based on finite sets, is that if $A\subsetneq B$ then $A$ and $B$ cannot be the "same size." This intuition, it turns out, is not a very useful one when dealing with infinite sets. – Thomas Andrews Feb 5 '13 at 14:52
Your $A=\{n\in\mathbb{N},\exists k\in\mathbb{N}, n=2k\}$ is usually written $2\mathbb{N}=\{2n, n\in\mathbb{N}\}$. Written that way, it seems obvious that there are as many elements in $2\mathbb{N}$ as in $\mathbb{N}$... So depending on how you look at it, your intuition gives different results. Hence the need for a convention (which should work with finite sets too): Same "size" means bijection. – xavierm02 Feb 5 '13 at 17:40
@L.F. I much prefer size to cardinality, actually. – Andrés E. Caicedo Feb 6 '13 at 1:22

Yes, with a side remark.

There are many ways to measure sizes of infinite sets, depending on the context. The most basic one is cardinality, and two sets have the same cardinality if there is a bijection between them.

If it is clear that "size" means "cardinality" then it is perfectly fine to say that.

Also related:

-
+1 Asaf. I thought I'd see you, if you were around! – amWhy Feb 5 '13 at 14:55
@amWhy: Thanks! Luckily, my nap time was over and I was awake for this... :-P – Asaf Karagila Feb 5 '13 at 14:59

Two sets are "the same size" is better said as "two sets have the same cardinality" when there exists a bijection from one to the other.

But essentially, the "size" of a set is the "cardinality of the set". Better yet, speaking of size, especially when speaking of the size of infinite sets, countable or otherwise, is a question of the cardinality of the sets.

Cardinal arithmetic acts pretty much as we would expect when examining the cardinality/size of finite sets. But cardinal numbers and cardinal arithmetic, specifically when equating or comparing the cardinality of infinite sets, is not necessarily what we would "expect", intuitively, until you have a firm grasp of what cardinality represents.

For example, the interval/subset of the real numbers given by the interval $(0, 1)$ has the same cardinality ("size") as the set of real numbers! There does, in fact, exist a bijection from the interval $(0, 1)$ to the entire set of real numbers. Here too, it seems very unintuitive to say so, which is why a thorough understanding of what cardinality is (and what it is not) is crucial.

As an aside: you might be interested in this post: A set is infinite if and only if it is equivalent to a proper subset of itself. Here, "equivalent to" means "has the same cardinality as".

-

If you apply an injective function to a set, intuitively the image should be the same size as the original set. Your set is the result of applying the injective function "multiply by 2" to the set $\mathbb N$, so it intuitively ought to be the same size as $\mathbb N$.

But as you point out, intuitively it's smaller, because it's a strict subset.

All this tells you is that intuitive ideas of size that you gather from the finite case cannot all transfer to the infinite case. You have to give up some things that are "obviously true" or "obviously equivalent" because with infinitely many items they aren't anymore.

-

For a different perspective from the other answers: you may be interested in the notion of the (natural) density of a set of natural numbers, which offers an intuitive notion of 'size' that jibes with the idea that there are 'half as many' even numbers as whole numbers — but with the catch that very few sets of interest actually have a non-zero density! The natural density $d(A)$ is defined as the limit $$\lim_{n\to\infty}\frac{\#\{i:i\leq n \wedge i\in A\}}{n}$$ - that is, intuitively, the limit of the percentage of numbers which are members of $A$, as we consider more and more integers. It's easy to see that the natural density of the even numbers is $\frac12$, and in general the density of the multiples of $k$ is $\frac1k$, just as you would expect; but with one or two notable exceptions, most other sets of interest that have a density tend to have a density of $0$ (for instance, the primes, or the square numbers) and some sets (for instance, the set of 'numbers with an odd number of $1$s in their binary expansion') have no density at all because the limit doesn't exist.

-
Surely the density of "numbers with an odd number of $1$s in their binary expansion" is a half, because for all $k$, exactly one of $2k$ and $2k + 1$ have the property? Perhaps something like "numbers most of whose binary expansion is $1$" works better? – Ben Millwood Apr 6 '15 at 21:22