# Proof about relations

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Mar 11th 2013, 04:46 PM
sebasvargasl
Could anybody help me prove the following statement? R[A]-R[B] is a subset of R[A-B]

• Mar 11th 2013, 04:59 PM
Plato
Re: Proof about relations
Quote:

Originally Posted by sebasvargasl
Could anybody help me prove the following statement? R[A]-R[B] is a subset of R[A-B]

Oh! come on

What gives you the right to assume that any of us should know what
$R[A]\text{ or }R[A-B]$ means?

• Mar 11th 2013, 06:16 PM
sebasvargasl
Re: Proof about relations
I'm sorry. I thought it was clear enough, my mistake. R[A] is the image of A under the relation R. y belongs to R[A] if and only if there exists x belonging to A for which the ordered pair (x,y) belongs to R
• Mar 12th 2013, 08:39 AM
Hartlw
Re: Proof about relations
Quote:

Originally Posted by sebasvargasl
Could anybody help me prove the following statement? R[A]-R[B] is a subset of R[A-B]

R[A-B] = xRy, x&y ϵ [A-B]X[A-B]
R[A] - R[B] = uRv, u&v ϵ [AXA]-[BXB]

So the challenge is to show every member of R[A]-R[B] is a member of R[A-B]:

[A-B] = all members of A not in B
[AXA]-[BXB] = all members of AXA not in BXB
• Mar 12th 2013, 09:36 AM
emakarov
Re: Proof about relations
Quote:

Originally Posted by sebasvargasl
R[A]-R[B] is a subset of R[A-B]

Assume y ∈ R[A] - R[B], i.e., y ∈ R[A], but y ∉ R[B]. Then there exists an x ∈ A such that xRy, but there is no x' ∈ B such that x'Ry. Now it is left to show that the x above is in A but not in B, i.e., x ∈ A - B.

Quote:

Originally Posted by Hartlw
R[A-B] = xRy, x&y ϵ [A-B]X[A-B]

There are two errors here. First, R[A-B] is a set, while xRy is a proposition. These are objects of different types, so they cannot be equal. Second, we are told that A and B are subsets of the domain of R, but we are not told what the codomain of R is. For all we know, R could be a subset of (A ∪ B) x C for some unrelated set C. Therefore, if xRy, we cannot guarantee that y ∈ A or y ∈ (A - B) x (A - B) or anything like this.
• Mar 12th 2013, 10:07 AM
Hartlw
Re: Proof about relations
xRy is standard notation for def of R as a subset (x,y) of ordered pairs of CXD, and in this case D is obviously C.

Like the rest of my post #4, it is self-explanatory without recourse to “codomain” (irrelavant) which my reference, or Google-wiki, doesn’t use wrt the definition of relation, so why even bring it up?

It looked like the rest of the proof was straight forward after I laid the groundwork. Try to get to it later.

EDIT: In xRy x is the domain and y is the range. Not obvious?
• Mar 12th 2013, 10:40 AM
emakarov
Re: Proof about relations
If R ⊆ X x Y, i.e., when R is a relation between two sets X and Y, I call X the domain and Y the codomain of R, by analogy with the situation when R is a function. The same terminology is used in Wikipedia.

Quote:

Originally Posted by Hartlw
xRy is standard notation for def of R as a subset (x,y) of ordered pairs of CXD, and in this case D is obviously C.

The OP may clarify, but it's not obvious to me that D = C, though it is possible. But even if R is a relation on a single set C, of which A and B are subsets, I don't understand the following.

Quote:

Originally Posted by Hartlw
R[A-B] = xRy, x&y ϵ [A-B]X[A-B]
R[A] - R[B] = uRv, u&v ϵ [AXA]-[BXB]

As I said, when one write p = q, p and q must be of the same type, e.g., both are numbers, or both are sets, or both are matrices. You should probably use set-builder notation because the left-hand side R[A - B] is a subset of C. Also, I don't understand if "x&y ∈ Z" means "x ∈ Z and y ∈ Z" or "(x, y) ∈ Z". If we don't write our claims precisely, we can't do mathematics.
• Mar 12th 2013, 10:50 AM
Hartlw
Re: Proof about relations
To me R[A] could mean only one thing: a subset (x,y) of AXA. The rest of post 4 follows.
• Mar 12th 2013, 11:13 AM
emakarov
Re: Proof about relations
Quote:

Originally Posted by Hartlw
To me R[A] could mean only one thing: a subset (x,y) of AXA. The rest of post 4 follows.

That's not what the OP wrote in post #3. Even if R is a relation on A, R[A] is a subset of A, not a subset of A x A. Just like when A = $\mathbb{R}$ and $R : \mathbb{R}\to\mathbb{R}$ is a function, the image of R (i.e., $R[\mathbb{R}]$) is a subset of $\mathbb{R}$, not a subset of $\mathbb{R}\times\mathbb{R}$. For example, the image of $\sin(x):\mathbb{R}\to\mathbb{R}$ is $[-1, 1]\subset\mathbb{R}$.
• Mar 13th 2013, 06:17 AM
Hartlw
Re: Proof about relations
Quote:

Originally Posted by sebasvargasl
Could anybody help me prove the following statement? R[A]-R[B] is a subset of R[A-B]

The best I could come up with was an example:

A={1.2.3.4,5} R = <
R[A]=(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4), (3,5),(4,5)
B={3,4,5,6}
R[B]= (3,4),(3,5),(3,6),(4,5),(4,6),(5,6)
R[A]-R[B]= (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)
[A-B]={1,2}
R[A-B]=(1,2)

so R[A-B] is a subset of R[A]-R[B]

for xRy, x is domain and y is codomain is correct. It’s really not a function. emakorov was right.
• Mar 13th 2013, 08:59 AM
Hartlw
Re: Proof about relations
Quote:

Originally Posted by sebasvargasl
Could anybody help me prove the following statement? R[A]-R[B] is a subset of R[A-B]

x,y ϵ [A-B] → x,y ϵ A and x,y ϵ’ B
So R[A-B] is a subset of R[A]-R[B]

compare with example in previous post.
• Mar 15th 2013, 12:29 PM
sebasvargasl
Re: Proof about relations
Thank you so much for your attention. I think I already have a proof.

Proof:
y∈R[A]-R[B]⇔y∈R[A] ∧ y∉R[B]⇔∃x(x∈A∧xRy) ∧ ∀x(x∉B∨¬xRy), let k be a specific set for which x∈A∧xRy holds, then (k∈A∧kRy) ∧ ∀x(x∉A∨¬xRy), since x∉B∨¬xRy holds for every set x, it does for k too, then (k∈A∧kRy) ∧ (k∉B∨¬kRy)⇔(k∈A∧kRy∧k∉B) ∨ (k∈A∧kRy∧¬kRy)⇔k∈A∧k∉B∧kRy⇔k∈A-B∧kRy⇔∃x(x∈A-B∧xRy)⇔y∈R[A-B]

∴R[A]-R[B] ⊂ R[A-B]
• Mar 15th 2013, 12:48 PM
emakarov
Re: Proof about relations
Yes, this is a pretty formal, but correct proof. I would write it using more words, as follows. Suppose y ∈ R[A] - R[B], i.e., y ∈ R[A] but y ∉ R[B]. Then there exists an x ∈ A such that xRy. We need to show that x ∉ B; then x ∈ A - B and y ∈ R[A - B]. But if x ∈ B, then xRy gives y ∈ R[B], which is not the case. Therefore, x ∉ B.
• Mar 16th 2013, 07:16 AM
Hartlw
Re: Proof about relations
Quote:

Originally Posted by Hartlw
x,y ϵ [A-B] → x,y ϵ A and x,y ϵ’ B
So R[A-B] is a subset of R[A]-R[B]

Why would you replace this simple,intelligible, proof with the previous two unintelligible, and wrong, proofs. Note the simple example in post #10. Since your proofs are unintelligible, do you at least have a simple, intelligible example to confirm your proofs?
• Mar 16th 2013, 07:34 AM
Hartlw
Re: Proof about relations
Quote:

Originally Posted by emakarov
Suppose y ∈ R[A] - R[B], i.e., y ∈ R[A] but y ∉ R[B].

This is an incorrect statement which only applies if A and B are disjoint sets. You have to first understand what A-B means. Draw a venn diagram of B overlapping part of A and then subtract B from A.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last