The Student Room Group

Set Theory

Hi guys,

I've been asked to show that (R∪S)−1=R−1∪S−1(R \cup S)^{-1} = R^{-1} \cup S^{-1}, where RR and SS are binary relations on some set AA.

This is my proof:

{(a,b),(c,d) ∣ (a,b)∈R−1,(c,d)∈S−1}\{ (a, b), (c, d) \ | \ (a, b) \in R^{-1}, (c, d) \in S^{-1} \}
{(a,b),(c,d) ∣ (a,b),(c,d)∈R−1∪S−1}\{ (a, b), (c, d) \ | \ (a, b), (c, d) \in R^{-1} \cup S^{-1} \}
{(a,b),(c,d) ∣ (b,a)∈R,(d,c)∈S}\{ (a, b), (c, d) \ | \ (b, a) \in R, (d, c) \in S \}
{(a,b),(c,d) ∣ (b,a),(d,c)∈R∪S}\{ (a, b), (c, d) \ | \ (b, a), (d, c) \in R \cup S \}
{(a,b),(c,d) ∣ (a,b),(c,d)∈(R∪S)−1}\{ (a, b), (c, d) \ | \ (a, b), (c, d) \in (R \cup S)^{-1} \}

Is this a valid proof?
(edited 9 years ago)
Original post by r3l3ntl3ss
Hi guys,

I've been asked to show that (R∪S)−1=R−1∪S−1(R \cup S)^-1 = R^-1 \cup S^-1.

This is my proof:

x

Is this a valid proof?

Could you reformat your LaTeX please?
Reply 2
Avatar for r3l3ntl3ss
r3l3ntl3ss
OP
10
Original post by sarcasmrules
Could you reformat your LaTeX please?


done, had a problem with the curly brackets
Original post by r3l3ntl3ss
done, had a problem with the curly brackets


This is what I would have done:

Multiply both sides by the union of R and S:
(R∪S)∪(R∪S)−1=(R∪S)∪(R−1∪S−1)(R \cup S) \cup (R \cup S)^{-1} = (R \cup S) \cup (R^{-1} \cup S^{-1})

sth operated with sth is e (identity):
e=(R∪S)∪(R−1∪S−1) e = (R \cup S) \cup (R^{-1} \cup S^{-1})

Union operation is commutative and associative, so:
e=(R∪R−1)∪(S∪S−1) e = (R \cup R^{-1}) \cup (S \cup S^{-1})

∴e=e∪e\therefore e = e \cup e
e=e e = e

I think yours is valid too.
Reply 4
Avatar for 0x2a
0x2a
2
What you've written is false

(R∪S)c≠Sc∪Rc(R \cup S)^c \neq S^c \cup R^c.

Instead (R∪S)c=Sc∩Rc(R \cup S)^c = S^c \cap R^c.

For these kinda of problems where you have a set AA and BB and you want to show that A=BA = B, you have to show inclusion on both sides so that A⊆BA \subseteq B and B⊆A B \subseteq A.

So assume x∈(R∪S)cx \in (R \cup S)^c and prove that x∈Sc∩Rcx \in S^c \cap R^c also and vice versa.
(edited 9 years ago)
Reply 5
Avatar for 0x2a
0x2a
2
Original post by sarcasmrules
This is what I would have done:

Multiply both sides by the union of R and S:
(R∪S)∪(R∪S)−1=(R∪S)∪(R−1∪S−1)(R \cup S) \cup (R \cup S)^{-1} = (R \cup S) \cup (R^{-1} \cup S^{-1})

sth operated with sth is e (identity):
e=(R∪S)∪(R−1∪S−1) e = (R \cup S) \cup (R^{-1} \cup S^{-1})

Union operation is commutative and associative, so:
e=(R∪R−1)∪(S∪S−1) e = (R \cup R^{-1}) \cup (S \cup S^{-1})

∴e=e∪e\therefore e = e \cup e
e=e e = e

I think yours is valid too.

(R∪S)∪(R∪S)c(R \cup S) \cup (R \cup S)^c is not ee. In fact A∪Ac=U A \cup A^c = U, where UU can be taken as the universe where A⊆UA \subseteq U.

Also ee as an identity makes no sense in set theory. There's no axiom of set theory that forces you to have an identity element in a set.
(edited 9 years ago)
Original post by 0x2a
(R∪S)∪(R∪S)c(R \cup S) \cup (R \cup S)^c is not ee. In fact A∪Ac=U A \cup A^c = U, where UU can be taken as the universe where A⊆UA \subseteq U.

Also ee as an identity makes no sense in set theory. There's no axiom of set theory that forces you to have an identity element in a set.

Oh crap, I read the title as "group theory" :colondollar:

I see where you're coming from. Ac∪AA^c \cup A would be any value in the Universe.
(edited 9 years ago)
Reply 7
Avatar for r3l3ntl3ss
r3l3ntl3ss
OP
10
Ah I also forgot to mention that RR and SS are binary relations on some set AA.

Is it still the same principle, though?
Reply 8
Avatar for 0x2a
0x2a
2
Original post by r3l3ntl3ss
Ah I also forgot to mention that RR and SS are binary relations on some set AA.

Is it still the same principle, though?


The thing is now that you say it's a binary relation (which I assume is symmetric), and defined such that R−1:={(b,a)∣(a,b)∈R}R^{-1} := \{(b,a)|(a,b) \in R\}, then (R∪S)−1=R−1∪S−1(R \cup S)^{-1} = R^{-1} \cup S^{-1} is correct.

Consider (b,a)∈(R∪S)−1⇒((a,b)∈R)∨((a,b)∈S)⇒(b,a) \in (R \cup S)^{-1} \Rightarrow ((a,b) \in R) \vee ((a,b) \in S) \Rightarrow ((b,a)∈R−1)∨((b,a)∈S−1)⇒(b,a)∈R−1∪S−1((b,a) \in R^{-1}) \vee ((b,a) \in S^{-1}) \Rightarrow (b,a) \in R^{-1} \cup S^{-1}, and so (R∪S)−1⊆R−1∪S−1(R \cup S)^{-1} \subseteq R^{-1} \cup S^{-1}. And you can show the converse showing that (R∪S)−1=R−1∪S−1(R \cup S)^{-1} = R^{-1} \cup S^{-1}.
(edited 9 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you