Intereting Posts

Can any monomorphism of a subfield of a splitting field be extended to an automorphism?
Number of ways distribute 12 identical action figures to 5 children
Represent every Natural number as a summation/subtraction of distinct power of 3
degree of a field extension
A question about the vector space spanned by shifts of a given function
How to derive an identity between summations of totient and Möbius functions
How many digits of the googol-th prime can we calculate (or were calculated)?
Variation of Tower of Hanoi
How many words can be formed from 'alpha'?
(Ito lemma proof): convergence of $\sum_{i=0}^{n-1}f(W(t_{i}))(W(t_{i+1})-W(t_{i}))^{2}.$
First Course in Linear algebra books that start with basic algebra?
ALL Orthogonality preserving linear maps from $\mathbb R^n$ to $\mathbb R^n$?
Conformal parametrization of an ellipse
Prove $\int^\infty_0\frac x{e^x-1}dx=\frac{\pi^2}{6}$
Another integral with Catalan

Take our old friend Robinson Arithmetic, and cut it down to a theory of successor and addition.

To spell that out (just to ensure that we are singing from the same hymn sheet), take the first-order theory with $\mathsf{0}$ as the sole constant, and $\mathsf{S}$ and $+$ as the built-in function signs, with the five axioms

- $\mathsf{\forall x\ 0 \neq Sx}$
- $\mathsf{\forall x\forall y\ Sx = Sy \to x = y}$
- $\mathsf{\forall x(x \neq 0 \to \exists y\ x = Sy)}$
- $\mathsf{\forall x\ (x + 0) = x}$
- $\mathsf{\forall x\forall y\ (x + Sy) = S(x + y)}$

and whose deductive system is your favourite classical first-order logic with identity.

- Logic and number theory books
- Does every nonempty definable finite set have a definable member?
- Show that $p \Rightarrow (\neg(q \land \neg p))$ is a tautology
- Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions
- intersection of the empty set and vacuous truth
- Book about different kind of logic

Since this cut-down theory doesn’t represent the recursive functions, you can’t use the usual proof of undecidability for an arithmetic. Since this cut-down theory doesn’t even know that addition is commutative, i.e. can’t prove $\mathsf{\forall x\forall y\ x = y = y + x}$, you can’t do the kind of manipulations inside the theory involved in a quantifier-elimination proof of decidability (cf. what happens when we add induction to this theory to get Presburger arithmetic, i.e. Peano Arithmetic minus multiplication).

Ermmmm …. so …. Drat it, I *ought* to know how to prove that this cut-down theory is decidable or that it is undecidable. But I seem to have forgotten, assuming I ever knew, and searching around hasn’t helped me out. OK folks, I’m more than likely to be having a senior moment here — so be gentle! — but how do we show the theory is (un)decidable?

- Logic, set theory, independence proofs, etc
- Show that the conditional statement is a tautology without using a truth table
- Circular logic in set definition - Tautology?
- Are there non-equivalent cardinal arithmetics?
- Proof of Drinker paradox
- Alternative categorification of metric spaces?
- Good books on mathematical logic?
- For what $a \in \Bbb R$ does $\neg(3a>21\implies a \leq 5)$ hold?
- Formal System and Formal Logical System
- “If P, then Q; If P, then R; Therefore: If Q, then R.” Fallacy and Transitivity

Consider the model $\mathfrak{M}$ with domain the natural numbers $\mathbb{N}$ plus one more object, say $a$. Define $S$ on $\mathbb{N}$ normally and $Sa=a$. Define $+$ on $\mathbb{N}$ normally and $x+a=a+x=a$ for all $x \in \mathfrak{M}$.

Then it is quite easy to prove that $\mathfrak{M}$ is a model of the $5$ axioms in which the statement $\varphi$, “there exists an $x$ such that $Sx=x$” is true.

So $\varphi$ cannot be decided by the axioms since in the standard model it is false and true here, so the theory is undecidable.

It is undecidable.

Let $\mathcal L$ be the first-order language with equality and one binary predicate $p({-},{-})$ and no constants or function symbols. Call an $\mathcal L$-sentence of the form $\varphi\land \exists x\exists y(x\ne y)$ “fancy” — it is then well known that satisfiability of fancy sentences is undecidable.

Consider the following translation from $\mathcal L$ into the your additive Robinson arithmetic:

$$\overline{\varphi\land\psi} \equiv \overline\varphi\land\overline \psi \qquad \overline{\neg\varphi} \equiv \neg\overline\varphi$$

$$\overline{\exists x.\varphi} \equiv \exists x(x=\mathsf S x \land \overline\varphi) \qquad \overline{x=y} \equiv x=y$$

$$\overline{p(x,y)} \equiv x+y=x $$

Now clearly if $\varphi$ is a fancy sentence and $\overline{\varphi}$ is consistent with additive Robinson arithmetic, then $\varphi$ is satisfiable — it is trivial to derive a model of the latter from a model of the former; the domain will be the elements that are their own successors.

On the other hand if $\varphi$ is a satisfiable fancy sentence, then there’s a model of additive Robinson arithmetic that satisfies $\overline\varphi$, as follows:

Let $(A,p)$ be a model of $\varphi$; without loss of generality take $A$ to be disjoint from $\mathbb N$. Because $\varphi$ is fancy $A$ has at least two elements, so let $f:A\to A$ be such that $f(a)\ne a$ for all $a\in A$. Now construct an model of additive Robinson arithmetic with domain $\mathbb N\cup A$, as follows:

$$ 0 = 0 $$

$$ \mathsf S n = (n+1) \qquad \mathsf Sa = a$$

$$ n\oplus n’ = (n+n’) \qquad a\oplus n= n\oplus a = a \qquad

a\oplus a’ = \begin{cases} a & \text{when }p(a,a’) \\ f(a) & \text{otherwise} \end{cases}$$

- Cannabis Equation
- Characteristics in the theory of PDE's – What's Going On?
- Evalutating $\lim_{x\to +\infty} \sqrt{x^2+4x+1} -x$
- How do I prove that $\det A= \det A^t$?
- What is the relation between connections on principal bundles and connections on vector bundles?
- The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $ p-(\frac{-ab}{p})$
- Prob 12, Sec 26 in Munkres' TOPOLOGY, 2nd ed: How to show that the domain of a perfect map is compact if its range is compact?
- An expression for $U_{h,0}$ given $U_{n,k}=\frac{c^n}{c^n-1}(U_{n-1,k+1})-\frac{1}{c^n-1}(U_{n-1,k})$
- Intersection of a properly nested sequence of convex sets , if nonempty and bounded , can never be open?
- Hexagonal circle packings in the plane
- Prove ${\large\int}_0^\infty\left({_2F_1}\left(\frac16,\frac12;\frac13;-x\right)\right)^{12}dx\stackrel{\color{#808080}?}=\frac{80663}{153090}$
- Polynomial of degree $-\infty$?
- Calculating equidistant points around an ellipse arc
- A formal proof required using real analysis
- Construct a finite field of 16 elements and find a generator for its multiplicative group.