Set Theory Watch

r3l3ntl3ss
Badges: 10
Rep:
?
#1
Report Thread starter 4 years ago
#1
Hi guys,

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

This is my proof:

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

Is this a valid proof?
0
reply
sarcasmrules
Badges: 14
Rep:
?
#2
Report 4 years ago
#2
(Original post by r3l3ntl3ss)
Hi guys,

I've been asked to show that (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?
0
reply
r3l3ntl3ss
Badges: 10
Rep:
?
#3
Report Thread starter 4 years ago
#3
(Original post by sarcasmrules)
Could you reformat your LaTeX please?
done, had a problem with the curly brackets
0
reply
sarcasmrules
Badges: 14
Rep:
?
#4
Report 4 years ago
#4
(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 \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 \cup S) \cup (R^{-1} \cup S^{-1})

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

\therefore e = e \cup e
 e = e

I think yours is valid too.
0
reply
0x2a
Badges: 2
Rep:
?
#5
Report 4 years ago
#5
What you've written is false

(R \cup S)^c \neq S^c \cup R^c.

Instead (R \cup S)^c = S^c \cap R^c.

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

So assume x \in (R \cup S)^c and prove that x \in S^c \cap R^c also and vice versa.
1
reply
0x2a
Badges: 2
Rep:
?
#6
Report 4 years ago
#6
(Original post by sarcasmrules)
This is what I would have done:

Multiply both sides by the union of R and S:
(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 \cup S) \cup (R^{-1} \cup S^{-1})

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

\therefore e = e \cup e
 e = e

I think yours is valid too.
(R \cup S) \cup (R \cup S)^c is not e. In fact  A \cup A^c = U, where U can be taken as the universe where A \subseteq U.

Also e 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.
0
reply
sarcasmrules
Badges: 14
Rep:
?
#7
Report 4 years ago
#7
(Original post by 0x2a)
(R \cup S) \cup (R \cup S)^c is not e. In fact  A \cup A^c = U, where U can be taken as the universe where A \subseteq U.

Also e 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"

I see where you're coming from. A^c \cup A would be any value in the Universe.
0
reply
r3l3ntl3ss
Badges: 10
Rep:
?
#8
Report Thread starter 4 years ago
#8
Ah I also forgot to mention that R and S are binary relations on some set A.

Is it still the same principle, though?
0
reply
0x2a
Badges: 2
Rep:
?
#9
Report 4 years ago
#9
(Original post by r3l3ntl3ss)
Ah I also forgot to mention that R and S are binary relations on some set A.

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) \in R\}, then (R \cup S)^{-1} = R^{-1} \cup S^{-1} is correct.

Consider (b,a) \in (R \cup S)^{-1} \Rightarrow ((a,b) \in R) \vee ((a,b) \in S) \Rightarrow ((b,a) \in R^{-1}) \vee ((b,a) \in S^{-1}) \Rightarrow (b,a) \in R^{-1} \cup S^{-1}, and so (R \cup S)^{-1} \subseteq R^{-1} \cup S^{-1}. And you can show the converse showing that (R \cup S)^{-1} = R^{-1} \cup S^{-1}.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Cranfield University
    Cranfield Forensic MSc Programme Open Day Postgraduate
    Thu, 25 Apr '19
  • University of the Arts London
    Open day: MA Footwear and MA Fashion Artefact Postgraduate
    Thu, 25 Apr '19
  • Cardiff Metropolitan University
    Undergraduate Open Day - Llandaff Campus Undergraduate
    Sat, 27 Apr '19

Have you registered to vote?

Yes! (219)
39.46%
No - but I will (38)
6.85%
No - I don't want to (37)
6.67%
No - I can't vote (<18, not in UK, etc) (261)
47.03%

Watched Threads

View All