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

1. Feb 27, 2014

### Panphobia

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. Feb 27, 2014

### Dick

f(0) could be either 0, 1 or undefined. Same for f(1). Count all of the possibilities.

3. Feb 27, 2014

### Panphobia

ohhhh I thought it was 2^2 possibilities not 3^2, thanks, because {} $\subset$ {0,1} and the value of {} is undefined correct?

4. Feb 27, 2014

### Dick

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.

5. Feb 27, 2014

### pasmith

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

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

See further this post by Tim Gowers.

6. Feb 27, 2014

### pasmith

Except that notation $f: A \to B$ means that the domain of $f$ is $A$ and the codomain of $f$ is $B$!

7. Feb 27, 2014

### Panphobia

On my practise mid term exam, it gives this exact question, the answer was 9, so pasmith, it can't be 4.

8. Feb 27, 2014

### PeroK

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.

9. Feb 27, 2014

### pasmith

Then your exam is wrong. By convention, $f: \{0,1\} \to \{0,1\}$ means that the domain and codomain of $f$ are both $\{0,1\}$, so that $f(0) \in \{0,1\}$ and $f(1) \in \{0,1\}$.

10. Feb 27, 2014

### Panphobia

Ok thanks, I shouldn't have doubted myself :P

11. Feb 27, 2014

### Panphobia

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
12. Feb 27, 2014

### PeroK

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|