Diagonal Argument : Cantor, Turing, Tarski and Lawvere

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/math/0305282.pdf
Update : There is a mistake 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/user-938398110...

[@hdbrot]

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 α.

[@RBanerj]

Great talk, nice job!

[@NoNTr1v1aL]

Absolutely amazing video!

[@mathematicalcoincidence5906]

Wow ! Thank you !

[@Nim2]

The intro is very cool, the video as well of course. :)

[@mathematicalcoincidence5906]

Thank you, Glad you like it!

[@saikat93ify]

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.

[@mathematicalcoincidence5906]

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

[@koin799]

I found this while looking for mvc iron man infinite

[@cannonball7]

You should look at the equation (arg(z)+pi)^(i*abs(z))

[@mathematicalcoincidence5906]

I don't see how it is related to the subject, Can you tell me more about it?

[@yubtubtime]

Looks like it could be a novel pairing function

[@eitanporat9892]

15:41 why is d bar defined in this way? it should be the reverse...

[@mathematicalcoincidence5906]

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).

[@mimzim7141]

Why does diagonal argument not work on computable real numbers?

[@mathematicalcoincidence5906]

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)

[@mimzim7141]

@@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.

[@mathematicalcoincidence5906]

@@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.