Could anybody help me prove the following statement? 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.
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.
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?
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.
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.Originally Posted by Hartlw
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.
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]
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.