we're going to go over partially ordered sets we'll see the definition and a couple examples and we'll also see a couple of Hossa diagrams to represent these partially ordered sets by the end of the lesson there's a good chance you'll be able to read and perhaps create your own Hossa diagrams but I will be focusing more on partially ordered sets in this video I'll leave a link in the description to my lesson focused just on Hossa diagrams if that's what you're looking for so what is a partially ordered set or post set well let's first think about the non-negative integers certainly they are ordered under our usual less than relation we would start with the number zero and the next number is one that's the next non-negative integer these two numbers are in order and we could keep on going to 2 and then to three to four and as far as we want if you pick any two non-negative integers we could certainly order them based on which is less than the other which one is further along in the number line but in ordering on elements of a set does not need to be this strict we don't have to have every pair of elements in some order we could be a little bit less strict and that's where partial orders come in a partial order might only relate certain elements of a set not all elements necessarily have some relation to each other here is the definition First beginning with the definition of partial order a relation r on a set a is a partial order if it is a reflexive relation an anti-symmetric relation and transitive then if we take that set a along with the partial order R this is called a partially ordered set or a post set here's an example of a pose set from set theory let's say s is the set containing one two and three then consider the power set of s this is a set that will actually have our relation on the power set of course is just the set of all subsets of the original set s so this contains things like the empty set the set containing one and two the set as itself all subsets of s then our relation R our partial order on the power set is going to be the subset relation I can just say that the relation is the subset relation but let's just take a close look at R notice that it is the set of ordered pairs X Y where X and Y are both from the power set of s so X and Y are both subsets of s and we'll say that two elements X and Y relate to each other and thus the ordered pair xy's In our relation if x is a subset of of Y then the power set of s together with this relation R forms a partially ordered set or post set now why is it a partially ordered set well we've got our set P of s it has been partially ordered because our subset relation is reflexive since every set is certainly a subset of itself so it's reflexive also the subset relation is anti-symmetric a relation being anti-symmetric means that no distinct elements relate symmetrically so no distinct elements relate in both directions said another way this means that if x relates to Y and Y relates to X then it must be the case that X is equal to Y again this is because anti-symmetry means that no two distinct elements relate symmetrically so if we have two elements that do relate symmetric quickly well they must not be distinct they must in fact be equal this is of course true of the subset relation this is precisely how we typically prove that two sets are equal if one's a subset of the other and that's also true in the other direction then the sets are equal so classic example of an anti-symmetric relation and of course the subset relation is transitive if x is a subset of Y and Y is a subset of Z then clearly X is also contained in Z and so indeed X is a subset of Z so subset satisfies transitivity so that's what makes this a partial order and thus a partially ordered set it's got a lot of nice order type properties you can travel from one element to the next via transitivity X is a subset of Y is a subset of Z so X is a subset of Z and if two distinct elements relate to each other they can't relate in the other direction that's pretty important for an order but it's a partial order because it's not required that all elements of the set relate to each other in some way for example if we consider the set containing one and three as well as the set containing one and two neither of these sets are subsets of each other so the power set here P of s has only been partially ordered before we move on to our next example here is the hassa diagram for this partially ordered set you may be surprised to see that it doesn't have any arrows indicating the direction of a relation but that's one of the smart features of a hassa diagram is that it gets around including any arrows the way it does that is by ensuring that if there were arrows they would all be pointing the same direction so in fact they're not necessary in this diagram our relation moves from top to bottom so for example the empty set goes up to the set containing two so I know the direction of this relation it's that the empty set relates to the set containing two the empty set is a subset of the set containing two similarly we go up from the set containing two to the set containing two and three thus it's this which is a subset of this not the other way around our relation goes up you could make a hassa diagram where the relation goes from top to bottom or left to right or right to left either way it's great to make sure the relation is always going the same direction because that allows us to not need arrows two other nice features of a hassa diagram notice that none of our elements have arrows connecting to themselves or lines connecting to themselves indicating that they relate to them themselves that's because hassa diagrams are for representing partially ordered sets and in a partially ordered set every element always relates to itself because partial orders are by definition reflexive so we don't need to clutter up our diagram with arrows indicating those reflexive relations we know they are there by definition of a partial order so we don't include them in the diagram finally you may notice that there is no line or Arrow joining the set containing two for example to the set containing one two and three even though the set containing two is a subset of the set containing one two and three the reason there's no Arrow there is that I know this is a subset of this by transitivity since the set containing two is a subset of the set containing one and two which is a subset of the set containing one two and three the relation between between these elements is just a result of transitivity and again since I know partially ordered sets are transitive any relation that results from that transitivity doesn't really need to be represented in the diagram in the diagram I can see this relation because I know pose sets are transitive and I see that we can travel along edges from the set containing two to the set containing one two and three since we can travel along edges to get from here to here I know that this set relates to this one and since we're going up the diagram I know the direction of the relation the set containing two is a subset of this set containing one two and three of course it shouldn't be surprising that the set containing one two and three is at the very top of the hassa diagram because every element in our partially ordered set relates to the set containing one two and three so it's got to be all the way at the top since I've ordered the element from bottom to top and then at the very bottom is the empty set because nothing relates to the empty set since nothing is a subset of the empty set aside of course from itself all right let's go on to one more example where we'll also Define minimal maximal minimum and maximum elements okay so we're going to let a be the set containing just a handful of positive integers and R is going to be the divides relation on a so R contains all ordered pairs X Y where X and Y are both from a and X divides y then this set a along with our divides relation R forms a posset division is reflexive since every number divides itself it's also anti-symmetric because if x divides Y and Y divides X well the only time that happens is when x equals Y and certainly division is also transitive if x goes into Y and Y goes into Z then X would also have to go into Z so the divides relation on our set a certainly forms a post set I'll leave it to you to verify those rules more formally here is the hassa diagram for the pose set again this diagram is ordered from bottom to top so we can go up from two to four that means that 2 divides 4. notice how I can travel across edges to get from 2 to 24 which tells me that 2 divides 24. again every element divides itself so we don't really need to draw those arrows in that's part of what makes a hassa diagram so elegant and notice again that the set has not been completely ordered not every pair of elements have a relation to each other there's no way to get between three and four by moving up the diagram they don't relate to each other in any way remember you've got to move up the diagram because that's the direction the relation takes in this diagram from bottom to top 7 and 35 they don't relate to any of the numbers over here which is interesting this hassa diagram has two disconnected components and this leads to a few quick definitions we say in element Y in a partially ordered set a is maximal if y relates to no element except itself so if y relates to U then Y Must equal u in our hassa diagram we can find the maximal elements at the tops of the components 24 is a maximal element it doesn't relate to anything except itself so it's all the way at the top of its component similarly 35 is a maximal element it doesn't relate to anything except itself notice of course maximal elements are not unique the definition of minimal element is similar we would say in element X is minimal if the only thing that relates to X is X itself so if U relates to x x must equal U these of course can be found at the bottoms of the components two is a minimal element because nothing relates to two except for itself in this set similarly three is a minimal element nothing relates to three here except for itself and seven of course is also minimal there are then the similar but certainly different ideas of a maximum element and a minimum element we would say that an element in a partially ordered set is a maximum if every single element relates to it 24 is not a maximum element because not every single element relates to it every element in its component relates to it but 35 and 7 both fail to relate to 24. so even though 24 is maximal same goes for 35 neither of them are maximum and similarly we would say that in element Little M is the minimum of a partially ordered set if it relates to everything else again there's no minimums here two does not relate to everything since it doesn't relate to 3 7 or 35 and 3 doesn't relate to everything since it doesn't relate to 4 2 8 7 or 35 so there are no minimums here this is in contrast to our first example in our first example the empty set was a minimal element it's at the bottom of its component but it is also minimum it relates to every single element in the partially ordered set the original set s the one containing one two and three is also maximum it's at the top of its component and its maximum everything relates to this set this set is the maximum of the partially ordered set it belongs to if there is a minimum or if there is a maximum those will be unique in a partially ordered set which is a straightforward proof I'll leave to you let me know if you want any help in the comments but that's it for this intro to partially ordered sets and hassa diagrams hope it was helpful here's just a quick review we say that a relation r on a set a is a partial order if it's reflexive anti-symmetric and transitive then the set a along with that partial order makes a partially ordered set we call it a partial order because it's not necessary that every pair of elements in a post set are put in any particular order you could have some elements like we said this one and this one that just do not relate to each other in any way a hassa diagram is a way of representing a partially ordered set that uses the features of a post set to cut back on the Clutter of the diagram in a haasa diagram there are no arrows representing the reflexive relationships between an element and itself because we know they exist same thing with transitive relations there are no arrows representing the transitive relations and in fact we don't need arrows explicitly to indicate Direction because Hossa diagrams are created in such a way that if they had arrows all of the arrows would be pointing the same direction the hosta diagrams I've shown you here have the order going from bottom to top but you could also go left to right or top to bottom let me know in the comments if you've got any questions or video requests [Music] wave it on me [Music] [Music]