## Does higher order arithmetic interpret the axiom of choice?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

By second order arithmetic I mean the axiomatic theory $Z_2$, that is Peano arithmetic extended by second order variables with the full comprehension axiom, and not defined semantically using power set in ZF. By third order arithmetic I mean that extended by third order variables and the comprehension axiom. And so on. Does each of these have an inner model which also satisfies the axiom of choice in each order, using constructibility? If not, do such inner models exist if we also extend induction to a higher order axiom? Is there a good reference on it?

-
If its helpful to know, second order arithmetics is a first order theory. The set variable are not actually second order variables. Usually the language would include a unary predicate that indicates something is a "set". – William Aug 3 at 3:15

3
I'm not sure I understand the question. On the one hand, it seems to me semantically impossible to have, say, a model of seventh-order arithmetic in which the seventh-order variables were well-ordered: what would this well-ordering consist of? On the other hand, given $n$, I can take a well-founded model $M$ of $V=L$ and look at the first $n$ many powersets of $\omega$. It seems to me that this gives a model of $n$-th order arithmetic in which the first $n-1$ many sorts are well-ordered. Am I understanding the question correctly? – Noah S Aug 3 at 3:25
William, yes people often say things like "axiomatic second order arithmetic $Z_2$ is a first order theory." Yet $Z_2$ is still widely called second order arithmetic. So I tried to be clear that I am asking about an axiomatic theory with stated axioms and not about what people call the full second order semantics. Noah, yes what you say is right. So my question is what does it take to get an inner model of $V=L$ in $Z_n$ without recourse to ZF. – Colin McLarty Aug 3 at 12:51

## 1 Answer

There is quite a bit of this in Simpson's book Subsystems of Second Order Arithmetic in the specific context of second-order arithmetic. Here are three relevant results:

Corollary VII.5.11 (conservation theorems). Let $T_0$ be any one of the $L_2$-theories $\Pi^1_\infty\text{-CA}_0$, $\Pi^1_{k+1}\text{-CA}_0$, $\Delta^1_{k+2}\text{-CA}_0$, $0 ≤ k < \infty$. Let $\phi$ be any $\Pi^1_4$ sentence. Suppose that $\phi$ is provable from $T_0$ plus $\exists X \forall Y (Y ∈ L(X ))$. Then $\phi$ is provable from $T_0$ alone.

Here $\Pi^1_\infty\text{-CA}_0$ has the full comprehension scheme for second order arithmetic, and hence also the full induction scheme.

Theorem VII.6.16 ($\Sigma^1_{k+3}$ choice schemes). The following is provable in $\text{ATR}_0$. Assume $\exists X \forall Y (Y ∈ L(X ))$. Then:

1. $\Sigma^1_{k+3}\text{-AC}_0$ is equivalent to $\Delta^1_{k+3}\text{-CA}_0$.
2. $\Sigma^1_{k+3}\text{-DC}_0$ is equivalent to $\Delta^1_{k+3}\text{-CA}_0$ plus $\Sigma^1_{k+3}\text{-IND}$.
3. Strong $\Sigma^1_{k+3}\text{-DC}_0$ is equivalent to $\Pi^1_{k+3}\text{-CA}_0$.
4. $\Sigma^1_\infty \text{-DC}_0$ ($=\bigcup_{k < \omega} \Sigma^1_k\text{-DC}_0$ ) is equivalent to $\Pi^1_\infty\text{-CA}_0$.

and

Corollary IX.4.12 (conservation theorem). For all $k <\omega$, $\Sigma^1_{k+3}\text{-AC}_0$ (hence also $\Delta^1_{k+3}\text{-AC}_0$ ) is conservative over $\Pi^1_{k+2}\text{-CA}_0$ for $\Pi^1_4$ sentences.

-

1
It looks ok to me. What looks wrong to you? – David Roberts Aug 3 at 5:12
@David Roberts: the math is rendering for me now as well. Yesterday, it was not rendering, and only displayed as raw TeX. It may have been a network issue with MathJaX, since I thought my connection was slow last night in other ways. – Carl Mummert Aug 3 at 10:38
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 44, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9421665072441101, "perplexity_flag": "middle"}