Diagonal Argument : Cantor, Turing, Tarski and Lawvere
ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- Diagonal Argument with 3 theorems from Cantor, Turing and Tarski. I show how these theorems use the diagonal arguments to prove them, then i show how they are related to Lawvere theorem and how it can change your point of view about them.
The paper on Lawvere theorem and self referential paradoxes from Noson S. Yanofsky : arxiv.org/pdf/...
Update : There is a mistake at 5:50 on the turing proof : the "reverse diagonal program" definition should be {1 if d(i)=0, Undefined if d(i)=1} which means it should stop if the program loop and loop (undefined) if the program stop.
#mathematics #math #maths #turing #cantor #proof #diagonal #self #theorem #theorems #category #paradox #surjective
Music : soundcloud.com...
10:34 It is instructive to look at the contraposition as well.
If there is a surjective function f: A -> Y^A for some A, then all α: Y -> Y have a fixpoint.
These are classically but not constructively equivalent but the proof of this version is very nice and constructs the fixpoint explicitly.
To prove this, let α: Y - > Y be any function.
Consider now g: A -> Y,
a -> α(f(a)(a)).
Let a‘ in A be a preimage of g under the surjective function f.
Then α(f(a‘)(a‘)) = g(a‘) = f(a‘)(a‘), so f(a‘)(a‘) is a fixpoint of α.
That's just a roundabout way of proving that a surjective function from A to Y^A (Y^A meaning the set of functions from A to Y) cannot exist, as long as Y has at least two elements. (If a and b are elements of Y, then it's trivial to create a function on Y without a fixed point: f: if x=a, then f(x)=b, otherwise f(x)=a.)
The intro is very cool, the video as well of course. :)
Thank you, Glad you like it!
Cantor was a genius who discovered uncountable real numbers cannot be one to one with the natural numbers, so he created two dimensional array of numbers, now the problem isn't that of counting but one of accommodation, in which even a new room can be created out of infinite rooms.
You make really high quality content ! You should have participated in the Summer of Mathematical Exposition challenge. It would surely have given your channel more visibility.
Thank you very much ! I'm so happy to hear this ! Yeah i did it but there were also many content at the same time
Hidden gem this channel
Great talk, nice job!
Absolutely amazing video!
Wow ! Thank you !
You should look at the equation (arg(z)+pi)^(i*abs(z))
I don't see how it is related to the subject, Can you tell me more about it?
Looks like it could be a novel pairing function
I found this while looking for mvc iron man infinite
15:41 why is d bar defined in this way? it should be the reverse...
Thank you i didn't notice i made a mistake,
So it should be {1 if d(i)=0, Undefined if d(i)=1} which means it should stop(1) if the program loop(0) and loop (undefined) if the program stop(1).
Why does diagonal argument not work on computable real numbers?
Because computable real numbers are countable, there exist a bijection with Natural numbers.
The diagonal argument can be applied only on an uncountable set, we suppose that it is countable and it leads to a contradiction which means that it must be uncountable. (Cantor : Suppose Real numbers are countable, create a diagonal numbers that is not in that set, contradiction)
@@mathematicalcoincidence5906 no it is not as simple. If i list the computable numbers and the apply the diagonal argument, then effectively i have created a procedure to compute that diagonal number. Hence this diagonal number is computable and by the diagonal argument it was not in the list.
And yet, the computable numbers are countable. You see the problematic is deeper.
@@mimzim7141 Ok sorry i've missed your point.
If we apply Diagonal Argument to a countable set, the diagonal numbers become a procedure to create a number outside of that set.
For Rationnal Q, if you compute the diagonal numbers you end with an irrationnal numbers. Because in the construction your number has always something different from all others rationnal, (different from all periodic decimals sequence that exists which means it is irrationnal).
In the case of computable real numbers, the diagonal numbers give you an uncountable real numbers, because the diagonal numbers will be different from all decimals of other computable real numbers.
@@mimzim7141 The fundamental reason why this doesn't work is: you can enumerate all computable real numbers. (Meaning: the set of all real numbers whose decimal expansion can be generated by an algorithm. And that's true because there are countably many algorithms - an algorithm is a finite object, under one of the several equivalent definitions of algorithmic computation. For example, there are countably many Turing machines.) But this enumeration itself can't be evaluated by an algorithm. There's no such algorithm which, given natural numbers a and b (under a suitable encoding) returns the b-th digit of the a-th computable number, such that this covers all computable numbers (and such that this algorithm is guaranteed to halt on every valid input). If you apply the diagonal procedure to the sequence of all computable numbers, you get a real number which differs from all computable numbers, and therefore the resulting number is not computable.
What if I replace this with numbers definable with a formula? The problem with this is that the notion of "a formula defines a real number" can't be formalized within the theory itself (e.g. in set theory). You can represent formulae as natural numbers (this is the Gödel numbering). But the notion of "formula represented by number n is true" (within the current model of set theory) can't be expressed as a formula. This is Tarski's theorem on non-definability of truth.