Problem 1 - Applied Discrete Structures

Question

For each of the following relations \(r\) defined on \(\mathbb{P}\), determine which of the given ordered pairs belong to \(r\) (a) \(x r y\) iff \(x \mid y ;(2,3),(2,4),(2,8),(2,17)\) (b) \(x r y\) iff \(x \leq y ;(2,3),(3,2),(2,4),(5,8)\) (c) \(x r y\) iff \(y=x^{2} ;(1,1),(2,3),(2,4),(2,6)\)

Step-by-Step Solution

Answer

For (a), (2,4) and (2,8) are in \(r\). For (b), (2,3), (2,4), and (5,8) are in \(r\). For (c), (1,1) and (2,4) are in \(r\).

Step 1: Understanding Divisibility Relation

The relation \(x \, r \, y\) is defined as \(x \mid y\), which means \(x\) divides \(y\) without a remainder. We verify this for each pair.

Step 2: Checking Pair (2,3)

Since 3 divided by 2 gives a remainder, 2 does not divide 3. Hence, the pair (2,3) is not in the relation.

Step 3: Checking Pair (2,4)

Since 4 divided by 2 leaves no remainder, 2 divides 4. Thus, the pair (2,4) is in the relation.

Step 4: Checking Pair (2,8)

Since 8 divided by 2 leaves no remainder, 2 divides 8. Thus, the pair (2,8) is in the relation.

Step 5: Checking Pair (2,17)

Since 17 divided by 2 gives a remainder, 2 does not divide 17. Hence, the pair (2,17) is not in the relation.

Step 6: Understanding Inequality Relation

The relation \(x \, r \, y\) is defined as \(x \leq y\). We verify this for each pair.

Step 7: Checking Pair (2,3) under Inequality

Since 2 is less than 3, the pair (2,3) is in the relation.

Step 8: Checking Pair (3,2) under Inequality

Since 3 is not less than or equal to 2, the pair (3,2) is not in the relation.

Step 9: Checking Pair (2,4) under Inequality

Since 2 is less than 4, the pair (2,4) is in the relation.

Step 10: Checking Pair (5,8) under Inequality

Since 5 is less than 8, the pair (5,8) is in the relation.

Step 11: Understanding Squaring Relation

The relation \(x \, r \, y\) is defined as \(y = x^2\). We verify this for each pair.

Step 12: Checking Pair (1,1) for Squaring

Since \(1^2 = 1\), the pair (1,1) is in the relation.

Step 13: Checking Pair (2,3) for Squaring

Since \(2^2 = 4\) and not equal to 3, the pair (2,3) is not in the relation.

Step 14: Checking Pair (2,4) for Squaring

Since \(2^2 = 4\), the pair (2,4) is in the relation.

Step 15: Checking Pair (2,6) for Squaring

Since \(2^2 = 4\) and not equal to 6, the pair (2,6) is not in the relation.

Key Concepts

Relations

In discrete mathematics, a relation is a connection or association between two sets of numbers or objects. It is similar to a rule that tells us how two elements are related. Relations can be thought of as general rules that tell us whether two elements have a certain property. They are often expressed in the form of ordered pairs, such as

• (2, 4)
• (3, 5)

Each pair consists of elements where the first element is related to the second one by some rule. Relations can be of many types including, but not limited to, divisibility, inequality, and equations. Understanding relations helps us comprehend how numbers interact or compare with each other. This foundational concept is used in various areas of mathematics and computer science.

Ordered Pairs

Ordered pairs are a fundamental component in understanding relations. An ordered pair consists of two elements, typically denoted as ewline \((x, y)\). Here, 'x' is referred to as the first component, and 'y' is the second component. The term "ordered" is crucial because

• (x, y)
• (y, x)

are not the same. The positions of the elements matter, which means (2, 3) is different from (3, 2). In sets of ordered pairs, the relation can be described by examining each element's position and evaluating the rules governing their relationship. Ordered pairs are often used to describe points in a coordinate system, such as in algebra or geometry, where each set maps a relation between coordinates.

Divisibility

Divisibility is one of the many relations between numbers, where we determine if one number is a factor of another. If we say a number \(x\) divides \(y\), written mathematically as ewline \(x \mid y\), it means when \(y\) is divided by \(x\), the remainder is zero. For instance, if you check if \(2 \mid 4\), you'll find it is true, as \(4 \div 2 = 2\) leaves no remainder. ewline

• If there is no remainder, the division is exact, meaning x divides y.
• If there is a remainder, x does not divide y.

This concept is essential when learning about factors, multiples, and properties of numbers. Naturally, divisibility plays a key role in fields such as number theory and cryptography.

Inequalities

Inequalities are another form of relation where we compare elements to show that one number is lesser or greater than the other. The expression ewline \(x \leq y\) signifies that \(x\) is less than or equal to \(y\). The "less than or equal" operator gives a broader scope than just being "less than." With inequalities:

• \(x \leq y\) includes situations where both numbers can be equal.
• It reflects a broader range of relationships between numbers, not just a strict ordering.

This concept is vital not just in pure mathematics but also in areas like economics and statistics, where comparisons of quantities or predictions under constraints are significant.