Find the Fixed points (Knaster-Tarski Theorem)

Question

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?

Answer 1

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.

Answer 2

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)$.