# Find the Fixed points (Knaster-Tarski Theorem)

Let $L=\mathcal P(\mathbb N)$ be a complete lattice of subsets of $\mathbb N$.

a) Justify that the function $F(X)=\mathbb N \setminus X$ does not have a Fixed Point.

I don't know how to solve this.

b) Be $F(X)=\left\{ x+1 \mid x\in X \right\}$. Find the smallest and the greatest Fixed points. (You can start with $\emptyset$ and $\mathbb N$ and see where it goes.)

My Solution:

Here I started like this for the least fixed point: $\emptyset \sqsubseteq F(\emptyset) = \emptyset$ (but this is just assumption, how do I prove this ?)

For greatest Fixed Point I have $\mathbb N \sqsupseteq F(\mathbb N) \sqsupseteq F(F(\mathbb N)) \sqsupseteq \cdots$ (But I can't make a assumption about the greatest fixed point). Which is it and why?

• Can you find any other fixed point, other than $\emptyset$? What would it mean for a non-empty set $X$ to be a fixed point? What do we know about non-empty subsets of $\mathbb N$? Jul 27, 2014 at 12:20
• First question: No i can't find any other except the empty set. second question: It means there is a $x \in X$ so that $F(x)=x$. Third question I am not sure. Jul 27, 2014 at 12:30
• @ThomasAndrews does a greatest fixed point exist ? If it does not exist is it then a $\emptyset$ ? Jul 27, 2014 at 12:40
• If $x\in X$ then $f(x)$ doesn't make sense, because $x$ is a single natural number, and $f$ has subsets of the natural numbers as its domain. Jul 27, 2014 at 12:45
• Where your question says "a complete lattice of a subset", might you have meant "a complete lattice of subsets"? ${}\qquad{}$ Jul 27, 2014 at 13:03

The set $\mathbb N\setminus X$ is the complement of $X$. Its members are precisely those members of $\mathbb N$ that are not members of $X$. A fixed point of the function $X\mapsto N\setminus X$ would be a set that is its own complement. It would satisfy $X=\mathbb N\setminus X$. If the number $1$ is a member of $X$ then $1$ would not be a member of $\mathbb N\setminus X$, since the latter set is the complement of $X$, but if $X=\mathbb N\setminus X$, then the number $1$ being a member of $X$ would mean that $1$ is a member of $\mathbb N\setminus X$. A similar contradiction follows from the assumption that $1$ is not a member of $X$.

The empty set is a fixed point of $X\mapsto \{x+1\mid x\in X\}$. If $X$ is any non-empty set, then $X$ has a smallest member. The smallest member of $X$ is not a member of $\{x+1\mid x\in X\}$. Therefore $X$ is not a fixed point of that function. That function therefore has only one fixed point.

• Thanks I now understand the first one. Jul 27, 2014 at 22:22
• @Devid : Suppose $X=\{15,23,97,245,\ldots\}$ Then $\{x+1\mid x\in X\}=\{16,24,98,246,\ldots\}$. That set cannot be equal to $X$ because $15$ is not a member of that set. That's the argument in my second paragraph. Jul 27, 2014 at 23:00

To justify that a function $f$ does not have a fixed point you have to argue as follows:

Suppose that $X$ was a fixed point of $f$, then $f(X)=X$. But now we have that ...

Where the ellipsis denote the rest of the arguments which you should fill for yourself. (Hint: Consider what is $f$ in this context).

As for the second part, you are right that $\varnothing$ is a fixed point, and therefore the least fixed point. Simply because $\varnothing\subseteq F(\varnothing)$ on one hand, and on the other hand, what is $\{x+1\mid x\in\varnothing\}$?

What is the largest fixed point? Well, here's a hint:

Note that if $A\subseteq\Bbb N$ is non-empty, then $\min A\notin F(A)$.

• Yeah the least fixed point was easy to find, but the largest fixed point is much harder to understand. Jul 27, 2014 at 22:27
• Read the last line again. What can you infer from it? Jul 27, 2014 at 22:28
• but what is $F(A)$ ? I think I understand, there is no minimum, because we added +1. But how will that help me with largest fixed point. Thanks for the helping. Jul 27, 2014 at 22:34
• $F(A)=\{x+1\mid x\in A\}$. It's not that there's no minimum, it just shows that $A\setminus F(A)\neq\varnothing$. What does that tell you? Jul 27, 2014 at 22:35