# increasing functions

• Dec 3rd 2008, 09:20 AM
makenqau
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.
• Dec 3rd 2008, 03:21 PM
ThePerfectHacker
Quote:

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.