Section 2.2: Problem 28 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

For each of the following pairs of structures, show that they are not elementarily equivalent, by giving a sentence true in one and false in the other. (The language here contains $\forall$ and a two-place function symbol $\circ$ .)

(a) $(\mathbb{R};\times)$ and $(\mathbb{R}^{∗};\times^{∗})$ , where $\times$ is the usual multiplication operation on the real numbers, $\mathbb{R}^{∗}$ is the set of non-zero reals, and $\times^{∗}$ is $\times$ restricted to the non-zero reals.

(b) $(\mathbb{N};+)$ and $(\mathbb{P};+^{∗})$ , where $\mathbb{P}$ is the set of positive integers, and $+^{∗}$ is usual addition operation restricted to $\mathbb{P}$ .

(c) Better yet, for each of the four structures of parts (a) and (b), give a sentence true in that structure and false in the other three.

(a), (b) and (c). The following table lists some sentences and whether each one is true in each structure.

Symbol	Formula
$\alpha$	$\exists x\forall yx\circ y=x$
	Exists $0$ ( $\times$ )
$\beta$	$\exists x\forall y(x\circ y=y\wedge\exists zy\circ z=x)$
	Exists $0$ ( $+$ ) or $1$ ( $\times$ ) such that every number has its opposite
$\gamma$	$\exists x\forall y\forall z(x=y\circ z\rightarrow(y=x\wedge z=x))$
	Exists $0\in\mathbb{N}$ ( $+$ )
$\delta$	$\forall x\exists yx\circ y\neq y$
	Absence of $0$ ( $+$ ) or $1$ ( $\times$ )
$\delta'$	$\exists x\forall y\forall zx\neq y\circ z$
	Exists number which is not the result of $\circ$ for any numbers (in particular, $\delta'\vDash\delta$ )

Formula	$(\mathbb{R};\times)$	$(\mathbb{R}^{∗};\times^{∗})$	$(\mathbb{N};+)$	$(\mathbb{P};+^{∗})$
$\alpha$	+
$\beta$		+
$\gamma$			+
$\delta$				+
$\delta'$				+

By the way, why $\delta'\vDash\delta$ . Suppose there is a model $\mathfrak{A}$ of $\delta'$ . Then $\vDash_{\mathfrak{A}}\exists x\forall y\forall zx\neq y\circ z$ iff $\vDash_{\mathfrak{A}}\exists y\forall x\forall zy\neq x\circ z$ only if $\vDash_{\mathfrak{A}}\forall x\exists y\forall zy\neq x\circ z$ only if $\vDash_{\mathfrak{A}}\forall x\exists yy\neq x\circ y$ which is logically equivalent to $\delta$ .

Subpages

Section 2.2: Problem 28 Solution

Section 2.2: Problem 28 Solution