Diagonal Argument : Cantor, Turing, Tarski and Lawvere

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

[@MikeRosoftJH]

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

[@honeybee9455]

Hidden gem this channel

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

[@sonarbangla8711]

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.

[@RBanerj]

Great talk, nice job!

[@NoNTr1v1aL]

Absolutely amazing video!

[@mathematicalcoincidence5906]

Wow ! Thank you !

[@jamestagge3429]

a bit off to the side of the topic but......................I think that all would find this interesting. I would greatly appreciate comments…………The means which Cantor employed in his proposition of diagnalization, i.e., about the infinite string of real numbers being larger than that of natural numbers is discussed and considered in a context in which it is ignored that there is no such thing as infinity in material reality for it defies the means and manner of existence which is that anything that does exist must be distinct, delineable and quantifiable. This understanding includes the products of the realm of the abstract as well in that there is none which is not ultimately the product of the material, contextual referents in reality, that context from which they arise. For example, the abstraction of a pink flying elephant is one formed of the fusion of the material colour pink, the material phenomenon flying and the material entity, elephant. What mathematicians such as Cantor have done is employ the most general understanding of infinity as a concept but ignore the inevitable contradictions which arise, muddying the waters of the context in which their propositions are formulated and presented. 1. Consider that the infinite string of natural numbers is a progression, that which extends outward (forever). Each unit member is a value, the progression advancing by that value plus 1 each time. However, that to which it is being compared, i.e., the infinite set of real numbers is structurally the opposite within the boundaries of the proposition. • In the infinite string or natural numbers, the span between any two unit members is ignored and the line proceeds from each value to the next, extending out forever. • In the proposed infinite string of real numbers, the list of unit members from the first unit member designated to the next, any other which might be identified (e.g., 1 to 2 or perhaps 1 to 1.00000001, etc.) is itself infinite. For this reason, the string cannot exist beyond its consideration as a line segment which is still problematic for reasons I point out below, its overall length a value arbitrarily assigned but finite. So, in the case of the real numbers, the infinite line of unit members would be contained within two designated units with infinite points between and could extend beyond that. The string of numbers does NOT extend outward but rather within itself. This is comparing apples to oranges. - There could be no list of real numbers for the designation of the very first in the list would never be completed or would just be impossible for it would have infinite digits. None of the real numbers could be designated and thus, nor could the list. This is not unlike the problems that arise with line segments in which it is claimed that they are composed of infinite points, yet they cannot be because if of finite length, each end would have to be designated by a point beyond which there was no other which by definition would mean that those points would have to have scope and dimension which would mean that there could not be infinite points composing the line segment. However, if these end points had scope and dimension, what would that be? If 10x, why not 5x then why not 1x, ad infinitum. Thus, the line segment could NOT be composed of infinite points but at the same time would have to be, demonstrating that infinity cannot be paired with material concepts due to such inevitable contradictions. • What then would be the measure by which the string of real numbers was determined to be larger than that of natural numbers? Here we see that the string of natural numbers was being considered by Cantor as such per its unending length, that length forced by the denial of consideration of the span between specified unit members, e.g., 1 to 2 to 3, etc. However the string of real numbers could not be judged in its size in comparison to the string of natural numbers because it would have infinite members within the span of the first two unit members specified. What this means is that both must be considered in terms of unit members only and not by the abstractions of their lengths, as if each at any specified length would have different quantities of unit members. Instead, the string of natural numbers could not be considered in terms of the span between two designated members and the string of real numbers must be considered in and only in that manner. Since length of the string then is not a consideration, we are left to consider only and compare the number of unit members in which case they are equal, their “quantity” being infinite. • I would venture that because of the above, we can only conclude that the list of natural numbers which is infinite, “stretched” along an infinite line could be “aligned” with the real numbers which are infinite while the “quantity” of them is contained within a finite distance, i.e., the length of a line segment arbitrarily defined. So, the comparison of the one quantity with the other is apart from the means of containment of each. This proposition of Cantor’s seems to be a bad analogy to make a mathematical point and is very sloppy in its disregard for the true nature of these concepts of infinity he employs. bit

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

[@koin799]

I found this while looking for mvc iron man infinite

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

[@MikeRosoftJH]

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

[@LaureanoLuna]

@@mimzim7141 The set of all computable real numbers is indeed enumerable (countable) but not recursively enumerable, and this is why the diagonal argument does not produce a procedure that could be used by some algorithm to compute the diagonal number.