Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    2
    ReputationRep:
    If f is a one to one function of the set X to the set Y and A, B \subseteq X, then f(A \oplus B) = f(A) \oplus f(B)



    If y \in f(A \oplus B) then there exists x \in A \oplus B so that f(x) = y. Then x \in A \setminus B or x \in B \setminus A

    So then x \in A so f(x) \in f(A) and f(x) \in f(B) as well so there exists a \ z \in B with f(x) = f(z) and f is a one to one so surely z = x with x \in B contradicting x \in A \setminus B

    So the contradiction proves that f(A \oplus B) \subseteq f(A \oplus B) and in turn f(A \oplus B) = f(A) \oplus (B) is true.

    Is this correct?
    Offline

    17
    ReputationRep:
    (Original post by AishaGirl)
    If f is a one to one function of the set X to the set Y and A, B \subseteq X, then f(A \oplus B) = f(A) \oplus f(B)
    What is \oplus supposed to mean here? I've never seen that notation used in this context.

    So the contradiction proves that f(A \oplus B) \subseteq f(A \oplus B)
    I think you have a typo here: showing f(A \oplus B) \subseteq f(A \oplus B) is hardly an achievement!
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by DFranklin)
    What is \oplus supposed to mean here? I've never seen that notation used in this context.

    I think you have a typo here: showing f(A \oplus B) \subseteq f(A \oplus B) is hardly an achievement!
    Oh yes my bad, I meant to say it proves that f(A) \oplus (B) \subseteq f(A \oplus B)

    \oplus is the symmetric difference, some books use the \triangle symbol. Sorry I should have clarified that.
    Offline

    17
    ReputationRep:
    (Original post by AishaGirl)
    Oh yes my bad, I meant to say it proves that f(A) \oplus (B) \subseteq f(A \oplus B)

    \oplus is the symmetric difference, some books use the \triangle symbol. Sorry I should have clarified that.
    OK, I perhaps should have guessed, but \oplus is used for a lot of other things at university and so it's not usual for it to be used for symmetric difference at that level.

    (Original post by AishaGirl)
    If y \in f(A \oplus B) then there exists x \in A \oplus B so that f(x) = y. Then x \in A \setminus B or x \in B \setminus A

    So then x \in A so f(x) \in f(A) and f(x) \in f(B) as well
    I don't see why this line follows. (I also don't see where you are "starting" your contradiction; it's usual to say something like

    "assume (for contradiction) that X is true. {...your argument...}, but this gives a contradiction and therefore it cannot be the case that X is true".

    It's important to have the preamble, because (since you want a contradiction) the initial assumption is wrong, and if you're going to write something you know is wrong, you need to make it clear what the reason is). You don't have to actively say "for contradiction" (though I would do so at A-level), but you do need to make it clear it's an assumption, not something you think is actually true.

    I'm not sure I'd prove this by contradiction anyhow, rather show that if x \in f(A \oplus B) then  x \in f(A) \oplus f(B) and vice-versa.
    • Thread Starter
    Offline

    2
    ReputationRep:
    DFranklin

    If I do it in the other direction and suppose y \in f(A) \oplus f(B) then y \in f(A) \setminus f(B) or y \in f(B) \setminus f(A) then  x \in A such that f(x) = y Suppose that x \in B also then y = f(x) \in f(B) again contradicting the fact that y \in f(A) \setminus f(B)

    So y \in A \setminus B proves that it the subset is true? I don't see the problem with using contradiction, are you just saying it's a lengthier way of doing it or rather that it's bad practice?

    What is a simpler way of doing it?

    Thanks.
    Offline

    17
    ReputationRep:
    (Original post by AishaGirl)
    DFranklin

    If I do it in the other direction and suppose y \in f(A) \oplus f(B) then y \in f(A) \setminus f(B) or y \in f(B) \setminus f(A) then  x \in A
    Why do you say that x \in A? It clearly doesn't have to be.

    I don't see the problem with using contradiction, are you just saying it's a lengthier way of doing it or rather that it's bad practice?
    Actually I'll kind of take that back; I think you'll probably have some contradiction argument somewhere. It's just that when you say "I'm going to prove X by contradiction", you usually mean "I'm going to assume X isn't true and derive a contradiction", whereas here it's more you're going to get some way down the road and then say to finish "I'd like Y to be true, and it must be true, because otherwise we get a contradiction".
    Offline

    11
    ReputationRep:
    (Original post by AishaGirl)
    What is a simpler way of doing it?
    I've only skimmed the previous posts so I'm not sure if your contradiction approach will work, but DFranklin has already outline another approach.

    In fact, it is the standard approach. If you want to prove that A=B where A and B are sets, then you have to show that x \in A \Leftrightarrow x \in B since that is the definition of equal sets.
    Offline

    17
    ReputationRep:
    (Original post by atsruser)
    I've only skimmed the previous posts so I'm not sure if your contradiction approach will work, but DFranklin has already outline another approach.

    In fact, it is the standard approach. If you want to prove that A=B where A and B are sets, then you have to show that x \in A \Leftrightarrow x \in B since that is the definition of equal sets.
    So, actually I think this is what she's trying to do; the contradiction comes later. "As you know...", if you're trying to prove things with the symmetric difference it's pretty common to get to a point where you want to say x is in M or N, but not both, and so end up with something like, "suppose X is in M and M, then ... which is a contradiction".

    I have to say that I kind of hate "fundamental" questions about set operations, because it always feels to me like "it's obvious", and any step-by-step proof doesn't actually make the truth of the statement clearer, rather the opposite. This probably indicates some deep flaw in my character...
 
 
 
  • 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.

  • Poll
    Will you be richer or poorer than your parents?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.