Alternative way to find if an infinite set is countable

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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.