Results 1 to 4 of 4

Math Help - Basic proof of identity in introductory set theory

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    12

    Basic proof of identity in introductory set theory

    Hi, this is my first post here so please tell me if there is something wrong about it...

    I just started to read "Notes on set theory" by Yiannis Moschovakis which is available online through my university library and now I am very unsure even about the first few introductory exercise. I would really appreciate some verification of my way to think here, especially since I am not very good in math and haven't read any thorough courses in logic et.c. before. Because this is just an online book which I picked up and started reading, there are no lecturers or such to ask either, hence I turn to mathhelpforum =)
    Also, sorry about this wall of text! But I guess I should post my entire attempt...
    ...in the end of the post I try to be a bit more specific!
    I realize that I may be way off with this attempt and there may very well be MAJOR misconceptions and errors. I appreciate all input, big thx in advance!


    An example of a problem is :"Show that for every injection f : X \rightarrow Y, and all A,B \subseteqX

    f[A \cap B] = f[A] \cap f[B].

    Also show that this is identity does not always hold if f is not an injection."


    First attempt at solution:

    ____________________start of first attempt________________________________

    if x \epsilon f[A \cap B], then there is some y \epsilonA \cap B such that f(y)=x.

    y \epsilon(A \cap B) \Leftrightarrow y \epsilonA \wedge y \epsilonB

    Hence, x \epsilon f[A \cap B] \Leftrightarrow y \epsilonA \wedge y \epsilonB


    If x \epsilon f[A] \cap f[B], then there is some y \epsilon A \wedge y \epsilon B such that f(y) = x.
    That is, x \epsilon f[A] \cap f[B] \Leftrightarrow y \epsilon A \wedge y \epsilon B

    Since f is an injection (stated in the problem formulation); x=f(y)=f(y) \Leftrightarrow y= y

    Using this to evolve the result from above:

    x \epsilon f[A] \cap f[B] \Leftrightarrow y \epsilon A \wedge y \epsilon B \Leftrightarrow y \epsilonA \wedge y \epsilonB \Leftrightarrowx \epsilon f[A \capB]

    f[A \cap B] = f[A] \cap f[B]

    If f isn't an injection, then x=f(y)=f(y) does not imply y=y.

    ________________________end of first attempt_____________________________

    Then I started to think about an example wof when the relation does not hold and I realized that my solution might not be very good.

    Hence, I tried to adjust my first attempt:

    ____________________start of augmentation___________________________

    If x \epsilon f[A] \cap f[B], then there is some y \epsilon A such that f(y) = x and y \epsilonB such that f(y)=x.

    Since f is an injection, x=f(y)=f(y) implies y=y.
    y \epsilonA \wedge y \epsilon B

    ___________________________end of augmentation_____________________

    Would this augmentation make the solution correct?
    Then if y is not equal to y , I think it would be quite easy to make a specific example of when the identity does not hold for a non-injective fcn. (for instance say f(x)=x^2 and y=-y, right?)


    What Im concerned about is probably mainly this:

    x f[A] f[B] y A y B yA yB
    by the argument that x=f(y)=f(y) implies y=yfor an injection.
    Thereby, both
    x f[A B] yA yB
    and
    x f[A] f[B] yA yB.

    is this even correct?? necessary?

    Big thx in advance for any input! // HeadmasterEel
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Hello and welcome to MathHelpForum. I must tell you the your formatting makes that post very difficult to read, much less follow.

    For any function f[A\cap B]\subseteq f[A]\cap f[B].
    That is a straightforward proof from the definitions.

    If f is injective the equality holds. Suppose that y\in(f[A]\cap f[B]).
    Then \left( {\exists a \in A} \right)\left[ {f(a) = y} \right] \wedge \left( {\exists b \in B} \right)\left[ {f(b) = y} \right].
    But f is injective and f(a)=y=f(b) so a=b.
    This means that y\in f[A\cap B]. DONE.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    12
    Thank you for your reply Plato!

    I will try to make my posts more readable, but I have a hard time using this LaTex properly despite reading a tutorial...
    Another issue is that I am not 100% sure how to formally use all logic symbols, so there may also be some peculiarities because of this. I beg any readers pardon and promise I will work on my logic skills!=)

    I think the proof you presented is indeed straightforward.

    May I state another identity and my attempt at a proof and ask you forum guys to verify it?

    Let's say f is injective and I want to show that f(A \setminus B) = f(A) \setminus f(B)



    x \epsilon f(A \setminus B) \Leftrightarrow (\exists y \epsilon (A \setminus B))[f(y)=x]
    Since f is injective, (\neg \exists b \epsilon B)[f(b)=x], because f(b)=x would imply y=b but y \epsilon (A \setminus B)
    Therefore, under the assumption that f is injective;
    x \epsilon f(A \setminus B) \Leftrightarrow ( (\exists y \epsilon (A \setminus B))[f(y)=x] \wedge (\neg \exists b \epsilon B)[f(b)=x]) ) \Leftrightarrow x \epsilon (f(A) \setminus f(B))

    Extra question:

    x \epsilon (f(A) \setminus f(B) ) \Rightarrow x \epsilon f(A\setminus B) regardless of if f is injective, but the reverse is only always true if f is injective. Am I right?

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Is it clear to you that if f(y)\notin f[B] then it must follow that y\notin B~?

    What is the relation between f[B^c]~\&~(f[B])^c~?.

    Then think about the fact that A\setminus B=A\cap B^c

    Look at the first question you posted.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic Set Theory
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 24th 2011, 06:08 PM
  2. (Basic) Combinatorial Identity.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 1st 2010, 10:12 PM
  3. Basic Trig Identity
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: November 8th 2009, 10:57 AM
  4. Basic identity proving
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 5th 2009, 01:26 PM
  5. Introductory Number Theory Book?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 15th 2008, 07:55 AM

Search Tags


/mathhelpforum @mathhelpforum