3
$\begingroup$

Suppose $(M, \mathcal X) \models ACA_0$. Recall that a subset $A \subseteq M$ is $inductive$ over $M$ if $M$ satisfies all instances of induction in the expanded language with a predicate for $A$. Suppose $A$ is inductive and let us denote by $(M, \mathcal X[A])$ the model whose second order part consists of all sets definable from parameters in $\mathcal X$ and $A$. What I want to know is whether or not this is necessarily again a model of $ACA_0$.

If it helps, my intended application concerns countable models ($M$ and $\mathcal X$ are both countable) and I know that the $A$ I have in mind is in fact inductive in the larger language i.e. $M$ satisfies all instances of induction in the language with predicates for $A$ and all elements of $\mathcal X$ (note that every set in a model of $ACA_0$ is inductive).

I suppose more generally I'm interested in knowing, given $A \notin \mathcal X$ which is inductive over $M$, what do I need to require of a $\mathcal Y$ so that $A \in \mathcal Y$, $\mathcal X \subseteq \mathcal Y$ and $(M, \mathcal Y) \models ACA_0$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hello Corey! When you say that $A$ is inductive, do you also allow other parameters from $\mathcal{X}$ into the formulas? And only first-order quantifiers, right? If you don't allow other class parameters, then there will be problems preventing an affirmative answer, since two classes can be fine individually, but not together (e.g. non-amalgamable reals, which together code a bad set). But if you do allow class parameters into the induction scheme for $A$, then what goes wrong with a direct affirmative answer? $\endgroup$
    – Joel David Hamkins
    Feb 21, 2018 at 1:50
  • $\begingroup$ Hello Joel! Yes, in detail I mean that if $\phi(x, A, X)$ is a formula with $X \in \mathcal X$ (or finitely many such $X$ of course) but only first order quantifiers then $(M, \mathcal X, A) \models (\phi(0, A, X) \land \forall n \phi(n, A, X) \rightarrow \phi(n + 1, A, X)) \rightarrow \forall x \phi(x, A, X)$. If a direct affirmative answer works I would be very happy, I just get the sense I'm missing something when I try to write it down. $\endgroup$
    – Corey Bacal Switzer
    Feb 21, 2018 at 2:27

1 Answer 1

Reset to default
4
$\begingroup$

The answer to your (first) question is in the negative.

More explicitly: given any countable nonstandard model $M$ of PA, there are inductive subsets $A$ and $B$ of $M$ such that the expansion $(M,A,B)$ fails to satisfy induction in the extended language. I know two ways to achieve this:

(1) Use (Cohen) forcing to construct $A$ and $B$. This was first done by Andrzej Mostowski in his paper: A remark on models of the Gödel-Bernays axioms for set theory. Sets and classes (on the work by Paul Bernays), pp. 325–340. Studies in Logic and the Foundations of Math., Vol. 84, North-Holland, Amsterdam, 1976.

Mostowski's strategy is similar to the proof of the theorem credited to Hugh Woodin in this MO answer of Joel Hamkins.

(2) Use tools of model theory (Beth's theorem, or that of Svenonius) to show that there are countable nonstandard models of PA (or ZF) that carry distinct (indeed continuum many) full inductive satisfaction classes. It is easy to see that if $A$ and $B$ are full satisfaction classes over a model $M$ of PA such that the expansion $(M,A,B)$ satisfies PA in the extended language, then $A=B$, so if $A$ and $B$ are distinct full inductive satisfaction classes over a model $M$ of PA (or ZF), then the expansion $(M,A,B)$ does not satisfy PA (or ZF) in the extended language.

So $A$ and $B$ are as in (1) or (2) above and $\cal{X}$ is chosen as the collection of all subsets of $M$ that are definable in $(M,A)$, then the model $(M,\cal{X}$$[B]$) fails to satisfy $ACA_0$ even though $(M,\cal{X})$ does satisfy $ACA_0$ and $B$ is inductive.

As for the second question: the only necessary and sufficient condition for $(M,\cal{X}$$[A]$) to satisfy $ACA_0$ that I know of is that $(M,X,A)$ satisfies PA in the extended language for every $X \in \cal{X}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is perfect thanks! For your remark in the last paragraph, do you know of a good reference? $\endgroup$
    – Corey Bacal Switzer
    Feb 21, 2018 at 2:58
  • $\begingroup$ The non-amalgamation of $A$ and $B$ is what I was referring to in my comments on the question, above, but this is not a counterexample, since $A$ is not inductive in the language with $B$ as a parameter. Right? This example is precisely why I asked that question in the comment. Since Corey said that he wanted a stronger notion of inductive than just inductive over $M$, it seems to rule out this non-amalgamation case, and I believe the answer is affirmative by a straightforward argument. $\endgroup$
    – Joel David Hamkins
    Feb 21, 2018 at 3:05
  • 1
    $\begingroup$ @JoelDavidHamkins I think I was writing my answer when you were writing your comment, otherwise I would have referred to it. From what I can tell, the formulation of the question did not specify any parameters from $\cal{X}$. If they are allowed, then the last paragraph of my answer applies. $\endgroup$
    – Ali Enayat
    Feb 21, 2018 at 3:08
  • $\begingroup$ @CoreySwitzer The result in the last paragraph follows fairly straightforwardly from the definition of the axioms of $ACA_0$, so Simpson's "bible" on SOSA would be the right reference. $\endgroup$
    – Ali Enayat
    Feb 21, 2018 at 3:11
  • $\begingroup$ @AliEnayat, Thanks for the reference! Yes, your last remark was exactly what I was looking for. I thought something like this might work but I was aware of the non-amalgamation result and I was worried that some extra hypothesis was needed on $A$ to avoid this. $\endgroup$
    – Corey Bacal Switzer
    Feb 21, 2018 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.