Re: FO logic without equality

On 3 Jun 2006 11:40:16 -0700, "Keith Ramsay" <kramsay@xxxxxxx> wrote:

As long as you're here I have a question, which I should probably
ask at the top before I start with the snippiness:

How do you do the original exercise via the compactness theorem?

Of course if we know that there are arbitrarily large finite
models then the compactness theorem shows there is an infinite
model. But that can't be it, since I don't see how to show there
are arbitrarily large finite models without using a construction
that would also give an infinite model...


[...]

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.

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

Since that's exactly what he said, yes it _is_ easy to believe.

I'm somewhat amazed
to see you attempting to convince us that you meant anything else.

[...]

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

I'm glad someone said that - I've been finding a lot of things
he's said about what he meant when he said something very hard
to believe, thought it was only me.

You missed the spot where he explained that the reason he
said something or other was because he didn't realize I
was referring to FOL without (or maybe it was with) equality...

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.

Not to get back to the logic, but of course it depends on what
we mean by "infinitely many copies". My impression of what was
meant at first by that was sort of the disjoint union of those
copies, where elements of a copy are only related to elements
of the same copy. Of course if instead we take those copies
and define the interpretations by "ignore what copy you're in"
that's all that's needed.

Keith Ramsay


************************

David C. Ullrich
.

Relevant Pages

  • Re: Functions and Relations
    ... Then all you'll ever need are equijoins. ... The interesting, genuinely infinite case comes about only when you deal with bignums, unlimited length strings or some other similarly lenient type. ... I think it'd mostly be funny if an engine could be forced to select from a blob type equality predicate, ... I think this sort of thing is not totally out of the question, because a) approximate answers are already within the DSS/OLAP/statistical canon, b) Codd and others have already suggested DBMS support for specialized representations like tuple bags collapsed to a set plus a count attribute, c) operationalizing and axiomatizing infinite sets and their approximate representations as disjoint unions shouldn't be too difficult, and d) solid modeling folks already have the necessary algorithms. ...
    (comp.databases.theory)
  • Re: Calculus XOR Probability
    ... equality between quantitative expresseions proven inductively hold in the ... infinite case. ... I think you are misreading Tony here. ... "believable counter-example" to his undefined assertions. ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... equality between quantitative expresseions proven inductively hold in the ... infinite case. ... time that the sum of naturals was N/2. ...
    (sci.math)
  • Re: FO logic without equality
    ... Use Compactness Theorem to show that if S is satisfiable then it has an ... The third part of that theorem, about surjective homomorphisms, ... because if M is any model it's very easy to give an infinite ... (That's in FOL without equality, ...
    (sci.logic)
  • Re: FO logic without equality
    ... |> T has an infinite model. ... |>> Suppose L is an FO language without equality. ... |compactness theorem is necessary to show ... |that there are infinite models in FOL ...
    (sci.logic)