- 1
- 75 365
Thricery
United Kingdom
Registrace 5. 12. 2011
A channel for maths and maths-adjacent things I find interesting
What A General Diagonal Argument Looks Like (Category Theory)
Diagonal Arguments are a powerful tool in maths, and appear in several different fundamental results, like Cantor's original Diagonal argument proof (there exist uncountable sets, or "some infinities are bigger than other infinities"), Turing's Halting Problem, Gödel's incompleteness theorems, Russell's Paradox, the Liar Paradox, and even the Y Combinator.
In this video, I try and motivate what a general diagonal argument looks like, from first principles. It should be accessible to anyone who's comfortable with functions and sets.
The main result that I'm secretly building up towards is Lawvere's theorem in Category Theory
[link.springer.com/chapter/10.1007/BFb0080769]
with inspiration from this motivating paper by Yanofsky
[www.jstor.org/stable/3109884].
This video will be followed by a more detailed video on just Gödel's incompleteness theorems, building on the idea from this video.
====Timestamps====
00:00 Introduction
00:59 A first look at uncountability
05:04 Why generalise?
06:53 Mathematical patterns
07:40 Working with functions and sets
11:40 Second version of Cantor's Proof
13:40 Powersets and Cantor's theorem in its generality
15:38 Proof template of Diagonal Argument
16:40 The world of Computers
21:05 Gödel numbering
23:05 An amazing program (setup of the Halting Problem)
25:05 Solution to the Halting Problem
29:49 Comparing two diagonal arguments
31:13 Lawvere's theorem
32:49 Diagonal function as a way for encoding self-reference
35:11 Summary of video
35:44 Bonus treat - Russell's Paradox
CORRECTIONS
21:49 - I pronounce "Gödel" incorrectly throughout the video, sorry! Thanks to those who have pointed it out.
- Let me know if you spot anything else!
This video has been submitted to the 3Blue1Brown Summer of Maths Exposition 2
#some2 #mathematics #maths
In this video, I try and motivate what a general diagonal argument looks like, from first principles. It should be accessible to anyone who's comfortable with functions and sets.
The main result that I'm secretly building up towards is Lawvere's theorem in Category Theory
[link.springer.com/chapter/10.1007/BFb0080769]
with inspiration from this motivating paper by Yanofsky
[www.jstor.org/stable/3109884].
This video will be followed by a more detailed video on just Gödel's incompleteness theorems, building on the idea from this video.
====Timestamps====
00:00 Introduction
00:59 A first look at uncountability
05:04 Why generalise?
06:53 Mathematical patterns
07:40 Working with functions and sets
11:40 Second version of Cantor's Proof
13:40 Powersets and Cantor's theorem in its generality
15:38 Proof template of Diagonal Argument
16:40 The world of Computers
21:05 Gödel numbering
23:05 An amazing program (setup of the Halting Problem)
25:05 Solution to the Halting Problem
29:49 Comparing two diagonal arguments
31:13 Lawvere's theorem
32:49 Diagonal function as a way for encoding self-reference
35:11 Summary of video
35:44 Bonus treat - Russell's Paradox
CORRECTIONS
21:49 - I pronounce "Gödel" incorrectly throughout the video, sorry! Thanks to those who have pointed it out.
- Let me know if you spot anything else!
This video has been submitted to the 3Blue1Brown Summer of Maths Exposition 2
#some2 #mathematics #maths
zhlédnutí: 75 393
The hand waving about the 17th entry on the list is actually proves that you cannot have a list of infinite list and be able to enumerate them because there is no way to compare them. They have no end so no matter how many digits in the list you compare you can never say you have compared them all so there is no way any recursive algorithm can be designed that will answer the question are two infinite series the same series
Same problem as all these proofs have the algorithm is never ending, so you never actually produce another entry for the list. In other words, there exist, no point at which you can say you are finished so there is no point at which you can say you have created a number that is not in the list.
Well done
Such a list is not possible that is it can not logiclly exist. Consider a universe of elements that is finite - say the English alphabet. Let's start with the set { a, b, c }. The possible combinations of the elements of this set can be enumerated - 1. a, b, c 2. a, c, b 3. b, a, c 4. b, c, a 5. c, a, b 6. c, b, a .... and so forth. Diagonalization of the list produces the elements a, c, c which is admittedly admittedly not on the list because we have been limited to sets with no repetition of elements. But this easily remedied by listing them as well. In which case diagonalization fails to produce a unique arrangement. But most importantly because such a list grows iterativly across the row - adding the letter {d} to our parent set so that that it comtains four elements, {a, b, c, d} extends the list of possible combinations to columns that extend down a page or more. The point point being that any list of combinations of a finite set of elements will grow downward by the factorial of its growth iterativly across. Diagonalization depends on a square list at least or perhaps one with longer rows than columns. But if diagonalization is to cover every entry then the list must contain at least as many elements from left to right as it does from top to bottom. Diagonalization fails with finite sets. And therefore cannot be extended to the the simplest infinity which as Zermelo points out is only initially available by counting.
In essence the problem is insisting that the representation be binary. Black or white. Reality is not binary, you can't shoehorn it into a binary representation. But consider that there are "valid" sequences such as 0.01001b00101... where b means both 0 and 1. We can validly write down a list that commutes --- the problem is you can't do it if F is binary --- you added a third state implicitly when you had it output infinite loop. It's important to recognize the difference between True and Valid. Valid things might be false but it's still a valid argument!
I prefer mapping to the set { 0, 1, ϕ } because ϕ is both a 0 and a 1, and it's also the root of x^2 + x + 1 in Z2, which makes it the solution to the liar paradox. #RM3 actually reduces the 4 valued logic you get from the field extension to 3 values, ϕ and ϕ+1 (¬ϕ) are symmetric. x(x+1) = 1 is the liar; x and not x is true. Non-classical logic is as natural as the complex numbers are, they are both field extensions, exactly the same.
Using #RM3, a three-valued logic, the idea that a digit is the opposite of itself is expressible and natural; Both is the third truth value, both true and false. Not Both is Both. It's equivalent to neither true nor false, if you want to look at it that way. So you can write down all the reals, just some of the digits aren't knowable.
What tablet and software are you using?😅
4:00 The diagonal argument is flawed and maliciously machinated to deceive anyone who is not careful, is too lazy, or lacks the clarity of mind to spot why is complete nonsense. In such diagonal arrangement is obvious that the number of bits will grow linearly while the number of combinations will grow exponentially, so there will be always sequences that can't fit.
Take all my money this is CZcams gold
What happens if we assume (1 = 0) && (1 != 1)? Does math remain same?
Need godel theorem next
great stuff! and thank you for the links
Interestingly both of Cantor's proofs about the countability of the Real numbers are based on this straw man fallacy. At 2:23 in the video: "Let's first assume that B is actually countable. This means we can find some exhaustive list of infinite binary sequences, where every possible infinite binary sequence, that is every member of B, appears somewhere on this list." That's not the actual meaning of "countable" for infinite sets. It sounds plausible because it would work for a finite set. For a finite set you can just (in principle) write them all down and have a look at them. For infinite sets we need a different definition of "countable" because you cannot just write down a list. The definition of "countable" for an infinite set is that you can create a 1-to-1 mapping (bijective function) between the Integers and every element of the infinite set (Real Numbers for instance). If you can find ANY 1-to-1 mapping between them, and prove that you have not missed any elements of the set, then you prove the set is "countable". Note, if you can find a single 1-to-1 mapping which works then the set is countable, regardless of how many other 1-to-1 mappings you can come up with which fail. For example you could map integers, "N", to fractions, "1/N", and conclude incorrectly that the fractions are "uncountable" because this mapping misses all fractions with numerators other than "1". A failed mapping in a finite set would tell you that your count is wrong. A failed mapping in an infinite set tells you nothing more than it's a failed mapping. There's a second error in the diagonal proof itself (and it's nice that you're using binary as this really drives the point home). If you apply the diagonal method to a sample of random numbers it looks plausible, but if you apply it to ordered numbers the problem is readily apparent as follows. The first column is a set of binary numbers, the next column applies the diagonal method to them: 001 1xx changing first digit from zero to one 010 10x changing second digit from one to zero 011 100 proving that 100 is not on the list 100 101 110 111 If you consider "N" Place Values, for any base "B" there are "B^N" possible values. As you consider more and more Place Values, the list grows (much) faster than the number of elements, "N", which you look at along the diagonal. So the assumption that moving along the diagonal you will eventually reach the "end of the list" is just completely wrong. You can see this on the truncated list, "100" is on the list, you just can't reach it with the diagonal method. Adding more place values only makes this problem worse. The diagonal method is based upon a straw man fallacy and also fails to even knock over the straw man.
Concerning your first point, a list in this context is shorthand for a bijection. Now, concerning your second point: for any integer B > 1 and any positive integer N, the diagonal argument shows that B^N > N. Yes! But the diagonal argument also shows this to be true for infinite values of N, such as the cardinality of the natural numbers. The uncountability of the reals can be phrased as "2^(ℵ₀) > ℵ₀", which is what the diagonal argument shows. Seriously. This is the conclusion of the diagonal argument. You claiming that the diagonal argument doesn't work because "2^(ℵ₀) > ℵ₀" is one of the more silly arguments against Cantor I've ever seen. You're essentially saying, "Cantor is completely correct, which is why he's wrong."
Great video. Impatient for the Godel follow-up. Any chance that such a categorical explanation could be given for the forcing argument?
cantor's stuff is wrong
My browser won't let me watch this. But do a video on RM3 next, a symmetric monoidal closed category
Linguistics example really was great
Self-reference is not what you think it is. See my papers about consciousness, like "Meaning and Context: A Brief Introduction", author: Cosmin Visan.
This is a very strong video
Wow. A new math channel. Interesting.
Why do you need to specify that countability means the ability to enumerate a set's members one at a time? Are there uncountable sets that can be exhaustively represented if their members are enumerated all at once? Looking forward to the Godel video!
Binary system is bad for this kind of proof because 1.011111111111111111111111... equals 1.100000000000000000000.... The simplest solution is to avoid 9's in the decimal system, 2's in the trinary, and so on.
LINGUISTS of MATH! so neat
Its a really nice video!
At 13:40;
this is bad. Don't watch.
I have a question. Our function L somehow acknowledges that there in fact is a listing of all posible 0 and 1 lists, because there they are, just input a certain k and you get the list b_k(-)=L(k,-). However, we prove that there is some list b that is not listed by any k, so doesn't this prove that L cannot exist as a function such that L(k,m) gives the mth element of the kth list of infinite sequences in the first place?
Excellent video, really like it. Would really love to hear your ideas about what the pattern itself "means" :) And looking forward for the Godel theorem video.
10:20 I lost you there. I mean even knowing the subject I lost you :D
Great and brilliant video! I'm just become a fan of yours, I respect your times but please for all humanity don't leave CZcams.
Great analysis
12:00 - Visually, this really looks like asking if every f: N --> {0, 1} is "representable", in the sense of Yoneda. Of course, it's not literally asking that because N doesn't have the necessary categorical structure, but I wonder if it's possible to construct a category with objects indexed by N whose Hom-sets encode L. Awesome video!
This was actually pretty mind blowing. One of those concepts that are extremely deep and powerful but once someone explains it to you in a pedagogical sense it feels so intuitive and simple like it is something that should have been obvious all along. Amazing video, my brain will never be the same again.
I'm in the fun side of CZcams
27:30 Doesn't the k used as input into k, also need an input? And so on?
I can't believe I only now came across this video, it is the absolute best and most comprehensive explanation of diagonal arguments out there, from beginning to end. I truly hope more videos are in the making!
Infinite was not defined. Assume there are countably infinite digits in a sequence. Then all the sequences are listable and the diagonal argument fails. If there are n digits in a sequence, there are 2^n sequences, for all n. Example: two digits in a sequence 1) 00 2) 01 3) 10 4) 11 The diagonal number is 10, which is in the list. A real number in [0,1) can be represented by a sequence of digits, finite for a rational number and countably infinite for an irrational number. Hence the real numbers are countable.
Lol
Well done! Many thanks for your clear inside into the background of category theory.
I'm late to the party here, but damn... this video is _criminally_ underexposed. A terse yet lucid illumination of a delightful, profound, and easily missed common thread. Bravo.
Everything really is just categoey theory, isnt it? 😬
Amazing video!
11:42
Bruh, how can you make one of the very best math explainer videos on youtube and then just stop!? Can you imagine how disappointed I was to finish this video and go to your page to start watching them all?
Excellent. I look forward to your presentation of Godel's incompleteness theorems.
The diagonal argument is only true if you want it to be true by accepting that a diagonal exists in the infinite world. Why accept that? Diagonals DO NOT EXIST in the finite realm. Why assume bit combination lists have diagonals? It's not even true for 3 bits. Three bits has 8 combinations. All possible diagonals not matching 3 bits of 3 numbers will be in that list. But a false diagonal from all 8 would be 8 bits long. Why should I be surprised that an 8 bit number can not be found in a 3 bit register? It seems that I can say that the 8 bits number is in my list when I get to 8 bits. And at 8 bits, the diagonals will be 256 bits long, so I will see them when I get there. Diagonal argument is a nice diagram/philosophy that directs our assumptions about infinity in the direction that is needed in order to continue with mathematical study in that direction. The diagonal argument is a good way to try and rationalize ideas withour worrying about specific assumptions that are required. For me, it's not proof that it must be this way. It's an example of how to view infinity in order see how it looks. And it looks pretty good over there using these assumptions. So I choose to believe the diagonal argument as a simply example of the leep of faith required to continue that way.
I disagree with the diagonal argument: Register size of 1 bit contains 1,0. Both 1 and it's opposite 0. Register size 2 contains these previous numbers with 0's prepended: 01,00. But also, their diagonal opposite exists within a 2 bit register: 11,10. Register of 3 bits contains all previous numbers with 0's prepended: 000,001,010,011. And when we generate all possible diagonal selections of all combinations of any three of these, we obtain these new 'opposites': 100,101,110,111 Register of size N contains all binary combinations of numbers of bit size N and ALL combinations of diagonals of that size of register. If the register leads off to infinity, as do the integers, then the register fits all numbers and their opposites by any diagonal that can be created within it.
More science, less math: THE STRUCTURE OF EXISTENCE czcams.com/video/UDGeXvDRwgU/video.html
Great great video. Looking forward to the next one about Gödel's theorem.
I love the way you motivate the proof of the halting problem. It's really surprising to see the similqrities with th classical diagonal argument!