2
$\begingroup$

According to Tarski's Fixpoint Theorem for lattices, if I have a complete lattice, $L$, and an order-preserving function, $f:L \to L$, then the set of all fixpoints of $L$ is also a complete lattice.

Now in my case I have a complete lattice that is just a powerset under inclusion. So $\vee := \cup$ and $\wedge:= \cap$. I also have an order-preserving function, so it seems to me that the set of all fixpoints also forms a complete lattice. The issue is that the set of fixpoints is not closed under $\cup$ and $\cap$, so I am struggling to see how the set of fixpoints is a lattice with the same $\vee$ and $\wedge$ as before, as they are no longer binary operations. Don't $\wedge$ and $\vee$ have to return an element in the set in order to be a lattice?

So through Tarski's theorem, are the join and meet on the set of fixpoints not necessarily the same as the join and meet on the original lattice? This seems strange since the function preserves order and the order defines the join and meet I thought. If an order-preserving function does preserve the join and meet, then why does Tarski's theorem "fail" here?

$\endgroup$
2
$\begingroup$

So through Tarski's theorem, are the join and meet on the set of fixpoints not necessarily the same as the join and meet on the original lattice?

Yes, this is exactly what's going on. Let $P$ denote a poset and $f$ denote an endomorphism of $P$. Then:

  1. The fixed points $\mathrm{Fix}(f)$ form a subset of $P$.
  2. Hence $\mathrm{Fix}(f)$ forms a subposet in a canonical way.
  3. If the poset $P$ happens to be a complete lattice, then the poset $\mathrm{Fix}(f)$ will also happen to be a complete lattice, by Knaster-Tarski. But it needn't be a sublattice of the original lattice.

This occurs because order-embeddings between posets needn't preserve meets or joins. Also interesting to note that just because an order-embedding preserves one of meets/joins, does not mean it preserves the other!

This seems strange since the function preserves order and the order defines the join and meet I thought.

Yep; definability does not imply preserved under homomorphism.

$\endgroup$
  • $\begingroup$ Huh. This is quite interesting. Is there any general way to deduce the order or the join and meet? I have definitions of what I want my join and meet to be but am struggling to prove the associativity of meet. I was hoping to use Tarski to avoid having to do that. Now it seems that Tarski assures my set is a complete lattice (which was obviously my suspicion), but now I am still left with the task of defining the join and meet. $\endgroup$ – Ebearr Sep 30 '14 at 20:38
  • $\begingroup$ @Ebearr, pretty sure that if $f$ is a closure operator, then arbitrary meets in $\mathrm{Fix}(f)$ will coincide with intersections. Are you finding that's not the case? Also, meets are associative in any lattice. $\endgroup$ – goblin Sep 30 '14 at 20:44
  • $\begingroup$ Yes, I actually just found a counterexample to my $f$ being a closure operator, so I shall remove that part of my questions. I know that meets are associative, but all that Tarski gives me is that my set is a lattice right? So I need to find my meet and join, correct? I know what I want them to be, I just haven't proven that the desired meet is in fact associative. $\endgroup$ – Ebearr Sep 30 '14 at 20:48
  • $\begingroup$ @Ebearr, I'm not sure I understand you. Meets, when they exist, are uniquely determined by the structure of the poset; you don't get to choose them. The meet of $x,y \in F$ is a special entity $x \wedge y \in F$ with the following important property: $a \leq x \wedge y$ iff $a \leq x$ and $a \leq y,$ for all $a \in F$. This determines $x \wedge y$ uniquely, if it exists. Now if $x \wedge y$ exists for all $x,y \in F$, like in the case you're dealing with, then this is equivalent to saying that $\wedge$ is a total function $F \times F \rightarrow F,$ in which it is necessarily associative. $\endgroup$ – goblin Sep 30 '14 at 20:54
  • $\begingroup$ Ah, I think I see now. I believe I was getting confused that meet and join no longer correspond to union and intersection. Now instead of thinking of them as union and intersection, I need to revert back to their definition as simply $\sup$ and $\inf$. I have ordered Davey and Priestly's Introduction to Lattices and Order as well as one of Gratzer's books. Hopefully they will help! This has been most enlightening. I really appreciate your help! $\endgroup$ – Ebearr Sep 30 '14 at 21:40

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.