What Could This Mysterious Symbol Mean?
51sIt opens with a mysterious Unicode symbol and turns a seemingly niche math question into a universal curiosity hook.
▶ Play ClipAI Summary
This video explores the mathematical concept of partial orders, sparked by a Unicode symbol posted on Twitter. It explains total vs. partial orders, shows how dependency trees in programming are a natural partial order, and walks through the topological sort algorithm used in build systems. It also highlights more elegant examples like divisibility and the path to semilattices and calculus.
Chapters
[00:04]
The Symbol in Question
A Unicode symbol posted by Freya sparked discussion; a colleague suggested it might be useful in partial orders to indicate when two objects are comparable.
[00:22]
Total Orders
In a total order, every pair of elements is either less than, greater than, or equal to; the relation is transitive. Examples include counting numbers, integers, rationals, and reals, but not complex numbers.
[01:37]
Defining Partial Orders
A partial order adds a third option: elements can be incomparable. This allows modeling more complex structures.
[01:51]
Example: Dependency Trees
In programming, splitting code across files creates a family tree of imports. Files must be compiled after their dependencies, and files without any dependency relationship are incomparable.
[03:19]
Topological Sorting Algorithm
Adapted from Knuth's 'The Art of Computer Programming': create a source list with dependency counts, repeatedly move zero-dependency items to the result list, and subtract one from dependents until all items are placed.
[04:48]
Handling Dependency Loops
If the source list contains no zero-dependency items, a circular dependency exists; the algorithm should exit with an error.
[05:17]
Real-World Applications
The algorithm can schedule parallel jobs and is used in make and similar build systems.
[05:44]
Divisibility as a Partial Order
On counting numbers, define a < b when a is a factor of b. Primes sit just above 1, composites above their prime factors, creating a beautiful structure.
[06:40]
General Principle
Any relation satisfying partial order laws is a partial order; proofs discovered for partial orders apply to all such structures (DRY mathematics).
[07:13]
Toward Semilattices
Partial orders underpin join- and meet-semilattices, which lead to the greatest lower bound needed for calculus. The creator may make a sequel if there's interest.
This video shows how a simple idea—adding 'incomparable' to ordering—connects a random Unicode symbol to real-world build systems and deep mathematical structures.
Mentioned in this Video
Tutorial Checklist
2
03:49
Check the source list for items with a dependency score of zero and move them to the result list (order among them doesn't matter).
4
04:32
Repeat the cycle with new items that have dropped to zero until every item is on the result list.
5
04:48
If the source list contains no zero-dependency items, a dependency loop exists; exit with an error.
Study Flashcards (8)
What is a total order?
easy
Click to reveal answer
What is a total order?
easy
Click to reveal answer
A relation where any two elements are comparable (<, =, >) and transitivity holds.
00:22
Which number system is NOT a total order?
easy
Click to reveal answer
Which number system is NOT a total order?
easy
Click to reveal answer
Complex numbers.
01:10
What extra option does a partial order allow compared to a total order?
easy
Click to reveal answer
What extra option does a partial order allow compared to a total order?
easy
Click to reveal answer
Incomparability — two elements may be neither less, greater, nor equal.
01:37
In a dependency tree, when are two files incomparable?
medium
Click to reveal answer
In a dependency tree, when are two files incomparable?
medium
Click to reveal answer
When there is no dependency chain between them in either direction.
03:06
What is the first step of the topological sort algorithm from Knuth?
medium
Click to reveal answer
What is the first step of the topological sort algorithm from Knuth?
medium
Click to reveal answer
Create a source list with every item to sort plus a count of its dependencies.
03:35
How do you detect a dependency loop in topological sorting?
medium
Click to reveal answer
How do you detect a dependency loop in topological sorting?
medium
Click to reveal answer
When the source list has items but none with a dependency score of zero.
04:48
What do make and build systems use in their core?
easy
Click to reveal answer
What do make and build systems use in their core?
easy
Click to reveal answer
The topological sort algorithm (or a variant) with dependencies.
05:30
Under divisibility as a partial order, when is a < b?
easy
Click to reveal answer
Under divisibility as a partial order, when is a < b?
easy
Click to reveal answer
When a is a factor of b.
06:00
💡 Key Takeaways
💡
Incomparability as the key addition
This single conceptual shift from total to partial orders unlocks modeling of real-world structures like file dependencies.
01:37
🔧
Topological sort from Knuth
The algorithm provides a concrete, executable method to handle dependency-ordered tasks, directly showing the practical payoff of partial orders.
03:35
📊
Divisibility forms a beautiful partial order
A purely aesthetic mathematical example that still obeys the same laws, illustrating the breadth of the concept.
05:44
⚖️
DRY mathematics with partial orders
One proof about partial orders applies to every structure that obeys the same laws, a powerful abstraction principle.
06:40Full Transcript
[00:04] propagandist Freya recently posted on Twitter about this Unicode character in Twitter about this Unicode character in response Le fox said such a symbol might be useful with partial orders to say these objects are comparable but what is
[00:22] a partial order and what does it mean for two objects to be comparable and how for two objects to be comparable and how do partial orders get
[00:37] perhaps we should introduce you to their more common partner a total either greater than smaller than or equal to every other element and the
[00:55] ordering is transitive in the way you expect so if mice a less than cats and cats are less than dragons then mice are less than dragons lots of things in less than dragons lots of things in maths are total orders the counting
[01:10] numbers the whole numbers and the rational numbers are all total orders even the horribly misnamed real numbers are a total order but not the complex numbers so if you take any pair of
[01:25] totally ordered numbers they will always be less than equal to or greater than be less than equal to or greater than each
[01:37] other a partial order is like a total order but as well as being less than equal to or greater than we also have the option of incomparable I think the option of incomparable I think examples always make things better the
[01:51] partial order that I encounter the most is dependency trees when you are programming you could put all of your program into a single file but then you end up with a massive file that is impossible to deal with thankfully we
[02:07] have a solution for this we can split a program across separate file and have program across separate file and have the main file import the secondary files these secondary in files can in turn have their own Imports so you get a sort
[02:22] have their own Imports so you get a sort of family tree of files now the thing is when you process or compile a program Source into an executable file you have to compile the dependencies before you compile the main file itself if you
[02:39] compile the main file itself if you treat less than as before then if something has a dependency on each other you can say something like Jason less than Maine if you have a chain of dependencies lib XY is less than system
[02:54] D is less than main this chain of dependencies will work will follow the transitive laws just like you would expect but if you try and compare Json
[03:06] expect but if you try and compare Json and system D there are no dependencies between them in either direction so it doesn't matter which order you compile doesn't matter which order you compile these libraries in so we can say that
[03:19] these files are incomparable what is even better is that because we now have even better is that because we now have a way to talk about partial orders mathematically we can create a sorting algorithm the Sorting algorithm I'm
[03:35] algorithm the Sorting algorithm I'm going to use is adapted from kns the art of computer programming first we create a source list with every item that you a source list with every item that you wish to sort and we add along with a
[03:49] recording of the number of dependencies that this item has check the source list for items with a score of zero move move these items from the
[04:01] source list onto the result list zero means this item has no dependencies since they have no dependencies between them these can be done in any order as long as they are at the top of the list so it doesn't matter
[04:16] what order we add these to the result list as long as they're put up to the top we then take all the items in the source list and subtract one from any dependent on an item we just added to the source list we can then repeat this
[04:32] cycle with the new items that have just dropped to zero we will then repeat this dropped to zero we will then repeat this until every item on the source list has been added to the results list well that's the theoretical algorithm
[04:48] that's the theoretical algorithm depending on your programming language to work best with the facilities that the programming language gives however the biggest iation you're going to have to check is the state where you get a
[05:03] to check is the state where you get a source list and there are no zeros which means that there was a dependency loop loop of some sort in that case you should exit out with some sort of error there are a couple of other variants on
[05:17] this system you can modify this algorithm so it will work for scheduling paralleled jobs with dependencies make and similar build
[05:30] dependencies make and similar build processing systems use this algorithm or a variant of of it or an improved variant of it in their core so that was variant of it in their core so that was one practical use of a partial order are
[05:44] there impractical uses of partial orders just partial orders that are fascinating just partial orders that are fascinating for Pure aesthetic mathematical Beauty yes there are here is another example of a partial order divisibility in in the
[06:00] counting numbers you can say that a number is less than another in this ordering if that number is a factor of the other so in this scheme two is less
[06:12] the other so in this scheme two is less than four because four has two as a than four because four has two as a factor however two is incomparable to three because they are not factors of each other this creates a ordering
[06:27] structure that looks something like this with one being at the bottom and all the Primes being next after one and all the composite numbers being above their
[06:40] primes and I just think this looks fascinating and beautiful as long as you have a relationship that follows partial order laws you have a partial order if you find out a proof about partial orders then you can apply it to
[06:57] everything that has this structure partial orders have a don't repeat yourself application to mathematics partial orders are also a foundation for the join semil latus and the meet semil latus which in turn allows us to find
[07:13] the greatest lower bound which is needed for calculus I would love to continue up for calculus I would love to continue up this particular Tower of structures so if there is enough interest I'll make a video on semilattices
[07:29] and why we need them you can show that you're interested by subscribing to my channel and sharing this video with people who you will think will enjoy it thank you very much and I hope to see you later goodbye
