1.Let n1,and S = . For a function f: , a subset D, is said t be invarient under f , if . 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 : such that deg(f) = 2.

(2)Further show that for any k such that 1 k n ther is a function f: that is deg(f)=.

Solution :Consider the function defined piecewise as f(x) = x – 1 is x () 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 = {)} 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 = {} where ) is the least element of the set

If 1) then -1) is not inside D as ) is the smallest element in D. Hence D is no more an invariant subset which is contrary to our initial assumption.

This ) must equal to 1.

As D is invariant subset ) 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.

(b)

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

f(x) = x for (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 ) subsets possible.