Orderings & Lattices · step 6 of 13

Chains, antichains & comparability

A chain is a subset in which every two elements are comparable — a totally ordered piece of the poset. An antichain is the opposite: no two of its elements are comparable. The length of the longest chain is the height of the poset and the size of the largest antichain is its width, and these two numbers capture most of what a poset "looks like".

Practise chains, antichains & comparability free → All Orderings & Lattices subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Find chains as upward pathsIn the Hasse diagram, a maximal chain is a path from a minimal element to a maximal one. Count vertices, not edges, for the chain size.
Find antichains as level setsElements at the same height are often pairwise incomparable, so the widest level is a good first candidate for the largest antichain.
Verify pairwise incomparabilityEvery pair in a proposed antichain needs checking — a single comparable pair disqualifies it.
Use the covering boundA poset covered by k chains has no antichain larger than k, since two elements of one chain are comparable. This bounds the width from above.

Worked example

For the divisors of 12 under divisibility, find the height and the width.

Chains: 1 ∣ 2 ∣ 4 ∣ 12 has four elements; so does 1 ∣ 2 ∣ 6 ∣ 12.
No chain has five elements, since 12 = 2²·3 has only three prime factors with multiplicity.
Antichains: {4, 6} are incomparable; so are {2, 3}. Try {4, 6, 3}: but 3 ∣ 6, so it fails.
The largest antichain has two elements.

Answer. Height 4 (e.g. 1, 2, 4, 12) and width 2 (e.g. {4, 6}).

Where marks get dropped

These are the specific errors that cost credit on chains, antichains & comparability questions — QED's rubric penalises each of them separately.

Counting edges instead of elements when giving chain length. Conventions differ, so state which you are using.
Assuming any set of same-height elements is an antichain. It usually is, but verify comparability directly.
Confusing a maximal chain (cannot be extended) with a maximum chain (longest overall). A maximal chain can be short.

Practise this until it is automatic

Unlimited fresh questions

QED generates new chains, antichains & comparability problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Orderings & Lattices mastery is tracked so you know when this is exam-ready.

Chains, antichains & comparability — frequently asked questions

What is Mirsky’s theorem?

A poset of height h can be partitioned into exactly h antichains, by grouping elements according to the length of the longest chain ending at them. It is the dual of Dilworth’s theorem.

Why do chains and antichains matter?

They measure the two ways a poset departs from being a set: height measures how ordered it is, width how parallel. In scheduling, height is the makespan and width is the number of machines needed.

Is a single element a chain and an antichain?

Yes, both, vacuously — there are no pairs to check. So is the empty set.

The rest of Orderings & Lattices

Partial orders, Hasse diagrams, bounds, lattices. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make chains, antichains & comparability exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →