How many functions are there from {0,1} to {0,1} without restricted domains?

[Panphobia]

Homework Statement

How many functions are there from {0,1} to {0,1}?

The Attempt at a Solution

I know the answer is 9, but how is the answer 9?

 

[Dick]

Homework Statement

How many functions are there from {0,1} to {0,1}?

The Attempt at a Solution

I know the answer is 9, but how is the answer 9?

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

 

[Panphobia]

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

 

[Dick]

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

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.

 

[pasmith]

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

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$?

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

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.

 

[pasmith]

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.

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

 

[Panphobia]

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

 

[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.

 

[pasmith]

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

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\}$.

 

[Panphobia]

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

 

[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.

 

[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|