Search Results
Search type | Search syntax |
---|---|
Tags | [tag] |
Exact | "words here" |
Author |
user:1234 user:me (yours) |
Score |
score:3 (3+) score:0 (none) |
Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
Views | views:250 |
Code | code:"if (foo != bar)" |
Sections |
title:apples body:"apples oranges" |
URL | url:"*.example.com" |
Saves | in:saves |
Status |
closed:yes duplicate:no migrated:no wiki:no |
Types |
is:question is:answer |
Exclude |
-[tag] -apples |
For more details on advanced search visit our help page |
Theories of arithmetic in first-order logic, such as Peano arithmetic, second-order arithmetic, Heyting arithmetic, and their subsystems and extensions. Models of Peano arithmetic.
15
votes
What is the canonical way to extend Peano's axioms to the set of all integers?
Here is a somewhat different way to think about it, although the result is equivalent to the theories in the other answers.
Begin with the observation that the structures $\langle\mathbb{N},+,\cdot,0, …
4
votes
Does strong provability imply syntactical provability?
Let me assume that you also include the axioms $\vdash A$ whenever $A$ is a logical axiom, for some fixed standard proof system using modus ponens as the only inference rule. And let me also assume th …
6
votes
Accepted
Do these two provability theories over PA differ in consistency strength?
No, both of these theories are equiconsistent with PA.
The reason is that given any model of PA, we may expand it to a model in the language with $\vdash$ by interpreting $\vdash\psi$ as true in the m …
9
votes
Accepted
Can we use remote provability to prove the first incompleteness theorem sans $\omega$-consis...
It doesn't contradict PA to have such a descending sequence. For example, you could instead simply keep substracting one from $g^{*1}$, and this would be provably descending, but there is no contradic …
12
votes
Accepted
Is there a useful measure of density of decidable sentences in PA?
Asymptotic density seems a very natural measure. The density of a set of sentences is the limit as $n\to\infty$ of the proportion of those sentences of length at most $n$ amongst all sentences of leng …
8
votes
Can set theory be interpreted in infinite arithmetic?
Without considering your system of arithmetic too closely, let me mention that ZFC is interpretable in Peano arithmetic, if one augments PA with the assertion that ZFC is consistent.
That is, ZFC is i …
16
votes
Con(PA) via non-well-foundedness?
This is a completely standard perspective in work on models-of-PA, a view that informs dozens of arguments. That is simply the nature of nonstandard models, that things they think are well founded are …
7
votes
Interpreting peano arithmetic without parameters
Let me give a simple example, which may help to clarify things.
Consider the integer line $\langle\newcommand\Z{\mathbb{Z}}\Z,<\rangle$, and the natural number order $\langle\newcommand\N{\mathbb{N} …
8
votes
Can there be computable non-standard models of PA in a weaker sense?
This is a great question!
Let me give a meager partial answer, for the case where we are talking
about nonstandard models of true arithmetic.
Theorem. No nonstandard model of true arithmetic arises …
7
votes
1
answer
571
views
Finding a PA cut in a nonstandard model of PA
For a certain project I am currently working on, I need to be able to find PA cuts in nonstandard models of PA, in desirable intervals. For example, I wonder if the following is true, where $\newcomma …
14
votes
Accepted
Dedekind-Peano axioms, but numbers have at most one successor
Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger ver …
7
votes
The additive structure of clusters of nonstandard models of arithmetic
If you intend literally to recover the addition operation of the given model $M$, then the answer is negative. For every nonstandard model of arithmetic $M$ there is another model $M'$ having exactly …
7
votes
Accepted
The additive structure of clusters of nonstandard models of arithmetic
The answer is yes. The additive cluster structure knows the additive structure of the original model up to isomorphism.
Theorem. The additive structure of any countable nonstandard model $M$ of $\newc …
2
votes
Is diamond consistent with 2nd order PA?
In the case of $\text{GBC}^-$, the answer is no, $\Diamond$ is not provable from the assumption that all reals are constructible. It is consistent with $\text{GBC}^-$ and even $\text{KM}^-$ that $\Dia …
11
votes
Accepted
Can the "real" Peano Arithmetic be inconsistent?
It seems that the Feferman-style description of PA will exhibit your requirements.
Specifically, consider the theory $P$ defined as follows. Begin to enumerate the usual PA axioms, but include the n …