# Tagged Questions

71 views

### How to define multiplication in addition terms in monadic second order logic?

How to define multiplication in addition terms in monadic second order logic? meaning, having natural numbers variables, N sub-groups variables, successor function, negations, "for every", "there ...
22 views

### An implication between two statements concerning integers

Does "Every non-empty bounded below set of integers has a smallest element" $\implies$ "If $m,n$ are integers with $m>n$ , then $m-n\ge1$" ? If not then what additional assumption is needed ...
70 views

### Logic and mathematical variables as objects

I am currently working on describing a predicate logic for which the objects are mathematical variables. Thus I can say stuff like: $\forall x: R(x) \implies \text{operator}(x)=1$ Here $x$ is a ...
117 views

### Why is the language of arithmetic usually $(+, \cdot, 0, s)$, not $(+, \cdot, 0, 1)$?

The formalized theory of arithmetic has usually $(+, \cdot, 0, s)$ as its language. However, from what we usually do in ring theory, it seems natural to use $(+, \cdot, 0, 1)$ as the language of ...
56 views

### $pq\mid (a - pq) \implies pq\mid a$?

This may be a dumb question. I'm not a math major, but, since I'm studying logic, I decided to learn a bit of number theory. I've just begun my studies (I'm reading Davenport's The Higher Arithmetic) ...
55 views

453 views

### Is the set of PA theorems the same as the set of solvable halting problems?

I am not sure if this is a trivial question. By Post's theorem we know that every PA (first order logic) theorem is equivalent to stating that a given input C in a given Turing machine halts or ...
75 views

### Proof by induction on $\{1,\ldots,m\}$ instead of $\mathbb{N}$

I often see proofs, that claim to be by induction, but where the variable we induct on doesn't take value is $\mathbb{N}$ but only in some set $\{1,\ldots,m\}$. Imagine for example that we have to ...
165 views

### Is every φ above the second level of the arithmetical hierarchy independent of PA?

If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
194 views

### What is it wrong in this argument about the interpretability hierarchy?

This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one. Background: (from ...
76 views

### Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n? This is a follow up from a previous question: Given a φ independent of PA which is true ...
193 views

### Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
128 views

### Similarity between integer and logical operations through parity

Lets observe the parity property of integers while adding them or multiplying. It's simple to notice that when we add two numbers, the parity of the result depends on parity of summands: ...
180 views

### Is the arithmetic most mathematicans use a modelled within first or a second order logic?

I often read that arithmetic in first order logic has problems and you really want to do it in second order logic. However, aren't the Zermelo–Fraenkel axioms written down in the language of first ...
159 views

304 views

### How is Kleene's T predicate defined?

What I don't understand is how to extract information from the number that encode the computation history. I know it's defined in Kleene's Introduction to Metamathematics. But what page? References ...