I have a question regarding Tarski's fixed point theorem. Consider the set $$\mathcal{X}:={0,1}^2:=\{(1,1), (0,1), (1,0), (0,0)\}$$

Consider the vector $X:=(X_1,X_2)$ taking value in $\mathcal{X}$.

Consider the function $h:\mathcal{X}\rightarrow \mathcal{X}$ $$ h:= \begin{cases} X_1:=1\{\epsilon_1+\delta X_2\geq 0\}\\ X_2:=1\{\epsilon_2+\delta X_1\geq 0\} \end{cases} $$ where $1\{\cdot \}$ is the indicator function taking value $1$ if the condition inside is satisfied and $0$ otherwise, $\delta$ is a positive parameter, and $\epsilon_1, \epsilon_2$ are any couple of real numbers.

Tarski's fixed point theorem tells me that, given some $\delta\geq 0, \epsilon_1, \epsilon_2$, the function $h$ has a greatest and a lowest fixed point. Let's call them $X^g, X^l$.

I am confused on the following: we have two elements in $\mathcal{X}$ which cannot be compared, i.e. $(1,0)$ and $(0,1)$. This means that

(A) It cannot be that $X^l=(0,1)$ and $X^u=(1,0)$ or viceversa. Correct?

(B) Other potential fixed points are only the points $X$ such that $X^l\leq X\leq X^u$, i.e., which are comparable with $X^l, X^u$. Correct?


(A) is not correct. The Knaster-Tarski theorem states that the greatest/lowest fixed point are greatest/lowest among fixed points. Take this example

$$f:\mathcal{X}\to\mathcal{X}$$ $$f(0,0)=(0,0)$$ $$f(x,y)=(1,0)\mbox{ otherwise}$$

This function is order preserving and it has two fixed points: $(0,0)$ and $(1,0)$ which are the least and greates respectively among themselves (the set of all fixed points).

(B) is correct.

  • $\begingroup$ Thanks. But in (A) I asked about $(0,1)$ and $(1,0)$. $\endgroup$ – STF Mar 17 '17 at 20:07
  • $\begingroup$ Can these be both fixed points? $\endgroup$ – STF Mar 17 '17 at 20:07
  • 1
    $\begingroup$ @STF Oh, at the same time? They can be fixed (e.g. the identity) but they can't be least and greatest at the same time by (B). $\endgroup$ – freakish Mar 17 '17 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.