2
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ 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$? $\endgroup$ Commented Jul 27, 2014 at 12:20
  • $\begingroup$ 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. $\endgroup$
    – Devid
    Commented Jul 27, 2014 at 12:30
  • $\begingroup$ @ThomasAndrews does a greatest fixed point exist ? If it does not exist is it then a $\emptyset$ ? $\endgroup$
    – Devid
    Commented Jul 27, 2014 at 12:40
  • $\begingroup$ 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. $\endgroup$ Commented Jul 27, 2014 at 12:45
  • 1
    $\begingroup$ Where your question says "a complete lattice of a subset", might you have meant "a complete lattice of subsets"? ${}\qquad{}$ $\endgroup$ Commented Jul 27, 2014 at 13:03

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks I now understand the first one. $\endgroup$
    – Devid
    Commented Jul 27, 2014 at 22:22
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jul 27, 2014 at 23:00
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Yeah the least fixed point was easy to find, but the largest fixed point is much harder to understand. $\endgroup$
    – Devid
    Commented Jul 27, 2014 at 22:27
  • $\begingroup$ Read the last line again. What can you infer from it? $\endgroup$
    – Asaf Karagila
    Commented Jul 27, 2014 at 22:28
  • $\begingroup$ 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. $\endgroup$
    – Devid
    Commented Jul 27, 2014 at 22:34
  • 1
    $\begingroup$ $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? $\endgroup$
    – Asaf Karagila
    Commented Jul 27, 2014 at 22:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .