Search:

[QUOTE=Marshmallow Marshall;967435]I am fine, lest Plotato makes his stellar comeback involving more insulting of the French. Thank you :P[/QUOTE]

mm choosing to not be nerdy to avoid getting picked on by a bully? was sc2mafia grade school all along?

Originally Posted by Marshmallow Marshall

I am fine, lest Plotato makes his stellar comeback involving more insulting of the French. Thank you :P

mm choosing to not be nerdy to avoid getting picked on by a bully? was sc2mafia grade school all along?

I’m glad he at least stopped talking in pure copypastas

I’m glad he at least stopped talking in pure copypastas

The set of rationals is countable though, it’s the irrational that present the problem

Although I guess I’m just responding to a copypasta. I wonder if plotato ever posts his own thoughts

The set of rationals is countable though, it’s the irrational that present the problem

Although I guess I’m just responding to a copypasta. I wonder if plotato ever posts his own thoughts

Let's try a proof that some infinite set is countable then. In general, to prove this we need to show that you can map a natural number (these are the numbers 0, 1, 2, 3 4, 5, .... to infinity, sometimes we include 0 sometimes we don't depending on textbook) to every element in the set.

The natural numbers are trivially countable since you can just assign 0 to 0, 1 to 1, 2 to 2, 3 to 3, and so on.

Integers (.... -3, -2, -1, 0, 1, 2, 3 ...) countable proof:
Map 0 to 0, 1 to 1, 2 to -1, 3 to 2, 4 to -2, 5 to 3, 6 to -3....

Now you may say that "HEY! wait a minute, then you're going to run out of natural numbers long before you finish the integers!" But the natural numbers is an infinite set. Pick any integer and I can give you the natural number that would produce it. We just needed to show that we can assign a unique natural number to every integer. Hence the integers are countable.

Now to show that a set is UNcountable you'd need to prove that there is no formula out there which can map a unique natural number to every single element in the set. Of course trying every possible formula would be impossible, hence we look for a more clever way to prove that any formula will fail.
For cantor's diagonalization theorem, in the video they are proving the set R(real numbers) is uncountable. In the wiki and generally the way the proof is shown, it's used on the set of all infinite length binary sequences. In either case, the idea is we first assume that there DOES exist a formula out there which manages to enumerate all the elements of the target set. Then we show that this enumeration must be missing an element of the set and therefore fails to map a natural number to every element in the set. In both cases, the elements here are all infinite in length. So, while yes we are constructing an infinite length element that is not in the enumeration, that element is still a valid member of the set we are trying to prove is uncountable.

Let's try a proof that some infinite set is countable then. In general, to prove this we need to show that you can map a natural number (these are the numbers 0, 1, 2, 3 4, 5, .... to infinity, sometimes we include 0 sometimes we don't depending on textbook) to every element in the set.

The natural numbers are trivially countable since you can just assign 0 to 0, 1 to 1, 2 to 2, 3 to 3, and so on.

Integers (.... -3, -2, -1, 0, 1, 2, 3 ...) countable proof:
Map 0 to 0, 1 to 1, 2 to -1, 3 to 2, 4 to -2, 5 to 3, 6 to -3....

Now you may say that "HEY! wait a minute, then you're going to run out of natural numbers long before you finish the integers!" But the natural numbers is an infinite set. Pick any integer and I can give you the natural number that would produce it. We just needed to show that we can assign a unique natural number to every integer. Hence the integers are countable.

Now to show that a set is UNcountable you'd need to prove that there is no formula out there which can map a unique natural number to every single element in the set. Of course trying every possible formula would be impossible, hence we look for a more clever way to prove that any formula will fail.
For cantor's diagonalization theorem, in the video they are proving the set R(real numbers) is uncountable. In the wiki and generally the way the proof is shown, it's used on the set of all infinite length binary sequences. In either case, the idea is we first assume that there DOES exist a formula out there which manages to enumerate all the elements of the target set. Then we show that this enumeration must be missing an element of the set and therefore fails to map a natural number to every element in the set. In both cases, the elements here are all infinite in length. So, while yes we are constructing an infinite length element that is not in the enumeration, that element is still a valid member of the set we are trying to prove is uncountable.