1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about onto functions.

  1. Dec 24, 2012 #1
    1. The problem statement, all variables and given/known data
    Given any set A, there does not exist a function f:A→P(A)
    It wants us to do a proof by contradiction and assume there is an onto function.
    For each element [itex] a \in A [/itex] f(a) is a particular subset
    of A. The assumption that f is onto means that every subset of A appears as f(a)
    for some [itex] a \in A [/itex] To arrive at a contradiction, we will produce
    a subset [itex] B \subseteq A [/itex] that is not equal to f(a) for
    any [itex] a \in A [/itex]
    [itex] B=\{a\in A:a\notin f(a)\} [/itex]
    If f is onto then it must be the case that B=f(a') for some a' in A.
    the contradiction arises when we consider if a' is an element of B.
    First show that the case that a' is in B leads to a contradiction.
    Now finish the argument by showing that the case a' is not in B
    is equally unacceptable.
    3. The attempt at a solution
    If a' is in B then a' is in A
    and if f is onto then f(a') is in B
    if f(a') is in B then f(a') is some a
    in A but this is a contradiction
    because we assumed that a was not in f(a).
    If a' is not in B then it is not in A and therefore
    it is not in anything.
    Am I headed the right direction?
     
    Last edited: Dec 24, 2012
  2. jcsd
  3. Dec 24, 2012 #2

    pasmith

    User Avatar
    Homework Helper

    This is somewhat confused.

    Given [itex]f[/itex], [itex]B[/itex] consists of exactly those elements [itex]a \in A[/itex] which are not members of their image, [itex]f(a) \subset A[/itex]. However there could be other elements of A which are members of their image.

    The point is that if [itex]f[/itex] is onto, then by definition [itex]B \subset A[/itex] must be the image of some [itex]a' \in A[/itex], so that [itex]f(a') = B[/itex]. Note that, by assumption, [itex]a' \in A[/itex]. Whether [itex]a' \in B[/itex] is another question.

    So what happens if [itex]a' \in B[/itex]? That would mean that [itex]a'[/itex] is not a member of its image. But its image is B. This is a contradiction.

    Now you need to show that a similar contradiction arises if you assume [itex]a' \notin B[/itex].
     
  4. Dec 24, 2012 #3
    is image f(a)=a
     
  5. Dec 24, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    a' was chosen to be in A.
    a' was chosen such that f(a')=B. It cannot be "in B".
    a is an element of A; f(a) is a subset of A. They cannot be equal.
    Start again at "If a' is in B then " and use the definition of B to deduce something about a'.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook