# Math Help - Injective Functions

1. ## Injective Functions

let P[{0,1}]be the power set of {0,1}.we say that a functionf from P[{0,1}] to {0,1,2,3,4,5} is increasing function if for any A,B belongs to P[{0,1}] we have f[A] is less than 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 sehrishqau
let P[{0,1}]be the power set of {0,1}.we say that a functionf from P[{0,1}] to {0,1,2,3,4,5} is increasing function if for any A,B belongs to P[{0,1}] we have f[A] is less than f[b] whenever A is a proper subset of B.How many such increasing functions are injective and how many are not
The domain P[{0,1}] has four elements, $\emptyset,\;\{0\},\;\{1\},\;\{0,1\}$. To save writing, I'll call these a,b,c,d respectively. The order relation of being a proper subset translates to a<b, a<c, b<d, c<d and of course a<d.

To specify an increasing injective function from P[{0,1}] to {0,1,2,3,4,5}, you have to choose four of the six elements in the range space (to form the range of the function). The element a must be mapped to the smallest of these four elements, and d must be mapped to the largest. The other two elements, b and c, can be mapped either way to the two remaining elements of the range. That gives a total of $2{6\choose4}$ possible functions.

To specify an increasing non-injective function from P[{0,1}] to {0,1,2,3,4,5}, you have to choose three of the six elements in the range space (to form the range of the function). The element a must be mapped to the smallest of these four elements, and d must be mapped to the largest. The other two elements, b and c, must both be mapped to the remaining element of the range. That gives a total of ${6\choose3}$ possible functions.