Re: FO logic without equality
- From: David C. Ullrich <ullrich@xxxxxxxxxxxxxxxx>
- Date: Tue, 30 May 2006 17:51:21 -0500
On Tue, 30 May 2006 17:28:39 +0200, Jan Burse <janburse@xxxxxxxxxxx>
wrote:
Hi
Li Yi wrote:
Suppose L is an FO language without equality.
S is a set of L-sentences.
Use Compactness Theorem to show that
if S is satisfiable then it has an
infinite model.
There is no such proof.
One can define in a FOL without equality,
the equality.
What?
This can be found in
every standard text book about logic.
What page of Enderton is this on?
So it doesn't matter wether = is builtin
or whether you have a relation symbol EQ
with the properties of =.
http://en.wikipedia.org/wiki/First-order_logic#Equality
How do you define a relation symbol with the property
that its interpretation in a structure is required to
be equality?
Then take for example the following
set S of sentences:
S= { forall x (x = c) }
(aka S = {forall x(EQ(x,c))} {
This S is satisifiable but it has
no infinite model. Actually its
models have exactly one element.
The following M is an infinite model of S.
Take the "universe" to be the natural
numbers N. Define the interpretation
c_M to be 0. And define the interpretation
EQ_M to be NxN.
In FOL without equality we _can_ give a sentence
that requires at least two elements in any model:
Ex Ey R(x,y) & Ax ~R(x,x).
Similarly for any n we can give a sentence that
requires at least n elements in a model. But
a sentence that says that there is only one
element? I don't think so.
The compactness theorem can be
used to show infinity stuff, but
that is not its main purpose. It
can also be used to show other things.
http://www.math.uiuc.edu/~messmer1/math314/compactness.pdf
(Note there is a difference between
a sentence phi_k saying M has cardinality
k (also excercise in every text book)
and a sentence phi saying M has some
cardiniality k<omega)
A theorem that deals with infinity
is the upward löwenheim skolem
theorem, which says if S is satisifiable
by a countable infinite model, then
it is also satisifiable by an uncountable
infinite model.
I wonder, why do we need compactness here?
Why can't we just copy the
original model for infinitely many times?
Try to copy a model of the particular
S above infinite times? What will be
the cardinality?
Did you have other S in mind?
Bye
************************
David C. Ullrich
.
- References:
- FO logic without equality
- From: Li Yi
- Re: FO logic without equality
- From: Jan Burse
- FO logic without equality
- Prev by Date: Re: Why? [was Re: Cantor`s powerset theorem is false?]
- Next by Date: Re: Is this right? (New model from old...)
- Previous by thread: Re: FO logic without equality
- Next by thread: Re: FO logic without equality
- Index(es):
Relevant Pages
|
|
