Skip to main content
since the question was just bumped, fix MO 1.0 -> 2.0 formatting issues
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of $2$-adic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to verify that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\\,(\phi(x)\to\phi(x+1))$$\mathbb Z_p\models\phi(0)\land\forall x\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\\,\phi(x)$$\mathbb Z_p\models\forall x\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of $2$-adic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to verify that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of $2$-adic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to verify that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.

added 4 characters in body
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of dyadic$2$-adic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to showverify that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of dyadic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to show that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of $2$-adic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to verify that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.

Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of dyadic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to show that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\\,\phi(x)$.   QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

  • The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.

  • The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.