Re: Nonfirstorderizability


Keith Ramsay wrote:
> 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.

That's not where I got it from. See my above post to Torkel.

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

Thanks for the thorough explanation including example. This is probably
much the same thing that Kaplan did in his proof--I wish I knew where
it was from since Boolos doesn't cite any references. Do you know? And
do you have any other sources on nonfirstorderizability (besides those
from Boolos)?

.

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