Skip to main content
MathOverflow

Return to Answer

fixed Peano axiom for addition
Source Link
user44143
user44143

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabd \rightarrow Sace) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The key definition of an $\omega$-model is "an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$". In this case we take $R_1$ to be the above $R$, and $R_2$ to be the above $S$, though this is not specified in the paper, and the whole definition is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415.

The advantage of using an $\omega$-model is that in an $\omega$-model the clauses above are enough to determine the addition relation completely, and to determine that any two elements can be added. Again, this is the only way I see to make sense of the argument, even though the paper does not specify this use of those clauses.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to define $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The key definition of an $\omega$-model is "an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$". In this case we take $R_1$ to be the above $R$, and $R_2$ to be the above $S$, though this is not specified in the paper, and the whole definition is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415.

The advantage of using an $\omega$-model is that in an $\omega$-model the clauses above are enough to determine the addition relation completely, and to determine that any two elements can be added. Again, this is the only way I see to make sense of the argument, even though the paper does not specify this use of those clauses.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to define $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabd \rightarrow Sace) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The key definition of an $\omega$-model is "an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$". In this case we take $R_1$ to be the above $R$, and $R_2$ to be the above $S$, though this is not specified in the paper, and the whole definition is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415.

The advantage of using an $\omega$-model is that in an $\omega$-model the clauses above are enough to determine the addition relation completely, and to determine that any two elements can be added. Again, this is the only way I see to make sense of the argument, even though the paper does not specify this use of those clauses.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to define $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

rearranged
Source Link
user44143
user44143

I think I understand how this begins now. The key definition is that:

an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$

or for these purposes

an $\omega$-model for the language $(R,S)$ is a model $M$ such that $(|M|,R)$ is isomorphic to $(\omega, x +1=y)$

This is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415; furthermore, the language is not specified in the paper. But once I figured that out, I could make sense of the rest of the argument.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The paper does not specify this useThe key definition of these clauses, but in an $\omega$-model they are enough to determineis "an $\omega$-model for the addition relation completelylanguage $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$". In this case we take $R_1$ to be the above $R$, and $R_2$ to be the above $S$, though this is not specified in the paper, and the whole definition is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415.

The advantage of using an $\omega$-model is that in an $\omega$-model, the first two clauses above are enough to determine the addition relation completely, and to determine that any two elements can be added. Again, this is the only way I see to make sense of the argument, even though the paper does not specify this use of those clauses.

So the difference in the treatment of the two original sentences is is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to be definingdefine $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

I think I understand how this begins now. The key definition is that:

an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$

or for these purposes

an $\omega$-model for the language $(R,S)$ is a model $M$ such that $(|M|,R)$ is isomorphic to $(\omega, x +1=y)$

This is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415; furthermore, the language is not specified in the paper. But once I figured that out, I could make sense of the rest of the argument.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The paper does not specify this use of these clauses, but in an $\omega$-model they are enough to determine the addition relation completely. In particular, in an $\omega$-model, the first two clauses are enough to determine that any two elements can be added.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to be defining $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The key definition of an $\omega$-model is "an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$". In this case we take $R_1$ to be the above $R$, and $R_2$ to be the above $S$, though this is not specified in the paper, and the whole definition is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415.

The advantage of using an $\omega$-model is that in an $\omega$-model the clauses above are enough to determine the addition relation completely, and to determine that any two elements can be added. Again, this is the only way I see to make sense of the argument, even though the paper does not specify this use of those clauses.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to define $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

removed unnecessary $\bigvee \bigwedge$ format, added notes on other typos and confusions
Source Link
user44143
user44143

I think I understand how this begins now. The key definition is that:

an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$

or for these purposes

an $\omega$-model for the language $(R,S)$ is a model $M$ such that $(|M|,R)$ is isomorphic to $(\omega, x +1=y)$

This is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415; furthermore, the language is not specified in the paper. But once I figured that out, I could make sense of the rest of the argument.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The paper does not specify this use of these clauses, but in an $\omega$-model they are enough to determine the addition relation completely. In particular, in an $\omega$-model, the first two clauses are enough to determine that any two elements can be added.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$ with. (The paper also says to put the rightquantifier-free portion into $\bigvee \bigwedge$$\bigvee_i \bigwedge_j$ form: $$\forall a,b,c,d,e\, \exists m,n,u,v\,$$ $$\Big((Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Sabc)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rbc \wedge \neg Sabd)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rde \wedge \neg Sabd)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge Sade \wedge \neg Sabd)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rbc \wedge c=d)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rde \wedge c=d)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge Sade \wedge c=d)\Big)$$

Now, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

As warnings forI also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should be replaced byread $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to be defining $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

I think I understand how this begins now. The key definition is that:

an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$

or for these purposes

an $\omega$-model for the language $(R,S)$ is a model $M$ such that $(|M|,R)$ is isomorphic to $(\omega, x +1=y)$

This is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415; furthermore, the language is not specified in the paper. But once I figured that out, I could make sense of the rest of the argument.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The paper does not specify this use of these clauses, but in an $\omega$-model they are enough to determine the addition relation completely. In particular, in an $\omega$-model, the first two clauses are enough to determine that any two elements can be added.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into $G_1(\theta)$ with the right $\bigvee \bigwedge$ form: $$\forall a,b,c,d,e\, \exists m,n,u,v\,$$ $$\Big((Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Sabc)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rbc \wedge \neg Sabd)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rde \wedge \neg Sabd)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge Sade \wedge \neg Sabd)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rbc \wedge c=d)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge \neg Rde \wedge c=d)$$ $$\vee\ (Sa0a \wedge Smmu \wedge Snnv \wedge Ruv \wedge Sade \wedge c=d)\Big)$$

Now we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

As warnings for the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should be replaced by $l>0$
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (4) seems to be defining $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by another definition.

I think I understand how this begins now. The key definition is that:

an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$

or for these purposes

an $\omega$-model for the language $(R,S)$ is a model $M$ such that $(|M|,R)$ is isomorphic to $(\omega, x +1=y)$

This is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415; furthermore, the language is not specified in the paper. But once I figured that out, I could make sense of the rest of the argument.

Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.

To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:

\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabc \rightarrow Sade) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}

The paper does not specify this use of these clauses, but in an $\omega$-model they are enough to determine the addition relation completely. In particular, in an $\omega$-model, the first two clauses are enough to determine that any two elements can be added.

So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.

To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.

I also see a few noteworthy items in the rest of the procedure:

  • Step (1) seems to have a typo, where $l<0$ should read $l>0$.
  • Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
  • Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
  • Step (4) seems to be defining $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
  • Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.

The density of confusing exposition in this section is remarkable.

added 9 characters in body
Source Link
user44143
user44143
added 36 characters in body
Source Link
user44143
user44143
added 40 characters in body
Source Link
user44143
user44143
added 11 characters in body
Source Link
user44143
user44143
Source Link
user44143
user44143