Consider the set $\mathbb{N}$ of all natural numbers; we can assign each natural number a point on a single axis. Let $A$ be the set of all of these points; $A$ is a countable set (we can assign each point to the natural number it represents and vice versa). Therefore, the cardinality of the power set of $A$ is equal to the cardinality of the continuum.

If we look at these points, we can create connections between them where each connection connects two points. Let $B$ be the set of all of those connections. A connection of two points is a subset of $A$ containing exactly 2 objects that belong to $A$, and so $B$ is the set of all subsets of $A$ which contain exactly 2 objects that belong to $A$.

The question is: what is the cardinality of $B$?

We came up with a few options, not sure whether they cover all cases, but these are the ones we thought about:

  1. $B$ is a countable set, which means its cardinality is the same as that of $A$ (This seems possible; however, we couldn't find an injective & surjective function that matches objects from $A$ to $B$)
  2. $B$'s cardinality is the cardinality of the continuum
  3. $B$'s cardinality is in between the cardinality of $A$ and the cardinality of the continuum and therefore denies the continuum hypothesis (This seems like a problematic possibility since it has been proved that the continuum hypothesis is independent of the axioms of set theory)
  4. $B$'s cardinality is smaller than that of $A$ (seems very unlikely, since $A$'s cardinality is the smallest infinite cardinal, and $B$ is clearly an infinite set).
  • 4
    $\begingroup$ I think you mean "set" when you say "group". $\endgroup$
    – Asaf Karagila
    Aug 22 '14 at 11:32
  • $\begingroup$ yes, i meant set, my bad. corrected all of the mentions of group to set (hopefully didn't miss any) $\endgroup$ Aug 22 '14 at 11:37
  • $\begingroup$ Now that we cleared that issue, the definition of $B$ is really unclear. $\endgroup$
    – Asaf Karagila
    Aug 22 '14 at 11:39
  • $\begingroup$ upon further thinking, a simpler way to view that problem crossed my mind. let N be the set of all natural numbers. B will be the set of all subsets of N, where the cardinal of all of those subets is 2. (as opposed to the power set of N, which contains subsets of different cardinals) edit: corrected "group" to "set" again. $\endgroup$ Aug 22 '14 at 11:43
  • 1
    $\begingroup$ Each connection can be put in correspondence with a (positive) fractional number (if the connections are not directed, then restrict to the fractions that have the numerator greater than denominator). It's well known that the rationals are countable. $\endgroup$
    – leonbloy
    Aug 22 '14 at 18:47

The set you are talking about is sometimes written as $\def\N{\Bbb N}\binom\N2$ in combinatorics: the set of all $2$-element subsets of$~\Bbb N$. It has the same cardinality as$~\N$. An explicit bijection is given by the combinatorial number system system for $k=2$: map the subset $\{a,b\}$ with $a<b$ to $\binom a1+\binom b2=a+\frac{b(b-1)}2$.

A similar bijection holds for $k$-element subsets for any fixed finite$~k$ (see the linked page). Even the union of all those sets is in bijection with$~\N$; in this case a slightly different bijection works: interpret the subset as a binary number, with the bit in position$~i$ indicating whether $i$ is present in the subset (value $1$) or not (value $0$).

In order to get an uncountable collection of subsets of$~\N$, your collection must contain some subsets that are infinite, and moreover need infinite information to describe (a necessary but not sufficient condition). As long as each element can be specified, using some fixed and definite encoding, by a finite amount of data, one can order the elements by size of those data first, and then for a fixed size by some total ordering of the encoding data (lexicographically for instance); this produces a well-ordering in which each element occurs in a position corresponding to a natural number. The above bijections are in fact inspired by fairly simple such ordering schemes, but using "largest element" in the place of "data size" (but that would no longer work for collections containing infinite subsets with finite descriptions).


The set $\{A\subseteq\Bbb N\mid |A|=2\}$, also sometimes denoted by $[\Bbb N]^2$, is countable.

To see this, note that there is an injection from $[\Bbb N]^2$ into $\Bbb N$ defined by considering a pair $\{m,n\}$, then if $m<n$ map it to $2^m3^n$.

Since the set is infinite, then it has to be countable.


It is clear that $|\mathbb N| \le A \le |\mathbb N\times\mathbb N|$.

But we know that $|\mathbb N|=\aleph_0$ and $|\mathbb N\times\mathbb N|=\aleph_0\cdot\aleph_0=\aleph_0$. (See here for some links to posts with proof of this fact.)

So we get $$ \aleph_0\le|A|\le \aleph_0$$ and now we get $|A|=\aleph_0$ from Cantor-Bernstein theorem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.