Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

Login

Username

Password

Not registered yet?

#1 2008-01-21 06:13:44

JaneFairfax
Legendary Member

Offline

Knaster–Tarski theorem

Recently I was stuck on how to to prove the following.



It eventually occurred to me that the problem might have something to do with the theory of posets and functions which preserve order in posets. I already knew something about posets (partially ordered sets). So I looked them up on the Internet – and found that the problem actually had something to do with complete lattices. A complete lattice is a poset in which every subset has a supremum and an infimum. The power set
with the subset order is certainly a complete lattice because if
is a collection of subsets of Q, its supremum is
and its infimum is
. (NB: this applies to the empty collection as well. The supremum of the empty collection is Ø and the infimum of the empty collection is Q.)

I presently found out about the Knaster–Tarski theorem: If L is a complete lattice and f:LL is an order-preserving function, then the set of all fixed points of f is also a complete lattice.

This doesn’t solve the original problem directly, but I sensed that I was on the right track. And then I found this: http://www.cas.mcmaster.ca/~forressa/ac … 1-talk.pdf http://i41.photobucket.com/albums/e271/Carduelis_carduelis/Clapping.gif

So, in the original problem, taking



will do the trick. http://www.clicksmilies.com/s1106/huepfen/jumping-smiley-017.gif

http://www.artofproblemsolving.com/Foru … p?t=183245

Last edited by JaneFairfax (2008-01-21 06:39:07)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

Board footer

Powered by FluxBB