Partial orders, Hasse diagrams, and lattices (intro) - Discrete Math

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?
Answer: 4 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.
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$ ?
Answer: Element $d$ must satisfy $d \wedge b = a$ and $d \wedge c = a$ with $d$ covering $a$ 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.
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?
Answer: 2 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.
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?
Answer: 16 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.
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?
Answer: 1 element must be added to serve as a join point for cross-pairs 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.
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?
Answer: 12 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.
In the Boolean lattice $B_3$ (the power set of a 3-element set ordered by inclusion), how many elements have exactly two complements?
Answer: 0 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.
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?
Answer: 7 elements including all necessary joins and meets 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.
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?
Answer: 6 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.
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$ ?
Answer: Height 7 and width 4, combining the maximum dimensions appropriately 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.
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?
Answer: Elements 4 and 6 no longer have a least upper bound in the remaining poset 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.
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?
Answer: There is exactly one maximal element and it is also the maximum element of the poset 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.

Start this quiz