Problem 6

Question

Let $r_{1}, r_{2},$ and $r_{3}$ be relations on any set $A .$ Prove that if $r_{1} \subseteq r_{2}$ then $r_{1} r_{3} \subseteq r_{2} r_{3}$

Step-by-Step Solution

Verified

Answer

If $r_1 \subseteq r_2$, then compositions satisfy $r_1r_3 \subseteq r_2r_3$.

1Step 1: Understanding the Relations and Composition

We are given that $r_1 \subseteq r_2$, indicating that every pair in relation $r_1$ is also in $r_2$. We need to prove that $r_1r_3 \subseteq r_2r_3$, meaning any pair resulting from the composition of $r_1$ and $r_3$ is also in the composition of $r_2$ and $r_3$.

2Step 2: Defining Relation Composition

The composition of two relations $r_i$ and $r_j$, denoted $r_ir_j$, consists of all pairs $(a, b)$ such that there exists an intermediate element $c$ for which $(a, c) \in r_i$ and $(c, b) \in r_j$. Our task is to confirm this definition holds for $r_1r_3 \subseteq r_2r_3$.

3Step 3: Proving the Subset Relation in Composition

To prove $r_1r_3 \subseteq r_2r_3$, assume $(x, y)$ is an element in $r_1r_3$. This implies there exists an element $z$ such that $(x, z) \in r_1$ and $(z, y) \in r_3$. Since $r_1 \subseteq r_2$, $(x, z) \in r_2$ must also be true. Therefore, the pair $(x, y)$ will also be in $r_2r_3$ because $(x, z) \in r_2$ and $(z, y) \in r_3$.

4Step 4: Concluding the Proof

Since any pair $(x, y)$ that can be formed in $r_1r_3$ can also be formed in $r_2r_3$ due to $(x, z) \in r_2$ for the same $z$, we conclude that $r_1r_3 \subseteq r_2r_3$, completing the proof.

Key Concepts

Relation CompositionSubset RelationProof in Discrete Mathematics

Relation Composition

In discrete mathematics, relation composition is an operation that combines two relations to form a new one. Consider two relations, $ r_i $ and $ r_j $, defined on a set $ A $. The composition of these relations, denoted as $ r_i r_j $, results in a set of ordered pairs $(a, b)$. This occurs if there is an intermediate element $ c $ where both $(a, c) \in r_i$ and $(c, b) \in r_j$ hold true. With composition, the connection is made through this intermediary element, allowing us to navigate from $ a $ to $ b $ via $ c $.

Key traits of relation composition:

It's associative, meaning $(r_1r_2)r_3 = r_1(r_2r_3)$.
This operation is not generally commutative, i.e., $ r_ir_j eq r_jr_i $.

Understanding this concept allows us to see how relations can chain together to express complex connections within a set.

Subset Relation

The subset relation is a foundational concept in set theory, which also applies within the context of relations. If $ r_1 \subseteq r_2 $, it signifies that every ordered pair in $ r_1 $ is also found in $ r_2 $. This establishes a containment hierarchy between the two relations. It's crucial to understand this to follow how properties of smaller relations extend to larger ones.

When we talk about subset relations in the realm of composition, like $ r_1r_3 \subseteq r_2r_3 $, it shows that all connections possible through the composition of $ r_1 $ with $ r_3 $ are also possible when using $ r_2 $ instead. This is vital for proving that certain relational compositions inherit properties from their constituent relations.

Proof in Discrete Mathematics

Proofs in discrete mathematics provide a logical method of verifying claims and statements using established rules and premises. When proving that $ r_1r_3 \subseteq r_2r_3 $, we need to show methodically that any possible pair in the first composite relation holds true in the second.

The proof involves:

Assuming an element $(x, y)$ belongs to $ r_1r_3 $, meaning there exists a $ z $ such that $(x, z) \in r_1 $ and $(z, y) \in r_3 $.
Using the fact $ r_1 \subseteq r_2 $ to infer $(x, z) \in r_2$.
Conclude that $(x, y)$ must also belong to $ r_2r_3 $ because the intermediary $(x, z) \in r_2$ holds.

Such proofs hinge on understanding both the composition process and the subset relationship, showing that certain properties remain invariant across transformations and extensions of relations.

Problem 6

Problem 7

Other exercises in this chapter

Problem 6

Let $C=\\{1,2,3,4,6,8,12,24\\}$ and define $t$ on $C$ by atb if and only if $a$ and $b$ share a common divisor greater than 1. Draw a digraph for \(t\

View solution

Problem 6

What common relations on $\mathbb{Z}$ are the transitive closures of the following relations? (a) $a S b$ if and only if $a+1=b$. (b) $a R b$ if and onl

View solution

Problem 7

Equivalence Classes. Let $A=\\{0,1,2,3\\}$ and let $$ r=\\{(0,0),(1,1),(2,2),(3,3),(1,2),(2,1),(3,2),(2,3),(3,1),(1,3)\\} $$ (a) Verify that $r$ is an equiv

View solution

Problem 7

(a) Let $A$ be any set and $r$ a relation on $A,$ prove that $\left(r^{+}\right)^{+}=r^{+}$. (b) Is the transitive closure of a symmetric relation alway

View solution