0
$\begingroup$

Denote be $\mathcal P_{MO}$ the set of the monadic second order axioms of Peano. Then as shown by Dedekind any two model are isomorphic to $\mathbb N$. Hence for a monadic second order sentence we have $$ \mathbb N \models \varphi \mbox{ iff } \mathcal P_{MO} \models \varphi $$ i.e., the natural numbers fullfil $\varphi$ iff every model that fulfills $\mathcal P_{MO}$ also fulfills $\varphi$.

Let $\mathcal P_{FO}$ be the first order Peano arithmetic where the monadic induction axiom is replaced by a first order induction scheme over arbitrary predicates.

Let $\psi$ be some first order sentence, then how to show that $\mathcal P_{FO} \models \psi$ implies $\mathbb N \models \psi$? (the other direction is clear, so I am asking about the relation between satisfiability of the axioms vs satisfiability in the natural numbers).

Similar for other first order axiomatization like Robinson arithmetic? The problem is that as mentioned here, the first order theories are not categorical.

$\endgroup$
5
  • 4
    $\begingroup$ "the other direction is clear" The other direction is false, since first-order PA isn't complete. $\endgroup$
    – Noah Schweber
    Dec 5, 2018 at 15:12
  • $\begingroup$ @NoahSchweber This is not the provability-relation which I would denote by $\vdash$, the notation $\Sigma \models \varphi$ means that every model that satisifies $\Sigma$, also satisfies $\varphi$, and as $\mathbb N$ satisfies $\Sigma = \mathcal P_{FO}$ this gives the mentioned direction... $\endgroup$
    – StefanH
    Dec 5, 2018 at 15:14
  • 4
    $\begingroup$ @StefanH The completeness theorem for first-order logic says that the relations $\models$ and $\vdash$ (between first-order theories and first-order sentences) are the same. The fact that $\mathbb{N}\models \mathcal{P}_{FO}$ means it's clear that $\mathcal{P}_{FO}\models \psi$ implies $\mathbb{N}\models \psi$, not the other way around. And the converse is false, as Noah said, exactly because $\mathcal{P}_{FO}$ is incomplete. $\endgroup$
    – Alex Kruckman
    Dec 5, 2018 at 15:31
  • $\begingroup$ Got it! Would anyone like to write up a full anwer.... $\endgroup$
    – StefanH
    Dec 5, 2018 at 15:36
  • $\begingroup$ @StefanH I've done so, finally. $\endgroup$
    – Noah Schweber
    Mar 27, 2021 at 2:42

1 Answer 1

Reset to default
1
$\begingroup$

To move this off the unanswered queue:

The fact that $\mathcal{P}_{FO}\models\psi\implies\mathbb{N}\models\psi$ is immediate from the definition of $\models$ once you know that $\mathbb{N}\models\mathcal{P}_{FO}$: by definition we have $\mathcal{P}_{FO}\models\psi$ iff every model of $\mathcal{P}_{FO}$ satisfies $\psi$, so since $\mathbb{N}\models\mathcal{P}_{FO}$ we must have $\mathbb{N}\models\psi$.

The other direction meanwhile is false, since $Th(\mathbb{N})$ is complete (every structure's theory is complete) but $\mathcal{P}_{FO}$ is not complete (per Godel - both incompleteness and completeness, the latter letting us freely switch between $\vdash$ and $\models$ when applying the former).

In general, whenever we have a theory and a model of that theory in mind, think of the theory as a probably-limited-approximation to the model: everything the theory knows is true (about that model), but there are probably lots of things the theory doesn't know.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .