Discrete Math Quiz: Partial Orders And Hasse Diagrams

12 questions · exam conditions

0:00

Partial Orders And Hasse DiagramsQuestion 1 of 12

Consider two finite posets $P_1$ and $P_2$ . If $P_1$ has height 3 and width 4, while $P_2$ has height 4 and width 3, what can be concluded about the height and width of their ordinal sum $P_1 ⊕ P_2$ ?

Height 7 and width 4, combining the maximum dimensions appropriately

Height 6 and width 7, reflecting the sum of both dimensions

Height 7 and width 7, taking the sum of heights and maximum width

Height 6 and width 4, using standard ordinal sum dimension rules

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Partial Orders And Hasse Diagrams

Practice Partial Orders And Hasse Diagrams in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Partial Orders And Hasse Diagrams, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

Height 7 and width 4, combining the maximum dimensions appropriately (correct answer)
Height 6 and width 7, reflecting the sum of both dimensions
Height 7 and width 7, taking the sum of heights and maximum width
Height 6 and width 4, using standard ordinal sum dimension rules

Explanation: In an ordinal sum P₁ ⊕ P₂, every element of P₁ is made less than every element of P₂. The height (maximum chain length) becomes height(P₁) + height(P₂) = 3 + 4 = 7, since we can extend any maximum chain in P₁ with any maximum chain in P₂. The width (maximum antichain size) is max(width(P₁), width(P₂)) = max(4, 3) = 4, because elements from P₁ and P₂ are never incomparable in the ordinal sum. Choice B incorrectly adds widths and subtracts from height. Choice C incorrectly adds widths. Choice D incorrectly computes the height.

Question 2

A poset has the property that every chain (totally ordered subset) has at most 4 elements, and every antichain (set of mutually incomparable elements) has at most 3 elements. What is the maximum possible number of elements in this poset?

7
9
12 (correct answer)
The maximum cannot be determined from the given constraints alone

Explanation: By Dilworth's theorem, if the maximum antichain size is 3, then the poset can be partitioned into at most 3 chains. Since each chain has at most 4 elements, the maximum total number of elements is 3 × 4 = 12. This maximum is achievable by taking 3 disjoint chains of length 4 each. Choice A (7) is too small and doesn't use the constraints optimally. Choice B (9) represents 3 chains of length 3, which doesn't maximize the chain lengths. Choice D is incorrect because Dilworth's theorem provides exactly the information needed to determine the maximum.

Question 3

Consider the relation $R$ on the set $\{a, b, c, d, e\}$ defined by the following pairs: $\{(a,a), (b,b), (c,c), (d,d), (e,e), (a,c), (c,e), (a,e), (b,d)\}$ . If we construct the Hasse diagram for this relation, how many edges will it contain?

4 (correct answer)
5
7
9

Explanation: First, verify that R is a partial order (reflexive, antisymmetric, transitive). The relation is reflexive (all identity pairs present), antisymmetric (no reverse pairs except identities), and transitive (since (a,c) and (c,e) are present, (a,e) must be present, which it is). In a Hasse diagram, we only show covering relations (immediate predecessors/successors) and omit reflexive pairs and transitive consequences. The transitive pair (a,e) is removed since a→c→e exists. The covering relations are: (a,c), (c,e), (b,d), plus one isolated element, giving us 4 edges total. Choice B counts an extra non-existent covering relation. Choice C includes some transitive edges. Choice D counts all non-reflexive pairs.

Question 4

Let $P$ be a finite poset where every element covers exactly two elements (except minimal elements which cover none). If $P$ has exactly 4 minimal elements and 1 maximal element, how many elements are at the second level from the bottom?

Cannot be determined from the given information
3
4
2 (correct answer)

Explanation: When you encounter a poset (partially ordered set) problem with covering relationships, you need to think systematically about how elements connect between levels. The key insight is that "covers" means there's a direct connection between adjacent levels with no intermediate elements. Let's work through this step by step. You have 4 minimal elements at the bottom level. Since every non-minimal element covers exactly two elements, each element at the second level must cover exactly 2 elements from the bottom level. Since the poset has exactly 1 maximal element at the top, all paths must eventually converge. The most efficient way for 4 minimal elements to connect upward (where each upper element covers exactly 2 lower elements) is to have 2 elements at the second level, with each covering 2 of the minimal elements. This creates the structure: 4 minimal elements → 2 second-level elements → 1 maximal element, where each second-level element covers exactly 2 minimal elements. Choice A is incorrect because the covering constraint and element counts provide enough information to determine the structure uniquely. Choice B (3 elements) is wrong because you can't efficiently pair 4 minimal elements with 3 second-level elements while maintaining the "covers exactly 2" rule. Choice C (4 elements) would mean each second-level element covers only 1 minimal element, violating the constraint that non-minimal elements must cover exactly 2. The correct answer is D. Remember: In poset problems, draw the structure! Visualizing the levels and connections helps you see the constraints and count elements accurately.

Question 5

Let $L$ be a lattice with elements $\{a, b, c, d, e\}$ where $a$ is the bottom element and $e$ is the top element. If $b \vee c = e$ and $b \wedge c = a$ , and both $b$ and $c$ cover $a$ , what must be true about element $d$ ?

Element $d$ must be comparable to both $b$ and $c$ under the lattice ordering
Element $d$ must equal either $b \vee d = e$ or $c \vee d = e$ but not both conditions
Element $d$ must satisfy $d \wedge b = a$ and $d \wedge c = a$ with $d$ covering $a$ (correct answer)
Element $d$ must be the unique complement of some element in the lattice structure

Explanation: Given that b∨c = e, b∧c = a, and both b,c cover a, we have b and c as complementary elements in a 5-element lattice with this structure. Since there are exactly 5 elements and we've accounted for a (bottom), e (top), b, and c (complementary atoms), the fifth element d must also be an atom (covering a) that's incomparable to both b and c, making b∧d = a and c∧d = a. Choice A is wrong because d must be incomparable to b,c. Choice B incorrectly assumes d joins with b or c to make e. Choice D is incorrect because in this lattice structure, d cannot be anyone's unique complement.

Question 6

Consider a poset $P$ where the width (size of maximum antichain) equals the height (length of maximum chain). If $P$ has width 4, and we know that $P$ can be partitioned into exactly 4 chains, what is the minimum number of elements $P$ must contain?

8
12
16 (correct answer)
The minimum cannot be determined from these constraints

Explanation: Given width = height = 4, the maximum chain has length 4 and maximum antichain has size 4. Since P can be partitioned into exactly 4 chains (which equals the width, consistent with Dilworth's theorem), and the height is 4, each chain must have exactly 4 elements to achieve the maximum chain length. If any chain had fewer than 4 elements, the height would be less than 4. Therefore, P must contain exactly 4 × 4 = 16 elements. Choice A (8) would give average chain length 2, contradicting height = 4. Choice B (12) would give average chain length 3, still too small. Choice D is incorrect because the constraints uniquely determine the minimum size.

Question 7

Consider a poset on $\{a, b, c, d, e, f\}$ where $a$ is the unique minimal element, $f$ is the unique maximal element, $b$ and $c$ are incomparable elements with $a < b, c < f$ , and $d$ and $e$ are incomparable elements with $a < d, e < f$ . If we want to extend this to a lattice by adding the minimum number of elements, how many elements must be added?

2 elements must be added to create proper joins and meets
1 element must be added to serve as a join point for cross-pairs (correct answer)
3 elements must be added to handle all incomparable pairs
0 elements need to be added as it already forms a lattice

Explanation: In the given poset, pairs like (b,d), (b,e), (c,d), and (c,e) each have f as an upper bound but lack a unique least upper bound, which is required for a lattice. Adding one element g where b,c,d,e < g < f creates the necessary least upper bounds: b∨d = b∨e = c∨d = c∨e = g. All other pairs already have proper meets and joins. Choice A overestimates the requirement. Choice C suggests too many elements. Choice D incorrectly assumes the poset is already a lattice.

Question 8

Consider the divisibility poset on $\{1, 2, 3, 4, 6, 8, 12, 24\}$ . If we remove the element 12 from this poset, which property is lost?

The resulting structure is no longer a partially ordered set due to transitivity violations
Elements 4 and 6 no longer have a least upper bound in the remaining poset (correct answer)
Element 24 is no longer the unique maximum element of the remaining poset
Elements 2 and 3 no longer have a greatest lower bound in the remaining poset

Explanation: In the original poset, LCM(4,6) = 12, so 4∨6 = 12. After removing 12, the upper bounds of 4 and 6 in the remaining set are only {24}, but 24 is not the least upper bound since 12 < 24 and 12 was the actual LUB. Without 12, elements 4 and 6 have upper bound 24 but no least upper bound within the remaining poset. Choice A is wrong because removing an element cannot violate transitivity. Choice C is incorrect because 24 remains the maximum. Choice D is wrong because GCD(2,3) = 1, and 1 remains in the poset.

Question 9

In the Boolean lattice $B_3$ (the power set of a 3-element set ordered by inclusion), how many elements have exactly two complements?

0 (correct answer)
2
4
6

Explanation: In any Boolean lattice, every element has exactly one complement. B₃ consists of all subsets of {1,2,3}: {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. Each subset S has complement S̄ where S ∪ S̄ = {1,2,3} and S ∩ S̄ = ∅. For example, {1,2} has unique complement {3}. The uniqueness of complements is a defining property of Boolean lattices. Choices B, C, and D incorrectly assume multiple complements can exist, which would violate the Boolean lattice structure where each element has exactly one complement.

Question 10

Consider the poset $(S, \leq)$ where $S = \{\{1\}, \{2\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$ ordered by set inclusion. Which statement about maximal and maximum elements is correct?

There is exactly one maximal element but no maximum element exists in the poset
There are exactly two maximal elements and no maximum element exists in the poset
There are exactly three maximal elements and no maximum element exists in the poset
There is exactly one maximal element and it is also the maximum element of the poset (correct answer)

Explanation: When analyzing posets for maximal and maximum elements, you need to understand the distinction: a maximal element has no elements above it, while a maximum element is comparable to (and greater than or equal to) every element in the poset. In this poset ordered by set inclusion (

\subseteq

), let's examine which elements are "on top." An element is maximal if no other element properly contains it. Looking at

S

, the largest set is

\{1,2,3\}

, which contains all other sets as subsets. Since no set in

S

properly contains

\{1,2,3\}

, it's maximal. More importantly,

\{1,2,3\}

is comparable to every element in

S

because every set in the collection is a subset of

\{1,2,3\}

. This makes it not just maximal, but the unique maximum element of the poset. Choice A is incorrect because while there is one maximal element, a maximum element does exist. Choice B fails because there aren't two maximal elements - sets like

\{1,2\}

and

\{1,3\}

are contained in

\{1,2,3\}

, so they're not maximal. Choice C is wrong for the same reason - elements that are properly contained in another element cannot be maximal. Choice D correctly identifies that

\{1,2,3\}

is the sole maximal element and is also the maximum element since it's comparable to every other element in the poset. Study tip: In inclusion-ordered posets, look for the "largest" set first - it's often both maximal and maximum. Maximum elements are rarer than maximal ones because they require universal comparability.

Question 11

Let $P = \{1, 2, 3, 6, 12, 24\}$ be ordered by divisibility. In the lattice formed by this poset, what is the join (least upper bound) of the elements 2 and 3?

5
6 (correct answer)
12
24

Explanation: Under divisibility ordering, the join of two elements is their least common multiple (LCM). We need to find LCM(2,3) = 6, and verify that 6 is in our poset P and is indeed the smallest element that both 2 and 3 divide into. Since 2|6 and 3|6, and 6 is the smallest such element in P, the join is 6. Choice A (5) is not even in the poset. Choice C (12) is an upper bound but not the least upper bound since 6 < 12 and both 2 and 3 divide 6. Choice D (24) is also an upper bound but much larger than necessary.

Question 12

In the poset of divisors of 210 ordered by divisibility, consider the sublattice generated by $\{6, 10, 14\}$ . How many elements are in this sublattice?

7 elements including all necessary joins and meets (correct answer)
5 elements including the generators and basic operations
9 elements when considering all combinations
6 elements from pairwise operations only

Explanation: Since 210 = 2×3×5×7, we have 6 = 2×3, 10 = 2×5, 14 = 2×7. The sublattice generated by {6, 10, 14} must include all meets and joins. We get: gcd(6,10) = gcd(6,14) = gcd(10,14) = gcd(6,10,14) = 2, lcm(6,10) = 30, lcm(6,14) = 42, lcm(10,14) = 70, lcm(6,10,14) = 210. The complete sublattice is {2, 6, 10, 14, 30, 42, 210} giving 7 elements total.