Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Partial order, lattice, and boolean algebra completenness question.

0 views
Skip to first unread message

mikharaki...@yahoo.com

unread,
Mar 29, 2006, 9:06:27 PM3/29/06
to
A theory is called complete if logical implication |- the same as
logical satisfaction |= .
Questions:
- Is partial order theory complete?
- Is lattice theory complete?
- Is boolean algebra complete?

Thank you.

(This looks suspiciously like homework assignment, but you may always
check posting history in order to be convinced otherwise:-)

matt...@dodgeit.com

unread,
Mar 29, 2006, 10:00:03 PM3/29/06
to
mikharaki...@yahoo.com wrote:
> A theory is called complete if logical implication |- the same as
> logical satisfaction |= .
> Questions:
> - Is partial order theory complete?
> - Is lattice theory complete?
> - Is boolean algebra complete?

Any basic text on model theory will answer questions like this. And
the answer to all three is no, if your mean the usual thing by ``T is a
complete theory,'' because there are models with exactly two elements
and models with more than two elements.

It's more interesting to limit the question to infinite posets,
infinite lattices, infinite boolean algebras. Each of these is also an
incomplete theory.

On the subject of complete theories. You may understand what complete
theories are, but your definition won't help anyone else. It's
clearer to say that a theory is complete if every sentence in the
language of of the theory is either provable or disprovable from the
theory.

Every theory has the property that a sentence is provable if and only
if it is satisfied by every model of the theory. Old-school notation
writes T |= S if S holds in every model of T, and T |- S if there is a
deduction of S from T. Godel showed that T |= S if and only if T |- S,
for any theory T and sentence S. So, in my mind, |- is _always_ the
same as |=, in the sense that T |- S if and only if T |= S. That's why
the definition at the top of the quote is questionable.

vc

unread,
Mar 30, 2006, 7:30:34 AM3/30/06
to

matt...@dodgeit.com wrote:
[...]

> Every theory has the property that a sentence is provable if and only
> if it is satisfied by every model of the theory.

So how do you go about proving a Godel sentence which is true but not
provable ?

>
> Old-school notation
> writes T |= S if S holds in every model of T, and T |- S if there is a
> deduction of S from T. Godel showed that T |= S if and only if T |- S,
> for any theory T and sentence S.

What specific Godel proof do you have in mind ? He showed the above
for FOL, not 'for any theory'.

> So, in my mind, |- is _always_ the
> same as |=, in the sense that T |- S if and only if T |= S.

That is obviously not right.

matt...@dodgeit.com

unread,
Mar 30, 2006, 9:20:03 AM3/30/06
to
vc wrote:
> matt...@dodgeit.com wrote:
> [...]
> > Every theory has the property that a sentence is provable if and only
> > if it is satisfied by every model of the theory.
>
> So how do you go about proving a Godel sentence which is true but not
> provable ?

The Godel sentence (of PA, for concreteness) isn't provable in PA and
isn't true in _every_ model of PA. It is true in the standard
model. If it were satisfied by every model of PA, it would be
provable from PA.

> > Old-school notation
> > writes T |= S if S holds in every model of T, and T |- S if there is a
> > deduction of S from T. Godel showed that T |= S if and only if T |- S,
> > for any theory T and sentence S.
> What specific Godel proof do you have in mind ? He showed the above
> for FOL, not 'for any theory'.

Yes, the whole discussion here is for first order logic and first order
semantics.

For any theory T in a first order language, and sentence S in that
language, the following are equivalent:

1. Every model of T satisfies S (first order semantics)

2. There is a proof of S from T (first order provability)

3. The is a finite conjunction T' of axioms in T such that the
implication T' => S is provable in bare first order logic (first order
provability)

Usually (1) is abbreviated T |= S and (2) is abbreviated T |- S.

> > So, in my mind, |- is _always_ the
> > same as |=, in the sense that T |- S if and only if T |= S.
>
> That is obviously not right.

Could you be more specific, since it actually is right? There are a
lot of poor descriptions of this around, especially in expository books
for nonmathematicians, so maybe that's where you got confused.

vc

unread,
Mar 30, 2006, 11:39:25 AM3/30/06
to

matt...@dodgeit.com wrote:
> vc wrote:
> > matt...@dodgeit.com wrote:
> > [...]
> > > Every theory has the property that a sentence is provable if and only
> > > if it is satisfied by every model of the theory.
> >
> > So how do you go about proving a Godel sentence which is true but not
> > provable ?
>
> The Godel sentence (of PA, for concreteness) isn't provable in PA and
> isn't true in _every_ model of PA. It is true in the standard
> model. If it were satisfied by every model of PA, it would be
> provable from PA.

Right.

> For any theory T in a first order language, and sentence S in that
> language, the following are equivalent:
>
> 1. Every model of T satisfies S (first order semantics)
>
> 2. There is a proof of S from T (first order provability)
>
> 3. The is a finite conjunction T' of axioms in T such that the
> implication T' => S is provable in bare first order logic (first order
> provability)

Right.

>
> Usually (1) is abbreviated T |= S and (2) is abbreviated T |- S.
>
> > > So, in my mind, |- is _always_ the
> > > same as |=, in the sense that T |- S if and only if T |= S.
> >
> > That is obviously not right.
>
> Could you be more specific, since it actually is right?

Sorry, I just noticed " |- is _always_ the same as |=, " and jumped
to a wrong conclusion. They (|-, |=) are always the same in the sense
of Godel's completeness theorem, but not in general.

mikharaki...@yahoo.com

unread,
Mar 30, 2006, 12:55:35 PM3/30/06
to

matt...@dodgeit.com wrote:
> mikharaki...@yahoo.com wrote:
> > A theory is called complete if logical implication |- the same as
> > logical satisfaction |= .
> > Questions:
> > - Is partial order theory complete?
> > - Is lattice theory complete?
> > - Is boolean algebra complete?
>
> Any basic text on model theory will answer questions like this. And
> the answer to all three is no, if your mean the usual thing by ``T is a
> complete theory,'' because there are models with exactly two elements
> and models with more than two elements.

It is a pity that it's really challenging to find such a simple answer
in basic introductory text. "The model theory cookbook" -- how about
this title?

Seriously, I'm not sure I understand why restriction on model
cardinality affects completeness. Somebody else mentioned that the
theory of boolean algebras with 2 elements is complete. What about
lattice and posets theories -- are they complete under some conditions?
(I'm interested in finite case with emphasis on lattices).

matt...@dodgeit.com

unread,
Mar 30, 2006, 1:20:32 PM3/30/06
to
mikharaki...@yahoo.com wrote:
> Seriously, I'm not sure I understand why restriction on model
> cardinality affects completeness.

For any finite structure M in a first-order language L (with the true
equality relation as part of the logic) there is a sentence S_M such
that any other structure in the language satisfying S_M is isomorphic
to M. Thus if there are two nonisomorphic finite models of the same
cardinality satisfying a theory T, then T is not complete. And if
there are two models of different cardinalities, one of them finite,
then T is not complete. So it is only useful to talk about
completeness for theories with no finite models at all.

> Somebody else mentioned that the
> theory of boolean algebras with 2 elements is complete. What about
> lattice and posets theories -- are they complete under some conditions?
> (I'm interested in finite case with emphasis on lattices).

There is only one Boolean algebra of cardinality 2, so the theory of
two-element Boolean
algebras is complete. So is the theory of one-element lattices and
one-element posets.
(If you call the powerset of the empty set a Boolean algebra, then
there is a unique one-element Boolean algebra, too.)

There is a well known classification of all finite Boolean algebras
that shows that there is at most one Boolean algebra of each finite
cardinality, up to isomorphism. This is not true for lattices or
posets.

mikharaki...@yahoo.com

unread,
Mar 30, 2006, 3:14:42 PM3/30/06
to
matt...@dodgeit.com wrote:
> Thus if there are two nonisomorphic finite models of the same
> cardinality satisfying a theory T, then T is not complete.

This was the key to approach my problem. (Is some fancy kind of lattice
theory is complete?) Thank you.

matt...@dodgeit.com

unread,
Mar 30, 2006, 3:39:43 PM3/30/06
to

The theory of atomless Boolean algebras does what you want. It can be
shown that this theory has only one isomorphism class of countable
models, and no finite models, and thus it is complete.

Other complete theories include: dense linear ordering without
endpoints and real closed fields.

vc

unread,
Mar 30, 2006, 4:12:18 PM3/30/06
to

matt...@dodgeit.com wrote:
[...]

> Other complete theories include: dense linear ordering without
> endpoints and real closed fields.

As well as arithmetic without multiplication (Presburger), or
arithmetic without addition, or elementary geometry, but I doubt it
will help the OP ;)

hid...@gmail.com

unread,
Mar 30, 2006, 6:17:26 PM3/30/06
to

I suspect there is a subtle misunderstanding here, so let me explain a
bit more what Mikito is asking about. He has defined a domain, the
domain of relations as defined in the relational model for databases,
and two operations over these relations that are generalizations of
operations in the relational algebra, and this domain plus these two
operations satisfy the lattice laws.

The question now is if these laws are complete in the sense that if we
take two expressions e1 and e2 that consists of these two operations
and variables then it holds that e1 = e2 under any interpretation of
these variables iff e1 can be algebraically rewritten to e2 using the
lattice identities.

I hope that clarifies things a bit.

-- Jan Hidders

vc

unread,
Mar 31, 2006, 11:59:25 AM3/31/06
to

I am not sure I understand. Do you mean the OP is interested in Codd's
'relational completenes' (or BP-completeness) rather than in complete
theories in Goedel's sense, or you meant something entirely different
?

It sounded as if he asked about completeness in the last sense of the
word.

>
> -- Jan Hidders

Jan Hidders

unread,
Apr 3, 2006, 4:29:58 AM4/3/06
to

vc wrote:

> hid...@gmail.com wrote:
> >
> > I suspect there is a subtle misunderstanding here, so let me explain a
> > bit more what Mikito is asking about. He has defined a domain, the
> > domain of relations as defined in the relational model for databases,
> > and two operations over these relations that are generalizations of
> > operations in the relational algebra, and this domain plus these two
> > operations satisfy the lattice laws.
> >
> > The question now is if these laws are complete in the sense that if we
> > take two expressions e1 and e2 that consists of these two operations
> > and variables then it holds that e1 = e2 under any interpretation of
> > these variables iff e1 can be algebraically rewritten to e2 using the
> > lattice identities.
> >
> > I hope that clarifies things a bit.
>
> I am not sure I understand. Do you mean the OP is interested in Codd's
> 'relational completenes' (or BP-completeness) rather than in complete
> theories in Goedel's sense, or you meant something entirely different
> ?
>
> It sounded as if he asked about completeness in the last sense of the
> word.

Yes, he is, and so am I. But I wasn't sure that it was clear that:
1) we restrict formulas to equations of the form e1 = e2 where e1 and
e2 consists of the two operations plus variables and
2) derivation is by algebraic rewriting only, so we derive e1 = e2 iff
we can rewrite e1 to e2

-- Jan Hidders

0 new messages