Deprecated; please use a more specific tag.

learn more… | top users | synonyms

-2
votes
0answers
40 views

n-th prime in first order arithmetics [on hold]

Recently I have thought about formalizing Turing machine in first order arithmetics, step by step, starting from the most basic things. But I quickly struck a problem - to continue, I need to find a ...
-1
votes
0answers
26 views

Is there a program for convenient working with equations and coefficients? [migrated]

I perform some calculations with one differential equation. Then I got a huge expression depending on $x$ and its degrees/powers. E.g. $$\alpha x+(4-x+\sqrt[3]{x})^2-(\beta\sqrt{x}+\frac12(x^3+1))^3 + ...
3
votes
2answers
255 views

Efficient representations of natural numbers via arithmetical expressions

A given natural number $n \in \mathbb{N}$ has many representations as expressions mixing other natural numbers and the operators and punctuation symbols $\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...
1
vote
1answer
178 views

Infinite board games: sentences about

As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A.. can a sentence be devised in A which automatically answers the basic ...
33
votes
2answers
2k views

What arithmetic information is contained in the algebraic K-theory of the integers

I'm always looking for applications of homotopy theory to other fields, mostly as a way to make my talks more interesting or to motivate the field to non-specialists. It seems like most talks about ...
18
votes
1answer
200 views

Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
11
votes
1answer
389 views

Does any lower bound on proofs of FLT improve Shepherdson 1965?

In 1965 Shepherdson proved that FLT is independent of the fragment of PA that uses only open induction and signature $0,S,+\times$. Indeed $2x+1\neq 2y$ is independent of that fragment. Schmerl ...
2
votes
0answers
69 views

Seeking name for an order raising operator in Higher Order Arithmetic.

Any class $X$ of order $j$ in HOA is in bijection with the order $j+1$ class built up from singletons $\{x\}$ of natural numbers $x$ just the way that $X$ is built up from the numbers $x$. And of ...
4
votes
0answers
337 views

How arithmetical is algebraic exponentiation?

Suppose $K$ is an exponential real closed field, i.e. there is an isomorphism, say exp, between the additive group of $K$ and the multiplicative group of its positive elements. Assume further that $Z$ ...
2
votes
0answers
146 views

Is this fragment of arithmetic on $p^{-\infty} {\mathbb Z}$ decidable?

Let $p$ be a prime number. Consider the abelian group $p^{-\infty} {\mathbb Z} = \bigcup p^{-n} {\mathbb Z}$ consisting of rational numbers whose denominator is a power of $p$, under addition. View ...
3
votes
1answer
159 views

Is there an $E_1$-definition of primality?

Here, $E_1$ denotes the set of arithmetic formulas starting with a bounded existential quantifier, followed by a quantifier-free formula. Is there an $E_1$-formula $\phi$ such that $\phi(n)$ holds iff ...
8
votes
1answer
330 views

Does higher order arithmetic interpret the axiom of choice?

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 ...
4
votes
2answers
774 views

Axiom to exclude nonstandard natural numbers

In Peano Arithmetic, the induction axiom states that there is no proper subset of the natural numbers that contains 0 and is closed under the successor function. This is intended to rule out the ...
3
votes
1answer
299 views

Godel 's Ladder: Undecidable PI_N sentences for N =2, 3, …

After Godel's groundbreaking results, a plethora of $\Pi_1^0$ undecidable arithmetical sentences have been found by many authors. But what about $\Pi_n^0$ for $n=2,3,.....$ ? There are, to my ...
9
votes
2answers
379 views

Z_2 versus second-order PA

These days, Peano Arithmetic ($PA$) refers to the first-order version of the axioms, where induction is only over formulas referring to natural number variables. Peano's original version of the ...
1
vote
3answers
481 views

Applicability of Deduction theorem to Primitive recursive arithmetic [closed]

Hello. I already asked the question here. The main point is that I tried to prove in Primitive recursive arithmetic (PRA) the totality of the Ackerman function, and I found, that the single thing ...
3
votes
2answers
394 views

NNO = (first order) PA

Recall the definition of a Natural Numbers Object in a topos, and the first order axioms for Peano Arithmetic. I am more familiar with the first definition than the second, so I cannot tell from the ...
7
votes
4answers
539 views

Reference Request: Non-Standard Models of PA

I am attempting to write an expository paper on non-standard models of PA that is accesible to students taking an introductory graduate course in mathematical logic (covering Godel's incompleteness ...
5
votes
4answers
468 views

parameters in arithmetic induction axiom schemas

The induction schema of Peano Arithmetic is standardly given as the universal closure of $\phi(0)\land \forall x (\phi(x)\rightarrow \phi(x+1)) \rightarrow \forall x\phi(x)$. However, since the ...
7
votes
1answer
482 views

Nelson natural number objects in a topos (say)

Nelson's predicative arithmetic (survey article) is a very weak system of arithmetic extending Robinson's $Q$ (Wikipedia). We can have natural number objects in a topos, or even a merely finitely ...
2
votes
2answers
528 views

Natural numbers of great kolmogorov complexity

Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...
5
votes
2answers
849 views

Set Theory inside Arithmetics via the Ackermann Yoga

Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of $ZF$-Infinity in $PA$ (see for refs this MO question and here for an excellent ...
8
votes
9answers
3k views

Is PA consistent? do we know it?

1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please). 2) There are proofs ...
8
votes
2answers
656 views

The different Branches of Arithmetics

... "and then the different branches of Arithmetic-- Ambition, Distraction, Uglification, and Derision." (Alice in Wonderland, chapter IX: the Mock Turtle's story) As a child I ...
10
votes
2answers
597 views

Is Robinson Arithmetic biinterpretable with some theory in LST?

Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
0
votes
2answers
605 views

Is division considered the mathematical dual of multiplication? [closed]

I'm doing a bit of research for a tech presentation that touches on the subject of mathematical duality. (To be clear, my presentation is not on mathematics or duality, but mentions duality in ...
3
votes
0answers
310 views

example just slightly better than the greedy construction

Roth's theorem provides an estimate for the largest size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial ...
1
vote
0answers
526 views

What is the name for(a^2 + b^2 + c^2 +…)/(a + b + c +…)? [closed]

That is, the sum of squares of some numbers divided by the sum of the numbers. The term "anti-harmonic mean" has been coined for this quantity. I'm hoping there is a better name.
2
votes
2answers
201 views

FTA in first order setting

When I took model theory is an undergraduate, early on we wrestled with trying to state the fundamental theorem of arithmetic in the first order language of arithmetic. The problem was that we needed ...
3
votes
0answers
575 views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
3
votes
2answers
449 views

finite or infinite many quadratic fields embedding into quaternion algebras?

Suppose $H$ is a indefinite quaternion algebra over $\mathbb{Q}$. Are there infinitely many quadratic fields that can be embedded into $H$?
7
votes
3answers
1k views

Gödel's Incompleteness Theorem and the complexity of arithmetic

In How complicated can structures be? Jouko Väänänen says: The guiding result of mathematical logic is the Incompleteness Theorem of Gödel, which says that the logical structure of number theory ...
47
votes
3answers
6k views

Nelson's program to show inconsistency of ZF

At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say: Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel ...
0
votes
1answer
196 views

length of 'digital' recurring expansion of rational number

Here's a question of a 'recreational' nature. A similar question has already been posed for radix 10 in particular: Integer division: the length of the repetitive sequence after the decimal point . ...
5
votes
2answers
546 views

Weakest subsystems of second order arithmetic for mathematical logic

It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it? What about the incompleteness theorems? Is ...
26
votes
8answers
3k views

Arithmetic fixed point theorem

I want to understand the idea of the proof of the artihmetic fixed point theorem. The theorem is crucial in the proof of Gödel's first Incompletness theorem. First some notation: We work in $NT$, the ...
6
votes
1answer
463 views

How to locate the paper that established Robinson Arithmetic?

If I'm not mistaken, it was in his seminal paper “An Essentially Undecidable Axiom System”, published in Proceedings of the International Congress of Mathematics (1950), 729–730, where R.M. ...
4
votes
7answers
2k views

Are real numbers countable in constructive mathematics?

We are talking about ordinary reals in constructive mathematics. Let represent each real number by infinite converging series: $$r = [\;(a_0,b_0),(a_1,b_1),...,(a_i,b_i),...\;]$$ $$where\quad a_i ...
22
votes
3answers
1k views

Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$. Is ...
5
votes
3answers
2k views

Non-computable but easily described arithmetical functions

I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted ...
7
votes
4answers
1k views

Incompleteness and nonstandard models of arithmetic

The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome. Reading Peter Smith's "Gödel Without (Too Many) ...
7
votes
1answer
895 views

models of PA which are isomorphic but not elementarily equivalent?

On page 164 of his book Models of Peano Arithmetic, Kaye states Friedman's Theorem: Let $M{\vDash}PA$ be nonstandard and countable, let $a\in M$ and let $n\in {\mathbb N}$. Then there is a proper ...
9
votes
4answers
2k views

Historically first uses of mathematical induction

I'm interested in find out what were some of the first uses of mathematical induction in the literature. I am aware that in order to define addition and multiplication axiomatically, mathematical ...
5
votes
2answers
833 views

A question about open induction

An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
10
votes
3answers
712 views

Reducing ACA₀ proof to First Order PA

According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA. http://en.wikipedia.org/wiki/Reverse_Mathematics First of all I have a few questions about the proof: a - What ...
2
votes
1answer
2k views

Counting trailing zeros for factorials [closed]

This question is not homework, just asked out of curiosity. I wondered how many zeroes could be found at the end of $1990!$ . I computed something that seemed to work and found out 439. So I computed ...
1
vote
3answers
2k views

“Interesting” properties of sets of natural numbers

On Wikipedia, there is a list of properties of sets of reals, which are in some sense "interesting": just have a look. I could not find a comparable list of properties of sets of natural numbers ...
1
vote
1answer
262 views

Naturally definable sets of natural numbers (3)

[This shall be the last of a series of questions, see Naturally definable sets of natural numbers (2)] I cannot explain why I have been so stubborn not to see the most straight-forward definition for ...
0
votes
3answers
508 views

Naturally definable sets of natural numbers

(This is a follow-up question from over there: Natural models of graphs.) (And it has a follow-up question over there: Naturally definable sets of natural numbers (2): Can the circle be broken?) ...