Problem 1 - Applied Discrete Structures

Question

(a) Let \(B=\\{a, b\\}\) and \(U=\mathcal{P}(B)\). Draw a Hasse diagram for \(\subseteq\) on \(U\). (b) Let \(A=\\{1,2,3,6\\} .\) Show that divides, \(\mid,\) is a partial ordering on \(A\). (c) Draw a Hasse diagram for divides on \(A\). (d) Compare the graphs of parts a and \(\mathrm{c}\).

Step-by-Step Solution

Answer

Both diagrams have similar hierarchical structures, but represent different concepts: set inclusion and divisibility.

Step 1: Identify Subsets for Hasse Diagram of Part (a)

First, determine the subsets of set \( B = \{a, b\} \). The subsets of \( B \) (also known as the power set \( U = \mathcal{P}(B) \)) are: \( \emptyset, \{a\}, \{b\}, \{a, b\} \).

Step 2: Determine Relation \( \subseteq \) for Part (a)

The relation \( \subseteq \) on \( U \) organizes the subsets in a hierarchical order based on set inclusion: \( \emptyset \subseteq \{a\}, \{b\} \subseteq \{a, b\} \).

Step 3: Draw Hasse Diagram for Part (a)

Construct the Hasse diagram by placing \( \emptyset \) at the bottom, connecting it upward to \( \{a\} \) and \( \{b\} \), which in turn connect to \( \{a, b\} \) at the top. Remove transitive edges.

Step 4: Check Partial Order Conditions for Part (b)

The relation 'divides' \( | \) on \( A = \{1, 2, 3, 6\} \) is a partial order. Verify reflexivity \((a|a)\), antisymmetry \((a|b \text{ and } b|a \Rightarrow a=b)\), and transitivity \((a|b \text{ and } b|c \Rightarrow a|c)\).

Step 5: Identify Divisibility Pairs for Hasse Diagram of Part (c)

List pairs \( (a, b) \) in \( A \) where \( a \mid b \). For \( A = \{1, 2, 3, 6\} \), 1 divides all, 2 and 3 divide 6, and each element divides itself.

Step 6: Draw Hasse Diagram for Part (c)

Start with 1 at the bottom, connecting to 2 and 3 separately. Both 2 and 3 connect to the topmost node 6. Remove transitive connections (e.g., direct connection from 1 to 6 is implicit).

Step 7: Compare Diagrams for Part (d)

Both diagrams are similar in structure, having a single minimum and maximum element with connecting intermediate nodes. However, the content represented by each node differs; one represents set inclusion, while the other shows divisibility.

Key Concepts

Partial Ordering

Partial ordering is a way to compare elements from a set with a relation that satisfies three key properties:

• Reflexivity: Every element relates to itself, meaning for any element \(a\), \(a\) is related to \(a\) (\(a \leq a\) in this case).
• Antisymmetry: If two elements are mutually related and distinct, they should be identical. In other words, if \(a \leq b\) and \(b \leq a\), then \(a = b\).
• Transitivity: If an element \(a\) is related to another element \(b\), and \(b\) is related to another element \(c\), then \(a\) should also relate to \(c\) (\(a \leq c\)).

Partial ordering is crucial in ensuring a manageable hierarchy among the elements of a set, where not every pair of elements needs to be comparable. It was applied in the divisibility relation \(|\) on the set \(A = \{1, 2, 3, 6\}\), confirming it as a partial order.

Power Set

To understand the concept of a power set, think about all possible subsets you can form from a given set. For a set \(B = \{a, b\}\), its power set, denoted \(\mathcal{P}(B)\), includes these subsets:

• The empty set \(\emptyset\)
• \(\{a\}\)
• \(\{b\}\)
• \(\{a, b\}\)

Each element of the power set is a subset of \(B\), and together they cover all potential combinations. When you create a Hasse Diagram using the power set, you illustrate how each of these subsets includes or is included in the others, providing a visual representation of set inclusion.

Set Inclusion

Set inclusion is a fundamental concept in set theory that describes when one set is a part of another. It is symbolized by \(\subseteq\). If set \(A\) includes all elements of set \(B\), we say \(B \subseteq A\).
In our example, the power set \(\mathcal{P}(B)\) of \(B = \{a, b\}\) forms a basis for understanding set inclusion by mapping out all ways subsets are contained within a larger set. This concept was clearly illustrated in Part (a) when determining relations like \(\emptyset \subseteq \{a\}\) and how it is utilized in constructing a Hasse diagram to show hierarchical relations.

Divisibility

Divisibility is a relational concept used to determine how one number can be divided by another without a remainder. In mathematical terms, for two integers \(a\) and \(b\), \(a\) divides \(b\) (represented by \(a \mid b\)) if there exists an integer \(k\) such that \(b = a \times k\).
When used as a relation, divisibility can exhibit partial ordering. Consider the set \(A = \{1, 2, 3, 6\}\). We analyze pairs such as \((1,2)\), \((1,3)\), and \((2,6)\), finding that 1 divides all elements, while 2 and 3 divide 6.
In practice, Hasse Diagrams help visualize these relationships by positioning 1 at the bottom (because it divides every number), with connections from 2 and 3 leading up to 6, illustrating how divisibility structures this set.