Analyzing a Divisibility Relation

Discrete Math · Axiom Academy

EXAMPLE Analyzing a Divisibility Relation Build the "divides" relation and discover how it forms a partial order on a finite set. Every element divides itself: (1,1), (2,2), (3,3), (4,4), (6,6), (12,12) are all in R. In the matrix: all diagonal entries are 1 If a | b and b | a, then a = b. Check: If 2 | 4, then 4 ∤ 2 (4 does not divide 2). The only time both (a,b) and (b,a) are in R is when a = b. In the matrix: symmetric entries are never both 1 (except on diagonal) If a | b and b | c, then a | c. Example: 2 | 4 and 4 | 12, so 2 | 12 ✓ Check another: 1 | 3 and 3 | 12, so 1 | 12 ✓ This holds for all cases in our relation Excellent work! You've successfully analyzed the divisibility relation and verified it forms a partial order. Here's what we learned: Building Relations: The divides relation on 1,2,3,4,6,12 contains 18 ordered pairs, found by systematically checking which elements divide which others. Matrix Representation: We can represent relations as matrices where entry (i,j) is 1 if the relation holds between elements i and j, and 0 otherwise. Reflexive Property: Every element divides itself (all diagonal entries are 1). This is essential for partial orders. Antisymmetric Property: If a divides b and b divides a, then a must equal b. In the matrix, symmetric pairs are never both 1 except on the diagonal. Transitive Property: If a divides b and b divides c, then a must divide c. Divisibility naturally preserves this chain relationship.

This is the written version of the interactive lesson above. See the full Discrete Math course.