1. Limited time only! Sign up for a free 30min personal 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!

Functions from {0,1} to {0,1}

  1. Feb 27, 2014 #1
    1. The problem statement, all variables and given/known data

    How many functions are there from {0,1} to {0,1}?
    3. The attempt at a solution
    I know the answer is 9, but how is the answer 9?
     
  2. jcsd
  3. Feb 27, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    f(0) could be either 0, 1 or undefined. Same for f(1). Count all of the possibilities.
     
  4. Feb 27, 2014 #3
    ohhhh I thought it was 2^2 possibilities not 3^2, thanks, because {} [itex]\subset[/itex] {0,1} and the value of {} is undefined correct?
     
  5. Feb 27, 2014 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, it's because they only said f:{0,1}->{0,1}. They didn't say the function was defined for all values in the set {0,1}. If they had said the DOMAIN of f was {0,1}, then the answer 4 would be correct. It's more legalese than important.
     
  6. Feb 27, 2014 #5

    pasmith

    User Avatar
    Homework Helper

    By what definition of "function" can it be said that if [itex]f: \{0,1\} \to \{0,1\}[/itex] then [itex]f(0)[/itex] is not either [itex]0[/itex] or [itex]1[/itex]?

    You were right the first time: there are four functions from [itex]\{0,1\}[/itex] to [itex]\{0,1\}[/itex], because there are exactly two choices for [itex]f(0)[/itex], and independently of that choice there are exactly two choices for [itex]f(1)[/itex].

    See further this post by Tim Gowers.
     
  7. Feb 27, 2014 #6

    pasmith

    User Avatar
    Homework Helper

    Except that notation [itex]f: A \to B[/itex] means that the domain of [itex]f[/itex] is [itex]A[/itex] and the codomain of [itex]f[/itex] is [itex]B[/itex]!
     
  8. Feb 27, 2014 #7
    On my practise mid term exam, it gives this exact question, the answer was 9, so pasmith, it can't be 4.
     
  9. Feb 27, 2014 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The definition of a function requires every element of the domain to have a defined function value. So, if f(0) or f(1) is not defined, then f is not a function of {0, 1}.

    The answer must be there are only 4 functions.
     
  10. Feb 27, 2014 #9

    pasmith

    User Avatar
    Homework Helper

    Then your exam is wrong. By convention, [itex]f: \{0,1\} \to \{0,1\}[/itex] means that the domain and codomain of [itex]f[/itex] are both [itex]\{0,1\}[/itex], so that [itex]f(0) \in \{0,1\}[/itex] and [itex]f(1) \in \{0,1\}[/itex].
     
  11. Feb 27, 2014 #10
    Ok thanks, I shouldn't have doubted myself :P
     
  12. Feb 27, 2014 #11
    One more question, if (A,B,C) is a function, and (A',B', C') is equal to that function if A=A' and B=B' and C=C': consider the function
    f: R -> R
    x|-> 1/x
    Which denote the same function as f.
    a)
    g: R -> R
    x|-> 1/x

    b)
    h: R* -> R
    u |-> 1/u

    c)
    d: R -> R
    w |-> w/w^2

    d)
    k: R->R
    z|-> z-1/(z*(z-1))

    I know that h cannot be right because R* != R, I know that g is the same as f, but I don't know b or c, according to the answers, d is the same as f, but not k, why is this? Oh wait nevermind, the domain of definition is different for k, sorry.
     
    Last edited: Feb 27, 2014
  13. Feb 27, 2014 #12

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    None of these are functions of R as they are not defined at 0. These are functions of R\{0} and in the last case R\{0, 1}.

    For two functions to be equal, the range, domain and all function values must be equal. It doesn't matter if two different different formulas are given, as long as the formulas are valid and equal on the same domain.

    For example:

    f: R -> R defined by f(x) = x is the same as:

    g: R -> R defined by 2x/2

    It's not the same as

    h: R\{0} -> R defined by f(x) = x^2/x

    And, strictly speaking:

    f: R -> R, f(x) = x^2

    is not the same as

    f: R -> [0, ∞), f(x) = x^2

    Another example is:

    f: C -> C, f(z) = |z|

    is not the same as:

    f: C -> R, f(z) = |z|
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Functions from {0,1} to {0,1}
  1. Proof that 0!=1? (Replies: 30)

  2. Prove a^0 = 1 if a=/=0 (Replies: 4)

  3. X^0 = 1? (Replies: 12)

Loading...