Re: What is This Set Called?

On Tue, 14 Jun 2005 roddleeh@xxxxxxx wrote:

> Let S be a finite set, and let f:S-->S be a function. Then consider the
> sequence of sets S, f(S), f(f(S)), f(f(f(S))), f(f(f(f(S))))...
> Call the intersection of all of these X. X has the interesting property
> that it is the largest subset of S on which f is a permutation. Does X
> have a name? If so, what is X called?
>
The fixed set of f.

A = /\_j f^j(S), j = 0,1,..
As f^j(S) is a descending nest of sets
when S is finite, at some point n,
f^j(S) = f^n(S) for all j >= n
A = f^n(S); f(A) = ff^n(S) = f^n(S) = A

--
f(A) = f(/\_j f^j(S)) subset /\_j f^(j+1)(S) = S /\ /\_j f^(j+1)(S) = A

Why is A subset f(A) ? Is there a counter example when S is infinite?

Nulset is a fixed set of f. The set of fixed points is a fixed set.
The union of any collection of fixed sets is a fixed set.
Every fixed set is a subset of A.

Now as f:P(S) -> P(S) is an ascending function on a complete lattice
the Knaster-Tarski theorem shows that the largest fixed set for f is
\/{ U | U subset f(U) }

----
.