Turn on thread page Beta
    • 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

    18
    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

    18
    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

    18
    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

    18
    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...
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: January 31, 2017
Poll
Do you think parents should charge rent?
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

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

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