Clarification on a Theorem on Relations(very basic and trival)

58 Views Asked by At

Suppose $R$ is a relation on a set $A$, that is, $R$ is a relation from a set $A$ to itself. Then $R◦R$, the composition of $R$ with itself, is always defined.

The Above is from "Schaum's Theory and Problems of Discrete Mathematics"

Consider the set $A= \{1,2\}$ $$R = \{(1,2)\}$$

How is $R◦R$ defined?

It seems to contradict this statement from the same book:

Let $A$, $B$ and $C$ be sets, and let $R$ be a relation from $A$ to $B$ and let $S$ be a relation from $B$ to $C$. That is, $R$ is a subset of $A×B$ and $S$ is a subset of $B ×C$. Then $R$ and $S$ give rise to a relation from $A$ to $C$ denoted by $R◦S$ and defined by: $a(R◦S)c$ if for some $b ∈ B$ we have $aRb$ and bSc. That is , $$R◦S =\{(a,c)|\exists b \in B : (a,b) \in R \& (b,c) ∈ S\} $$

2

There are 2 best solutions below

0
On

$R\circ R$ is, in this case, $\varnothing$. The case of $R\circ R$ is just the special case of the second quoted piece of text where $A=B=C=\{1,2\}$ and $R=S=\{(1,2)\}$. Notice that it is true that every ordered pair that is a member of $\varnothing$ is an ordered pair from $A\times A$, vacuously.

You can check that the definition of $R\circ S$ specializes in this case to $\{(a,c)|\exists b\in A:(a,b)\in R\wedge (b,c)\in R\}$. How many pairs are there in $A\times A$ that meet this condition?

2
On

DISCLAIMER
This is an ad hoc explanation that conveys my understanding(and misuderstandings) of this theorem. I wrote this due to @GerryMyerson 's suggestion to that effect.

By the definition of the composition of two relations $R$ $\&$ $S$ defined on $A \rightarrow B$ and $B \rightarrow C$ respectively $A, B, C$ being non-empty, we have; $R \circ S$ defined as : $$(a,c)| \exists b \in B: (a,b) \in R \& (b,c) \in S$$

Now the empty set $\phi \subset D$ where $D$ is any set.

The definition of a relation is a subset of the product set.

It is vacuously true, that the empty relation is a subset of the product set of any set $A$. The 'counter example' in the question is merely a case of $R \circ R$ being the empty relation. Thus $R \circ R$ is always defined.

$$R \circ R = (NULL, c), \exists b \in A: (NULL, b) \in R \& (b, c) \in R)$$

In this case, $b$ is $1$ and $c$ is $2$.

I'm 'guessing' $(NULL, e) \& (e, NULL)$ is considered $\phi$ but $(NULL, NULL)$ is not. $e$ representing any element of a set$.\tag{*}$

In particular, any for any two relations their composition is defined if the domain of the first is the codomain of the second. This means a scenario in which the first equation as the same domain and range, i.e it is a relation on a set.

We get: $$R \circ S = (a,c)| \exists b \in A: (a,b) \in R \& (b,c) \in S$$

The empty relation is considered a relation, so given that of the sets $A, B, C; A = B$ $A, B, C$ being non-empty.

We'll at least have $$ R \circ S = (NULL, c), \exists b \in A: (NULL, b) \in R \& (b, c) \in S$$

OR $$ R \circ S = (a, NULL), \exists b \in A: (a, b) \in R \& (b, NULL) \in S$$

The symbol $NULL$ denoting the element of the empty set? Or an empty element. Anyway, it's an Adhoc symbol I made to convey my understanding of this theorem.

$(*)$ The reason why I said I guess $(NULL,NULL)$ is not considered $\phi$ was because if it was then the composition of all relations would be defined.

EDIT
I rethought my explanation, and found out that it doesn't resolve my fundamental dissonance:

If the composition of two relations is considered defined when $R\circ R = \phi$, then doesn't that mean that the composition of all relations is defined?

I was told, that it's only when the domain of the first is the codomain of the second. I guess that's true, but don't understand why that's true. Even my adhoc model fails to explain it.

A counter example:

Consider the sets $A, B, C$
$ A = \{1\}, B = \{2,3\} $ $\& C = \{9\}$
$R: A \rightarrow B, S: B \rightarrow C $ $R =\{(1,2)\}, S = \{(3,9)\}$

$ \exists 2 \in B: (1,2) \in R$ $ \& (2,NULL) [\phi] \in S$

$$\therefore R\circ S = \{(1,NULL)\} || \{(NULL, 3)\}$$

Thus my ad hoc model fails, but it was only a model meant to try to.convey my understanding of the answer that the empty relation is considered as definitive of the composition of two relations. I still can't understand how that answer doesn't imply that any two relations are defined.