Constructively proving that the integers are countable

[Kuciwalker]

That was the proof we did, from Hopcroft/Ullman/Motwani.

Just out of curiosity, which book did you use for this course?

I don't know. I've never actually read any of my CS textbooks.

Quite interesting. Where can I read further on this?

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

Though, that article looks pretty crappy.

http://en.wikipedia.org/wiki/Turing_degree looks better.

[KrazyHorse]

Originally posted by Sirotnikov

ok i read it up.

you set up a function to match x/y to (x,y) which is countable.
or you can setup f(m/n) = 2^m * 3^n.

this annoying, and unexpected.

but does the definition of countable not require that the matching functions be unto?

we still haven't reached it, under what subject is it usually taught?

Countability requires simply a bijection between the set and SOME SUBSET of the naturals

Since any infinite subset of the naturals is bijective with the naturals (use the well-ordering of the naturals under <=) any infinite countable set is therefore directly provable to be bijective with the naturals

[KrazyHorse]

If a set is infinite it is therefore sufficient to show that there is an injective function from the set to the naturals. The fact that a bijection exists follows directly.

[Kuciwalker]

.

[KrazyHorse]

Originally posted by KrazyHorse
If a set is infinite it is therefore sufficient to show that there is an injective function from the set to the naturals. The fact that a bijection exists follows directly.

To be more explicit, let f:S->N be an injective function. Let f(S) be the image of f in N. let g:f(S)->N be a bijection between an infinite subset of the naturals and the naturals themselves. g(f):S->N is therefore a bijection

[aneeshm]

Originally posted by Kuciwalker

That was the proof we did, from Hopcroft/Ullman/Motwani.

Just out of curiosity, which book did you use for this course?

I don't know. I've never actually read any of my CS textbooks.

?

Then what do you learn from, other than the lectures?

[Kuciwalker]

Originally posted by aneeshm
?

Then what do you learn from, other than the lectures?

Nothing? (Well, ignoring the practical experience gained in project classes.)

I do read math texts, as they tend to be a lot better than the lectures.

[aneeshm]

Originally posted by Kuciwalker

Nothing? (Well, ignoring the practical experience gained in project classes.)

The lectures are sufficient?

[Kuciwalker]

Usually the lectures themselves are even unnecessary, all you need are the lecture notes (helpfully online in PDF).

[aneeshm]

Originally posted by Kuciwalker
Usually the lectures themselves are even unnecessary, all you need are the lecture notes (helpfully online in PDF).

Is this generally the case, or specific to CMU? Because as far as my experience goes, the lectures are generally only enough to cover the fundamentals, all the deep study has to be done on your own, from the texts.

[Sirotnikov]

bah

it is increasingly frustrating having to refer to a dictionary to read KH's post.

Learning math in hebrew, we use other hebrew words for things like injection bijection etc.

[KrazyHorse]

surjection (prefix like "sur" in French meaning "over") is a mapping f from A to B such that f(A) = B

injection is a mapping g from A to B s.t. g(a) = g(a') implies a=a'

bijection is surjection AND injection

[KrazyHorse]

injection also called "one-to-one"
surjection also called "onto"

confusingly, bijection also called "one-to-one correspondence"

This is why injection, surjection, bijection terminology better

[Jon Miller]

one-to-one and onto is what we used for bijection

JM

[Solver]

The terminology for this is silly. I had one course where the things were referred to as injections and surjections, and another where they were referred to as "onto" and "over". Redundancy