Skip to main content

All Questions

Filter by
Sorted by
Tagged with
14 votes
0 answers
654 views

Reverse Mathematics of Euclid's theorem

Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that ...
David Roberts's user avatar
  • 35.5k
10 votes
1 answer
542 views

Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...
Pedro Sánchez Terraf's user avatar
19 votes
1 answer
748 views

What non-standard model of arithmetic does Hofstadter reference in GEB?

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
Dave Pritchard's user avatar
8 votes
2 answers
428 views

Models of arithmetic in a signature with exponentiation but not addition and multiplication

Let $\mathcal{L}_{\mathrm{exp}}$ be the language with signature $(0, ^\prime, <, \mathrm{exp})$ (with $0$ interpreted as zero, $^\prime$ as successor, and $\mathrm{exp}(x)$ as $2^x$) and let $\...
Beau Madison Mount's user avatar
3 votes
0 answers
85 views

What is the relation of total functions in second order arithmetic and fast growing hierarchies?

Answer to this questions shows that fast growing hierarchies can grow arbitrarily fast for some definition of 'arbitrary'. Can second order arithmetic define all these functions (for any ordinal) ...
Łukasz Lew's user avatar
3 votes
0 answers
324 views

Is the quantifier-free fragment of Robinson arithmetic essentially undecidable?

It is well known that Robinson arithmetic (Q) is undecidable, and in fact essentially undecidable. Matiyasevich's theorem implies that the quantifier-free fragment of Q is also undecidable. However, I'...
Mak Nazečić-Andrlon's user avatar
7 votes
1 answer
597 views

Can an uncountable model of Peano Arithmetic be recursive?

Can an uncountable model of Peano Arithmetic be recursive? What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
Christopher King's user avatar
6 votes
1 answer
727 views

What is the consistency strength of this theory?

Language: first-order logic Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation). Axioms: those of identity ...
Zuhair Al-Johar's user avatar
11 votes
2 answers
441 views

Are all generalized Scott sets realized as generalized standard systems?

Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so. The standard system of a nonstandard ...
Noah Schweber's user avatar
7 votes
2 answers
237 views

On models of $Th_{\Pi_2}(PA)$

Let $M$ be a nonstandard model of $PA$. Q1. Is there any way to get a submodel $N\subset M$ such that $N\models Th_{\Pi_2}(PA)$, but $N\not\models PA$? Q2. Especially, what combinatorial principle ...
Erfan Khaniki's user avatar
1 vote
0 answers
346 views

approaching the border between absolute convergence and divergence of series

Let us consider absolute convergent series $\ell^{1^+}$ ordered under eventual dominance (mod finite) $<^*$. T. Bartoszynski proved that unbounded number ${\frak b}(\ell^{1^+}, <^*)$ equals ...
Peter Vojtas's user avatar
3 votes
0 answers
144 views

A conservativity result of intuitionistic set theory over arithmetic

In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...
namsap's user avatar
  • 355
1 vote
0 answers
205 views

Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?

Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...
Christopher King's user avatar
8 votes
1 answer
334 views

Analog of Tennenbaum's theorem for EFA

EFA can prove the exponential function to be total, but it cannot prove the superexponential function to be total. Is there an analog of Tennenbaum's theorem (which states the PA has no recursive non-...
Thomas Klimpel's user avatar
3 votes
1 answer
120 views

If one adds an inductive subset to a model of $ACA_0$, do we always get a new model of $ACA_0$?

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$. ...
Corey Bacal Switzer's user avatar
8 votes
2 answers
730 views

Is every true statement independent of $PA$ equivalent to some consistency statement?

Most true statements independent of PA that I know of is equivalent to some consistency statement. For example Con(PA), Con(PA + Con(PA)), Con(PA + Con(PA) + Con (PA + Con(PA)), $\dots$ Goodstein's ...
Christopher King's user avatar
17 votes
1 answer
2k views

What is known about the relationship between Fermat's last theorem and Peano Arithmetic?

As far as I know, whether Fermat's Last Theorem is provable in Peano Arithmetic is an open problem. What is known about this problem? In particular, what is known about the arithmetic systems $PA + \...
Christopher King's user avatar
7 votes
1 answer
246 views

Independent/Easy fraction of sentences over PA

Let $S(n)$ be the set of all sentences over PA of length at most $n$ (counting the quantifier symbols, boolean connectives, arithmetic operations and constants, and counting each variable as length $1$...
user21820's user avatar
  • 2,912
7 votes
1 answer
572 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 $\...
Joel David Hamkins's user avatar
8 votes
0 answers
345 views

What arithmetic is interpretable in Mayberry's Euclidean set theory?

John Mayberry published what he calls a Euclidean set theory in his book The Foundations of Mathematics in the Theory of Sets. It is ZF with the axiom of infinity replaced by an axiom saying "the ...
Colin McLarty's user avatar
8 votes
1 answer
535 views

Is ZFC+(negation of a large cardinal axiom) arithmetically sound?

My knowledge in set theory is very limited, so I apologize if this question is naive or trivial: Let $A$ to be a large cardinal axiom. $T=ZFC+\neg A$ is a consistent theory. My question is: Question ...
Payam Seraji's user avatar
1 vote
2 answers
777 views

Can you remove all the extra arithmetic from ZFC (or other theories)?

Let $\mathbb{N}$ be the standard model of the natural numbers. For any statement in the language of arithmetic, we can translate into a statement in the language of set theory by asking if it is true ...
Christopher King's user avatar
7 votes
2 answers
708 views

On a theorem of Zhang Jinwen about models of arithmetic

In the paper ''A Nonstandard Model of Arithmetic Constructed by means of Forcing Method'', Zhang Jinwen states the following in his abstract: The first nonstandard model of arithmetic was given by ...
Mohammad Golshani's user avatar
6 votes
1 answer
172 views

Logical complexity of hard functions conjectures

Let $\phi_1$ and $\phi_2$ be the following statements: $\phi_1:$ There is a function $f:\{0,1\}^*\to\{0,1\}$ computable in $E$ that has circuit complexity $2^{\Omega(n)}$. $\phi_2:$ There is a ...
Erfan Khaniki's user avatar
12 votes
2 answers
1k views

Trouble with models of PA and ZFC

I have a big trouble in my mind, here is my false reasoning: The Goodstein's theorem is undecidable in (first order) Peano Arithmetic. There exist a non standard model N of PA where the Goodstein's ...
PostAsAGuest's user avatar
8 votes
1 answer
1k views

Can the "real" Peano Arithmetic be inconsistent?

Assuming $\text{PA}$ is consistent. Then $\text{PA} + \neg\text{Con}(\text{PA})$ is consistent and have a model, say $M$. We know $M$ must be nonstandard, in which case, there is a nonstandard proof ...
Ruizhi Yang's user avatar
5 votes
1 answer
195 views

Can extensions of $Q$ contradict Löb with recursive reflection?

It is an odd and arguably unacceptable situation that $PA$ does not have $\vdash_{PA}(Pr_{PA}\ulcorner A\urcorner\to A)$ for false recursive sentences $A$. However, it is not clear to me that Löb'...
Frode Alfson Bjørdal's user avatar
2 votes
1 answer
142 views

Does $WKL_0$ plus CON(PA+X) give a binary tree model of PA+X?

In the context of reverse mathematics $WKL_0$ is considered equivalent to Gödel's completeness theorem over $RCA_0$. Does this mean that e.g. $WKL_0$ plus the consistency statement CON(PA+X) gives a ...
Frode Alfson Bjørdal's user avatar
1 vote
0 answers
113 views

How do I justify these nontheorems in the absence of the Existence Property for $PA$

Let $\Pi$ be the provability predicate for $PA$. I want to conclude that $PA\nvdash\exists x(\alpha(x)\wedge\lnot\Pi\ulcorner \alpha(\overset{.}{x}) \urcorner)$ and $PA\nvdash\exists x(\lnot \alpha(x)\...
Frode Alfson Bjørdal's user avatar
2 votes
1 answer
225 views

How does the existence property fail in $PA$?

Who or what is a good reference that explains how the (numerical) existence property fails for $PA$? Alternatively, what is a good example? It e.g. is clear that the disjunction property must fail ...
Frode Alfson Bjørdal's user avatar
6 votes
2 answers
1k views

Are omega-consistent extensions of PA always consistent with each other?

The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just: ...
N. Virgo's user avatar
  • 1,344
4 votes
0 answers
292 views

the strength of saying "each sentence of true arithmetic has a recursive proof"

Let $PA_{\omega}$ be just like $PA$ except that $PA_{\omega}$-proofs can use any number of applications of the recursive $\omega$-rule. The recursive $\omega$-rule allows the following: For each ...
Haidar's user avatar
  • 449
4 votes
1 answer
480 views

$f_{\epsilon_0}$ and provably total functions in $PA$

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that $f(x)=y \iff PA\vdash \phi(x,y)$ and $PA\vdash \forall x \exists y \phi(x,y)$ I know (not in ...
Eric's user avatar
  • 2,619
1 vote
1 answer
238 views

Elementary functions in a formalized PA

I'm having trouble understanding some parts of the paper "Provably computable functions and the fast growing hierarchy" by Buchholz and Wainer (1987). On page 183 they say that their system has ...
Gabriel Nivasch's user avatar
1 vote
1 answer
311 views

Forcing the consistency of $ZF$ from a fragment of $ZF$

Implicit in the technique of forcing is the following relative consistency result: If $\mathfrak M$$\vDash$$T$, and therefore $T$ is consistent (where $\mathfrak M$ is the ground model) then if $\...
Thomas Benjamin's user avatar
5 votes
1 answer
485 views

Extensions of the Ackermann interpretation to nonstandard theories of arithmetic

In their paper, " On Interpretations of Arithmetic and Set Theory" (Notre Dame Journal of Formal Logic, Vol. 8, No. 4 (2007), pp. 497-510) in section 7, "Fragments of Arithmetic and Set ...
Thomas Benjamin's user avatar
6 votes
1 answer
209 views

Is $PRA$ + $TI({\epsilon_0})$ mutually interpretable with some theory in the language of set theory?

As is well known, the following theory is equiconsistent with $PA$: $ZFC$ with the axiom of infinity replaced by its negation. Since this theory is equiconsistent with $PA$, it would seem ...
Thomas Benjamin's user avatar
2 votes
1 answer
458 views

Is the statement "All numbers are counting numbers" independent of $PA$?

In his paper, "Completed versus Incomplete Infinity in Arithmetic" (which can be found here), the late Edward Nelson defines the notion of 'counting number' as follows: 0 is a counting ...
Thomas Benjamin's user avatar
10 votes
0 answers
161 views

Minkowski's lattice theorem in fragments of arithmetic

It is widely remarked that Minkowski's lattice theorem (or, convex body theorem) is a kind of geometrical pigeonhole principle. And it seems it should have a very elementary proof at least for convex ...
Colin McLarty's user avatar
9 votes
1 answer
873 views

Is there any set theory $T$ such that $T$ plus true arithmetic is complete with respect to statements in set theory?

Is there an effective set theory $T$ such that $T + $$TA$ is consistient and complete. It should at least prove all theorems of $ZF$ true, so that it is a "standard" set theory. In particular, the ...
Christopher King's user avatar
2 votes
1 answer
247 views

How can two theories $T$ and $T+\phi$ be mutually interpretable?

Following Koellner in http://plato.stanford.edu/entries/independence-large-cardinals/, "a theory $T_1$ is interpretable in $T_2$ ($T_1 \leq T_2$) when, roughly speaking, there is a translation $\tau$ ...
Henning H's user avatar
4 votes
0 answers
219 views

Construction of model of arithmetic from an arbitrary model

Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that: $M'\models PA^-$ (or $...
Erfan Khaniki's user avatar
2 votes
2 answers
281 views

Interpreting peano arithmetic without parameters

I will accept an answer in the form of references to the literature about my question as well as any other information. I am quite ignorant of the area and that will be clear from my question. I ...
Matt Brin's user avatar
  • 1,625
1 vote
1 answer
186 views

What is difference between length of proof and length of its presentation in Peano Arithmetic?

In this paper http://www.sciencedirect.com/science/article/pii/0304397584901117 page $19$ or $29$ it seems to imply there is a difference between length of proof and length of its presentation in ...
Turbo's user avatar
  • 13.9k
3 votes
0 answers
198 views

What is the known weakest axiom system has Löb's derivability conditions?

We know that Peano Arithmetic satisfies Löb's derivability conditions, which is required in the proof of Gödel's 2nd incompleteness theorem. Is this the best result? If not, is there any known weaker ...
Ruizhi Yang's user avatar
9 votes
1 answer
580 views

Interpreting Robinson arithmetic in a very weak set theory

It is known that adjunctive set theory interprets Robinson arithmetic, and that extensionality is not needed for that. (Montagna and Mancini, "A minimal predicative set theory", Notre Dame Journal of ...
Thomas Schindler's user avatar
5 votes
0 answers
287 views

Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?

Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).
Thinniyam Srinivasan Ramanatha's user avatar
1 vote
1 answer
629 views

In what sense is the "descending chain principle" for ordinals less than $\epsilon_0$ 'infinitary?

In the introduction to his paper "Assignment of Ordinals to Terms for Primitive Recursive Functionals of Finite Type", W.A. Howard writes: Gentzen...showed that the consistency of first order (...
Thomas Benjamin's user avatar
8 votes
0 answers
1k views

What's Reeb's take on naive integers?

Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
Mikhail Katz's user avatar
  • 16.6k
3 votes
1 answer
404 views

Simplest PA theorem whose proof requires encoding of sequences even though the statement itself doesn't

What is the simplest number-theoretic theorem whose proof requires exponentiation or finite sequences/sets (so any proof in Peano Arithmetic would need to use encodings of such things using e.g. Gödel'...
Gabriel Nivasch's user avatar

1 2 3
4
5
7