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

Printable View

- Mar 11th 2013, 04:46 PMsebasvargaslProof about relations
Could anybody help me prove the following statement? R[A]-R[B] is a subset of R[A-B]

- Mar 11th 2013, 04:59 PMPlatoRe: Proof about relations
- Mar 11th 2013, 06:16 PMsebasvargaslRe: 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 AMHartlwRe: Proof about relations
- Mar 12th 2013, 09:36 AMemakarovRe: Proof about relations
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.

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 AMHartlwRe: 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 AMemakarovRe: 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.

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**

- Mar 12th 2013, 10:50 AMHartlwRe: 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 AMemakarovRe: Proof about relations
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 = $\displaystyle \mathbb{R}$ and $\displaystyle R : \mathbb{R}\to\mathbb{R}$ is a function, the image of R (i.e., $\displaystyle R[\mathbb{R}]$) is a subset of $\displaystyle \mathbb{R}$, not a subset of $\displaystyle \mathbb{R}\times\mathbb{R}$. For example, the image of $\displaystyle \sin(x):\mathbb{R}\to\mathbb{R}$ is $\displaystyle [-1, 1]\subset\mathbb{R}$.

- Mar 13th 2013, 06:17 AMHartlwRe: Proof about relations
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 AMHartlwRe: Proof about relations
- Mar 15th 2013, 12:29 PMsebasvargaslRe: 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 PMemakarovRe: 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 AMHartlwRe: Proof about relations
- Mar 16th 2013, 07:34 AMHartlwRe: Proof about relations