Timeline for How special is first-order $\mathsf{PA}$?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2021 at 8:52 | comment | added | Dave L Renfro | I like your definition of "natural logic"! Maybe one can go further and distinguish between strong and weak versions, where strong means "empty intersection of author sets" and weak means "subset-incomparable author sets". | |
| Mar 3, 2021 at 22:27 | answer | added | Ali Enayat | timeline score: 13 | |
| Mar 3, 2021 at 18:58 | vote | accept | Noah Schweber | ||
| Mar 3, 2021 at 13:36 | comment | added | Corey Bacal Switzer | Great! That's very nice. | |
| Mar 3, 2021 at 13:25 | comment | added | Noah Schweber | Incidentally, that's $\Pi^0_1\wedge\Sigma^0_1$, and it's easy to show that that's optimal: no $\Pi^0_1\vee\Sigma^0_1$ formula will pin down $\mathbb{N}$. | |
| Mar 3, 2021 at 13:18 | comment | added | Noah Schweber | @CoreySwitzer I think I figured it out: just pair up the sets :P. Think of $X$ as a pair of sets $X_0,X_1$ (e.g. $X_0=\{n: 2n\in X\}, X_1=\{n: 2n+1\in X\}$) and let $\Phi(X)$ say "it is not the case that both $X_0$ and $X_1$ contain $0$ and are closed under successor but $X_0\not=X_1$." I think that works. | |
| Mar 3, 2021 at 11:30 | comment | added | Corey Bacal Switzer | This is not entirely clear to me. To be honest it's been a while since I thought about this result. However there is a discussion of this point in the Kossak-Schmerl book. For instance, induction can be formulated this way, though it's not immediately obvious (you have to use the equivalent, least number principle). My guess is that many other "natural" examples can, with some MacGuyvering, be formulated with this restriction as well. However I don't see a general way to do it right now. | |
| Mar 3, 2021 at 11:23 | comment | added | Noah Schweber | @CoreySwitzer Ah, I'm starting to get it. One last question: why does such a $\Phi$ exist in the first place? Since all quantifiers have to be bounded to $X$ we can't use e.g. "$X$ is not a nontrivial proper cut." | |
| Mar 3, 2021 at 11:16 | comment | added | Corey Bacal Switzer | Roughly the point is suppose you had some alternative axiomatization of arithmetic of the form "finite sentences" + "scheme". If the second order version of this theory obtained by replacing your scheme by one sentence of the form $\forall X...$ is categorical for $\mathbb N$ then in fact the first order scheme version proves $\mathsf{PA}$. Does that make sense? The relevance to your question is that if you wanted to weaken $\mathsf{PA}$ to something else, then second order logic will no longer be strong for induction. | |
| Mar 3, 2021 at 11:14 | comment | added | Corey Bacal Switzer | I'm not sure I understand your objection, $I\Sigma_1$ doesn't prove $\mathsf{PA}$ and has nonstandard models. The theorem essentially says the following. Suppose you have a finite set $T$ of FO sentences in the language of arithmetic and scheme $\Phi(X)$ so that, as a second order theory $T + \forall X \Phi(X)$ has the standard model as its unique model. The theorem says that in this case the FO theory consisting of some finite set $T_1$ (potentially a little bigger than $T$) and every instance $\Phi(X)$ where the variable $X$ is replaced by a first order formula proves $\mathsf{PA}$. | |
| Mar 3, 2021 at 10:56 | comment | added | Corey Bacal Switzer | Of course you're right it's trivial otherwise. The point is that $\mathsf{PA}$ is the minimal first order theory whose second order version is categorical for $\mathbb N$. The (suggested) intuition is that therefore $\mathsf{PA}$ is the {\em right} theory for arithmetic, whatever that means. | |
| Mar 3, 2021 at 10:50 | comment | added | Corey Bacal Switzer | Sorry, I formulated it poorly. The exact result is this: Suppose $\Phi(X)$ is a first order formula with variable $X$ so that each quantifier is restricted to $X$ (i.e. every quantifier is of the form $\exists x \in X$ or $\forall x \in X$). If there is a finite FO theory $T$ in the language of $\mathsf{PA}$ so that the only model of $T + \forall X \varphi(X)$ is the standard model then there is a finite set of sentences $T_1$ in the language of $\mathsf{PA}$ so that $\mathbb N \models T_1$ and $T_1 + \Phi(def) \vdash \mathsf{PA}$ where $\Phi(def)$ means the FO scheme version of $\Phi$. | |
| Mar 3, 2021 at 10:49 | comment | added | Corey Bacal Switzer | I ran out of room. Here 2nd order $\mathsf{PA}$ is the theory $\Gamma + \forall X \Psi(X)$ where $\Psi(X)$ expresses induction for $X$ and $\Gamma$ is your favorite finite set of additional axioms needed to formulate $\mathsf{PA}$.This is proved in "On schemes axiomatizing arithmetic". In {\em Proceedings of the International Congress of Mathematicians}, Vol. 1, 2 (Berkeley, Calif., 1986). There is a nice exposition in Chapter 7 of Kossak and Schmerl's The Structure of Models of Peano Arithmetic. | |
| Mar 3, 2021 at 10:46 | comment | added | Corey Bacal Switzer | It's not immediately applicable to your question but you might be interested in the following result of Wilkie. Everyone knows Peano's theorem that full second order logic is strong for induction in your terminology. However, Wilkie showed that in fact $\mathsf{PA}$ is the weakest theory with this property. Namely, if we take a finite set of FO sentences $\Gamma$ and a scheme $\Phi(X)$ where $X$ is a second order variable. If (in 2nd order logic) $\Gamma + \forall X \Phi(X)$ has $\mathbb N$ as its unique model then $\Gamma + \forall X \Phi(X) \vdash \mathsf{PA}$. | |
| Mar 3, 2021 at 7:03 | answer | added | James E Hanson | timeline score: 10 | |
| Mar 3, 2021 at 3:49 | history | asked | Noah Schweber | CC BY-SA 4.0 |