[FOM] Proof Theory Query
Monroe Eskew
meskew at math.uci.edu
Mon Oct 12 01:27:16 EDT 2009
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
>
>
More information about the FOM
mailing list