Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help understanding a proof

  1. Apr 10, 2014 #1
    I'm reading about countable and uncountable sets, I found the following statement: "The set of the functions from [itex]\mathbb{Z}[/itex] to [itex][0,1][/itex] is uncountable" with the following proof: "To see that, suppose the set countable having the list [itex]\{f_1,f_2,\dots\}[/itex] and define [itex]f(x) = f_n(1/n)[/itex] if [itex]x=1/n[/itex] and [itex]f(x)=0[/itex] if [itex]x\neq 1/n[/itex] for any n".

    Could someone explain this proof further?. It seems to me that he is trying to construct a function that is different from every [itex]f_i[/itex], but I don't see how the new function is necessarily different from every [itex]f_i[/itex], can't we have the possibilty that all the functions have the same values at [itex]1/n[/itex] for every [itex]n[/itex] but they are different for other values?.
     
    Last edited: Apr 10, 2014
  2. jcsd
  3. Apr 10, 2014 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The proof doesn't make any sense. The function ##f## being constructed does not even appear to be defined on the correct domain, ##\mathbb{Z}##.

    Try the following instead. Suppose that we have an enumeration ##\{f_1, f_2, \ldots\}##. We now construct ##f : \mathbb{Z} \rightarrow [0,1]## that is not in the list.

    First, let ##g : \mathbb{Z} \rightarrow \mathbb{Z}^{+}## be any bijection. For each ##n \in \mathbb{Z}##, set ##f(n)## equal to any value in ##[0,1]## other than ##f_{g(n)}(n)##. If we want to be concrete (to avoid invoking the axiom of choice), put
    $$f(n) = \begin{cases}
    1 & \text{ if }f_{g(n)}(n) = 0 \\
    0 & \text{ otherwise} \\
    \end{cases}$$
    Now given any ##m \in \mathbb{Z}^+##, we see that ##f## cannot equal ##f_m## because it differs from ##f_m## at the point ##n = g^{-1}(m)##.
     
    Last edited: Apr 10, 2014
  4. Apr 10, 2014 #3
    Thanks a lot.
    But that was my mistake. The proposition is about the set of functions from [itex][0,1][/itex] to [itex]\mathbb{Z}[/itex]
     
  5. Apr 10, 2014 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    OK, the proof is still incorrect as stated. It would be OK if it said

    Perhaps for concreteness, something like
     
  6. Apr 10, 2014 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Assuming you know [0, 1] is uncountable:

    [tex]f_a(a) = 1 \ and \ f_a(x) = 0 \ otherwise[/tex]
    Defines an uncountable set of functions: one for each a in [0, 1]
     
  7. Apr 10, 2014 #6
    Thanks a lot, now that makes sense.
    Still, for the last example if [itex]f_1(1)=1[/itex] wouldn't be [itex]f(1)=2[/itex] which exceeds the domain?, maybe something like [itex]f(x)=[f_n(1/n)]/2[/itex] would work better?.
     
  8. Apr 10, 2014 #7

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I thought you wanted to map from ##[0,1]## to ##\mathbb{Z}##. So the value of ##f(x)## can be as big as we like, but you can't divide by 2, because the result may not be an integer.
     
  9. Apr 10, 2014 #8
    Yes, you're right. I'm sorry, I read it too fast and didn't think it through :frown:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help understanding a proof
  1. Proof Help (Replies: 1)

  2. Help with proof (Replies: 14)

  3. Proof help (Replies: 6)

Loading...