Re: FO logic without equality


Jan Burse wrote:
|David C. Ullrich wrote:
|> What you said was that whether we're talking about
|> FOL with or without equality does not matter to
|> whether it is true that if T has a model then
|> T has an infinite model. How does _that_ follow
|> from the above?
|
|No I didn't say that.

I find it rather hard to believe that you really meant by your remark
the kind of thing you are now claiming you meant by it.

|My original post was:
| > 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.
|
|With my statement "There is no such proof",
|I was refering to the claim that the
|compactness theorem is necessary to show
|that there are infinite models in FOL
|without equality.

Where's the claim that the "compactness theorem is necessary"? All the
exercise does is to say to use it. If one can show that there are
models
with > n elements for each n, then one can use compactness to show
there are infinite models.

To think that the _necessity_ of the compactness theorem for the
exercise is at issue seems quite a remarkable misunderstanding of it,
and I find it frankly very hard to believe that you misunderstood it as
badly as that. It would be hardly credible to think that one "needs"
some particular theorem to show the result, and indeed, nobody made
such a claim.

|Then I wrote:
| > One can define in a FOL without equality,
| > the equality. This can be found in
| > every standard text book about logic.
| >
| > 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

I can easily imagine someone reading that "equality can be defined"
and slipping up, imagining that it meant the difference between first
order logic without equality and first order logic with equality was
irrelevant in a case like the exercise.

The problem is, if one has an infinite model of first-order logic with
equality, and defines equality the way that's indicated on the
Wikipedia page, you may only get an equivalence relation coarser
than the equality on the original equality for the domain of the model.
The domain modulo that equivalence may be finite even if the domain
is infinite. It makes a difference for the exercise whether = is
built-in or
one uses a relation with the properties of =.

That you meant to say that whether = is built-in or not is irrelevant
to
the original exercise would be easy to believe. I'm somewhat amazed
to see you attempting to convince us that you meant anything else.

| > 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.

Here again, very very plausible that you'd be still making this simple
mistake of thinking whether one uses EQ or = was irrelevant, and
very very implausible that you were trying to answer some derivative
question about the necessity of the compactness theorem. If you
thought that this was an example of a satisfiable theory in first-order
logic without equality with no infinite model, it would make sense
that you'd be including it here. Why else would you include it?

|With the above I simply opened a big parenthesis
|and closed it. It was a little excurse in
|FOL with equality. Some Ullrich began then
|a big thread about this all being false.

I think you're more responsible for having perpetuated the thread
unnecessarily. You could've cleared it up days ago by saying what
you mean and meaning what you say.

|And he is now threading the question of the
|relevance of the above. But note this was only
|a parenthesis after which I came back to my
|original concern:

A concern rather tangential to the original question you were
answering.

| > 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.
|
|So I was a little elaborating in my post
|whether it could be the compactness theorem
|or something else that this infinite question
|rose from. Actually when one looks at
|the löwenheim skolem proof via compactness,
|it makes the use of equality. But in FOL
|without equality we don't have equality,
|so I personnaly crossed out the possibility
|of compactness and löwenheim skolem proof
|as relevant to the question by Li Yi.

So you claim to like this high-class mathematical logic. That's
a fine thing. But it's not very helpful to answering the question.

| > Try to copy a model of the particular
| > S above infinite times? What will be
| > the cardinality?
| > Did you have other S in mind?
|
|So to find out more about what it is all
|about in Li Yi post, I posed the above
|equestion, what S it is all about.

I think it's pretty obvious that infinitely many copies of a nonempty
model will have infinitely many elements, which is all that was
needed.

Keith Ramsay

.

Relevant Pages

  • Re: FO logic without equality
    ... FOL with or without equality does not matter to ... T has an infinite model. ... >> Suppose L is an FO language without equality. ... compactness theorem is necessary to show ...
    (sci.logic)
  • Re: FO logic without equality
    ... One can define in a FOL without equality, ... that its interpretation in a structure is required to ... no infinite model. ... a sentence phi_k saying M has cardinality ...
    (sci.logic)
  • FO logic without equality
    ... 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. ...
    (sci.logic)
  • Re: FO logic without equality
    ... One can define in a FOL without equality, ... no infinite model. ... a sentence phi_k saying M has cardinality ... S above infinite times? ...
    (sci.logic)
  • Re: FO logic without equality
    ... but comparing it to FOL with equality ... for the non satisfiability is not S ... There exists consistent theories T in FOL ...
    (sci.logic)