# Tagged Questions

Deprecated; please use a more specific tag.

42 views

### n-th prime in first order arithmetics [closed]

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 ...
26 views

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 ...
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 ...
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) ...
900 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 ...
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 ...
834 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 ...
713 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 ...
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 ...
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 ...