Question

R is a relation from A to B.
S is a relation from B to C.
If Ran(R) ∈ Dom(S), prove Dom(S o R) = Dom(R)

Answer 1

so basically, i need to prove Dom(S o R) ⊆ Dom(R), which I did. Now i'm having a bit difficulty proving Dom(R) ⊆ Dom(S o R)

Answer 2

ahh typo...
i meant to say
"If Ran(R) ⊆ Dom(S), prove Dom(S o R) = Dom(R) "

Answer 3

here is what i did so far to prove Dom(R) ⊆ Dom(S o R).

let x ∈ Dom(R), then by definition, x ∈ A and ∃b∈B such that (x,b)∈R

Answer 4

since b∈Ran(R) and given that Ran(R) ⊆ Dom(S), then b∈Dom(S)

Answer 5

and by definition, ∃c∈C such that (b,c) ∈ S. I'm stuck here

Answer 6

Isn't \(\text{Dom}(S\circ R)\subseteq \text{Dom}(S)\subseteq B\)?

Answer 7

no, Dom(S o R) contains those elements in A, while Dom(S) contains those elements in B. So the two sets are different.

Answer 8

I was thinking, since ∃b∈B ∃c∈C such that (x,b) ∈ R and (b,c) ∈ S, then x ∈ Dom(S o R) by definition.

Answer 9

\[
\forall a,b\quad (a,b)\in R \quad b\in \text{Range}(R)\implies b \in \text{Domain}(S) \implies \exists b, c \quad (b,c) \in S \\
\implies (a,c) \in (S\circ R)
\]

Answer 10

Maybe change it to \(\forall b\;\exists a\)

Answer 11

Definition of range:\[
\forall b \in \text{Range}(R) \implies \exists a\quad (a,b)\in R
\]From \(\text{Range}(R)\subseteq \text{Domain}(S)\) we get:\[
b \in \text{Range}(R) \implies b\in \text{Domain}(S)
\]Definition for domain: \[
b\in \text{Domain}(S) \implies \exists c\quad (b, c)\in S
\]Combining the first and third implications, and using definition of composition:\[
\exists a,c\quad (a,b)\in R\land (b,c)\in S \implies (a,c) \in (S\circ R)
\]

Answer 12

To finish it, you need to use \(\forall a\)

Answer 13

Yes, x was arbitrary (which is equivalent to ∀a), x∈Dom(S o R)

Answer 14

I guess you would say \[
\forall a \in \text{Domain}(R) \implies \exists b\in \text{Range}(R)
\]Subset gives\[
b\in \text{Range}(R) \implies b \in \text{Domain}(S)
\]Then we say \[
b \in \text{Domain}(S) \implies \exists c \quad (b,c) \in S
\]

Answer 15

which implies (a,c) ⊆ SoR, which implies a ∈ Dom(S o R). Got it :)

Answer 16

\[
\forall a \exists b,c \quad (a,b) \in R \quad \land \quad (b,c) \in S \implies (a,c)\in (S\circ R) \implies a \in \text{Domain}(S\circ R)
\]

Answer 17

thank you for your replies ^.^b