Author 
Message 
Herman Rubin science forum Guru
Joined: 25 Mar 2005
Posts: 730

Posted: Thu Jul 20, 2006 5:58 pm Post subject:
Re: Tarski fixedpoint theorem



In article <Pine.BSI.4.58.0607200340470.26041@vista.hevanet.com>,
William Elliot <marsh@hevanet.remove.com> wrote:
Quote:  From: Butch Malahide <fred.galvin@gmail.com
Newsgroups: sci.math
Subject: Re: Tarski fixedpoint theorem
You mean, how does he use a fixedpoint theorem in a proof of the
theorem "a lattice is complete if every chain has a sup"? You would
have to ask him. The proof I'm familiar with does not use any
fixedpoint theorem, though it does use the axiom of choice, and I
don't think you can prove it in ZF.
Assume lattice L with a sup for every chain.
bottom = sup nulset in L; L nonnul
top in L. Otherwise, for all x in L, some a_x not <= x
Let f(x) = lub(x, a_x); for all x, x <= f(x)
As every chain has sup, apply fixed point theorem
some x with x = f(x) = lub(x, a_x); a_x <= x, no!
The fixed point theorem doesn't require AxC but it does require
existence of ordinals with cardinality greater than the lattice.
Does the existence of such ordinals require AxC or well ordering?

See my earlier comment; as posted, it requires nothing
beyond ZF. One does not need a cardinality greater than
that of the lattice, but one which is not less than or
equal to that of the lattice, and this is Hartogs'
construction.

This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)4946054 FAX: (765)4940558 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Thu Jul 20, 2006 10:43 am Post subject:
Re: Tarski fixedpoint theorem



From: Butch Malahide <fred.galvin@gmail.com>
Newsgroups: sci.math
Subject: Re: Tarski fixedpoint theorem
Quote:  You mean, how does he use a fixedpoint theorem in a proof of the
theorem "a lattice is complete if every chain has a sup"? You would
have to ask him. The proof I'm familiar with does not use any
fixedpoint theorem, though it does use the axiom of choice, and I
don't think you can prove it in ZF.

Assume lattice L with a sup for every chain.
bottom = sup nulset in L; L nonnul
top in L. Otherwise, for all x in L, some a_x not <= x
Let f(x) = lub(x, a_x); for all x, x <= f(x)
As every chain has sup, apply fixed point theorem
some x with x = f(x) = lub(x, a_x); a_x <= x, no!
The fixed point theorem doesn't require AxC but it does require
existence of ordinals with cardinality greater than the lattice.
Does the existence of such ordinals require AxC or well ordering?
Assume A subset L;
Let B = below A = { x  x <= A } = { x  x lower bound A }
bottom in B; assume C chain within B, sup C not in B
some a in A with not sup C <= a
C <= glb(a, sup C); sup C <= glb(a, sup C) <= a, no!
for all chains C subset B, sup C in B.
From above, top_B in B. top_B = inf B
Thus L is a complete lattice. Fanstastic theorem. Any others?

Quote:  Let B be the Boolean algebra of all finite and cofinite subsets of
some infinite set S. Every finite chain in B has a sup and an inf.

Let B = P(N)
Quote:  Are there any infinite chains? Not necessarily, I think.

Yes, Aj = [1,j] /\ N, j in N
Quote:  At any rate, every chain in B is countable;

Likely.
Quote:  if B happens to be Dedekindfinite (I think this is possible),
then every chain in B is finite.

Dedekindfinite? Never hear that word.
Dedekind complete is same as bounded complete,
every bounded nonnul set has inf, sup.
No. Cj = { 2n  n in [0,j] /\ N }. sup{ Cj  j in N } ??
Quote:  Could be, I guess; but not if S can be partitioned into two
infinite sets. OK, let T be some infinite set such that P(T) is
Dedekindfinite, let S = T x {0,1}, and let B = {X subset S: X is
finite or cofinite}; every chain in B is finite and has a sup and an
inf, but B is not complete.

Ok
 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Thu Jul 20, 2006 3:55 am Post subject:
Re: Tarski fixedpoint theorem



On Wed, 19 Jul 2006, Butch Malahide wrote:
Quote:  William Elliot wrote:
From: Chip Eastham <hardmath@gmail.com
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.
Does (0,1] dissuade you of such notion?
Are you trying to say that the lattice (0,1] has a sup for every chain?
Two questions: Is the empty set a chain? What is its sup?
No problem. {1} \/ (0,1] is a counter example, is it not? 


Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Thu Jul 20, 2006 2:08 am Post subject:
Re: Tarski fixedpoint theorem



Butch Malahide wrote:
Quote:  Chip Eastham wrote:
I don't consider the empty set a chain, at least in this context.
Birkhoff's "Lattice Theory", 2nd ed., p. 10: "Clearly any subset of a
chain is a chain; so is the dual of any chain." I would have thought
"any subset" would include the empty set.

Certainly a reasonable definition.
Quote:  If it would make things clearer, we should perhaps give the
qualification nonempty chain, ie. lattice (0,1] has a sup for
every nonempty chain. A chain is simply a totally ordered
subset of the lattice (or more generally, of a poset).
Of course if the "empty chain" is allowed, then chaincomplete
(every chain has a sup) would require the lattice (or poset) to have
a minimum element.
I don't know about "chaincomplete", but the standard definition of
"complete lattice" definitely requires it to have a greatest element
and a least element.

Yes, a complete lattice has a sup and inf for every subset, and a
greatest and least element in particular. A chaincomplete lattice
is more general.
Quote:  But according to the terminology defined here:
http://en.wikipedia.org/wiki/Completeness_(order_theory)
suggests that this is not the convention, since (for example)
directed subsets are intended to generalize chains, but are
not allowed to be empty, and a "directed complete partial
order" (dcpo) which happens to have a least element is
termed a "pointed dcpo" or "complete partial order". Note
in particular the statement there:
"The following equivalence requires the Axiom of Choice:
A poset is chaincomplete if and only if it is a dcpo."
A Google search for "empty chain" in connection with
lattice or poset turned up mostly its appearance as the
tail end of "nonempty chain". For example:
[Posets and Zorn's Lemma]
http://john.fremlin.de/schoolwork/logic/logic/node6.html
Defn. A (nonempty) poset X is chaincomplete
if every nonempty chain has a supremum.
What term do they use for the dual notion, "every nonempty chain has
an infimum"? I guess they call that "dually chaincomplete"? They can
define their terms however they want to, but it sounds a bit awkward to
me.

The Wikipedia article describes the dual of a directed complete
poset as a filtered complete poset, but notes that this notion
is not much used. As above the Axiom of Choice implies
directed complete poset is equivalent to chaincomplete poset
at least for the nonempty chain has a sup definition.
http://en.wikipedia.org/wiki/Directed_set
Subset A of a poset is directed iff:
A is not the empty set.
For any a,b in A, there exists c in A s.t. a,b <= c.
Clearly any nonempty totally ordered set (chain) is directed.
regards, chip 

Back to top 


Fred Galvin science forum beginner
Joined: 31 Jul 2005
Posts: 21

Posted: Wed Jul 19, 2006 8:57 pm Post subject:
Re: Tarski fixedpoint theorem



Chip Eastham wrote:
Quote: 
I don't consider the empty set a chain, at least in this context.

Birkhoff's "Lattice Theory", 2nd ed., p. 10: "Clearly any subset of a
chain is a chain; so is the dual of any chain." I would have thought
"any subset" would include the empty set.
Quote:  If it would make things clearer, we should perhaps give the
qualification nonempty chain, ie. lattice (0,1] has a sup for
every nonempty chain. A chain is simply a totally ordered
subset of the lattice (or more generally, of a poset).
Of course if the "empty chain" is allowed, then chaincomplete
(every chain has a sup) would require the lattice (or poset) to have
a minimum element.

I don't know about "chaincomplete", but the standard definition of
"complete lattice" definitely requires it to have a greatest element
and a least element.
Quote:  But according to the terminology defined here:
http://en.wikipedia.org/wiki/Completeness_(order_theory)
suggests that this is not the convention, since (for example)
directed subsets are intended to generalize chains, but are
not allowed to be empty, and a "directed complete partial
order" (dcpo) which happens to have a least element is
termed a "pointed dcpo" or "complete partial order". Note
in particular the statement there:
"The following equivalence requires the Axiom of Choice:
A poset is chaincomplete if and only if it is a dcpo."
A Google search for "empty chain" in connection with
lattice or poset turned up mostly its appearance as the
tail end of "nonempty chain". For example:
[Posets and Zorn's Lemma]
http://john.fremlin.de/schoolwork/logic/logic/node6.html
Defn. A (nonempty) poset X is chaincomplete
if every nonempty chain has a supremum.

What term do they use for the dual notion, "every nonempty chain has
an infimum"? I guess they call that "dually chaincomplete"? They can
define their terms however they want to, but it sounds a bit awkward to
me. 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Wed Jul 19, 2006 6:38 pm Post subject:
Re: Tarski fixedpoint theorem



William Elliot wrote:
Quote:  On Wed, 19 Jul 2006, Butch Malahide wrote:
William Elliot wrote:
From: Chip Eastham <hardmath@gmail.com
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.
Does (0,1] dissuade you of such notion?
Are you trying to say that the lattice (0,1] has a sup for every chain?
Two questions: Is the empty set a chain? What is its sup?
Oh, what effect then does this have upon Chip's comments of his preceeding
paragraph?

I don't consider the empty set a chain, at least in this context.
If it would make things clearer, we should perhaps give the
qualification nonempty chain, ie. lattice (0,1] has a sup for
every nonempty chain. A chain is simply a totally ordered
subset of the lattice (or more generally, of a poset).
Of course if the "empty chain" is allowed, then chaincomplete
(every chain has a sup) would require the lattice (or poset) to have
a minimum element.
But according to the terminology defined here:
http://en.wikipedia.org/wiki/Completeness_(order_theory)
suggests that this is not the convention, since (for example)
directed subsets are intended to generalize chains, but are
not allowed to be empty, and a "directed complete partial
order" (dcpo) which happens to have a least element is
termed a "pointed dcpo" or "complete partial order". Note
in particular the statement there:
"The following equivalence requires the Axiom of Choice:
A poset is chaincomplete if and only if it is a dcpo."
A Google search for "empty chain" in connection with
lattice or poset turned up mostly its appearance as the
tail end of "nonempty chain". For example:
[Posets and Zorn's Lemma]
http://john.fremlin.de/schoolwork/logic/logic/node6.html
Defn. A (nonempty) poset X is chaincomplete
if every nonempty chain has a supremum.
regards, chip 

Back to top 


Fred Galvin science forum beginner
Joined: 31 Jul 2005
Posts: 21

Posted: Wed Jul 19, 2006 4:38 pm Post subject:
Re: Tarski fixedpoint theorem



William Elliot wrote:
Quote:  On Wed, 19 Jul 2006, Butch Malahide wrote:
William Elliot wrote:
From: Chip Eastham <hardmath@gmail.com
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.
Does (0,1] dissuade you of such notion?
Are you trying to say that the lattice (0,1] has a sup for every chain?
Two questions: Is the empty set a chain? What is its sup?
Oh, what effect then does this have upon Chip's comments of his preceeding
paragraph?

You mean, how does he use a fixedpoint theorem in a proof of the
theorem "a lattice is complete if every chain has a sup"? You would
have to ask him. The proof I'm familiar with does not use any
fixedpoint theorem, though it does use the axiom of choice, and I
don't think you can prove it in ZF.
Let's see. Let B be the Boolean algebra of all finite and cofinite
subsets of some infinite set S. Every finite chain in B has a sup and
an inf. Are there any infinite chains? Not necessarily, I think. At any
rate, every chain in B is countable; if B happens to be Dedekindfinite
(I think this is possible), then every chain in B is finite. Is B
complete? Could be, I guess; but not if S can be partitioned into two
infinite sets. OK, let T be some infinite set such that P(T) is
Dedekindfinite, let S = T x {0,1}, and let B = {X subset S: X is
finite or cofinite}; every chain in B is finite and has a sup and an
inf, but B is not complete. 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Wed Jul 19, 2006 11:12 am Post subject:
Re: Tarski fixedpoint theorem



On Wed, 19 Jul 2006, Butch Malahide wrote:
Quote:  William Elliot wrote:
From: Chip Eastham <hardmath@gmail.com
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.
Does (0,1] dissuade you of such notion?
Are you trying to say that the lattice (0,1] has a sup for every chain?
Two questions: Is the empty set a chain? What is its sup?
Oh, what effect then does this have upon Chip's comments of his preceeding 
paragraph? 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Wed Jul 19, 2006 10:55 am Post subject:
Re: Tarski fixedpoint theorem



From: Herman Rubin <hrubin@odds.stat.purdue.edu>
Newsgroups: sci.math
Subject: Re: Tarski fixedpoint theorem
Quote:  William Elliot <marsh@hevanet.remove.com> wrote:
Tarski fixedpoint theorem
nonnul (partially) ordered S,
f:S > S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
What can be proved with Tarski's fixedpoint theorem
AxC, Zorn's lemma, Kuratowski's lemma,
Hausdorff maximality theorem, well ordering?
All or none, no doubt, as they're all equivalent. Which would be
the easiest to prove with Tarski's theorem? Any hints or is
Tarski's theorem actually weaker than AxC?
As you stated it, the theorem is true in ZF with no
further assumptions.
Proof: Let x_0 be an element of S. For each ordinal
alpha > 0, let x_alpha = f(sup{x_beta : beta < alpha}).
By transfinite induction, the x_beta form a chain, and
hence x_alpha can be defined for alpha as far as we want.
But this gets us past the cardinality of S, by Hartogs'
lemma. Hence, f(x_alpha) is eventually constant.

Oh, wake up, it's weaker than AxC.
Why did I think that proof needed AxC?
Quote:  Using the choice function f assumed, one can use this
to prove the others from AC.

http://en.wikipedia.org/wiki/BourbakiWitt_theorem
showed how to prove Zorn's lemma from AxC and that theorem.
How about well ordering from AxC? Does the theorem
make it any easier to prove well ordering from AxC?
Any pointers or is there better way?
 

Back to top 


Fred Galvin science forum beginner
Joined: 31 Jul 2005
Posts: 21

Posted: Wed Jul 19, 2006 8:22 am Post subject:
Re: Tarski fixedpoint theorem



William Elliot wrote:
Quote:  From: Chip Eastham <hardmath@gmail.com
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.
Does (0,1] dissuade you of such notion?

Are you trying to say that the lattice (0,1] has a sup for every chain?
Two questions: Is the empty set a chain? What is its sup? 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Wed Jul 19, 2006 2:43 am Post subject:
Re: Tarski fixedpoint theorem



William Elliot wrote:
Quote:  From: Chip Eastham <hardmath@gmail.com
William Elliot wrote:
Tarski fixedpoint theorem
nonnul (partially) ordered S,
f:S > S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
What can be proved with Tarski's fixedpoint theorem
AxC, Zorn's lemma, Kuratowski's lemma,
Hausdorff maximality theorem, well ordering?
All or none, no doubt, as they're all equivalent. Which would be
the easiest to prove with Tarski's theorem? Any hints or is
Tarski's theorem actually weaker than AxC?
Can you give a citation for this result?
In my attempts to prove 'Tarski's Theorem' implies AxC, doubts aroused.
There is no indication that 'Tarski's Theorem' implies AxC in
http://en.wikipedia.org/wiki/BourbakiWitt_theorem
but mostly a repeat of stuff I knew or was discovering.
 BourbakiWitt theorem
for a chain complete poset X, and
f : X to X
f (x) geq x,
f has a fixed point. Such a function f is called inflationary.
Proof
Pick some y in X . Define a function K recursively on the ordinals as
follows:
K(0) = y
K(a + ) = f(K(a)).
If b is a limit ordinal, then by construction
{ K( alpha ) : alpha < beta }
is a chain in X. Define
K( beta ) = sup { K( alpha ) : alpha < beta }.
This is now an increasing function from the ordinals into X. It cannot
be strictly increasing, as if it were we would have an injective
function from the ordinals into a set, violating Hartogs' lemma.
Therefore the function must be eventually constant, so for some
alpha , K( alpha^+ ) = K ( alpha );
that is,
f(K(a)) = K(a).
So letting
x = K(a),
we have our desired fixed point. Q.E.D.
Applications
The BourbakiWitt theorem has various important applications. One of
the most common is in the proof that the axiom of choice implies
Zorn's lemma. We first prove it for the case where X is chain
complete and has no maximal element. Let g be a choice function on
P(X)  { varnothing }.
Define a function
f : X to X
by
f(x) = g( { y : y > x } ).
This is allowed as, by assumption, the set is nonempty. Then f(x)
x, so f is an inflationary function with no fixed point, contradicting
the theorem.
This special case of Zorn's lemma is then used to prove the
Hausdorff maximality principle, that every poset has a maximal
chain, which is easily seen to be equivalent to Zorn's Lemma.

The descriptions of Tarski's fixedpoint theorem, or the
KnasterTarski fixedpoint theorem as written up in this
Wikipedia article:
http://en.wikipedia.org/wiki/KnasterTarski_theorem
require that S is a complete lattice. Bronislaw Knaster's
association with this result seems to be having proved
and used it for the lattice of subsets of a set (power set).
However you ask about partially ordered S with a least
upper bound (sup) for every chain.
A "converse" was proved by Anne C. Davis in 1955 (see
link in above article to Project Euclid downloadable PDF)
Posh, I can't PDF.
Homeland security revoked my licence for forbidden knowledge ;)
that any lattice S with the property that every increasing
function on S has a fixed point must be complete. This
answered a question raised by Tarski himself.
Fantastic.
I've seen converses like this before, but not as striking.
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.

William: Does (0,1] dissuade you of such notion?
Yes, your crisp counterexample quickly dissuaded me,
but I had to get back to my laptop (source of forbidden
knowledge) to reexamine the statement of Anne Davis's
result. She shows that the lattice is complete if (and
only if) every increasing function has a fixed point.
The crucial distinction that I stumbled over is between
an increasing function:
x <= y implies f(x) <= f(y) for all x,y
and an "inflationary" function:
x <= f(x) for all x
Actually Davis merely cites Birkoff's reference work,
Lattice Theory, for the proposition that in a complete
lattice every increasing function has a fixed point.
She concentrates on the converse of that, so it is
not quite a converse to Tarski's theorem as the
Wikipedia discussion might suggest.
regards, chip 

Back to top 


Herman Rubin science forum Guru
Joined: 25 Mar 2005
Posts: 730

Posted: Wed Jul 19, 2006 12:57 am Post subject:
Re: Tarski fixedpoint theorem



In article <Pine.BSI.4.58.0607180322250.25941@vista.hevanet.com>,
William Elliot <marsh@hevanet.remove.com> wrote:
Quote:  Tarski fixedpoint theorem
nonnul (partially) ordered S,
f:S > S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
What can be proved with Tarski's fixedpoint theorem
AxC, Zorn's lemma, Kuratowski's lemma,
Hausdorff maximality theorem, well ordering?
All or none, no doubt, as they're all equivalent. Which would be the
easiest to prove with Tarski's theorem? Any hints or is Tarski's theorem
actually weaker than AxC?

As you stated it, the theorem is true in ZF with no
further assumptions.
Proof: Let x_0 be an element of S. For each ordinal
alpha > 0, let x_alpha = f(sup{x_beta : beta < alpha}).
By transfinite induction, the x_beta form a chain, and
hence x_alpha can be defined for alpha as far as we want.
But this gets us past the cardinality of S, by Hartogs'
lemma. Hence, f(x_alpha) is eventually constant.
Using the choice function f assumed, one can use this
to prove the others from AC.

This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)4946054 FAX: (765)4940558 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Tue Jul 18, 2006 12:33 pm Post subject:
Re: Tarski fixedpoint theorem



From: Chip Eastham <hardmath@gmail.com>
William Elliot wrote:
Quote:  Tarski fixedpoint theorem
nonnul (partially) ordered S,
f:S > S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
What can be proved with Tarski's fixedpoint theorem
AxC, Zorn's lemma, Kuratowski's lemma,
Hausdorff maximality theorem, well ordering?
All or none, no doubt, as they're all equivalent. Which would be
the easiest to prove with Tarski's theorem? Any hints or is
Tarski's theorem actually weaker than AxC?
Can you give a citation for this result?

In my attempts to prove 'Tarski's Theorem' implies AxC, doubts aroused.
There is no indication that 'Tarski's Theorem' implies AxC in
http://en.wikipedia.org/wiki/BourbakiWitt_theorem
but mostly a repeat of stuff I knew or was discovering.
 BourbakiWitt theorem
for a chain complete poset X, and
f : X to X
f (x) geq x,
f has a fixed point. Such a function f is called inflationary.
Proof
Pick some y in X . Define a function K recursively on the ordinals as
follows:
K(0) = y
K(a + ) = f(K(a)).
If b is a limit ordinal, then by construction
{ K( alpha ) : alpha < beta }
is a chain in X. Define
K( beta ) = sup { K( alpha ) : alpha < beta }.
This is now an increasing function from the ordinals into X. It cannot
be strictly increasing, as if it were we would have an injective
function from the ordinals into a set, violating Hartogs' lemma.
Therefore the function must be eventually constant, so for some
alpha , K( alpha^+ ) = K ( alpha );
that is,
f(K(a)) = K(a).
So letting
x = K(a),
we have our desired fixed point. Q.E.D.
Applications
The BourbakiWitt theorem has various important applications. One of
the most common is in the proof that the axiom of choice implies
Zorn's lemma. We first prove it for the case where X is chain
complete and has no maximal element. Let g be a choice function on
P(X)  { varnothing }.
Define a function
f : X to X
by
f(x) = g( { y : y > x } ).
This is allowed as, by assumption, the set is nonempty. Then f(x) >
x, so f is an inflationary function with no fixed point, contradicting
the theorem.
This special case of Zorn's lemma is then used to prove the
Hausdorff maximality principle, that every poset has a maximal
chain, which is easily seen to be equivalent to Zorn's Lemma.

Quote:  The descriptions of Tarski's fixedpoint theorem, or the
KnasterTarski fixedpoint theorem as written up in this
Wikipedia article:
http://en.wikipedia.org/wiki/KnasterTarski_theorem
require that S is a complete lattice. Bronislaw Knaster's
association with this result seems to be having proved
and used it for the lattice of subsets of a set (power set).
However you ask about partially ordered S with a least
upper bound (sup) for every chain.
A "converse" was proved by Anne C. Davis in 1955 (see
link in above article to Project Euclid downloadable PDF)

Posh, I can't PDF.
Homeland security revoked my licence for forbidden knowledge ;)
Quote:  that any lattice S with the property that every increasing
function on S has a fixed point must be complete. This
answered a question raised by Tarski himself.

Fantastic.
I've seen converses like this before, but not as striking.
Quote:  Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice.

Does (0,1] dissuade you of such notion?
Quote:  This is starting to sound like
Zorn's lemma, albeit for lattices rather than partial orders.

A long time ago on sci.math it was claimed "Tarski's Theorem"
implied Zorn's lemma. Tarski's Theorem for complete lattices can
be proven without AxC. Thus for it or Davis' converse to imply
AxC, is not immediate. Does Davis avoid AxC and equivalents?
 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Tue Jul 18, 2006 11:39 am Post subject:
Re: Tarski fixedpoint theorem



William Elliot wrote:
Quote:  Tarski fixedpoint theorem
nonnul (partially) ordered S,
f:S > S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
What can be proved with Tarski's fixedpoint theorem
AxC, Zorn's lemma, Kuratowski's lemma,
Hausdorff maximality theorem, well ordering?
All or none, no doubt, as they're all equivalent. Which would be the
easiest to prove with Tarski's theorem? Any hints or is Tarski's theorem
actually weaker than AxC?

Hi, William:
Can you give a citation for this result?
The descriptions of Tarski's fixedpoint theorem, or the
KnasterTarski fixedpoint theorem as written up in this
Wikipedia article:
http://en.wikipedia.org/wiki/KnasterTarski_theorem
require that S is a complete lattice. Bronislaw Knaster's
association with this result seems to be having proved
and used it for the lattice of subsets of a set (power set).
However you ask about partially ordered S with a least
upper bound (sup) for every chain.
A "converse" was proved by Anne C. Davis in 1955 (see
link in above article to Project Euclid downloadable PDF)
that any lattice S with the property that every increasing
function on S has a fixed point must be complete. This
answered a question raised by Tarski himself.
Davis's result in combination of with the "Tarski theorem"
you would then imply that any lattice with a sup for every
chain is a complete lattice. This is starting to sound like
Zorn's lemma, albeit for lattices rather than partial orders.
regards, chip 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Tue Jul 18, 2006 10:24 am Post subject:
Tarski fixedpoint theorem



Tarski fixedpoint theorem
nonnul (partially) ordered S,
f:S > S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
What can be proved with Tarski's fixedpoint theorem
AxC, Zorn's lemma, Kuratowski's lemma,
Hausdorff maximality theorem, well ordering?
All or none, no doubt, as they're all equivalent. Which would be the
easiest to prove with Tarski's theorem? Any hints or is Tarski's theorem
actually weaker than AxC?
 

Back to top 


Google


Back to top 



The time now is Wed Jun 20, 2018 1:06 pm  All times are GMT

