Constructively proving that the integers are countable

[Kuciwalker]

Originally posted by Felch
Non-continuous. Basically I'm saying that natural numbers are countable because there's a line between each number, while real numbers blur.

Basically I mean that I can count every integer between X and Y. I can not count ever real number between X and Y.

You can't count (in your sense) every rational between X and Y, but the rationals are countable.

[Kuciwalker]

Originally posted by Felch
Was this what the original question was?

I guess it's not countable if you say so. It sounds (in theory) countable to me. It's impossible to actually do it, but I could count every power set of natural numbers less than 5.

{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {1,2,3} ...

However, I'm probably just not understanding the specifics of the language being used here.

Consider "the set of all even numbers". It will never show up in your list.

[KrazyHorse]

Originally posted by Felch
Was this what the original question was?

I guess it's not countable if you say so. It sounds (in theory) countable to me. It's impossible to actually do it, but I could count every power set of natural numbers less than 5.

{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {1,2,3} ...

However, I'm probably just not understanding the specifics of the language being used here.

It's not what the original quesion was. I'm coming up with a set which looks "discrete" to me, yet which is not countable.

The power set of naturals than 5 is of course countable. In fact, it only has 16 elements in it.

Your construction doesn't work for the entire set of naturals though.

[Felch]

Originally posted by Kuciwalker
You can't count (in your sense) every rational between X and Y, but the rationals are countable.

Well, my definition isn't precise, but I understand that rationals are countable.

What I mean (for example) is that you can't count every real number between 0 and 1.

Let me explain what I was thinking.

It is impossible to count a continuous set of numbers. You can always just add on another decimal place at the end and keep going. That's pretty clear.

However, it should be (theoretically) possible to count non-continuous numbers, even if they are infinite. Starting at 1 or 0 or whatever, you can just keep going until you're dead.

However, I know that I'm missing something, because KH is saying that you can't count a power set of natural numbers. While I accept this, I don't really understand it.

The way it seems to me, if you can count to a hundred, you can count to a thousand. And if you can count the power set of all natural numbers less than 5, you can count the power set of all natural numbers less than 50. It follows that you can count to any number.

Are these things [power set of all natural numbers] uncountable because they're infinite? If so, how are integers countable?

I'm probably using a different definition of countable than what is used at higher levels of math.

[Solver]

You are in fact asking about Cantor's theorem. For any set with cardinality n, the cardinality of its power set is > n. An uncountable set has cardinality greater than the set of natural numbers. So you see that the power set of all natural numbers has a greater cardinality than the set of natural numbers, hence it's uncountable. You can look up the proof of the theorem specifically for infinitely countable sets, like the set of natural numbers.

In fact, the general proof is expressed very concisely here:

http://planetmath.org/encyclopedia/ProofOfCantorsTheorem.html

[KrazyHorse]

You can count the power set of any FINITE set, but the power set of an INFINITE set (like the naturals) is uncountable.

Countable means that the set is either finite (like the power set of a finite set) OR it is a special type of infinite (identical to the natural numbers' infinity).

It turns out that the power set of any set is always strictly "bigger than" the set, so the power set of a countably infinite set (the naturals) is uncountable.

[Kuciwalker]

Well, my definition isn't precise, but I understand that rationals are countable.

What I mean (for example) is that you can't count every real number between 0 and 1.

Let me explain what I was thinking.

It is impossible to count a continuous set of numbers. You can always just add on another decimal place at the end and keep going. That's pretty clear.

However, it should be (theoretically) possible to count non-continuous numbers, even if they are infinite. Starting at 1 or 0 or whatever, you can just keep going until you're dead.

Why are the reals 'continuous' while the rationals are not?

The way it seems to me, if you can count to a hundred, you can count to a thousand. And if you can count the power set of all natural numbers less than 5, you can count the power set of all natural numbers less than 50. It follows that you can count to any number.

Are these things [power set of all natural numbers] uncountable because they're infinite? If so, how are integers countable?

But there are things in "the power set of all natural numbers" that aren't in "the power set of all natural numbers less than N" for any N. e.g. the set of all even numbers.

[Kuciwalker]

I'm probably using a different definition of countable than what is used at higher levels of math.

Actually, I think you've got that term right.

Countable means that you can enumerate (list in some order) the set, and for any guy X in the set, you will eventually list X.

For 'sufficiently large' infinite sets, like the reals, this isn't possible (see Cantor's diagonalization of the reals for precisely why).

[Solver]

Speaking of cardinalities, a question for the experts. If I understand correctly, there might exist a transfinite number larger than aleph-null and smaller than aleph-one if the axiom of choice is false. Question: do any serious mathematicians today consider situations when the axiom of choice is not true?

[KrazyHorse]

Yes.

[Felch]

Originally posted by Kuciwalker
Why are the reals 'continuous' while the rationals are not?

I suppose that really doesn't make sense.

Now I'm just more confused than ever. In the future I'll just avoid these threads altogether.

[aneeshm]

Originally posted by Felch
I skipped most of this thread because I knew I wouldn't be smart enough to understand it, but why isn't it just axiomatic that you can count something that is discrete, like integers? What good does it do? It's less useful than memorizing a hundred digits of pi, because that at least impresses some people. Being able to prove that you can count integers is just a math-wank.

It's been done before, so you're not proving anything that isn't already understood. It's self-evident, so you're not going to impress the laymen. And it doesn't seem to have any application, so it's not like you wind up with some sweet laser or doomsday device or anything.

Pure math like this should not be on tests. It should be done for the joy of working with numbers.

I understand where you're coming from, but though this material wasn't formally part of the syllabus, it is still part of the foundations of the theory of computation, and I have no problem with them testing it.

In fact, the understanding of why it is necessary that there will exist an infinity of languages which will not be accepted by any conceivable Turing machine hinges on idea that no bijection can be constructed between a countably and an uncountably infinite set.

The set of all possible languages given an alphabet is uncountably infinite, while there are only a countably infinite number of possible Turing machines. How this can be can be is seen from the natural construction of the Turing machines, where an entire machine can be encoded as a single natural. Given this construction, any given natural can be interpreted as a Turing machine, and any Turing machine encoded as a unique natural. So, having established a bijection between all possible machines and all natural numbers, we can say with confidence that there exist languages which will never be accepted by any Turning machine.

What this boils down to in practical terms is that there will always be problems which a Turing machine, or, in simpler terms, a computer, simply cannot solve, irrespective of how much time or memory you give it.

It is difficult, if not impossible, to truly appreciate the necessity and beauty of the Church-Turing thesis without this insight.

[Kuciwalker]

I understand where you're coming from, but though this material wasn't formally part of the syllabus, it is still part of the foundations of the theory of computation, and I have no problem with them testing it.

In fact, the understanding of why it is necessary that there will exist an infinity of languages which will not be accepted by any conceivable Turing machine hinges on idea that no bijection can be constructed between a countably and an uncountably infinite set.

You mean discrete finite automaton there, not Turing machine.

[Lul Thyme]

Originally posted by Solver
Question: do any serious mathematicians today consider situations when the axiom of choice is not true?

People who do this kind of stuff usually call themselves set theorists. Yes it is usually considered "serious mathematics".

In the rest of mathematics, the axiom of choice is usually "accepted" (or it's irrelevant), although some mathematicians might point out when a proof uses the axiom of choice.

[KrazyHorse]

Also, in my experience mathematicians will avoid using the axiom of choice whenever possible as a "stylistic" choice...