Re: Nonfirstorderizability

Michael De wrote:
|To show in general the nonfirorderizability of an English sentence we
|translate it into the langauge of (first or second-order) arithmetic
|and show that it is true in every nonstandard model but false in the
|standard model.

I find this description a bit puzzling.

Oh, so the Wikipedia page on plural quantification says
something like this, eh? That's less than maximally helpful.
Ugh. Somebody should edit it.

|I don't understand how this shows an English sentence
|(e.g. the Geach-Kaplan one: 'some critics admire only one another')
|nonfirstorderizable. What is the relevancy of arithmetic in this
|technique?

Here's my guess as to the type of argument they mean.

The Geach-Kaplan sentence refers implicitly to a domain D
including critics and other individuals they may admire,
to the property C(x) of being a critic, and to the relationship
A(x,y) of admiration. In such a context, non-first-orderizability
usually means that there's no first-order formula involving
only the predicates A and C that's equivalent to the
Geach-Kaplan sentence.

One possible way to show this is to exhibit two models D1,D2,
i.e. domains D1 and D2 with predicates C1(x) and A1(x,y) on D1
and predicates C2(x) and A2(x,y) on D2, which are equivalent
as far as first-order sentences are concerned, but where the
Geach-Kaplan sentence holds only in D1, not D2. By equivalent
here I mean that each first-order sentence involving C and A
holds in D1 if it holds in D2, and holds in D2 if it holds in
D1.

My guess is that the role played by arithmetic here is purely
in cooking up suitable models D1 and D2. Suppose for example
we assume that individuals are labelled with nonnegative
integers. Suppose C(x) equivalent to x>0, so that 0 is the
only noncritic, and everybody else is a critic. Suppose that
A(x,y) is equivalent to y+1=x, so that each critic admires
the previous critic, except 1, who admires 0 who is not a
critic.

The model as I've just described it fails the Geach-Kaplan
sentence, at least the way I read it. Any (nonempty) collection
of critics contains a critic (the one labelled by the smallest
integer) who admires someone outside of the group. If 1 is in
the group, then 1 admires someone who isn't even a critic
at all.

Now, to finish the job we need a second model that is
equivalent as far as first-order sentences are concerned,
but where the Geach-Kaplan sentence is true. It appears that
the argument makes use of the existence of models having
relationships analogous to the usual arithmetic ones
(addition, multiplication) that are equivalent to the
natural numbers as far as first-order sentences are
concerned, but that are not the same structure up to
isomorphism, in the sense that there is no one-to-one
correspondence with the natural numbers compatible with
the operations of addition and multiplication.

This is perhaps overkill, since the only relationship we
actually used was the relationship of one number being the
successor of another. 0 can be defined as the nonnegative
integer that isn't the successor of any other one. There's
a relatively simple example of a model equivalent as far
as first-order sentences in terms of the successor relation
are concerned, but not isomorphic. Let there be two separate
sequences, A0,A1,A2,... indexed by the nonnegative integers,
and another one ...,B_{-2},B_{-1},B0,B1,B2,... indexed by
integers, negative as well as 0 or positive. Consider A0 to
be the only noncritic again. Let each A_{n+1} admire only
A_n, and each B_{n+1} admire only B_n.

This modified model satisfies the Geach-Kaplan sentence
since the B's are some critics who only admire each other.

Is it first-order equivalent to the simpler one, that in
effect has only the A's in it? Yes it is. This is not too
hard to prove by characterizing the relationships that can
be first-order defined in terms of C(x) and A(x,y) in this
model. For each predicate P(x1,...,xn) that's first-order
definable in C and A in this model, there exists an integer
N such that P only detects relationships between elements
that are within N of each other, roughly speaking. More
precisely, suppose a1,...,an and a1',...,an' are elements
of the model, and suppose that

(1) For each i if either a_i or a_i' is one of the
A0,...,AN then a_i'=a_i.
(2) For each i,j, if for some integer k, 0<=k<=N, a_i
is k steps ahead of a_j in one of the sequences, then
a_i' is likewise k steps ahead of a_j', and conversely.

Then P(a1,...,an) is true if P(a1',...,an') is true and
conversely.

One can show that if two predicates P1 and P2 satisfy that
property, then so do P1&P2, ~P1, and (Ex1)P(x1,...,xn).
If P1 satisfies it with N1 and P2 satisfies it with N2,
then P1&P2 satisfies it with the larger of N1 and N2
for instance. ~P1 satisfies it with the same value of N
as for P1. Quantification like (Ex1)P(x1,...,xn) is the
interesting case. If P satisfies the condition above
with a given N, then for (Ex1)P(x1,...,xn) we might need
to use twice as large a value of N. If P is possibly
able to notice whether x1 lies within N of one of the
x2,...,xn, then (Ex1)P might be able to notice that two
of the x2,...,xn are within 2N by observing that there's
an x1 that lies within N of each.

Filling in the details, this is all that is needed to show
that all first-order definable relations in this model
have the property I described. In fact, with a bit further
of an argument we can show that any predicate for which
there exists an N that makes the property I just described
hold can be first-order defined in terms of C(x) and A(x,y).

Note that this analysis shows that there's no first-order way
to distinguish between the A sequence and the B sequence. The
difference between them is that the A's are connected by a
finite sequence of steps to A0, the sole noncritic admired by
any of them, and the B's are not. But first-order predicates
P(x) definable in terms of C(x) and A(x,y) all either say that
x is in a finite set of specified A's (identified by the number
of steps to A0) or that x is *not* in a specified finite set
of A's. Each such predicate fails to distinguish among the A's
that are far enough away from A0 and the B's.

It may seem peculiar that we're dealing with infinite models
here. It's not necessary to do so. It's only an artifact of
the technique we chose. For each first-order sentence S we
could put together, there are finite models that are equivalent
as far as S is concerned, one satisfying Geach-Kaplan and the
other one not. It's only because we decided to make models
that are simultaneously equivalent as far as *all* first-order
sentences are concerned that we needed infinite ones.

Keith Ramsay

.

Relevant Pages

  • Re: Nonfirstorderizability
    ... > The Geach-Kaplan sentence refers implicitly to a domain D ... > including critics and other individuals they may admire, ... > as far as first-order sentences are concerned, ...
    (sci.logic)
  • Re: Nonfirstorderizability
    ... would you mind explaining to a simple lay person ... I take that sentence to imply the Geach-Kaplan sentence but not the ... That there are at most two critics who admire only each other ...
    (sci.logic)
  • Re: Nonfirstorderizability
    ... > I take that sentence to imply the Geach-Kaplan sentence but not the ... That there are at most two critics who admire only each other ... predicate, let me see what happens when that predicate is removed: ...
    (sci.logic)
Loading