Constructively proving that the integers are countable

[Kuciwalker]

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

Uh, it's on tests in theoretical math classes. For a lot of people undergraduate math is just stuff you'd do for 'the joy of working with numbers'.

[KrazyHorse]

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?

Because that wouldn't make any sense?

For instance, let's look at the set of all subsets of the natural numbers.

To list some elements of this set (called the "power set" of the naturals):

{3}, {1,8,14}, {35, 953, 1525554, 334252123}

Would you call this set "discrete"?

Because it is very easily demonstrable that the power set of the naturals is NOT countable.

[Kuciwalker]

To be fair, the power set of the naturals contains infinite elements, which he may not consider discrete.

The set of all finite subsets of the naturals would be countable (unless I'm missing something obvious), because there's a bijection with the finite strings.

[Lul Thyme]

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 do you mean by "discrete" here?

While "discrete" is used often in mathematics, in the sense you are using it above, it usually doesn't have a technical definition.

If there were one, it probably would be equivalent to "countable" so your question is somewhat circular. Integers are "discrete" because they are countable. As to why this isn't an axiom, it's probably because it's not needed. As you saw, the proof is extremely short and simple anyway.

[KrazyHorse]

Then what is his definition of "discrete"?

[Kuciwalker]

Incidentally, I've found that bijection with the finite strings is often easier to show than with the naturals, so it's usually the best way to show that something is countable.

[Kuciwalker]

Originally posted by KrazyHorse
Then what is his definition of "discrete"?

Why are you asking me?

[KrazyHorse]

Because you seem to be claiming to understand what he may mean by it?

[Kuciwalker]

I'm claiming to understand what may be excluded under it, e.g. things with an infinite description.

[Jon Miller]

Originally posted by KrazyHorse


Cool. I just never see you post on math stuff.

I rarely post on physics stuff either.

JM

[Solver]

Originally posted by Lul Thyme


I know this thread has probably veered way off-topic by now

It's true that a finite union of countables sets is countable but, on the other hand, the proof of this statement is essentially the proof that the integers are countable.

If they are developing the basic theory in class, they probably would only allow things that have already been proved in proofs so they would need to prove this "from scratch".

But can't you prove that the union of countables is countable without resorting to the countability of integers. I remember something along the lines of, if we have a set A = {a0, a1... } and B = {b0, b1...}, where both sets are countable, all elements of A, if its cardinality is n, can be counted by a map of k: k=ak for k < n and k=i - n if k >= n. Then elements from both the set A and B can be counted as k: k = a(k/2) for even k and k = b((k-1)/2) for odd k. If I remember this correctly, it proves that the union of countables is countable and could be used if building theory in class from scratch.

[Kuciwalker]

But can't you prove that the union of countables is countable without resorting to the countability of integers.

Not without doing a proof of identical complexity.

[Lul Thyme]

Originally posted by Solver


But can't you prove that the union of countables is countable without resorting to the countability of integers. I remember something along the lines of, if we have a set A = {a0, a1... } and B = {b0, b1...}, where both sets are countable, all elements of A, if its cardinality is n, can be counted by a map of k: k=ak for k < n and k=i - n if k >= n. Then elements from both the set A and B can be counted as k: k = a(k/2) for even k and k = b((k-1)/2) for odd k. If I remember this correctly, it proves that the union of countables is countable and could be used if building theory in class from scratch.

Yes of course, but that's essentially the same proof that the integers are countable!
Reread what aneeshm, KH and Kuci posted earlier...

If they had actually proved this in class, then they wouldn't waste time proving that the integers are countable (except possibly as an exercise to make sure the students understood).

[Felch]

Originally posted by KrazyHorse
Then what is his definition of "discrete"?

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.

What is the mathematical definition of discrete?

For instance, let's look at the set of all subsets of the natural numbers.

To list some elements of this set (called the "power set" of the naturals):

{3}, {1,8,14}, {35, 953, 1525554, 334252123}

Would you call this set "discrete"?

Because it is very easily demonstrable that the power set of the naturals is NOT countable.

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.

[Felch]

Originally posted by Kuciwalker
Uh, it's on tests in theoretical math classes. For a lot of people undergraduate math is just stuff you'd do for 'the joy of working with numbers'.

Undergraduate math classes like this are why I majored in bull**** history instead of something that could get me a job.