[FOM] Proof Theory Query

[Monroe Eskew]

Joe,

Here's a complete answer:  Neither implies the other.

Let T be the finitely axiomatizable theory of dense linear orders
(DLO).  Let T' be the theory of DLO's without endpoints.  Let M be a
countable model of T' and let D be the diagram of M, with constants
c_i, i \in \omega as names.  Let c_\omega be a new constant.  Let L be
the language {<, c_1, c2, ... , c_n, ..., c_\omega}, and let S be the
closure of T union D under logical consequence in L.  Clearly M
satisfies S if we expand its language in the obvious way and assign
c_\omega to a random point.

Let \phi(x) be an arbitrary formula in L, and suppose S contains
\exists x \phi(x).  Since M satisfies S, S contains  \phi(c_i) for
some i \in \omega.  Thus S has property P1.

Let \psi be the sentence, "There is a maximal element."  Let \phi(x)
be "x is less than or equal to c_\omega."  Then (\forall x \phi(x) -->
\psi) is in S.  However, (\phi(c_i_1) & ... & \phi(c_i_n)) -->\psi) is
not in S for any finite collection of c_i's.  This is because M
satisfies (\phi(c_i_1) & ... & \phi(c_i_n)) if we assign c_\omega to
anything greater than c_i_1,...,c_i_n.  Thus S does not have property
P2.  Thus P1 does not imply P2.

Now for the other direction, let n be a composite number and let T be
the theory of cyclic groups of order n.  Let S be closure of T union
{"c_i \not= c_j" : i \not= j, 0<i,j<n+1}.  S thinks there is a
generator for the group, and it knows that the c_i's exhaust the
group, but it does not know which of them is a generator.  Clearly S
has property P2.  But if \phi(x) is "x is a generator", then S does
not contain a witness to that.

-Monroe



On Sat, Oct 10, 2009 at 7:57 AM,  <joeshipman at aol.com> wrote:
> Let T be a recursively axiomatizable first-order theory in a language
> with countably infinitely many constant symbols c0, c1, ....
>
> Consider the following properties:
>
> P1: Whenever ExPhi(x) is in T, there exists i such that Phi(c_i) is in
> T.
>
> P2: Whenever AxPhi(x)-->Psi is in T, there exist finitely many
> constants c_i1, c_i2, ..., c_i_n such that
> ((Phi(c_i1)&Phi(c_i2)&...&Phi(c_i_n))-->Psi) is in T.
>
> What are these properties called, and can a theory have one but not the
> other?
>
> -- JS
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>