Partially Ordered Sets and Lattices | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 2.5 Free with a free account

Partially Ordered Sets and Lattices

Discrete Mathematics · Chapter 2: Set Theory and FunctionsSection 2.5 · lesson 13 of 878 min · free with a free account

← Cardinality and Types of SubsetsNext lesson: Functions: Definitions and Terminology →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

When some pairs compare - and some simply don't.

  • Test a relation for reflexivity, antisymmetry, and transitivity
  • Define a partial order and draw its Hasse diagram
  • Identify chains, antichains, and total orders
  • Compute joins and meets, and recognize a lattice

Transcript

Everything said in the video, section by section (1,237 words). Read along, or search it.

Set Theory and Functions

Partially Ordered Sets and Lattices

This section studies how elements of a set can be ordered, when not every pair can be compared. We'll test relations for three key properties, and define a partial order. We'll draw orders as Hasse diagrams. And we'll meet chains, antichains, and lattices, where every pair has a least upper bound and a greatest lower bound.

The Opening Problem

Does One Role Sit Inside Another?

A cloud platform defines every access-control role by exactly the set of permissions it grants, drawn from a fixed universe such as read, write, and delete. When an auditor asks whether one role's access sits inside another's, the question is a familiar one. Is one permission set a subset of the other? Comparing roles this way produces a rich structure. Some pairs compare cleanly, with one strictly containing the other. Other pairs are incomparable. Neither contains the other. And any two roles can be combined into the smallest role covering both, or restricted to the largest role inside both. This structure is called a partially ordered set, and, with a little more machinery, a lattice. Both appear constantly in permission systems, package version resolution, and database query planning.

Definition

Relations and 3 Key Properties

A relation R on a set A is a subset of A cross A, the set of ordered pairs of elements of A. We write a R b to mean the pair a, b is in R. A relation is reflexive if a R a holds for every a. It's antisymmetric if a R b and b R a together force a to equal b. And it's transitive if a R b and b R c together force a R c.

Proof

Subset Inclusion Has All 3

Take P, the power set of read, write, and delete, with the subset relation. It satisfies all three properties, and each can be proved outright. Reflexive. Every element of a set A is trivially an element of A, so A is a subset of itself. Antisymmetric. If A is a subset of B and B is a subset of A, then by the definition of set equality, A equals B. Transitive. If A is inside B and B is inside C, take any x in A. It's in B, and so it's in C. So A is a subset of C. Not every relation has all three. On a social network, let a R b mean a is a friend of b. That's typically symmetric, not antisymmetric. a R b and b R a hold constantly for different people. And it isn't transitive, since a friend of a friend isn't guaranteed to be a friend.

Definition

Partial Orders and Posets

A relation on a set is a partial order if it's reflexive, antisymmetric, and transitive. The set together with the relation is called a partially ordered set, or poset. The less-than-or-equal symbol is used generically for any partial order, not only the numeric one. And a less than b means a is at most b, and a isn't equal to b. An element b covers a if a is less than b, and nothing sits strictly between them. A Hasse diagram draws a finite poset. It places b above a whenever a is less than b, and joins them with a line precisely when b covers a. Reflexive loops are left out, since every element relates to itself. And any relation already implied by transitivity is left out too.

Figure 2.5.1

The Hasse Diagram of the Power Set

Here's the Hasse diagram for the power set of r, w, d, ordered by inclusion. Each edge is a covering relation. The empty set is covered by each singleton. Each singleton is covered by the two pairs that contain it. And each pair is covered by r, w, d. No edge joins the empty set directly to r, w, d. That relation already follows from the edges in between. The gold path is a chain, which we'll define next. The singletons form an antichain.

Comparability

Chains, Antichains, and Total Orders

In a poset, elements a and b are comparable if a is at most b, or b is at most a. Otherwise they're incomparable. A chain is a subset in which every two elements are comparable. The empty set, r, the pair r w, and r, w, d form a chain. Each is a subset of the next. An antichain is a subset in which no two distinct elements are comparable. The three singletons are one. None is a subset of another. The three pairs form a second antichain. A poset in which every pair is comparable, so the whole poset is one chain, is called a total order. The usual ordering of the real numbers is total. Any two reals can be compared. But subset inclusion has incomparable pairs, and that's exactly what makes it partial.

Table 2.5.1

4 Relations Compared

This table checks four relations. Subset inclusion, divisibility on the positive integers, and at-most on the reals are all reflexive, antisymmetric, and transitive. So all three are partial orders. Here, a divides b means b is a whole-number multiple of a. Is a friend of fails every property, so it isn't a partial order at all. Among the three genuine partial orders, only at-most on the reals is total. Subset inclusion and divisibility each have incomparable pairs. For example, r and w. Or three and five, since neither divides the other.

Definition

Bounds, Join, Meet, and Lattices

In a poset, u is an upper bound of a and b if both a and b are at most u. And l is a lower bound if l is at most both. The join of a and b is their least upper bound. It's an upper bound that's at most every other upper bound. The meet of a and b is their greatest lower bound, defined the same way in the other direction. A poset in which every pair of elements has both a join and a meet, is called a lattice. Notice that join and meet are defined abstractly here, with no mention of union or intersection at all.

Worked Example

Join Is Union, Meet Is Intersection

For the power set, the join of two sets turns out to be exactly their union, and the meet exactly their intersection. That's worth proving, not assuming. Take A equal to r, d, and B equal to w, d. Their union, r, w, d, is an upper bound, since both are subsets of it. And it's the least one. Any set containing both A and B must contain r, w, and d, so nothing smaller works. Their intersection, d, is a lower bound, since it's inside both. And it's the greatest. Any set inside both A and B can only contain common elements, and d is the only one. That argument didn't depend on the particular sets chosen. So every pair has a join and a meet, and the power set, ordered by inclusion, is a lattice.

Takeaways

Order Without Total Comparison

To summarize. Reflexive, antisymmetric, and transitive are three independent properties, and a partial order needs all three. A partial order need not compare every pair. Incomparable pairs are exactly what make it partial, rather than total. A Hasse diagram shows only covering relations, yet it still fully determines the order. And a chain is a totally ordered subset, while an antichain has no two elements comparable. In a lattice, every pair has a join and a meet. For subset inclusion, those are exactly union and intersection. Here's something to think about. Can a relation be both symmetric and antisymmetric at the same time? Using the definitions, work out what such a relation would have to look like, and give a small example. Or explain why none can exist.

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Partially Ordered Sets and Lattices

How do you check whether a relation is a partial order?
A relation is a partial order if it is reflexive, antisymmetric, and transitive, so you test each property. Reflexive means a\,R\,a for every a. Antisymmetric means a\,R\,b and b\,R\,a force a=b. Transitive means a\,R\,b and b\,R\,c force a\,R\,c. "Is a friend of" fails, while \subseteq passes all three.
How do you draw a Hasse diagram of a poset?
To draw a Hasse diagram, place b above a whenever a<b and join them with a line only if b covers a, meaning nothing lies strictly between them. Leave out reflexive loops and any edge implied by transitivity. For the power set of \{r,w,d\}, there is no direct edge from \emptyset to \{r,w,d\}.
What is the difference between a chain, an antichain, and a total order?
A chain is a subset in which every two elements are comparable, while an antichain is a subset in which no two distinct elements are comparable. A total order is a poset that is itself one chain. In the power set of \{r,w,d\}, the three singletons form an antichain, and \emptyset, \{r\}, \{r,w\}, \{r,w,d\} form a chain.
How do you find the join and meet of two elements, and what makes a poset a lattice?
The join of a and b is their least upper bound, and the meet is their greatest lower bound. A poset is a lattice when every pair has both. In the power set ordered by \subseteq, the join is the union and the meet is the intersection. For A=\{r,d\} and B=\{w,d\}, the join is \{r,w,d\} and the meet is \{d\}.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →