Order relations
A reflexive, antisymmetric and transitive relation: total or partial order, Hasse diagram, maximal elements and maximum, upper bounds, least upper bound, and the usual orders (≤, divisibility, inclusion, lexicographic).
- 32 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Order relation: what is it?
Show the answer
A relation that is reflexive, antisymmetric and transitive at once: it arranges elements from smallest to largest, without requiring every pair to be comparable.
≤ on ℤ, divisibility on ℕ* and inclusion on subsets of a set are orders. < is not one in the broad sense: it is not reflexive.
Divisibility on {2, 3, 4, 6, 12}: does this set have a least element?
- No: 2 and 3 are minimal but incomparable
- Yes, it is 2, because it divides the most elements
- Yes, it is 12, which every other element divides
- No: no element is minimal
Show the answer
No: 2 and 3 are minimal but incomparable
A least element would divide every element. 2 does not divide 3, 3 does not divide 2: both are minimal, neither is least. 12 is the greatest element, not the least.
In the … order, two words are compared letter by letter; a word that is the beginning of the other comes ….
Show the answer
In the lexicographic order, two words are compared letter by letter; a word that is the beginning of the other comes first.
“10” comes before “100”, and “100” before “21”: the comparison stops at the first position where the characters differ. This is why sorting strings puts “9” after “21”.
Total order: what is it?
Show the answer
An order where any two elements are always comparable: for x and y, either x ≤ y or y ≤ x.
The elements line up on a single chain, like ≤ on the integers. Sorting an array assumes a total order on its elements.