Cardinality as the natural numbers

[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 I am curious - can anyone give me an example of a set, where this is not possible?

 

[Stephen Tashi]

can anyone give me an example of a set, where this is not possible?

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?

 

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

 

[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?

 

[mathman]

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?

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?

 

[aaaa202]

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

 

[pbuk]

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?

That's a very good question, definitely 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.

 

[CompuChip]

In any case the proof amounted to finding a way of labeling the elements uniquely.
But I am curious - can anyone give me an example of a set, where this is not possible?

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.

 

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

 

[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".

 

[Zafa Pi]

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.

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?

 

[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?

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.

 

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

 

[Zafa Pi]

...

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.

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.