Constructively proving that the integers are countable

[Elok]

Originally posted by KrazyHorse

Sorry, must have gotten my sets mixed up. It's been a while. Should I have said "negative one, zero, one, two, three" or "negative one, one, two, three" or what? Either way it works. Geez, you math people are slow.

No, you need to say something like:

"0, 1, -1, 2, -2, 3, -3,..."

That's precisely the classic bijection between the ints and the naturals

Ah, I see. They're not integers unless you put them in a certain order. Is this like math syntax or something?

[Kuciwalker]

My requirements to get a double major in math (thus, no breadth requirements):

1 semester of intro compsci (HS credit)
calc 1 and 2 (HS credit)
"concepts of math" (tested out)
1 semester discrete math (satisfied by "great theoretical ideas in CS")
linear algebra (HS credit)
multivar (HS credit)
diffeq (HS credit)
algebra (taking next semester)
real analysis 1 & 2 (just finished 1 this semester)
some number of math electives
(currently I have: combinatorics, basic logic, operations research, and numerical methods; I also have a bunch of CS courses which are really math ones, like computer algebra and computational discrete math)
3 math, stats, or CS electives (... yeah, I think I've got this one)

The online academic audit for this major is kinda buggy, but this looks right. The "3 courses left" is from when I went to talk to the math advisor to officially declare the double major.

[Kuciwalker]

Originally posted by Elok
Ah, I see. They're not integers unless you put them in a certain order. Is this like math syntax or something?

No, the thing is that originally, you were talking about the "naturals" (the positive integers). The integers include the negative numbers. In order to "show a bijection with the naturals", you have to list them in a particular kind of way - you have to list the integers such that for any particular one, you know you'll reach it in a finite amount of time.

Thus you can't, e.g., "list all of the positive integers from 1 to infinity, then list all of the negative integers from -1 to -infinity" because it'll take you forever to get to -1.

A bijection, btw, is just a one-to-one association between all the guys in one group and all the guys in the other. Thus, given that listing and some natural number n, I can tell you the nth guy in that listing; alternatively, given that listing and some integer k, I can give you n, where n is how far into that list k appears. When two groups of elements (sets) have a bijection between them, we say they have the same size.

Thus we say "there are as many integers as there are naturals", despite the fact that intuitively there are more integers than naturals (every natural is an integer, plus there are extra integers that aren't naturals).

[KrazyHorse]

Originally posted by Elok


Ah, I see. They're not integers unless you put them in a certain order. Is this like math syntax or something?

No, they're not the integers unless you actually write them all down at some point.

You wrote "-1, 0, 1, 2, ..."

Unless "..." means something crazy in your world you're never going to write down -2, -3, etc.

You need to create a "bijection" (a certain type of mapping between the two sets). Basically, this is equivalent to writing down a sequence of integers such that every integer is guaranteed to appear once and only once.

If I write "0, 1, -1, 2, -2,..."

and you ask me "when will z (an integer) show up?" I can tell you precisely when.

If z <= 0 then it shows up in the "1-2z"th position
If z > 0 then it shows up in the "2z"th position

[Solver]

Originally posted by Asher
One of the best features in the new version of C#is lambda expressions.

.NET 3.5? Cool, I still haven't had a chance to work with it.

[Asher]

Originally posted by Solver


.NET 3.5? Cool, I still haven't had a chance to work with it.

Was added in 3.0

http://blah.winsmarts.com/2006/05/19/demystifying-c-30--part-4-lambda-expressions.aspx

[Elok]

Originally posted by KrazyHorse


No, they're not the integers unless you actually write them all down at some point.

You wrote "-1, 0, 1, 2, ..."

Unless "..." means something crazy in your world you're never going to write down -2, -3, etc.

You need to create a "bijection" (a certain type of mapping between the two sets). Basically, this is equivalent to writing down a sequence of integers such that every integer is guaranteed to appear once and only once.

If I write "0, 1, -1, 2, -2,..."

and you ask me "when will z (an integer) show up?" I can tell you precisely when.

If z <= 0 then it shows up in the "1-2z"th position
If z > 0 then it shows up in the "2z"th position

That's not counting, it's listing. Counting goes in order, and -1 and 1 are opposites. They don't belong next to each other. If I'm counting a bunch of things, I don't say "one, eight, two, seven, three, six, four, five," attractive though the symmetry may be. I start from low and go to high. Even my two-year-old nephew knows that.

[KrazyHorse]

Okay, Elok.

[KrazyHorse]

http://en.wikipedia.org/wiki/Countable_set

[KrazyHorse]

The concept you're trying to grasp at is an "ordered set".

http://en.wikipedia.org/wiki/Ordered_set

[KrazyHorse]

The fact that you can't list the integers in order from low to high is due to the fact that the standard "<=" is not a well-ordering

http://en.wikipedia.org/wiki/Well-ordered_set

on the integers

Edit: oops.

[Kuciwalker]

Originally posted by KrazyHorse
The fact that you can't list the integers in order from low to high is due to the fact that there does not exist a well-ordering

http://en.wikipedia.org/wiki/Well-ordered_set

on the integers

Uh, what? Trivial well-ordering on the integers: use the bijection with the naturals. Done.

I think you meant to say that <= is not a well-ordering on the integers.

[Saras]

damn it you guys make me feel more stupid than necessary

[KrazyHorse]

Originally posted by Kuciwalker


Uh, what? Trivial well-ordering on the integers: use the bijection with the naturals. Done.

I think you meant to say that <= is not a well-ordering on the integers.

Yeah, sorry. Brain fart.

[Solver]

Elok, you may even be surprised to know that being countable doesn't mean there's a finite amount of that stuff Integers are countable but infinitely so. You can not actually list all integers, except in a notation like ..., -2, -1, 0, 1, 2, ..., but they are countable.

The "size" (more precisely, cardinality) of such a set that contains an infinite amount of elements but is, nonetheless, countable is referred to as aleph-null.