Question Corner and Discussion Area

Is there a function f fromYes, there is such a function. All such functions arise through the following type of construction:N(the set of natural numbers) to itself, such that such that f^2 (the composition of f with f) sends every n to n^n?

Let C denote the set {1^1, 2^2, 3^3, ...}. Subdivide the rest of the natural numbers (those that are not in C) into two disjoint sets A and B, in any way you like, except that you need to have infinitely many numbers in each of the two sets. (For example, you could list the numbers that are not in C: 2,3,5,6,7,.... Then let the set A consist of the first number in this list, the third number in this list, and so on, while B consists of the second number in this list, the fourth number in this list, and so on).

Enumerate the numbers in A, calling them a_1, a_2, .... Similarly, enumerate the numbers in B, calling them b_1, b_2, ....

Now define f on the sets A and B by defining f(a_i) = b_i and f(b_i) = a_i^(a_i). (Note that f maps A to B and maps B to C).

Define f on the set C by setting f(1)=1 and, for all n>1, define f(n^n) = f(n)^(f(n)).

If n is in A or B, this definition is well-defined, for we have already defined f(n), and the above formula tells us how to define f(n^n).

If n is in C, the way we make this definition correct is to think of it as an inductive definition: assume we have already defined f(m^m) for all m < n and are now trying to define f(n^n). In the case in which n happens to be in C, that means n=m^m and it is easy to verify that m < n, hence f(m^m) has already been defined, and we get an inductive definition of f(n^n) in terms of it.

The function f has now been defined for all natural numbers. It remains to show that f(f(n))=n^n for all n. There are three cases.

*Case 1*: n is in A. Then n=a_i for some i.
We then have f(f(n)) = f(b_i) = a_i^(a_i) = n^n as required.

*Case 2*: n is in B. Then n=b_i for some i.
We then have f(f(n)) = f(a_i^(a_i)) = f(a_i)^(f(a_i)) =
b_i^(b_i) =
n^n as required.

*Case 3*: To prove that
f(f(n))=n^n for all n in C, suppose to the contrary that there
are some n in C for which f(f(n)) != n^n. Let n=N be the
smallest of these. We know N>1, since f(f(1))=1=1^1.
We also know N is in C, so N = m^m for some m,
and clearly m < N (the only time m = m^m is when m=1, and
we know that our number N is greater then 1).

Either m is in A, or it is in B, or it is in C but is smaller than N, and in all three of these cases we already know f(f(m))=m^m =N. It follows that f(f(N)) = f(f(m^m)) = f(f(m)^(f(m))) = f(f(m))^(f(f(m))) = N^N. This contradicts our choice of N as being the smallest counterexample to f(f(n)) = n^n, showing that no counterexample exists, and hence f has the desired property.

You can also prove that *all* functions with this property
are given by a construction of the above form.
Assume we have such a function f. The first thing to note is
that f must satisfy the property f(n^n) = f(n)^(f(n)) for all n,
since f(n^n) = f(f^2(n)) = f^2(f(n)) = f(n)^(f(n)).

Now, let C be the same set as above, and divide the numbers that are not in C into two classes, A and B, where A is the set of x not in C for which f(x) is not in C, and B is the set of x not in C for which f(x) is in C.

One can prove that f sets up a one-one correspondence from A to B, as follows: if x is in A, we know f(x) is not in C, but f(f(x)) = x^x which is in C, proving that f(x) is in B. This proves that f maps A into B.

This mapping is one-to-one: if f(x)=f(y), then f(f(x))=f(f(y)), so x^x = y^y, and it's easy to verify that for natural numbers this only happens when x=y.

This mapping is onto: every element b in B is obtained as f(a) for some a in A. This is because f(b) is in C, so f(b)=a^a for some a, and b^b = f(f(b)) = f(a^a) = f(a)^(f(a)) from which it follows that b=f(a).

So, if you label the elements of A as a_1, a_2, ... and define b_i = f(a_i), then f is precisely the function defined above, since f(a_i)=b_i (by definition), f(b_i) = f(f(a_i)) = a_i^(a_i) (by the argument of the previous paragraph), and for every element n^n in C, f(n^n) = f(n)^(f(n)). This is precisely the definition given above.

This part of the site maintained by (No Current Maintainers)

Last updated: April 19, 1999

Original Web Site Creator / Mathematical Content Developer: Philip Spencer

Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu

Navigation Panel:

Go backward to Solving a Quadratic with Non-Constant Coefficients

Go up to Question Corner Index

Go forward to Largest Possible Number?

Switch to graphical version (better pictures & formulas)

Access printed version in PostScript format (requires PostScript printer)

Go to University of Toronto Mathematics Network Home Page