FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Tarski fixed-point theorem
Post new topic   Reply to topic Page 1 of 1 [15 Posts] View previous topic :: View next topic
Author Message
William Elliot
science forum Guru


Joined: 24 Mar 2005
Posts: 1906

PostPosted: Tue Jul 18, 2006 10:24 am    Post subject: Tarski fixed-point theorem Reply with quote

Tarski fixed-point 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 fixed-point 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
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Tue Jul 18, 2006 11:39 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

William Elliot wrote:
Quote:
Tarski fixed-point 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 fixed-point 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 fixed-point theorem, or the
Knaster-Tarski fixed-point theorem as written up in this
Wikipedia article:

http://en.wikipedia.org/wiki/Knaster-Tarski_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

PostPosted: Tue Jul 18, 2006 12:33 pm    Post subject: Re: Tarski fixed-point theorem Reply with quote

From: Chip Eastham <hardmath@gmail.com>
William Elliot wrote:

Quote:
Tarski fixed-point 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 fixed-point 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/Bourbaki-Witt_theorem
but mostly a repeat of stuff I knew or was discovering.

-- Bourbaki-Witt 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 Bourbaki-Witt 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 non-empty. 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 fixed-point theorem, or the
Knaster-Tarski fixed-point theorem as written up in this
Wikipedia article:

http://en.wikipedia.org/wiki/Knaster-Tarski_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.
Sad 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?

Quote:
regards, chip

----
Back to top
Herman Rubin
science forum Guru


Joined: 25 Mar 2005
Posts: 730

PostPosted: Wed Jul 19, 2006 12:57 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

In article <Pine.BSI.4.58.0607180322250.25941@vista.hevanet.com>,
William Elliot <marsh@hevanet.remove.com> wrote:
Quote:
Tarski fixed-point 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 fixed-point 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)494-6054 FAX: (765)494-0558
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Wed Jul 19, 2006 2:43 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

William Elliot wrote:
Quote:
From: Chip Eastham <hardmath@gmail.com
William Elliot wrote:

Tarski fixed-point 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 fixed-point 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/Bourbaki-Witt_theorem
but mostly a repeat of stuff I knew or was discovering.

-- Bourbaki-Witt 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 Bourbaki-Witt 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 non-empty. 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 fixed-point theorem, or the
Knaster-Tarski fixed-point theorem as written up in this
Wikipedia article:

http://en.wikipedia.org/wiki/Knaster-Tarski_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.
Sad 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 re-examine 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
Fred Galvin
science forum beginner


Joined: 31 Jul 2005
Posts: 21

PostPosted: Wed Jul 19, 2006 8:22 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

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
William Elliot
science forum Guru


Joined: 24 Mar 2005
Posts: 1906

PostPosted: Wed Jul 19, 2006 10:55 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

From: Herman Rubin <hrubin@odds.stat.purdue.edu>
Newsgroups: sci.math
Subject: Re: Tarski fixed-point theorem

Quote:
William Elliot <marsh@hevanet.remove.com> wrote:
Tarski fixed-point 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 fixed-point 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/Bourbaki-Witt_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
William Elliot
science forum Guru


Joined: 24 Mar 2005
Posts: 1906

PostPosted: Wed Jul 19, 2006 11:12 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

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
Fred Galvin
science forum beginner


Joined: 31 Jul 2005
Posts: 21

PostPosted: Wed Jul 19, 2006 4:38 pm    Post subject: Re: Tarski fixed-point theorem Reply with quote

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 fixed-point 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
fixed-point 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 Dedekind-finite
(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
Dedekind-finite, 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
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Wed Jul 19, 2006 6:38 pm    Post subject: Re: Tarski fixed-point theorem Reply with quote

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 non-empty chain, ie. lattice (0,1] has a sup for
every non-empty 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 chain-complete
(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 chain-complete 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 "non-empty chain". For example:

[Posets and Zorn's Lemma]
http://john.fremlin.de/schoolwork/logic/logic/node6.html

Defn. A (non-empty) poset X is chain-complete
if every non-empty chain has a supremum.

regards, chip
Back to top
Fred Galvin
science forum beginner


Joined: 31 Jul 2005
Posts: 21

PostPosted: Wed Jul 19, 2006 8:57 pm    Post subject: Re: Tarski fixed-point theorem Reply with quote

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 non-empty chain, ie. lattice (0,1] has a sup for
every non-empty 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 chain-complete
(every chain has a sup) would require the lattice (or poset) to have
a minimum element.

I don't know about "chain-complete", 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 chain-complete 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 "non-empty chain". For example:

[Posets and Zorn's Lemma]
http://john.fremlin.de/schoolwork/logic/logic/node6.html

Defn. A (non-empty) poset X is chain-complete
if every non-empty chain has a supremum.

What term do they use for the dual notion, "every non-empty chain has
an infimum"? I guess they call that "dually chain-complete"? 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

PostPosted: Thu Jul 20, 2006 2:08 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

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 non-empty chain, ie. lattice (0,1] has a sup for
every non-empty 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 chain-complete
(every chain has a sup) would require the lattice (or poset) to have
a minimum element.

I don't know about "chain-complete", 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 chain-complete 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 chain-complete 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 "non-empty chain". For example:

[Posets and Zorn's Lemma]
http://john.fremlin.de/schoolwork/logic/logic/node6.html

Defn. A (non-empty) poset X is chain-complete
if every non-empty chain has a supremum.

What term do they use for the dual notion, "every non-empty chain has
an infimum"? I guess they call that "dually chain-complete"? 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 chain-complete poset
at least for the non-empty 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 non-empty totally ordered set (chain) is directed.

regards, chip
Back to top
William Elliot
science forum Guru


Joined: 24 Mar 2005
Posts: 1906

PostPosted: Thu Jul 20, 2006 3:55 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

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? Wink
Back to top
William Elliot
science forum Guru


Joined: 24 Mar 2005
Posts: 1906

PostPosted: Thu Jul 20, 2006 10:43 am    Post subject: Re: Tarski fixed-point theorem Reply with quote

From: Butch Malahide <fred.galvin@gmail.com>
Newsgroups: sci.math
Subject: Re: Tarski fixed-point theorem

Quote:
You mean, how does he use a fixed-point 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
fixed-point 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 Dedekind-finite (I think this is possible),
then every chain in B is finite.

Dedekind-finite? Never hear that word.
Dedekind complete is same as bounded complete,
every bounded nonnul set has inf, sup.

Quote:
Is B complete?

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
Dedekind-finite, 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
Herman Rubin
science forum Guru


Joined: 25 Mar 2005
Posts: 730

PostPosted: Thu Jul 20, 2006 5:58 pm    Post subject: Re: Tarski fixed-point theorem Reply with quote

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 fixed-point theorem

You mean, how does he use a fixed-point 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
fixed-point 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)494-6054 FAX: (765)494-0558
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [15 Posts] View previous topic :: View next topic
The time now is Fri Nov 24, 2017 2:34 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Uniform point picking on a hexagon, exluding a disc Olw Math 3 Wed Jul 19, 2006 9:21 pm
No new posts Point Defects in Emergent Vacuum ODLRO Geometrodynamics Jack Sarfatti Math 0 Tue Jul 18, 2006 10:52 pm
No new posts Quasi chinese remainder theorem cliomseerg@kriocoucke.mai Math 2 Mon Jul 17, 2006 1:22 pm
No new posts *unique* prime factorizations; the fundamental theorem of... DGoncz@aol.com Math 5 Sun Jul 16, 2006 9:53 am
No new posts Another nice mean value like theorem eugene Math 3 Wed Jul 12, 2006 3:09 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0379s ][ Queries: 16 (0.0038s) ][ GZIP on - Debug on ]