TITLE: Given function π, prove that seg(x) is a well ordered set
QUESTION [2 upvotes]: (ZF) Let $\langle A,\le \rangle$ be a linear ordered set. Let the function $π : \mathscr{P}(A) \to \mathscr{P}(A)$ be defined by:
$$π(X) = \{y ∈ A : \mathrm{seg}(y) \subseteq X\}$$
Prove that $π$ is monotonic and if that $A^*$ is the smallest fixed point of  $π$, then for each $x ∈ A$ the following equivalence holds:
$$x \in A^* \iff \langle \mathrm{seg}(x), {\le} \cap(\mathrm{seg}(x)×\mathrm{seg}(x))\rangle \text{ is a well ordered set}$$
What I have in mind is the following:
To use Tarsky's theorem about fixed points which states that: if π is a monotonic function, defined in P(A),  there exists a point x in P(A) for which π(x)=x.
I will name this point A.
Then if I consider π to be a linear operator, I think that I will have to prove that π preserves the order, namely: π(x)<π(y) for x<y. So in this way I will get π to be an increasing function with lower bound π(A)=A.
Is it correct, can you please help me to solve this problem?
Thank you in advance!

REPLY [1 votes]: To use Tarsky's theorem about fixed points which states that: if π is a monotonic function, defined in P(A), there exists a point x in P(A) for which π(x)=x. I will name this point A.

The problem already gives you $A^*$. It is unclear why you want to introduce another fixed point "A".

Then if I consider π to be a linear operator,

What is a linear operator (in this context)? I usually encounter this when there is a vector space.

I think that I will have to prove that π preserves the order, namely: π(x)<π(y) for x<y. So in this way I will get π to be an increasing function with lower bound π(A)=A.

Let me break down your task for this assignment.

Prove $\pi$ is order-preserving/monotonic i.e. for all $S,T\in\mathscr{P}(A)$, if $S\subseteq T$, then $\pi(S)\subseteq \pi(T)$.
Prove the equivalence "$\iff$" statement assuming $A^*$ is already given. From (1.) and by Tarski's theorem, one already knows $A^*$ exists.

$$x \in A^* \iff \langle \mathrm{seg}(x), {\le} \cap(\mathrm{seg}(x)×\mathrm{seg}(x))\rangle \text{ is a well ordered set}$$
Hints:

$\pi(S)=\{y\in A:\mathrm{seg}(y)\subseteq S\}$ and $\pi(T)=\{y\in A:\mathrm{seg}(y)\subseteq T\}$
$x\in A^*\Leftrightarrow x\in \pi(A^*)$.
For the forward implication, it is enough to show that the sublinear ordered set $\langle A^*, \le... \rangle$ is well ordered. Suppose it is not; by contradiction take a nonempty subset $S$ without a least element. Without loss of generality suppose $S$ is upward closed i.e. if $s\in S$ and $s\le x$ then $x\in S$. Consider the complement $A^*\setminus S$. It can be shown that this complement is a $\pi$-fixed-point resulting in a contradiction to the fact that $A^*$ is the least fixed point.
For the reverse implication, it is enough to show $\mathrm{seg}(x)\subseteq A^*$.
This is straight-forward. Suppose by contradiction it is not true. Then there exists $s<x$ such that $s\notin A^*$. If you take the smallest such $s$, then the contradiction is within reach if you recall $\pi(A^*)=A^*$.
{"set_name": "stack_exchange", "score": 2, "question_id": 3973794}