b.stat amd b.math 2012

1.Let n$\geq$1,and S = $\{1,2,3,,,,,,,,,,n\}$. For a function f:$ S\implies S $ , a subset D, $D \subseteq S$ is said t be invarient under f , if $f(x)\in D$ . Note that the empty set and S are invariant for all f . Let deg(f) be the number of subsets of S invariant under f .
(1)Show that there is a function f :$ S\implies S $ such that deg(f) = 2.
(2)Further show that for any k such that 1 $\leq $ k $\leq $ n ther is a function f:$ S\implies S $ that is deg(f)=$2^k $.

Solution :Consider the function defined piecewise as f(x) = x – 1 is x ($\neq1$) and f(x) = n if x = 1

Of course null set and the entire sets are invariant subsets. We prove that there are no other invariant subsets.

Suppose D = {$(a_1 , a_2 , … , a_k $)} be an invariant subset with at least one element.

Since we are working with natural numbers only, it is possible to arrange the elements in ascending order (there is a least element by well ordering principle).

Suppose after rearrangement D = {$(b_1 , b_2 , … , b_k)$} where $(b_1$) is the least element of the set

If $(b_1$$\neq $ 1) then $(f(b_1) = b_1$ -1) is not inside D as $(b_1$) is the smallest element in D. Hence D is no more an invariant subset which is contrary to our initial assumption.

This $(b_1$) must equal to 1.

As D is invariant subset $(f(b_1) = n $) must belong to D. Again f(n) = n-1 is also in D and so on. Thus all the elements from 1 to n are in D making D=S.

Hence we have proved that degree of this function is 2.


For a natural number ‘k’ to find a function with deg(f) = $(2^k$) define the function piecewise as

f(x) = x for (1$\leq x $ $\leq(k-1)$)
= n for x=k
= x-1 for the rest of elements in ‘n’

To construct an invariant subset the ‘k-1’ elements which are identically mapped, and the entirety of the ‘k to n’ elements considered as a unit must be considered. Thus there are total k-1 + 1 elements with which subsets are to be constructed. There are $(2^k$) subsets possible.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s