Page 1 of 2 12 LastLast
Results 1 to 15 of 25
Like Tree4Thanks

Math Help - Proof about relations

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    Cali
    Posts
    20
    Thanks
    1

    Proof about relations

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

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Proof about relations

    Quote Originally Posted by sebasvargasl View Post
    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?

    Define your terms!
    Thanks from sebasvargasl
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2013
    From
    Cali
    Posts
    20
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Proof about relations

    Quote Originally Posted by sebasvargasl View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof about relations

    Quote Originally Posted by sebasvargasl View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    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?
    Last edited by Hartlw; March 12th 2013 at 10:36 AM. Reason: add "irrelevant"
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof about relations

    Quote Originally Posted by Hartlw View Post
    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}.
    Thanks from sebasvargasl
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Proof about relations

    Quote Originally Posted by sebasvargasl View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Proof about relations

    Quote Originally Posted by sebasvargasl View Post
    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.
    Thanks from sebasvargasl
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Mar 2013
    From
    Cali
    Posts
    20
    Thanks
    1

    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]
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Proof about relations

    Quote Originally Posted by Hartlw View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Proof about relations

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Proof regarding Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 9th 2012, 09:38 AM
  2. Relations proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 2nd 2010, 01:25 PM
  3. Equivalence Relations Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 10th 2009, 03:33 PM
  4. Reflexive relations proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2007, 03:46 AM
  5. Equiv. Relations + Proof!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 18th 2007, 05:17 AM

Search Tags


/mathhelpforum @mathhelpforum