Skip to main content
correct reference
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

[4] Emil Jeřábek, Division by zero, in: Liber Amicorum Alberti: A Tribute to Albert VisserArchive for Mathematical Logic 55 (J. van Eijck, R. Iemhoff, J. J. Joosten, eds.2016), Tributes volno. 30, College Publications, London7, 2016pp. 997–1013.

[4] Emil Jeřábek, Division by zero, in: Liber Amicorum Alberti: A Tribute to Albert Visser (J. van Eijck, R. Iemhoff, J. J. Joosten, eds.), Tributes vol. 30, College Publications, London, 2016.

[4] Emil Jeřábek, Division by zero, Archive for Mathematical Logic 55 (2016), no. 7, pp. 997–1013.

reference for Q
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

EDIT: I realized that the “exercise” in Claim 2 below was incorrect, so let me formulate the result for the slightly stronger theory $$Q^+=Q+\forall x\,0\cdot x=0$$ where it works. I can still proveWhile $D_Q$ is also decidable (hopefully correctly now), but the argumentthis is considerably more complicated and would not fit heredifficult to prove; see [4].

[3] Alex Wilkie, Some results and problems on weak systems of arithmetic, in: Angus Macintyre (ed.), Logic Colloquium ’77, North-Holland, 1978, pp. 285–296.

[4] Emil Jeřábek, Division by zero, in: Liber Amicorum Alberti: A Tribute to Albert Visser (J. van Eijck, R. Iemhoff, J. J. Joosten, eds.), Tributes vol. 30, College Publications, London, 2016.

EDIT: I realized that the “exercise” in Claim 2 below was incorrect, so let me formulate the result for the slightly stronger theory $$Q^+=Q+\forall x\,0\cdot x=0$$ where it works. I can still prove $D_Q$ is decidable (hopefully correctly now), but the argument is more complicated and would not fit here.

[3] Alex Wilkie, Some results and problems on weak systems of arithmetic, in: Angus Macintyre (ed.), Logic Colloquium ’77, North-Holland, 1978, pp. 285–296.

EDIT: I realized that the “exercise” in Claim 2 below was incorrect, so let me formulate the result for the slightly stronger theory $$Q^+=Q+\forall x\,0\cdot x=0$$ where it works. While $D_Q$ is also decidable, this is considerably more difficult to prove; see [4].

[3] Alex Wilkie, Some results and problems on weak systems of arithmetic, in: Angus Macintyre (ed.), Logic Colloquium ’77, North-Holland, 1978, pp. 285–296.

[4] Emil Jeřábek, Division by zero, in: Liber Amicorum Alberti: A Tribute to Albert Visser (J. van Eijck, R. Iemhoff, J. J. Joosten, eds.), Tributes vol. 30, College Publications, London, 2016.

correction
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

EDIT: I realized that the “exercise” in Claim 2 below was incorrect, so let me formulate the result for the slightly stronger theory $$Q^+=Q+\forall x\,0\cdot x=0$$ where it works. I can still prove $D_Q$ is decidable (hopefully correctly now), but the argument is more complicated and would not fit here.

Proposition: $D_Q$$D_{Q^+}$ is decidable (in fact, coNP-complete).

Proof: The main point is that $Q$$Q^+$ has weird models where one can satisfy next to any equation $p(\ob x)=q(\ob x)$, and the exceptions are easy to deal with.

Let $\ub n=S^n(0)$ denote the numeral for $n\in\N$. Consider the model $\N^\infty$ of $Q$$Q^+$ with domain $\mathbb N\cup\{\infty\}$, where $x+\infty=\infty+x=x\cdot\infty=\infty\cdot x=\infty$, except that $\infty\cdot0=0$$\infty\cdot0=0\cdot\infty=0$. By induction on the complexity of the term $p$, we show

Claim 1: If the value of $p(\ob\infty)$ in $\N^\infty$ is $n\in\N$, then $Q$$Q^+$ proves $\forall\ob x\,p(\ob x)=\ub n$.

Given terms $p,q$, we can compute the value of $p(\ob\infty)$ and $q(\ob\infty)$ in $\N^\infty$. If both equal $\infty$, we have a witness that $(p,q)\notin D_Q$$(p,q)\notin D_{Q^+}$ and we are done. By Claim 1, the remaining cases are when one of the terms is provably equal to a standard constant, hence we can assume without loss of generality that $q$ is $\ub n$ for some $n\in\N$.

Claim 2: $Q$ proves $$\begin{align*} x+y=\ub n&\to\LOR_{k,l\colon k+l=n}(x=\ub k\land y=\ub l),\\ x\cdot y=\ub n&\to\LOR_{k,l\colon kl=n}(x=\ub k\land y=\ub l)\qquad\text{for }n\ne0,\\ x\cdot y=0&\to x=0\lor y=0 \end{align*}$$$$\begin{align*} x+y=\ub n&\to\LOR_{k,l\colon k+l=n}(x=\ub k\land y=\ub l),\\ x\cdot y=\ub n&\to x=0\lor\LOR_{k,l\colon kl=n}(x=\ub k\land y=\ub l)\qquad\text{for }n\ne0,\\ x\cdot y=0&\to x=0\lor y=0 \end{align*}$$ for every $n\in\N$.

Claim 3: $Q$$Q^+$ proves $p(\ob x)\le\ub n\to p(\ob x)=p(\ob x^{\le n})$.

Again, we prove this by induction on the complexity of $p$. For example, assume that $p=p_0\cdot p_1$. Reason in $Q$$Q^+$, and let $p(\ob x)=\ub m$ for some $m=0,\dots,n$. If $m\ne 0$, then $p_0(\ob x)=\ub k$ and $p_1(\ob x)=\ub l$ for some $k,l\le n$ such that $kl=m$ by Claim 2 (the case $p_0(\ob x)=0$ is impossible by the extra axiom). By the induction hypothesis, we have also $p_0(\ob x^{\le n})=\ub k$ and $p_1(\ob x^{\le n})=\ub l$, hence $p(\ob x^{\le n})=\ub m$.

If $m=0$, then Claim 2 gives $p_0(\ob x)=0$ or $p_1(\ob x)=0$, hence $p_0(\ob x^{\le n})=0$ or $p_1(\ob x^{\le n})=0$ by the induction hypothesis. In the latter case, we obtain $p(\ob x^{\le n})=0$ immediately; in the former case, we observe that the value $u$ of $p_1(\ob x^{\le n})$ is standard, hence $0\cdot u=0$, sothus $p(\ob x^{\le n})=0$ follows as well.

Now, resuming the proof of decidability of $D_Q$$D_{Q^+}$: if there is a model of $Q$$Q^+$ in which $p(\ob x)=\ub n$ is satisfiable, then by Claim 3, it is also satisfiable by a tuple of elements of $\{0,\dots,n\}$. The value of $p(\vec x)$ on standard tuples is evaluated the same in all models, hence we can as well do it in the standard model. Thus, $$(p(\ob x),\ub n)\in D_Q\iff\forall\ob x\in\{0,\dots,n\}\,p(\ob x)\ne n,$$$$(p(\ob x),\ub n)\in D_{Q^+}\iff\forall\ob x\in\{0,\dots,n\}\,p(\ob x)\ne n,$$ which is a decidable condition.

Proposition: $D_Q$ is decidable (in fact, coNP-complete).

Proof: The main point is that $Q$ has weird models where one can satisfy next to any equation $p(\ob x)=q(\ob x)$, and the exceptions are easy to deal with.

Let $\ub n=S^n(0)$ denote the numeral for $n\in\N$. Consider the model $\N^\infty$ of $Q$ with domain $\mathbb N\cup\{\infty\}$, where $x+\infty=\infty+x=x\cdot\infty=\infty\cdot x=\infty$, except that $\infty\cdot0=0$. By induction on the complexity of the term $p$, we show

Claim 1: If the value of $p(\ob\infty)$ in $\N^\infty$ is $n\in\N$, then $Q$ proves $\forall\ob x\,p(\ob x)=\ub n$.

Given terms $p,q$, we can compute the value of $p(\ob\infty)$ and $q(\ob\infty)$ in $\N^\infty$. If both equal $\infty$, we have a witness that $(p,q)\notin D_Q$ and we are done. By Claim 1, the remaining cases are when one of the terms is provably equal to a standard constant, hence we can assume without loss of generality that $q$ is $\ub n$ for some $n\in\N$.

Claim 2: $Q$ proves $$\begin{align*} x+y=\ub n&\to\LOR_{k,l\colon k+l=n}(x=\ub k\land y=\ub l),\\ x\cdot y=\ub n&\to\LOR_{k,l\colon kl=n}(x=\ub k\land y=\ub l)\qquad\text{for }n\ne0,\\ x\cdot y=0&\to x=0\lor y=0 \end{align*}$$ for every $n\in\N$.

Claim 3: $Q$ proves $p(\ob x)\le\ub n\to p(\ob x)=p(\ob x^{\le n})$.

Again, we prove this by induction on the complexity of $p$. For example, assume that $p=p_0\cdot p_1$. Reason in $Q$, and let $p(\ob x)=\ub m$ for some $m=0,\dots,n$. If $m\ne 0$, then $p_0(\ob x)=\ub k$ and $p_1(\ob x)=\ub l$ for some $k,l\le n$ such that $kl=m$ by Claim 2. By the induction hypothesis, we have also $p_0(\ob x^{\le n})=\ub k$ and $p_1(\ob x^{\le n})=\ub l$, hence $p(\ob x^{\le n})=\ub m$.

If $m=0$, then Claim 2 gives $p_0(\ob x)=0$ or $p_1(\ob x)=0$, hence $p_0(\ob x^{\le n})=0$ or $p_1(\ob x^{\le n})=0$ by the induction hypothesis. In the latter case, we obtain $p(\ob x^{\le n})=0$ immediately; in the former case, we observe that the value $u$ of $p_1(\ob x^{\le n})$ is standard, hence $0\cdot u=0$, so $p(\ob x^{\le n})=0$ follows as well.

Now, resuming the proof of decidability of $D_Q$: if there is a model of $Q$ in which $p(\ob x)=\ub n$ is satisfiable, then by Claim 3, it is also satisfiable by a tuple of elements of $\{0,\dots,n\}$. The value of $p(\vec x)$ on standard tuples is evaluated the same in all models, hence we can as well do it in the standard model. Thus, $$(p(\ob x),\ub n)\in D_Q\iff\forall\ob x\in\{0,\dots,n\}\,p(\ob x)\ne n,$$ which is a decidable condition.

EDIT: I realized that the “exercise” in Claim 2 below was incorrect, so let me formulate the result for the slightly stronger theory $$Q^+=Q+\forall x\,0\cdot x=0$$ where it works. I can still prove $D_Q$ is decidable (hopefully correctly now), but the argument is more complicated and would not fit here.

Proposition: $D_{Q^+}$ is decidable (in fact, coNP-complete).

Proof: The main point is that $Q^+$ has weird models where one can satisfy next to any equation $p(\ob x)=q(\ob x)$, and the exceptions are easy to deal with.

Let $\ub n=S^n(0)$ denote the numeral for $n\in\N$. Consider the model $\N^\infty$ of $Q^+$ with domain $\mathbb N\cup\{\infty\}$, where $x+\infty=\infty+x=x\cdot\infty=\infty\cdot x=\infty$, except that $\infty\cdot0=0\cdot\infty=0$. By induction on the complexity of the term $p$, we show

Claim 1: If the value of $p(\ob\infty)$ in $\N^\infty$ is $n\in\N$, then $Q^+$ proves $\forall\ob x\,p(\ob x)=\ub n$.

Given terms $p,q$, we can compute the value of $p(\ob\infty)$ and $q(\ob\infty)$ in $\N^\infty$. If both equal $\infty$, we have a witness that $(p,q)\notin D_{Q^+}$ and we are done. By Claim 1, the remaining cases are when one of the terms is provably equal to a standard constant, hence we can assume without loss of generality that $q$ is $\ub n$ for some $n\in\N$.

Claim 2: $Q$ proves $$\begin{align*} x+y=\ub n&\to\LOR_{k,l\colon k+l=n}(x=\ub k\land y=\ub l),\\ x\cdot y=\ub n&\to x=0\lor\LOR_{k,l\colon kl=n}(x=\ub k\land y=\ub l)\qquad\text{for }n\ne0,\\ x\cdot y=0&\to x=0\lor y=0 \end{align*}$$ for every $n\in\N$.

Claim 3: $Q^+$ proves $p(\ob x)\le\ub n\to p(\ob x)=p(\ob x^{\le n})$.

Again, we prove this by induction on the complexity of $p$. For example, assume that $p=p_0\cdot p_1$. Reason in $Q^+$, and let $p(\ob x)=\ub m$ for some $m=0,\dots,n$. If $m\ne 0$, then $p_0(\ob x)=\ub k$ and $p_1(\ob x)=\ub l$ for some $k,l\le n$ such that $kl=m$ by Claim 2 (the case $p_0(\ob x)=0$ is impossible by the extra axiom). By the induction hypothesis, we have also $p_0(\ob x^{\le n})=\ub k$ and $p_1(\ob x^{\le n})=\ub l$, hence $p(\ob x^{\le n})=\ub m$.

If $m=0$, then Claim 2 gives $p_0(\ob x)=0$ or $p_1(\ob x)=0$, hence $p_0(\ob x^{\le n})=0$ or $p_1(\ob x^{\le n})=0$ by the induction hypothesis, thus $p(\ob x^{\le n})=0$ as well.

Now, resuming the proof of decidability of $D_{Q^+}$: if there is a model of $Q^+$ in which $p(\ob x)=\ub n$ is satisfiable, then by Claim 3, it is also satisfiable by a tuple of elements of $\{0,\dots,n\}$. The value of $p(\vec x)$ on standard tuples is evaluated the same in all models, hence we can as well do it in the standard model. Thus, $$(p(\ob x),\ub n)\in D_{Q^+}\iff\forall\ob x\in\{0,\dots,n\}\,p(\ob x)\ne n,$$ which is a decidable condition.

do the argument for Q properly
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209
Loading
added 693 characters in body
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209
Loading
added 1143 characters in body
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209
Loading
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209
Loading