# Thread: increasing functions

1. ## increasing functions

Let P ({0,1}) denote the power set of the set {0,1}, We say that a function
f:P({0,1}) to {1,2,...,5} is increasing function if for any
A,B belongs toP({0,1}) we have f (A) < f(B) whenever A is a proper subset of
B . How many such increasing functions are injective and how many are
not.

2. Originally Posted by makenqau
Let P ({0,1}) denote the power set of the set {0,1}, We say that a function
f:P({0,1}) to {1,2,...,5} is increasing function if for any
A,B belongs toP({0,1}) we have f (A) < f(B) whenever A is a proper subset of
B . How many such increasing functions are injective and how many are
not.
Say that $\displaystyle A<B$ or $\displaystyle B<A$ then $\displaystyle f(A) < f(B)$ or $\displaystyle f(B) < f(A)$.
Therefore, $\displaystyle \emptyset, \{ 0,1\}, \{ 0\}$ must be mapped into distinct elements and $\displaystyle \emptyset, \{0,1\}, \{ 1\}$ must be mapped into distinct elements if $\displaystyle f$ is increasing.
However, since $\displaystyle \{ 0 \} \not < \{ 1 \}$ or $\displaystyle \{ 1 \} \not < \{ 0 \}$ it means we cannot conclude that $\displaystyle f( \{ 0 \} ) \not = f(\{1\})$ if $\displaystyle f$ is increaing.

Based on the above reasoning we have the following possibilities:
1. $\displaystyle \emptyset \mapsto 1 , \{ 0 \} \mapsto 2, \{ 1 \} \mapsto 3, \{0,1\} \mapsto 4,5$
2. $\displaystyle \emptyset \mapsto 1, \{ 0\} \mapsto 3, \{ 1 \}\mapsto 2, \{ 0,1 \} \mapsto 4,5$
3. $\displaystyle \emptyset \mapsto 2, \{ 0 \}\mapsto 3, \{ 1 \} \mapsto 4, \{0,1\} \mapsto 5$
4. $\displaystyle \emptyset \mapsto 2, \{ 0 \} \mapsto 4, \{ 1 \} \mapsto 3, \{ 0,1\} \mapsto 5$

I get six.