Quinneapolis
[math] the diagonalization proof, in its basic form. because I'm a nerd who likes both math and explaining things
Quinneapolis
/fixes OP
Quinneapolis
so diagonalization proofs are a whole category of proofs, that deal with the concept of different kinds of infinity
Quinneapolis
there are, to ignore some esoteric weirdo shit, two kinds of infinite
Quinneapolis
countable infinities, and uncountable infinities
Quinneapolis
a set is countably infinite if you can order all of the things into an infinitely-long list
Quinneapolis
for example, the set of all positive integers is countably infinite
Quinneapolis
1, 2, 3, 4, 5, etc
Quinneapolis
the set of all integers is also countably infinite
Quinneapolis
you could list them like 0, 1, -1, 2, -2, 3, -3, etc
Quinneapolis
an infinitely long list, but a predictable list that eventually contains any integer
Quinneapolis
uncountable infinites are sets so infinite that they can't be put in any list, even an infinitely long list
Quinneapolis
the set of all numbers is uncountably infinite. not just integers, all of the ones in between
Quinneapolis
the set of all numbers between 0 and 1 is uncountably infinite
Quinneapolis
and that is what we're here to prove
Quinneapolis
it's possible to kind of think of a way you might order a list of all numbers between 0 and 1
Quinneapolis
maybe start with 0.0, 0.1, 0.2, etc up to 0.9, then 0.11, 0.12, 0.13, etc
Quinneapolis
or go 0.5, then cut each half of that in half to get 0.25 and 0.75, then halve each of those, etc
Quinneapolis
that'd give you a list of numbers that looks like this
that'd give you a list of numbers that looks like this
Quinneapolis
actually let's do this one
actually let's do this one
Quinneapolis
skips 0 but whatever
Quinneapolis
works better for my example
Quinneapolis
so given this list
Quinneapolis
I can create a number that I can prove does not exist anywhere in the list
Quinneapolis
how I make it:
Quinneapolis
take the diagonal
take the diagonal
Quinneapolis
increase each digit by 1
Quinneapolis
if it's a 9, roll it around to 0
Quinneapolis
and you get this new number
and you get this new number
Quinneapolis
where is it in the list?
Quinneapolis
it's not in slot 1 - the 1st digit is off by 1
Quinneapolis
it's not in slot 2 - the 2nd digit is off by 1
Quinneapolis
it's not in slot X - the Xth digit is off by 1
Quinneapolis
every number on the list is guaranteed to be at least one digit off from the new number
Quinneapolis
proving that the number is not on the list
Quinneapolis
and you could try to fix this
Quinneapolis
by making this mystery number the 1st number on the list, then moving all the others down 1
Quinneapolis
like so
like so
Quinneapolis
but this is futile
Quinneapolis
because you can just do it again
Quinneapolis
take the diagonal of the new list, offset each digit
Quinneapolis
you've got a new number that isn't on the list
Quinneapolis
no matter what the content of the list is, you can create a number that isn't on the list
Quinneapolis
therefore, real numbers are uncountable
Quinneapolis
they can't be comprehensively listed
Quinneapolis
you can expand this proof to prove things like the existence of functions that can't be expressed in any programming language
Echo
Neat. : D