{"id":171430,"date":"2023-09-06T12:23:06","date_gmt":"2023-09-06T17:23:06","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2023\/09\/what-a-general-diagonal-argument-looks-like-category-theory"},"modified":"2023-09-06T12:23:06","modified_gmt":"2023-09-06T17:23:06","slug":"what-a-general-diagonal-argument-looks-like-category-theory","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2023\/09\/what-a-general-diagonal-argument-looks-like-category-theory","title":{"rendered":"What A General Diagonal Argument Looks Like (Category Theory)"},"content":{"rendered":"<p><\/p>\n<p><iframe style=\"display: block; margin: 0 auto; width: 100%; aspect-ratio: 4\/3; object-fit: contain;\" src=\"https:\/\/www.youtube.com\/embed\/dwNxVpbEVcc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope;\n   picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p>Diagonal Arguments are a powerful tool in maths, and appear in several different fundamental results, like Cantor\u2019s original Diagonal argument proof (there exist uncountable sets, or \u201csome infinities are bigger than other infinities\u201d), Turing\u2019s Halting Problem, G\u00f6del\u2019s incompleteness theorems, Russell\u2019s Paradox, the Liar Paradox, and even the Y Combinator.<\/p>\n<p>In this video, I try and motivate what a general diagonal argument looks like, from first principles. It should be accessible to anyone who\u2019s comfortable with functions and sets.<\/p>\n<p>The main result that I\u2019m secretly building up towards is Lawvere\u2019s theorem in Category Theory.<br \/> [<a href=\"https:\/\/link.springer.com\/chapter\/10.1007\/BFb0080769\">https:\/\/link.springer.com\/chapter\/10.1007\/BFb0080769<\/a>]<br \/> with inspiration from this motivating paper by Yanofsky.<br \/> [<a href=\"https:\/\/www.jstor.org\/stable\/3109884\">https:\/\/www.jstor.org\/stable\/3109884<\/a>].<\/p>\n<p>This video will be followed by a more detailed video on just G\u00f6del\u2019s incompleteness theorems, building on the idea from this video.<\/p>\n<p>====Timestamps====<br \/> 00:00 Introduction.<br \/> 00:59 A first look at uncountability.<br \/> 05:04 Why generalise?<br \/> 06:53 Mathematical patterns.<br \/> 07:40 Working with functions and sets.<br \/> 11:40 Second version of Cantor\u2019s Proof.<br \/> 13:40 Powersets and Cantor\u2019s theorem in its generality.<br \/> 15:38 Proof template of Diagonal Argument.<br \/> 16:40 The world of Computers.<br \/> 21:05 G\u00f6del numbering.<br \/> 23:05 An amazing program (setup of the Halting Problem)<br \/> 25:05 Solution to the Halting Problem.<br \/> 29:49 Comparing two diagonal arguments.<br \/> 31:13 Lawvere\u2019s theorem.<br \/> 32:49 Diagonal function as a way for encoding self-reference.<br \/> 35:11 Summary of video.<br \/> 35:44 Bonus treat \u2014 Russell\u2019s Paradox.<\/p>\n<p>CORRECTIONS<\/p>\n<div class=\"more-link-wrapper\"> <a class=\"more-link\" href=\"https:\/\/lifeboat.com\/blog\/2023\/09\/what-a-general-diagonal-argument-looks-like-category-theory\">Continue reading \u201cWhat A General Diagonal Argument Looks Like (Category Theory)\u201d | &gt;<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Diagonal Arguments are a powerful tool in maths, and appear in several different fundamental results, like Cantor\u2019s original Diagonal argument proof (there exist uncountable sets, or \u201csome infinities are bigger than other infinities\u201d), Turing\u2019s Halting Problem, G\u00f6del\u2019s incompleteness theorems, Russell\u2019s Paradox, the Liar Paradox, and even the Y Combinator. In this video, I try and [\u2026]<\/p>\n","protected":false},"author":661,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523,2229],"tags":[],"class_list":["post-171430","post","type-post","status-publish","format-standard","hentry","category-computing","category-mathematics"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/171430","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/661"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=171430"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/171430\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=171430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=171430"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=171430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}