1
vote
2answers
237 views

Infinite play with tape, or covering the integers with prime arithmetic progressions

It is possible that a more technical version of this question has been asked and answered in the literature. If so, then a reference is much appreciated. I will phrase it in terms of colored tapes ...
14
votes
2answers
501 views

Unboundedness of primes in bounded arithmetic

Wilkie's well known question asks whether $I\Delta_{0}$ proves the unboundedness of primes. We know that by adding a sentence to $I\Delta_{0}$ which says "the exponential function is total", it is ...
3
votes
1answer
415 views

Forcing and divisibility

A version of this question got a couple of comments but no answer on stackexchange. I learned the concept of forcing in logic from Boolos & Jeffrey's book Computability and Logic (second edition, ...
7
votes
1answer
411 views

Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?

In the math.se question Proof of no prime-representing polynomial in 2 variables, Alon Amit asks if Ribenboim's claim that a prime-representing polynomial (a Diophantine polynomial in which the ...
9
votes
2answers
845 views

Non-Standard Prime

Hello, My question is about the non-standard models of the integers. If we add to the Peano's axioms $P$ of arithmetic the following axioms for a fixed constant $c$: $c \neq 0$, $c \neq 1$, $c \neq ...
19
votes
1answer
1k views

Nontrivial circular arguments?

There is a famous circular argument for the Prime Number Theorem (PNT). It turns out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates that taken together imply ...
4
votes
1answer
423 views

Implication of Polignac's conjecture on prime distribution in models of PA

Polignac's conjecture (PC) is that there exists infinitely many pairs of consecutive prime numbers that are a distance $d$ apart for some natural number $d$. The twin prime conjecture is the ...
24
votes
3answers
2k 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
1answer
925 views

Polynomial representing prime numbers

Along the lines of Polynomial representing all nonnegative integers, but likely well-known question: is there a polynomial $f \in \mathbb Q[x_1, \dots, x_n]$ such that $f(\mathbb Z\times\mathbb ...