I'm studying about countable and uncountable sets, and I have found that an infinite set is countable if and only if its possible to find a bijective relation between that set and the set of natural numbers.

I got a bit confused thinking the way of the definition above, so I thought of another way to find if a set is countable or uncountable. I'm not sure if it's correct so I would like to get some help.

An infinite set S is countable if and only if:

  • Given any ordering relation that covers all the elements of S: for each pair (e1, e2) of elements of S, it is always possible, starting from e1, to reach e2 by counting the elements between e1 and e2 one by one (the same if starting from e2 and going towards e1).

This way I can prove that P(N) is uncountable by establishing an order relation that states all the subsets of N that are elements of P(N) and have cardinality 'c' are located in the left of all of those that have cardinality 'c+1'. So I can start from, for example, {1}, and knowing that {1,2} is in some place to the right of {1}, even if I try to reach {1,2} from {1} counting element by element to the right, I will never, so P(N) is uncountable.

I thought this way because it's easier for me to undersand, but I'm not sure if I'm right.

  • $\begingroup$ This way looks ok, but I would caution you that the definition involving bijections is what people will expect you to know! $\endgroup$ – The Count Apr 11 '17 at 2:01
  • 2
    $\begingroup$ @PaulSinclair: Both of you are wrong. $ω+1$ is obviously countable but no amount of counting is going to get you from $0$ to $ω$. $\endgroup$ – user21820 Apr 11 '17 at 5:13
  • 1
    $\begingroup$ @TheCount: It's certainly not okay; see above comment. $\endgroup$ – user21820 Apr 11 '17 at 5:14
  • 1
    $\begingroup$ You can also look at math.stackexchange.com/questions/2183147/… $\endgroup$ – Asaf Karagila Apr 11 '17 at 5:50
  • 1
    $\begingroup$ If you change "Given any relation of order that..." to "There is a relation of order that covers all the elements of S, such that for each pair...", then your proposed definition would work. But this seems to be just a bijection in disguise, so I'm not sure if that is what you are looking for. $\endgroup$ – Danijel Apr 11 '17 at 14:06

This is not correct. For instance, the set $\mathbb{Q}$ is countable, but with its usual order you cannot go from (say) $0$ to $1$ by "counting elements one by one". So just having such an order does not allow you to conclude a set is uncountable.

  • $\begingroup$ Thanks for the clarification! $\endgroup$ – John Apr 11 '17 at 2:22
  • 1
    $\begingroup$ @John If this answers your question, please make sure to click the check mark underneath the up/down vote buttons to accept it. (Feel free to wait a little while first if you think better answers might come in, but please accept an answer at some point if one of them resolves your confusion.) Welcome to StackExchange. $\endgroup$ – jpmc26 Apr 11 '17 at 4:47

The problem with your definition, which was pointed by the other answers and some of the comments, is that it has a universal quantification.

Infinite sets are weird. Double-U, Ee, Eye, Ar, Dee. WEIRD.

What I mean by that is that infinite sets have a lot of properties that are counterintuitive to our preliminary intuition which is based on finite sets.

In particular, infinite sets will usually have properties predicates on something existing. Like the existence of a bijection. And we can usually prove that there exists other objects which do not satisfy the same properties. For example, if there is a bijection between $A$ and $\Bbb N$, there there are also injective functions which are not bijections, and there are surjective functions which are not bijective.

On the other hand, between two finite sets, if there is a bijection, all injective or surjective functions are bijections.

Another example, more pertinent to your question is ordering. An infinite set can be linearly ordered in many non-isomorphic way. Just a countable set has $2^{\aleph_0}$ different ways that we can linearly order it, without any one of them being as any other. How many of them have this "finite interval" property? Essentially three (the integers, positive integers, negative integers).

On the other hand, given a finite set, any two linear orders are in fact isomorphic. So stating something about one is the same as stating about all of them.


If you wanted to fix your definition, then, you would have to say that there exists an ordering with the said property. But this is just the same as finding a bijection between the set and $\Bbb N$ or $\Bbb Z$. So we are back to square one.

It's good that you're toying with these alternative definitions. This is how you learn the correct ones and develop the correct intuition about these kind of sets.

  • 1
    $\begingroup$ I would pronounce the letter i as /ˈaɪ/ and in your style as Eye rather than Ay $\endgroup$ – Henry Apr 11 '17 at 10:12
  • $\begingroup$ Henry, thanks. Coming from the point of view of a native Hebrew speaker, these differences are sometimes lost on me. I felt that "Aye" would have been excessive. But I guess "eye" would be better. $\endgroup$ – Asaf Karagila Apr 11 '17 at 12:44

Another example: Take two increasing sequences, $a_n$ and $b_m$, such that $a_n<a_{n+1}<b_m<b_{m+1}$ for all $n,m\ge1$. For example, you may take $a_n=1-\frac1n$ and $b_m=2-\frac1m$. Then you cannot reach any $b_m$ starting with any $a_n$.


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.