Thank you.
(This looks suspiciously like homework assignment, but you may always
check posting history in order to be convinced otherwise:-)
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.
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.
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.
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.
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).
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.
This was the key to approach my problem. (Is some fancy kind of lattice
theory is complete?) Thank you.
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.
As well as arithmetic without multiplication (Presburger), or
arithmetic without addition, or elementary geometry, but I doubt it
will help the OP ;)
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
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
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