Question

anyone got time?
R is a relation from A to B. S and T are relations from B to C. Prove (S o R)\(T o R) ⊆ (S\T) o R

Answer 1

nobody got time for this! Just kiddin!:)

Answer 2

\(S\setminus T \equiv S\cap T^C\)

Answer 3

so are you saying I need to expand (S o R)\(T o R) and then compare with
\[(S\cap T^C) o R \] ?

Answer 4

urg... that latex is supposed to show

Answer 5

First consider what you could do base on the algebraic properties you know. If that doesn't work you look all arbitrary elements.

Answer 6

well, here is what I have so far:

S o R = { (a,c) ∈ A x C | ∃b∈B ( (a,b)∈R and (b,c) ∈ S)}
T o R = { (a,c) ∈ A x C | ∃b∈B ( (a,b)∈R and (b,c) ∈ T)}

(S o R)\(T o R) = {(a,c) | (a,c)∈(S o r) and (a,c)∉(S o T) }

I expanded (a,c)∈(S o r) and (a,c)∉(S o T), so
∃b∈B ( (a,b)∈R and (b,c) ∈ S) and ~∃b∈B ( (a,b)∈R and (b,c) ∈ T)

then I distribute the negation sign:
∃b∈B ( (a,b)∈R and (b,c) ∈ S) and ∀b∈B ( (a,b)∉R or (b,c) ∉ T)

Answer 7

(S o R)\(T o R) = {(a,c) | (a,c)∈(S o r) and (a,c)∉(S o T) }

This doesn't make sense

Answer 8

oh typo O.O

I meant,
(S o R)\(T o R) = {(a,c) | (a,c)∈(S o R) and (a,c)∉(T o R) }

Answer 9

follow by
∃b∈B ( (a,b)∈R and (b,c) ∈ S) and ~∃b∈B ( (a,b)∈R and (b,c) ∈ T)
∃b∈B ( (a,b)∈R and (b,c) ∈ S) and ∀b∈B ( (a,b)∉R or (b,c) ∉ T)

Answer 10

the first line got cut off

Answer 11

... ~(a,b)∈T and something?

Answer 12

perhaps change from \(\exists b\) to \(\forall b\). That was a mistake

Answer 13

Actually maybe start off from
∃b∈B ( (a,b)∈R and (b,c) ∈ S) and ∀b∈B ( (a,b)∉R or (b,c) ∉ T)

Answer 14

You should define (S\T) o R

Answer 15

ok, that's where I got stuck. I was thinking about using distributive law, but not sure

Answer 16

define (S\T) o R ? ok, hold on

Answer 17

{(a,c} ∈ AxB | ∃b∈B ( (a,b) ∈ R and (b,c)∈(S\T)) }

Answer 18

yes?

Answer 19

you'll have to expand it

Answer 20

ok, hold on...

Answer 21

∃b∈B ( (a,b) ∈ R and (b,c)∈ S\T )
∃b∈B [ (a,b) ∈ R and ((b,c)∈ S and (b,c)∉T)]

Yes?

Answer 22

using associative law, i can remove some parenthesis
∃b∈B ( (a,b) ∈ R and (b,c)∈ S and (b,c)∉T )

yes?

Answer 23

yes

Answer 24

ok, so i have on the left side:
∃b∈B ( (a,b)∈R and (b,c) ∈ S) and ∀b∈B ( (a,b)∉R or (b,c) ∉ T)

and on the right side:
∃b∈B ( (a,b) ∈ R and (b,c)∈ S and (b,c)∉T )

Answer 25

ohhh, i think i got something. Wouldn't (a,b)∉R a false condition?

Answer 26

Not necessarily. The \(b\)s are not the same.

Answer 27

but it says all b's are not in R

Answer 28

i'm looking at the statement ∀b∈B ( (a,b)∉R or (b,c) ∉ T)

Answer 29

suppose bo, then (a,bo)∉R or (bo,a)∉T

Answer 30

if we check all element in B, then
suppose b1, then (a,b1)∉R or (b2,a)∉T
.
.
.
all the way to the last element of B

Answer 31

\[
(a,c) \in (S \circ R)\setminus(T \circ R) \\
\implies \exists b\quad (a,b) \in R\land (b,c)\in S \land \lnot[\exists b'\quad (a,b') \in R\land (b',c)\in T] \\
\implies \exists b\quad (a,b) \in R\land (b,c)\in S \land \forall b'\quad (a,b') \notin R\lor (b',c)\notin T
\] We can say :\[
\forall b'\quad (a,b') \notin R\lor (b',c)\notin T\implies (a,b)\notin R\lor (b,c)\notin T
\]So we have \[
\exists b\quad (a,b) \in R\land (b,c)\in S \land(a,b)\notin R\lor (b,c)\notin T
\]

Answer 32

We distribute across the \(\lor\).

Answer 33

\[

\exists b\quad (a,b) \in R\land (b,c)\in S \land [(a,b)\notin R\lor (b,c)\notin T]\\
\implies \exists b \\
(a,b) \in R\land (b,c)\in S \land(a,b)\notin R \\
\lor\\
(a,b) \in R\land (b,c)\in S\land (b,c)\notin T
\]The first one is always false due to \( (a,b) \in R \land(a,b)\notin R\), so it simplifies to: \[
\exists b\quad (a,b) \in R\land (b,c)\in S\land (b,c)\notin T
\]

Answer 34

how does
\[\forall b'\quad (a,b') \notin R\lor (b',c)\notin T\implies (a,b)\notin R\lor (b,c)\notin T\]

?

Answer 35

Implicitly, \(\forall b'\in B \quad f(b') \implies b\in B \quad f(b)\)

Answer 36

If it is true for every element in B, then it is true for some arbitrary element in B.

Answer 37

Even more explicit, \(\forall b'\in B \quad f(b') \implies \exists b\in B \quad f(b)\)