Tagged Questions

0
votes
0answers
49 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
44 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
1
vote
1answer
101 views

Are there statements in set theory about arithmetic beyond the reach of the analytical hierarchy?

Even if the answer were negative for arithmetics(I have no idea), in the more general case: Can any mathematical statement be expressed as a $\Delta_m^n$ (with n, m belongs to N) statement in a chosen ...
16
votes
1answer
366 views

Are the real numbers ever needed to prove a property of the natural numbers?

Suppose no one had invented/discovered the real numbers yet (so e.g., no calculus), would this constrain the possible theorems or knowledge we could have about the natural numbers?
-1
votes
3answers
166 views

Two easy proofs by contradiction

Check the validity of the statements below using contradiction method (i) p: The sum of an irrational number and a rational number is irrational (ii) q: If $n$ is a real number with $n ...
7
votes
4answers
415 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 ...
2
votes
2answers
65 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 ...
5
votes
1answer
136 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 ...
2
votes
3answers
156 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 ...
2
votes
1answer
71 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 ...
9
votes
1answer
136 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 ...
2
votes
2answers
86 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: ...
3
votes
1answer
139 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 ...
3
votes
0answers
125 views

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?

There is a recursive definition of the set of squares which uses only addition: $CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$ $IS(x)⇔ x=0 ...
3
votes
2answers
160 views

$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?

Update : Should have left the Arithmetic out of this question, the new modified question is posted here : $\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable? ...
2
votes
2answers
86 views

logic and with additions

the table of logic and ($ \wedge $) is 0 0 0 0 1 0 1 0 0 1 1 1 I can build a "logic and" operation with additions and subtractions?
3
votes
2answers
157 views

What does a nonstandard proof of Con(PA) look like?

As in Godel's incompleteness theorem natural numbers encode proofs of theorems. Due to Godel's completeness theorem there is a natural number (in some nonstandard model) that proves $Con(PA)$. What ...
1
vote
3answers
227 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 ...
13
votes
3answers
617 views

Can multiplication be defined in terms of divisibility?

Peano Arithmetic has two axioms which use the multiplication symbol: ∀x:x*0=0 and ∀x:∀y:x*Sy=x+x*y. The 2-term relation "x divides y" can be expressed as D(x,y) := ∃z:z*x=y. Multiplication is a ...
4
votes
1answer
270 views

Non Higher-Order Formulation of Gödels Incompletness Theorem

I was just having a look at Gödels incompletness theorem as found in: http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf I noticed that Gödel used a higher order logic. At least ...