WEBVTT 1 00:00:00.120 --> 00:00:03.120 Welcome to the deep Dive today. Our mission is to 2 00:00:04.599 --> 00:00:08.599 basically decode the invisible architecture that's operating inside your computer 3 00:00:08.720 --> 00:00:09.080 right now. 4 00:00:09.480 --> 00:00:14.279 Yeah, we are taking the physical breaks of reality, you know, steel, glass, concrete, 5 00:00:14.919 --> 00:00:18.519 and we're just trading them completely for pure thought exactly. 6 00:00:19.039 --> 00:00:21.399 We are going to explore some pretty mind bending stuff 7 00:00:21.480 --> 00:00:26.120 like infinite sets, digital logic, and will end with this 8 00:00:26.519 --> 00:00:29.960 wild mathematical puzzle about thirty six military officers. 9 00:00:30.039 --> 00:00:32.799 Oh, the Eiler one. Yeah, that is such a good. 10 00:00:32.640 --> 00:00:35.840 Story, right, It famously proved a mathematical genius wrong and 11 00:00:35.920 --> 00:00:37.880 actually made the front page of the New York Times. 12 00:00:38.000 --> 00:00:40.799 It really is an incredible journey. And you know, while 13 00:00:40.799 --> 00:00:44.000 the term discrete mathematics sounds like a well, like a 14 00:00:44.039 --> 00:00:47.759 purely academic, intimidating concept, it is actually the ultimate toolkit 15 00:00:47.799 --> 00:00:48.799 for clear thinking. 16 00:00:48.560 --> 00:00:50.240 Which is something I think everyone could use a bit 17 00:00:50.240 --> 00:00:50.520 more of. 18 00:00:50.759 --> 00:00:54.240 Oh, definitely. It's essentially the discipline of breaking down these massive, 19 00:00:54.399 --> 00:01:01.079 chaotic problems into solvable, totally logical steps, which is a 20 00:01:01.200 --> 00:01:04.000 highly practical skill for you the listener, whether you are 21 00:01:04.040 --> 00:01:08.200 writing complex software code or honestly just trying to organize 22 00:01:08.239 --> 00:01:09.680 the logistics of your daily life. 23 00:01:09.760 --> 00:01:12.280 Yeah, Okay, so let's unpack this. We are pulling all 24 00:01:12.280 --> 00:01:15.840 of this from Scheriman, Shridharan and ar Bellachristian's textbook on 25 00:01:15.920 --> 00:01:20.079 the Foundations of Discrete Math, right, and what's really fascinating 26 00:01:20.079 --> 00:01:23.079 about their approach is how well we have to start 27 00:01:23.079 --> 00:01:25.879 by defining the absolute baselines before we can build anything else. 28 00:01:25.920 --> 00:01:28.760 Like we all generally know the basics of set theory, right, 29 00:01:28.879 --> 00:01:31.560 just grouping unique elements together, sure, like a basket of 30 00:01:31.599 --> 00:01:34.840 fruit exactly. But where this deep dive gets interesting is 31 00:01:34.840 --> 00:01:38.319 how rigorously the text defines the boundaries of those sets. 32 00:01:38.400 --> 00:01:40.480 Yeah, because of the mathematical reality is that you just 33 00:01:40.519 --> 00:01:44.159 cannot manipulate objects until you know exactly where the borders are. 34 00:01:44.879 --> 00:01:48.599 And this is where concepts like de Morgan's laws come 35 00:01:48.599 --> 00:01:49.040 into play. 36 00:01:49.200 --> 00:01:51.040 Right, which sounds intense. 37 00:01:51.000 --> 00:01:53.959 It sounds worse than it is. A fundamental rule from 38 00:01:53.959 --> 00:01:56.959 the source material states that the complement of a union 39 00:01:57.359 --> 00:01:58.959 is the intersection of the compliments. 40 00:01:59.359 --> 00:02:02.519 Okay, wait, let's translate that. So, rather than looking at 41 00:02:02.560 --> 00:02:06.200 sets as just buckets of items, de Morgan's laws look 42 00:02:06.239 --> 00:02:09.000 at the logical boundaries. So if we have say set 43 00:02:09.039 --> 00:02:12.960 A and Set B, the union is everything inside both 44 00:02:13.000 --> 00:02:16.599 sets combined, and the complement of that union is just 45 00:02:16.599 --> 00:02:19.120 the entire rest of the universe, Like everything that is 46 00:02:19.120 --> 00:02:21.000 strictly outside of both A and B. 47 00:02:21.199 --> 00:02:25.840 Exactly, which de Morgan mathematically proved is completely identical to 48 00:02:25.879 --> 00:02:28.639 taking everything outside of A and then finding the exact 49 00:02:28.639 --> 00:02:30.800 places where it overlaps with everything outside of B. 50 00:02:31.039 --> 00:02:31.400 Wow. 51 00:02:31.520 --> 00:02:34.120 Okay, yeah, you are literally defining what a thing is 52 00:02:34.159 --> 00:02:37.719 by mathematically proving what it isn't You're establishing this perfect 53 00:02:37.759 --> 00:02:38.680 logical symmetry. 54 00:02:39.120 --> 00:02:41.840 And once we establish those boundaries, then we can start 55 00:02:42.039 --> 00:02:44.439 organizing the chaos. Right, Because the text has this whole 56 00:02:44.479 --> 00:02:46.879 section on equivalence relations. 57 00:02:46.479 --> 00:02:48.199 Right, which is just a fancy way of saying we 58 00:02:48.240 --> 00:02:51.039 need a mechanism for grouping things based on a specific, 59 00:02:51.159 --> 00:02:52.439 totally unbending rule. 60 00:02:52.800 --> 00:02:55.719 So the example they use is grouping integers by whether 61 00:02:55.759 --> 00:02:57.560 their difference is a multiple of five. 62 00:02:58.360 --> 00:03:01.120 Yeah, and think about the mechanics of what that rule 63 00:03:01.199 --> 00:03:05.919 actually accomplishes. If you group integers modulo five, you take 64 00:03:05.960 --> 00:03:09.960 the infinite, literally never ending sea of whole numbers, just 65 00:03:10.159 --> 00:03:13.879 endless numbers, right, and you perfectly partition them into exactly 66 00:03:14.319 --> 00:03:20.199 five neat, non overlapping equivalence classes. Everything finds an exact 67 00:03:20.319 --> 00:03:24.240 non contradictory place. You are imposing a finite order onto 68 00:03:24.560 --> 00:03:26.199 an infinite universe. 69 00:03:25.960 --> 00:03:29.680 Which is awesome until human intuition completely breaks down, because 70 00:03:29.680 --> 00:03:31.120 then we get into cardinality. 71 00:03:31.280 --> 00:03:33.000 Ah yeah, the infinities, right. 72 00:03:33.000 --> 00:03:35.919 Cardinality is the mathematical measure of the size of a set. 73 00:03:36.159 --> 00:03:38.439 For a finite set, you just you know, count the 74 00:03:38.479 --> 00:03:39.680 items one, two, three. 75 00:03:39.759 --> 00:03:41.879 But when we get to infinite sets, you obviously can't 76 00:03:41.919 --> 00:03:44.599 count them. You have to compare them logically, which leads 77 00:03:44.639 --> 00:03:46.759 us straight to the Shorter Bernstein theorem. 78 00:03:46.719 --> 00:03:49.120 And Shorter Burnstein is just a brilliant solution to this 79 00:03:49.199 --> 00:03:52.840 exact problem of infinity. The theorem basically states that if 80 00:03:52.840 --> 00:03:55.360 set X is smaller than or equal to set why, 81 00:03:55.560 --> 00:03:57.960 and set why is smaller than or equal to set ACT, 82 00:03:58.000 --> 00:03:58.280 then they. 83 00:03:58.240 --> 00:03:59.879 Must be the exact same size. 84 00:04:00.000 --> 00:04:03.479 One incredibly obvious if we're talking about physical objects, like 85 00:04:03.960 --> 00:04:06.159 if I have equal or fewer books than you, and 86 00:04:06.199 --> 00:04:08.560 you have equal or fewer books than me, we obviously 87 00:04:08.599 --> 00:04:09.879 have the exact same number. 88 00:04:09.639 --> 00:04:12.639 Of books, right. But proving that holds true when the 89 00:04:12.680 --> 00:04:15.280 sets are infinite, when you literally cannot count the books, 90 00:04:15.800 --> 00:04:18.439 that requires a very specific mechanism. 91 00:04:18.000 --> 00:04:19.920 Because you can't just tally them up exactly. 92 00:04:19.959 --> 00:04:23.279 It requires mapping. So since set X is smaller than 93 00:04:23.519 --> 00:04:26.519 or equal to HY, we know every item in X 94 00:04:26.560 --> 00:04:29.480 can find a unique partner and why even if Y 95 00:04:29.560 --> 00:04:32.800 has some items left over, And because why is smaller 96 00:04:32.839 --> 00:04:35.600 than or equal to X, every item and Y can 97 00:04:35.600 --> 00:04:37.360 map back to a unique partner in X. 98 00:04:37.680 --> 00:04:40.360 So you basically play ping pong between the two infinities. 99 00:04:40.480 --> 00:04:42.759 You do, you map an element from X to Y, 100 00:04:42.920 --> 00:04:44.879 and then map that new element back to X, and 101 00:04:44.920 --> 00:04:48.000 so on. This creates these chains of connections. 102 00:04:47.480 --> 00:04:49.000 Like invisible threads between them. 103 00:04:49.079 --> 00:04:51.759 Yeah, some chains might loop in a circle, some might 104 00:04:51.839 --> 00:04:54.600 just stop, and some might bounce back and forth infinitely. 105 00:04:54.800 --> 00:04:57.639 But because every single element in both sets belongs to 106 00:04:57.680 --> 00:05:00.680 exactly one of these chains, you can use to perfectly 107 00:05:00.680 --> 00:05:03.319 pair up every item and X with an item and 108 00:05:03.480 --> 00:05:05.360 Y with zero leftovers. 109 00:05:05.639 --> 00:05:06.879 Oh wow, Yeah. 110 00:05:06.759 --> 00:05:09.680 Guarantees a one to one correspondence without ever needing to 111 00:05:09.720 --> 00:05:11.680 actually count a single item. 112 00:05:12.120 --> 00:05:14.079 So you use the structure of the chains to prove 113 00:05:14.120 --> 00:05:16.600 the sizes are identical. But I feel like the real 114 00:05:16.680 --> 00:05:19.399 twist on infinity comes when we look at the power set. 115 00:05:19.600 --> 00:05:20.560 Oh Canter's proof? 116 00:05:20.720 --> 00:05:23.519 Yes, yes, So for the listener, the power set of 117 00:05:23.519 --> 00:05:25.920 a set is the set of all its possible subsets. 118 00:05:25.959 --> 00:05:28.319 So if your original set is a list of three ingredients, 119 00:05:28.720 --> 00:05:31.199 the power set is every possible recipe you can make 120 00:05:31.240 --> 00:05:34.439 by combining them, including, you know, making nothing at all, right, 121 00:05:34.480 --> 00:05:38.399 the empty set exactly. But the text details Canter's proof, 122 00:05:38.759 --> 00:05:41.160 which demonstrates that the power set of any set is 123 00:05:41.199 --> 00:05:44.160 always strictly larger than the original set itself. Wait, so 124 00:05:44.240 --> 00:05:46.519 if a set is already infinite, its power set is 125 00:05:46.519 --> 00:05:49.560 a bigger infinity. How can something be bigger than endless? 126 00:05:49.600 --> 00:05:51.759 I know it hurts your brain a little, Yeah, but 127 00:05:51.839 --> 00:05:54.279 the mechanism can't use for this proof relies on a 128 00:05:54.319 --> 00:06:00.360 logical contradiction involving what we call ordinary and extraordinary elements. Okay, 129 00:06:01.000 --> 00:06:05.160 Imagine you try to pair every single item in an 130 00:06:05.199 --> 00:06:09.199 infinite set X to a unique subset in its power set. 131 00:06:09.480 --> 00:06:11.560 You assume you can match them one to one perfectly. 132 00:06:11.920 --> 00:06:14.319 So we are setting up our ping pong match again, 133 00:06:14.600 --> 00:06:17.120 hoping to prove they are the same size exactly. 134 00:06:17.399 --> 00:06:20.920 Now, some elements might happen to map to a subset 135 00:06:21.120 --> 00:06:24.879 that actually contains that element. The proof labels these elements 136 00:06:24.920 --> 00:06:28.399 as ordinary okay, But other elements might map to a 137 00:06:28.480 --> 00:06:32.240 subset that does not contain the element itself. These are 138 00:06:32.279 --> 00:06:33.759 labeled extraordinary. 139 00:06:33.839 --> 00:06:38.000 Okay, let's unpack this. Let's gather all those extraordinary elements, 140 00:06:38.000 --> 00:06:40.279 the ones that don't belong in their partner subsets, and 141 00:06:40.319 --> 00:06:42.720 put them into a brand new subset. Let's call it 142 00:06:42.720 --> 00:06:43.839 the misfit subset. 143 00:06:44.000 --> 00:06:46.839 I like that. So, since it is a combination of elements, 144 00:06:46.879 --> 00:06:51.360 this misfit subset must exist within the power set somewhere right. 145 00:06:51.399 --> 00:06:54.639 And because we assumed every subset has a unique partner 146 00:06:54.680 --> 00:06:58.439 element from our original set, this misfit subset must have 147 00:06:58.480 --> 00:07:01.319 a partner item. Let's call that partner item Bob. 148 00:07:01.600 --> 00:07:03.040 Bob the misfit Bob. 149 00:07:03.240 --> 00:07:06.000 So does Bob belong inside the misfit subset? 150 00:07:06.079 --> 00:07:07.600 Wait, hold on, walk me through that one more time. 151 00:07:07.639 --> 00:07:10.240 I'm losing the threat of the paradox here. If Bob 152 00:07:10.319 --> 00:07:12.680 is the partner to the misfit subset, where does he 153 00:07:12.759 --> 00:07:13.399 logically go. 154 00:07:13.600 --> 00:07:17.120 Let's just test both options. Option one. Bob is inside 155 00:07:17.160 --> 00:07:20.279 the misfit subset. But remember the rule for being a misfit. 156 00:07:21.040 --> 00:07:23.639 You are only extraordinary if you do not belong to 157 00:07:23.720 --> 00:07:24.879 your partnered subset. 158 00:07:25.040 --> 00:07:28.120 Oh, so, if Bob is inside his partnered subset. He 159 00:07:28.199 --> 00:07:29.879 is ordinary exactly, and. 160 00:07:29.839 --> 00:07:32.639 If he's ordinary, he cannot be allowed inside a subset 161 00:07:32.680 --> 00:07:34.240 made exclusively of misfits. 162 00:07:34.519 --> 00:07:37.160 Right, so we move to option two. Bob is not 163 00:07:37.279 --> 00:07:39.560 inside the misfit subset, but if he is. 164 00:07:39.519 --> 00:07:41.759 Not in his partnered subset, that makes him a misfit 165 00:07:41.800 --> 00:07:44.519 by definition, which means he should be in it. 166 00:07:44.959 --> 00:07:47.839 Oh, that's wild. It's an impossible loop. He can only 167 00:07:47.839 --> 00:07:49.680 be in the subset if he isn't in it, and 168 00:07:49.720 --> 00:07:51.759 he can only be kept out if he belongs in it. 169 00:07:51.839 --> 00:07:55.319 Right, the logical rule literally breaks its own definition. That 170 00:07:55.439 --> 00:07:59.199 contradiction proves our initial assumption was wrong. A perfect one 171 00:07:59.240 --> 00:08:02.519 to one mapping is impossible. There are always more subsets 172 00:08:02.560 --> 00:08:05.519 than elements, so the power set is a fundamentally larger 173 00:08:05.560 --> 00:08:06.600 tier of infinity. 174 00:08:06.759 --> 00:08:10.839 So there are sizes of infinity that literally dwarf other infinities. 175 00:08:10.920 --> 00:08:13.199 That's okay, we have our sets, We have these different 176 00:08:13.199 --> 00:08:15.240 infinite piers, but we can't just leave them sitting in 177 00:08:15.240 --> 00:08:16.240 an abstract pile. 178 00:08:16.399 --> 00:08:19.000 Now we have to organize them, right, which brings us. 179 00:08:18.959 --> 00:08:23.600 To the next structural block, partially ordered sets or posits. 180 00:08:24.040 --> 00:08:27.279 Yeah, puzzits introduce hierarchical structure, we start looking at how 181 00:08:27.319 --> 00:08:30.800 things relate to one another. Visually, you can map a 182 00:08:30.839 --> 00:08:34.720 posit using a Hassei diagram, where larger items sit physically 183 00:08:34.759 --> 00:08:37.279 above smaller ones, connected by vertical lines. 184 00:08:37.440 --> 00:08:39.120 It looks a lot like a corporate or chart. 185 00:08:39.159 --> 00:08:40.480 Honestly, it really does. 186 00:08:40.600 --> 00:08:44.200 But the partially impartially ordered is the crucial distinction here, 187 00:08:44.240 --> 00:08:47.159 because in a total order, like numbers on a number line, 188 00:08:47.240 --> 00:08:50.120 everything can be compared. Three is less than four, four 189 00:08:50.200 --> 00:08:53.279 is less than five, But in a partial order, some 190 00:08:53.519 --> 00:08:55.879 elements are completely incomparable. 191 00:08:56.000 --> 00:08:58.799 The Org chart analogy is perfect for this. Think about 192 00:08:58.799 --> 00:09:01.759 two mid level managers who both report to the same 193 00:09:01.840 --> 00:09:04.919 vice president and they manage the same entry level employees 194 00:09:04.960 --> 00:09:08.000 beneath them. Okay, they share upper bounds and lower bounds, 195 00:09:08.600 --> 00:09:11.200 but they have no direct authority over each other. They 196 00:09:11.200 --> 00:09:14.240 sit at the exact same level, entirely unconnected. You cannot 197 00:09:14.240 --> 00:09:16.559 say manager A is greater than manager B. 198 00:09:16.879 --> 00:09:19.320 Right, So posits give us structure, but it can be 199 00:09:19.519 --> 00:09:23.039 a bit loose and disconnected. To get closer to the 200 00:09:23.080 --> 00:09:26.320 actual machinery of computer science, we have to tighten the rules. 201 00:09:26.960 --> 00:09:29.440 We move from posits to lattices. 202 00:09:29.519 --> 00:09:33.639 Right, and lattices are a highly specific, honestly beautiful refinement 203 00:09:33.679 --> 00:09:37.200 of a posit. In a lattice, any two elements you 204 00:09:37.320 --> 00:09:40.559 choose must have two things, a meat and a join. 205 00:09:40.879 --> 00:09:42.039 Okay, define those for me. 206 00:09:42.600 --> 00:09:47.679 The meat or infamum is their greatest lower bound, the 207 00:09:47.840 --> 00:09:51.399 join or supremum is their least upper bound. 208 00:09:52.279 --> 00:09:54.440 So no matter which two items you pick on the chart, 209 00:09:54.519 --> 00:09:56.399 even if they are unconnected to each other, you can 210 00:09:56.399 --> 00:09:59.559 always trace their lines down to a shared foundation the meat, 211 00:09:59.799 --> 00:10:01.919 and trace their lines up to a shared ceiling of 212 00:10:02.000 --> 00:10:02.600 the joint. 213 00:10:02.480 --> 00:10:06.000 Exactly, and that rigid structure yields the duality principle. The 214 00:10:06.039 --> 00:10:09.480 symmetry of a lattice dictates that any valid logical formula 215 00:10:09.519 --> 00:10:12.720 remains completely valid if you just swap every meat with 216 00:10:12.799 --> 00:10:14.960 a join and every join with a meat. It's a 217 00:10:14.960 --> 00:10:16.159 mathematical mirror image. 218 00:10:16.200 --> 00:10:18.159 But of course, not all lattice is play nice. There 219 00:10:18.159 --> 00:10:21.440 are two specific formations that totally ruin the structural symmetry, 220 00:10:21.519 --> 00:10:23.960 the diamond lattice and the pentagonal lattice. Ah. 221 00:10:24.039 --> 00:10:27.720 Yes, the troublemakers of discrete math. We call them that 222 00:10:27.759 --> 00:10:32.759 because they break two highly desirable mathematical rules, distributivity and modularity. 223 00:10:32.919 --> 00:10:36.320 A distributive lattice behaves like regular algebra, where you can 224 00:10:36.360 --> 00:10:40.320 distribute terms across an equation. The diamond and pentagonal lattices 225 00:10:40.480 --> 00:10:43.039 warp the math, so distributivity just fails. 226 00:10:43.240 --> 00:10:46.159 How does a pentagon shape actually warp the math? Though? Like, 227 00:10:46.399 --> 00:10:49.320 what does it conceptually mean for the lattice to fail? 228 00:10:49.519 --> 00:10:52.240 Okay, go back to your org chart. Imagine a mid 229 00:10:52.320 --> 00:10:57.320 level manager who reports to the VP, but somehow simultaneously 230 00:10:57.440 --> 00:11:00.559 sidesteps the director who is supposedly on on the chain 231 00:11:00.559 --> 00:11:02.039 of command directly above them. 232 00:11:02.200 --> 00:11:04.200 Oh, so they have a shortcut exactly. 233 00:11:04.279 --> 00:11:07.679 The pentagonal lattice creates a structural bypass. It breaks the 234 00:11:07.720 --> 00:11:10.360 logical chain of command. If you try to distribute a 235 00:11:10.360 --> 00:11:14.879 mathematical operation across that lattice, the bypass causes the equation 236 00:11:15.279 --> 00:11:17.799 to resolve to two completely different answers depending on the 237 00:11:17.799 --> 00:11:21.879 path you take. It ruins the predictability of algebraic distributivity and. 238 00:11:21.919 --> 00:11:24.559 The mathematical reality detailed in the source material is that 239 00:11:24.639 --> 00:11:28.559 any non modular lattice secretly contains this pentagonal shape hiding 240 00:11:28.559 --> 00:11:29.000 inside it. 241 00:11:29.120 --> 00:11:29.919 Yeah, it's wild. 242 00:11:30.240 --> 00:11:33.000 So if a logical structure is fundamentally flawed in that 243 00:11:33.000 --> 00:11:36.519 specific way, that five sided bypass is buried in the 244 00:11:36.639 --> 00:11:39.000 architecture somewhere, just causing trouble. 245 00:11:38.840 --> 00:11:41.960 Which leads us to the ultimate structural question. What happens 246 00:11:41.960 --> 00:11:44.919 when you build a lattice with zero bypasses, a perfectly 247 00:11:44.960 --> 00:11:50.000 distributive lattice where every single element has a unique exact opposite, 248 00:11:50.240 --> 00:11:53.840 a complement, and the entire structure is bounded by an 249 00:11:53.960 --> 00:11:56.919 ultimate ceiling of a universal one and a basement floor 250 00:11:57.279 --> 00:11:58.320 of a universal zero. 251 00:11:58.600 --> 00:12:01.840 Here's where it gets really interesting. You get Boolean algebra. 252 00:12:02.080 --> 00:12:04.840 George Bull developed this in eighteen fifty. He was literally 253 00:12:04.840 --> 00:12:08.840 just trying to mathematically manipulate logical statements true or false, 254 00:12:09.200 --> 00:12:13.080 A and D or not t pure abstract mass exactly. 255 00:12:13.200 --> 00:12:16.679 But by proving that logical thought could be manipulated algebraically, 256 00:12:17.039 --> 00:12:20.960 he inadvertently laid the absolute groundwork for the digital computer, 257 00:12:21.440 --> 00:12:24.679 decades before anyone even dreamed of building physical hardware. 258 00:12:25.000 --> 00:12:28.200 Boolean algebra is the invisible architecture of the digital age. 259 00:12:28.519 --> 00:12:32.960 It's a complemented distributive lattice. Every element has a unique opposite, 260 00:12:33.120 --> 00:12:35.720 everything operates strictly between zero and one, and there are 261 00:12:35.720 --> 00:12:38.919 absolutely no pentagonal bypasses to warp the logic. 262 00:12:39.159 --> 00:12:44.000 Okay, So looking at the representation theorem for finite boolean algebras, 263 00:12:44.600 --> 00:12:47.320 my takeaway is that it's basically squashing all this complex 264 00:12:47.399 --> 00:12:50.879 logic into simple binary strings. Is it really just saying 265 00:12:50.960 --> 00:12:52.799 everything reduces down to ones and l's. 266 00:12:53.559 --> 00:12:57.000 It is not just reducing them, it is preserving them perfectly. 267 00:12:57.559 --> 00:13:00.639 The representation theorem guarantees a lossless translation. 268 00:13:00.879 --> 00:13:02.600 Lossless Okay, you weren't. 269 00:13:02.320 --> 00:13:05.120 Losing the complexity of the algebra. You are mapping it. 270 00:13:05.639 --> 00:13:08.600 Think of the atoms of the lattice. These are the 271 00:13:08.679 --> 00:13:13.360 smallest indivisible elements, sitting just above that universal zero floor. 272 00:13:14.120 --> 00:13:16.960 The theorem proves that any element in the entire infinite 273 00:13:16.960 --> 00:13:20.200 algebra can be constructed by a unique combination of these 274 00:13:20.200 --> 00:13:21.200 foundational atoms. 275 00:13:21.399 --> 00:13:24.879 So if you're lettice relies on say five specific atoms, 276 00:13:24.919 --> 00:13:26.840 you just need a five digit sequence of ones and 277 00:13:26.879 --> 00:13:27.799 nails exactly. 278 00:13:27.879 --> 00:13:30.320 The sequence serves as a characteristic vector. It tells you 279 00:13:30.360 --> 00:13:32.840 exactly which atoms are on and which are off to 280 00:13:32.879 --> 00:13:35.159 build any specific logical argument in that system. 281 00:13:35.320 --> 00:13:39.120 So you are perfectly translating abstract logical thought into binary code. 282 00:13:39.360 --> 00:13:43.159 Yes, that mathematical mapping is the exact reason we can 283 00:13:43.159 --> 00:13:46.080 take pure logic and run it through the physical electrical 284 00:13:46.159 --> 00:13:48.000 switches of a computer processor. 285 00:13:48.200 --> 00:13:51.919 Okay, so we've established this perfect binary Boolean universe where 286 00:13:52.000 --> 00:13:56.679 everything is one or zero. But abstract algebraic rules aren't enough, right, 287 00:13:57.080 --> 00:13:59.840 We need to know if specific structures can actually exist 288 00:13:59.840 --> 00:14:02.559 with in those rules in the real world, which pulls 289 00:14:02.639 --> 00:14:07.000 us out of pure algebra and write into combinatoric commonataorics. 290 00:14:07.080 --> 00:14:10.360 Yes, this is the study of finite structures. We transition 291 00:14:10.440 --> 00:14:13.679 from theory into the actual mechanics of existence. The field 292 00:14:13.679 --> 00:14:17.240 generally splits into two categories, existence problems, which ask if 293 00:14:17.240 --> 00:14:20.759 a structure can even exist, and enumeration problems, which asks 294 00:14:20.799 --> 00:14:21.919 how many of them exist? 295 00:14:22.279 --> 00:14:25.000 So, as an expert, is the real thrill of combinatorics 296 00:14:25.080 --> 00:14:27.960 actually counting all the variations? Or is it the existence 297 00:14:28.000 --> 00:14:31.320 problem like the Aha moment of proving something is fundamentally 298 00:14:31.360 --> 00:14:35.679 possible or impossible without having to physically test every single variation. 299 00:14:36.000 --> 00:14:40.159 Oh, finding a structural impossibility through an existence problem is 300 00:14:40.240 --> 00:14:44.159 often much more elegant. You don't need to exhaustively count 301 00:14:44.200 --> 00:14:48.200 the solutions if you can prove the architecture itself forbids 302 00:14:48.240 --> 00:14:52.159 any solution from existing in the first place. The mutilated 303 00:14:52.240 --> 00:14:55.879 checkerboard problem is the classic example of this logical shortcut. 304 00:14:55.960 --> 00:14:59.279 Okay, picture a standard checkerboard for a second, alternating black 305 00:14:59.279 --> 00:15:02.840 and white squares sixty four squares total. Now, take a 306 00:15:02.840 --> 00:15:05.720 pair of scissors and cut off the top right corner 307 00:15:05.720 --> 00:15:09.120 square and the bottom left corner square. Okay, because they 308 00:15:09.120 --> 00:15:12.519 are diagonally opposite, they are the exact same color. Let's 309 00:15:12.519 --> 00:15:15.240 say we removed two white squares, so we are left 310 00:15:15.279 --> 00:15:18.399 with a mutilated sixty two square board thirty two black 311 00:15:18.440 --> 00:15:20.720 squares and thirty white squares, right, And. 312 00:15:20.720 --> 00:15:23.120 The challenge here is to cover this entire sixty two 313 00:15:23.159 --> 00:15:27.360 square board perfectly with thirty one dominoes. A domino is 314 00:15:27.399 --> 00:15:30.399 exactly the size of two adjacent squares. If you treat 315 00:15:30.399 --> 00:15:33.039 this like an enumeration problem, you might try to physically 316 00:15:33.120 --> 00:15:35.399 test thousands of domino arrangements, and. 317 00:15:35.360 --> 00:15:37.320 You'd get frustrated every single time you end up with 318 00:15:37.320 --> 00:15:39.399 two empty squares that aren't touching exactly. 319 00:15:40.000 --> 00:15:43.360 But the existence problem approach looks for the structural mandate. 320 00:15:43.639 --> 00:15:45.360 It looks for the parity argument. 321 00:15:45.519 --> 00:15:49.240 Yes, every single domino, because it covers two adjacent squares, 322 00:15:49.480 --> 00:15:53.159 must cover exactly one black square and exactly one white square, 323 00:15:53.600 --> 00:15:55.559 There is no other physical way to place it on 324 00:15:55.600 --> 00:15:59.440 the grid. Right Therefore, thirty one dominos will perfectly cover 325 00:15:59.519 --> 00:16:02.639 thirty one black squares and thirty one white squares. 326 00:16:02.399 --> 00:16:05.399 But our mutilated board has thirty two black squares and 327 00:16:05.440 --> 00:16:08.440 thirty white squares. It literally doesn't matter how clever you 328 00:16:08.480 --> 00:16:11.519 are with your arrangement. The fundamental parity of the board 329 00:16:11.600 --> 00:16:14.559 mathematically clashes with the fundamental parity of the dominos. 330 00:16:14.720 --> 00:16:17.639 Is it structural impossibility, no trial and error required. 331 00:16:17.840 --> 00:16:21.360 You locate the invisible wall that prevents a solution which 332 00:16:21.440 --> 00:16:24.240 transitions us perfectly to the grand finale puzzle of the 333 00:16:24.279 --> 00:16:27.919 source material. Euler's thirty six officers problem a. 334 00:16:28.919 --> 00:16:31.320 Leonard Euler is one of the greatest mathematical minds in 335 00:16:31.360 --> 00:16:34.879 human history, and he encountered an existence problem that really 336 00:16:35.240 --> 00:16:36.399 challenged his assumptions. 337 00:16:36.480 --> 00:16:38.879 You have thirty six military officers. They come from six 338 00:16:38.919 --> 00:16:42.120 different regiments, and they hold six different ranks. Euler wanted 339 00:16:42.159 --> 00:16:44.480 to arrange them in a six by six grid, sort 340 00:16:44.519 --> 00:16:47.559 of like a complex Sudoku board, so that no rank 341 00:16:47.639 --> 00:16:49.960 or regiment repeats in any row or column. 342 00:16:50.120 --> 00:16:52.279 Every row must have one of each rank, in one 343 00:16:52.279 --> 00:16:55.000 of each regiment, and the exact same requirement applies to the. 344 00:16:54.919 --> 00:16:57.480 Columns right an Eiler tried to find a solution and 345 00:16:57.559 --> 00:17:01.480 just couldn't. Another mathematician named Terry eventually proved by exhaustive 346 00:17:01.559 --> 00:17:05.160 enumeration that the six by six grid is indeed impossible 347 00:17:05.200 --> 00:17:07.880 to construct. The structural wall is totally real. 348 00:17:08.400 --> 00:17:10.759 But Eiler didn't just stop at the six by six grid. 349 00:17:11.240 --> 00:17:13.799 He looked at the math and noticed a pattern. He 350 00:17:13.880 --> 00:17:16.319 knew a two by two grid was impossible, he knew 351 00:17:16.359 --> 00:17:19.559 six by six was impossible, so he famously conjectured that 352 00:17:19.640 --> 00:17:22.640 this specific kind of grid was impossible for any size 353 00:17:22.640 --> 00:17:25.000 that fit the mathematical formula four and plus two. 354 00:17:25.039 --> 00:17:27.640 Meaning a ten by ten grid, a fourteen by fourteen grid, 355 00:17:27.680 --> 00:17:31.559 and eighteen by eighteen grid, all of them fundamentally impossible. 356 00:17:31.680 --> 00:17:31.920 Yep. 357 00:17:32.000 --> 00:17:34.319 And for a very long time the mathematical world just 358 00:17:34.480 --> 00:17:36.920 accepted it, because you know, if Euler says there's a 359 00:17:36.960 --> 00:17:39.200 structural impossibility, you'd tend to believe him. 360 00:17:39.319 --> 00:17:43.039 Right. It really serves as a cautionary tale about mathematical assumptions. 361 00:17:43.480 --> 00:17:46.200 Even a genius of Euler's caliber can spot a pattern 362 00:17:46.240 --> 00:17:48.799 that turns out to be a fantom. He saw the 363 00:17:48.839 --> 00:17:51.559 impossibilities at two x two and six by six and 364 00:17:51.640 --> 00:17:55.559 assumed a structural parity issue that extended infinitely through the numbers. 365 00:17:56.039 --> 00:17:58.839 He assumed an invisible wall was there, but he was wrong. 366 00:17:59.839 --> 00:18:03.519 The textbook highlights the incredible twist that occurred in nineteen 367 00:18:03.599 --> 00:18:10.119 fifty nine three mathematicians Bow's Shrekandan Parker. They earned literally 368 00:18:10.200 --> 00:18:11.640 the greatest nickname. 369 00:18:11.279 --> 00:18:13.319 In math history, boiler spoilers. 370 00:18:13.440 --> 00:18:16.480 Boiler spoilers. They proved that the ten by ten matrix 371 00:18:16.519 --> 00:18:18.119 is actually possible. 372 00:18:17.680 --> 00:18:21.400 And the textbook literally prints their ten by ten matrix 373 00:18:21.440 --> 00:18:24.079 counter example. You can look at the grid and verify 374 00:18:24.160 --> 00:18:25.920 the ranks and regiments yourself, and. 375 00:18:26.000 --> 00:18:29.119 Disproving Oiler on a ten by ten grid was such 376 00:18:29.160 --> 00:18:31.359 a massive shock to the system that it made the 377 00:18:31.400 --> 00:18:33.599 front page of the New York Times. It was headline 378 00:18:33.680 --> 00:18:35.599 news that a mathematical wall had been broken. 379 00:18:35.880 --> 00:18:38.640 It was a triumph of the existence problem. They didn't 380 00:18:38.720 --> 00:18:42.519 just theoretically argue against Eiler. They manifested the structure. They 381 00:18:42.599 --> 00:18:45.680 proved that the invisible architecture Oiler thought was blocking the 382 00:18:45.680 --> 00:18:49.720 ten by ten grid simply didn't exist. The math totally 383 00:18:49.720 --> 00:18:50.559 allowed for a solution. 384 00:18:50.839 --> 00:18:54.480 Wow, so we've covered a massive amount of invisible architecture today. 385 00:18:54.559 --> 00:18:56.880 We started by looking at the infinite resiicans of the 386 00:18:56.920 --> 00:19:00.240 power set, establishing that some infinities are mathematically low larger 387 00:19:00.319 --> 00:19:03.079 than others. We take those sets and built the hierarchical 388 00:19:03.119 --> 00:19:06.440 ladders of puffits and lattices. We saw how the strict 389 00:19:06.599 --> 00:19:10.279 distributive rules of Boolean algebra converted those ladders into the 390 00:19:10.319 --> 00:19:14.039 lossless ones and zeros of digital computer code. And finally, 391 00:19:14.119 --> 00:19:17.359 we saw how applying those discrete rules to combinations of 392 00:19:17.400 --> 00:19:21.319 items allowed us to see the actual structural walls of 393 00:19:21.359 --> 00:19:23.359 the mutilated checkerboard. 394 00:19:22.920 --> 00:19:25.640 And break through the assumed walls of Euler's thirty six 395 00:19:25.640 --> 00:19:30.000 officers exactly. You know, the true value of understanding discrete 396 00:19:30.000 --> 00:19:34.200 mathematics is that it fundamentally changes how you look at 397 00:19:34.200 --> 00:19:35.000 the world around you. 398 00:19:35.240 --> 00:19:35.559 Yeah. 399 00:19:35.599 --> 00:19:38.240 You start to spot the hidden parity arguments in your 400 00:19:38.319 --> 00:19:38.920 daily life. 401 00:19:39.000 --> 00:19:39.960