Cardinality as the natural numbers

1. Aug 27, 2013

aaaa202

I have seen a lot of examples of sets with same cardinality as the natural numbers. For instance the even numbers or the cartesian product. In any case the proof amounted to finding a way of labeling the elements uniquely.
But Im curious - can anyone give me an example of a set, where this is not possible?

2. Aug 27, 2013

Stephen Tashi

What do you mean by "this"? Is the example to have the same cardinality of the natural numbers? Or is the example not to have the same cardinality as the natural numbers?

3. Aug 27, 2013

Number Nine

The real numbers are the usual example. A few others are the power set of the natural numbers (the set of all its subsets) and the set of all infinite strings of 0's and 1's.

4. Aug 27, 2013

aaaa202

so I have looked up cantors diagonalization argument. Pretty cool idea. But to be honest, and I guess it's a stupid worry, I don't quite get the whole idea that we can write each real number in (0,1) as a decimal fraction. Where does this property of the real numbers come from?

5. Aug 27, 2013

mathman

I can't tell what your question means. This is just the way numbers are expressed. Do you have any other way of expressing real numbers?

6. Aug 27, 2013

aaaa202

maybe the fundamental axioms for real numbers: ordering, completeness etc etc.

7. Aug 27, 2013

MrAnchovy

That's a very good question, definately not a stupid worry - you certainly cannot just assume that each real number can be expressed in this way. However Cantor's diagonalisation argument (applied to the real numbers) does not require this to be true: it shows that a subset of real numbers (those that can be so represented) is uncountable, so the entire set must also be uncountable.

8. Aug 27, 2013

CompuChip

Two sets have the same cardinality if there is a bijection between them. So if your question is: is there an example of a countably infinite set (i.e. having the same cardinality as the natural numbers) for which there is no way of labeling the elements uniquely, the answer is: no, by definition, because we can find a bijection to $\mathbb{N}$ and use that to label them.

9. Aug 28, 2013

verty

Each member of P(N) the power set of the natural numbers corresponds to a binary number between 0 and 1, where the n'th digit = 1 if and only if n $\in$ N, 0 otherwise. N itself corresponds to 0.1111111111111111...b, that is, 1. To every such number there corresponds a member of P(N), so they have the same cardinality, $2^{\aleph_0}$ I believe. But to be honest, these aleph numbers confuse the heck out of me.

10. Aug 28, 2013

aleph-aleph

Cantor's diagonalisation argument is not the only proof. He gave his first uncountability proof in his 1874 paper "on a property of the set of real algebraic numbers".

11. Sep 5, 2013

Zafa Pi

For any countable set, C, I know of there exists a well defined explicit 1 to 1 map from N to C. Is it possible to define a set D and, say, show it's countable by a contradiction argument with no known way to give an explicit map?

12. Sep 5, 2013

Zafa Pi

I think I now have an answer to my question. Let D be the set of all Turing programs that halt. D is countably infinite (infinite is easy and the set of all the programs is countable). But by Turing's theorem there is no way (1st order) to tell which ones halt. Thus no explicit map can be given.

13. Sep 6, 2013

SteveL27

If by a well-defined bijection you mean a bijection expressible in finitely many symbols (either as a formula, or algorithm, etc.) then it's easy to show that there are many sets bijectable to N that have no explicit bijection.

There are uncountably many countable sets (of natural numbers, for example). In fact the cardinality is the same as the cardinality of the reals, $2^{\aleph_0}$. You can see this by lining up all the natural numbers 1, 2, 3, ...

Below each of the numbers, write a 1 or a 0. The set of naturals corresponding to 1 defines a particular countable (or finite) subset of the naturals. So for each binary sequence, there's a distinct countable set. We know there are $2^{\aleph_0}$ binary sequences, therefore $2^{\aleph_0}$ countable sets.

Now, there are only countably many finite strings. So almost all countable sets do not have a definable bijection with N. That is, countably many do and uncountably many don't.

Last edited: Sep 6, 2013
14. Sep 6, 2013

Zafa Pi

What you say is correct. But I named a particular well known set without a definable (1st order) bijection. This is what I was looking for in my 1st post.