CS486 Problem Set 9 DUE: 4/17/03

1.

a)

We give a finite model of a semigroup that is not commutative.

$$D = \{ \mathsf{a}, \mathsf{b} \}$$

$$\boldsymbol{=} = \{ (\mathsf{a},\mathsf{a}), (\mathsf{b},\mathsf{b}) \}$$

$$\begin{array}[t]{\vert c\vert\vert c\vert c\vert} \hline... ...thsf{b} & \mathsf{b} & \mathsf{b} \\ \hline \end{array}$$

Clearly, $\boldsymbol{=}$ satisfies ref, sym, and trans. Likewise, $\boldsymbol{\circ}$ satisifies subst, functionality, and assoc. Hence, $\langle D, \boldsymbol{=}, \boldsymbol{\circ} \rangle$ is a semigroup. Furthermore, $\mathsf{a} \boldsymbol{\circ} \mathsf{b} = \mathsf{a} \neq \mathsf{b} = \mathsf{b} \circ \mathsf{a}$; hence $\langle D, \boldsymbol{=}, \boldsymbol{\circ} \rangle$ is not a commutative semigroup.

b)

We give a finite model of a commutative semigroup that is not a monoid.

$$D = \{ \mathsf{a}, \mathsf{b} \}$$

$$\boldsymbol{=} = \{ (\mathsf{a},\mathsf{a}), (\mathsf{b},\mathsf{b}) \}$$

$$\begin{array}[t]{\vert c\vert\vert c\vert c\vert} \hline... ...thsf{b} & \mathsf{a} & \mathsf{a} \\ \hline \end{array}$$

Clearly, $\boldsymbol{=}$ satisfies ref, sym, and trans. Likewise, $\boldsymbol{\circ}$ satisifies subst, functionality, assoc, and comm. Hence, $\langle D, \boldsymbol{=}, \boldsymbol{\circ} \rangle$ is a commutative semigroup. Furthermore, $\boldsymbol{\circ}$ does not satisfy ident; hence $\langle D, \boldsymbol{=}, \boldsymbol{\circ} \rangle$ is not a monoid.

2.

Consider the Boolean ring $\langle \mathbb{B}, \boldsymbol{=}, \boldsymbol{\Leftrightarrow}, \boldsymbol{\lor}, \mathbf{T}, \mathbf{F}\rangle$; that is, in addition to the ring axioms, we assume the following axiom:

$$\begin{array}{ll} \mbox{\texttt{idemp$_{\boldsymbol{\lor... ...ll }{x}){(x\boldsymbol{\lor}x\boldsymbol{=}x)} \end{array}$$

We also assume the following axiom (although it may be provable from the previous axioms):

$$\begin{array}{ll} \mbox{\texttt{const$_{\boldsymbol{\Le... ...ol{\Leftrightarrow}x\boldsymbol{=}\mathbf{T})} \end{array}$$

We first prove two useful derived theorems:

ident $_{\boldsymbol{\Leftrightarrow}}$-with $_{\boldsymbol{\lor}}$: $({\forall }{x}){({(x\boldsymbol{\lor}\mathbf{T}\boldsymbol{=}\mathbf{T})}{\land }{(\mathbf{T}\boldsymbol{\lor}x\boldsymbol{=}\mathbf{T})})}$

$$\begin{array}{rcl} (1) & \mathbf{T}\boldsymbol{=}(\mathb... ...thbf{T} & \mbox{\texttt{subst}\{11,10\}} \\ \end{array}$$

$$\begin{array}{rcl} (1) & \mathbf{T}\boldsymbol{=}(\mathb... ...thbf{T} & \mbox{\texttt{subst}\{11,10\}} \\ \end{array}$$

comm $_{\boldsymbol{\lor}}$: $({\forall }{x,y}){(x\boldsymbol{\lor}y\boldsymbol{=}y\boldsymbol{\lor}x)}$

$$\begin{array}{rcl} (1) & (x\boldsymbol{\lor}x)\boldsymbo... ...\lor}x) & \mbox{\texttt{subst}\{29,30\}} \\ \end{array}$$

Define $\boldsymbol{\sim}$, $\boldsymbol{\land}$, and $\boldsymbol{\supset}$ as follows:

$$\begin{array}{rcl} \boldsymbol{\sim}x & \equiv & x\bolds... ...{\Leftrightarrow}\mathbf{F})\boldsymbol{\lor}y \end{array}$$

We prove the following laws using the Boolean ring axioms:

(1)

$p\boldsymbol{\supset}(p\boldsymbol{\lor}q)$

$$\begin{array}{rcll} p\boldsymbol{\supset}(p\boldsymbol{\... ...t{const$_{\boldsymbol{\Leftrightarrow}}$}} \\ \end{array}$$

(2)

$(p\boldsymbol{\land}q)\boldsymbol{\supset}p$

$$\begin{array}{rcll} (p\boldsymbol{\land}q)\boldsymbol{\s... ...t{const$_{\boldsymbol{\Leftrightarrow}}$}} \\ \end{array}$$

(3)

$(p\boldsymbol{\land}q)\boldsymbol{\supset}q$

$$\begin{array}{rcll} (p\boldsymbol{\land}q)\boldsymbol{\s... ...t{const$_{\boldsymbol{\Leftrightarrow}}$}} \\ \end{array}$$

(4)

$p\boldsymbol{\supset}(q\boldsymbol{\supset}p)$

$$\begin{array}{rcll} p\boldsymbol{\supset}(q\boldsymbol{\... ...t{const$_{\boldsymbol{\Leftrightarrow}}$}} \\ \end{array}$$

(5)

$\boldsymbol{\sim}q\boldsymbol{\supset}(q\boldsymbol{\supset}p)$

$$\begin{array}{rcll} \boldsymbol{\sim}q\boldsymbol{\supse... ...rightarrow}}$-with$_{\boldsymbol{\lor}}$}} \\ \end{array}$$

(6)

$p\boldsymbol{\supset}q\boldsymbol{\supset}(\boldsymbol{\sim}q\boldsymbol{\supset}\boldsymbol{\sim}p)$

$$\begin{array}{rcll} p\boldsymbol{\supset}(q\boldsymbol{\... ...exttt{const$_{\boldsymbol{\Leftrightarrow}}$}} \end{array}$$

(7)

$(p\boldsymbol{\lor}p)\boldsymbol{\Leftrightarrow}p$

$$\begin{array}{rcll} (p\boldsymbol{\lor}p)\boldsymbol{\Le... ...t{const$_{\boldsymbol{\Leftrightarrow}}$}} \\ \end{array}$$

3.

$\langle \mathbb{Z}, \boldsymbol{=}_5, \boldsymbol{+}, \boldsymbol{*} \rangle$ is a field.

$$\begin{array}{\vert c\vert\vert c\vert c\vert c\vert c\ver... ... 2 \\ \hline 4 & 4 & 0 & 1 & 2 & 3 \\ \hline \end{array}$$

$$\begin{array}{\vert c\vert\vert c\vert c\vert c\vert c\ver... ... 2 \\ \hline 4 & 0 & 4 & 3 & 2 & 1 \\ \hline \end{array}$$

Clearly, $\boldsymbol{=}_5$ satisfies ref, sym, and trans, $\boldsymbol{+}$ satisfies subst and functionality, and $\boldsymbol{*}$ satisifes subst and functionality. By inspection, we see that $\boldsymbol{+}$ satisfies assoc and comm, $0$ is the identity element for $\boldsymbol{+}$, and $\boldsymbol{+}$ satisfies inv. By inspection, we see that $\boldsymbol{*}$ satisfies assoc and comm, $1$ is the identity element for $\boldsymbol{*}$, and $\boldsymbol{*}$ satisfies inv'. Furthermore, we see that $\boldsymbol{*}$ satisfies Z. Finally, we see that $\boldsymbol{+}$ and $\boldsymbol{*}$ satisfy distrib.

4.

Define $x\boldsymbol{<}y \equiv ({\exists }{z}){(x\boldsymbol{+}(z\boldsymbol{+}\mathbf{1})\boldsymbol{=}y)}$. We prove the seven axioms of discrete linear orders for $\boldsymbol{<}$ from the Peano axioms. We assume that all of the axioms of integral domains have been proven from the Peano axioms. We first prove some useful lemmas:

lemma1: $({\forall }{x,z}){({(x\boldsymbol{+}z\boldsymbol{=}x)}{\supset }{(z\boldsymbol{=}\mathbf{0})})}$

$$\begin{array}{cll} & \mathbf{0}\boldsymbol{+}z\boldsym... ...ldsymbol{=}\mathbf{0} & \mbox{\texttt{ihyp}} \end{array}$$

lemma2: $({\forall }{x,a,y}){({(x\boldsymbol{+}a\boldsymbol{=}y)}{\supset }{({(x\boldsymbol{=}y)}{\lor }{(x\boldsymbol{<}y)})})}$

$$\begin{array}{cll} & x\boldsymbol{+}\mathbf{0}\boldsym... ...x\boldsymbol{=}y)}{\lor }{(x\boldsymbol{<}y)} \end{array}$$

lemma3: $({\forall }{x,y}){({(x\boldsymbol{=}y)}{\supset }{(x\boldsymbol{+}\mathbf{1}\boldsymbol{=}y\boldsymbol{+}\mathbf{1})})}$

$$\begin{array}{cll} & x\boldsymbol{=}y \\ \land & ... ... \mbox{\texttt{add-base}[$y$],\texttt{subst}} \end{array}$$

lemma4: $({\forall }{x,y,u,v}){({({(x\boldsymbol{<}y)}{\land }{(u\boldsymbol{<}v)})}{\supset }{(x\boldsymbol{+}u\boldsymbol{<}y\boldsymbol{+}v)})}$

$$\begin{array}{cll} & {(x\boldsymbol{<}y)}{\land }{(u\b... ...}[$a\boldsymbol{+}\mathbf{1}\boldsymbol{+}b$]} \end{array}$$

lt-asym: $({\forall }{x,y}){({x\boldsymbol{<}y}{\supset }{{\sim }{(y\boldsymbol{<}x)}})}$

$$\begin{array}{cll} & {\sim }{({x\boldsymbol{<}y}{\sups... ...ol{<}y}{\supset }{{\sim }{(y\boldsymbol{<}x)}} \end{array}$$

lt-trans: $({\forall }{x,y,z}){({({x\boldsymbol{<}y}{\land }{y\boldsymbol{<}z})}{\supset }{(x\boldsymbol{<}z)})}$

$$\begin{array}{cll} & {(x\boldsymbol{<}\mathbf{0})}{\l... ...ihyp}[$z$]} \\ \supset & x\boldsymbol{<}z \end{array}$$

lt-linear: $({\forall }{x,y}){({{(x\boldsymbol{<}y)}{\lor }{(y\boldsymbol{<}x)}}{\lor }{(x\boldsymbol{=}y)})}$

$$\begin{array}{cll} & & \mbox{\texttt{base}[$x$]} \\ ... ...athbf{1})} & \mbox{\texttt{lemma3}[$x$,$y$]} \end{array}$$

lt-discrete: $({\forall }{x,y}){{\sim }{({(x\boldsymbol{<}y)}{\land }{(y\boldsymbol{<}x\boldsymbol{+}\mathbf{1})})}}$

$$\begin{array}{cll} & {\sim }{{\sim }{({(x\boldsymbol{<... ...{(y\boldsymbol{<}x\boldsymbol{+}\mathbf{1})})} \end{array}$$

lt-0-1: $\mathbf{0}\boldsymbol{<}\mathbf{1}$

$$\begin{array}{cll} & (\mathbf{0}\boldsymbol{+}\mathbf... ...bf{1} & \mbox{\texttt{lt-def}[$\mathbf{0}$]} \end{array}$$

lt-mono-+: $({\forall }{x,y,z}){({(x\boldsymbol{<}y)}{\supset }{(x\boldsymbol{+}z\boldsymbol{<}y\boldsymbol{+}z)})}$

$$\begin{array}{cll} & x\boldsymbol{<}y & \mbox{\text... ...l{+}\mathbf{1} & \mbox{\texttt{lt-def}[$a$]} \end{array}$$

lt-mono-*: $({\forall }{x,y,z}){({({(\mathbf{0}\boldsymbol{<}z)}{\land }{(x\boldsymbol{<}y)})}{\supset }{(x\boldsymbol{*}z\boldsymbol{<}y\boldsymbol{*}z)})}$

$$\begin{array}{cll} & {(\mathbf{0}\boldsymbol{<}\mathbf... ...l{<}y\boldsymbol{*}(z\boldsymbol{+}\mathbf{1}) \end{array}$$