Section 2.2: Problem 24 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

Let $h$ be an isomorphic embedding of $\mathfrak{A}$ into $\mathfrak{B}$ . Show that there is a structure $\mathfrak{C}$ isomorphic to $\mathfrak{B}$ such that $\mathfrak{A}$ is a substructure of $\mathfrak{C}$ . Suggestion: Let $g$ be a one-to-one function with domain $|\mathfrak{B}|$ such that $g(h(a))=a$ for $a\in|\mathfrak{A}|$ . Form $\mathfrak{C}$ such that $g$ is an isomorphism of $\mathfrak{B}$ onto $\mathfrak{C}$ .

Remark: The result stated in this exercise should not seem surprising. On the contrary, it is one of those statements that is obvious until you have to prove it. It says that if you can embed $\mathfrak{A}$ isomorphically into $\mathfrak{B}$ , then for all practical purposes you can pretend $\mathfrak{A}$ is a substructure of $\mathfrak{B}$ .

First we construct a set $C$ by adding to $|\mathfrak{A}|$ one element for each point of $|\mathfrak{B}|$ not in $\mbox{ran}h$ . For example, consider $g:|\mathfrak{B}|\rightarrow|\mathfrak{B}|\times\{0\}\cup|\mathfrak{A}|$ such that $g(b)=\begin{cases} a & \mbox{if }b\in\mbox{ran}h\mbox{ and }h(a)=b\mbox{ (}h\text{ is one-to-one)},\\ <b,0> & \mbox{otherwise}. \end{cases}$ Then

. Note, that $g:|\mathfrak{B}|\rightarrow C$ is bijective, and $|\mathfrak{A}|\subseteq C$ . Let $g'=g^{-1}:C\rightarrow|\mathfrak{B}|$ . Note, that by definition, for $a\in|\mathfrak{A}|\subseteq C$ , $g(h(a))=a$ , hence, $g'(a)=g'(g(h(a)))=h(a)$ .

Now, we construct a structure $\mathfrak{C}$ with the universe $C$ such that $\mathfrak{A}$ is a substructure of $\mathfrak{C}$ , and $\mathfrak{C}$ is isomorphic to $\mathfrak{B}$ .

For any predicate symbol $P$ , we define $<c_{1},\ldots,c_{n}>\in P^{\mathfrak{C}}$ iff $<g'(c_{1}),\ldots,g'(c_{n})>\in P^{\mathfrak{B}}$ . For a constant symbol $c$ , let $c^{\mathfrak{C}}=g(c^{\mathfrak{B}})$ . Finally, for a function symbol $f$ , we define $f^{\mathfrak{C}}(c_{1},\ldots,c_{n})=g(f^{\mathfrak{B}}(g'(c_{1}),\ldots,g'(c_{n})))$ . Then, for any predicate parameter, $<b_{1},\ldots,b_{n}>\in P^{\mathfrak{B}}$ iff $<g'(g(b_{1})),\ldots,g'(g(b_{n}))>\in P^{\mathfrak{B}}$ iff $<g(b_{1}),\ldots,g(b_{n})>\in P^{\mathfrak{C}}$ . For a constant parameter, $c^{\mathfrak{C}}=g(c^{\mathfrak{B}})$ . And for a function parameter, $g(f^{\mathfrak{B}}(b_{1},\ldots,b_{n}))=g(f^{\mathfrak{B}}(g'(g(b_{1})),\ldots,g'(g(b_{n}))))=f^{\mathfrak{C}}(g(b_{1}),\ldots,g(b_{n}))$ . Therefore, $g$ is an isomorphism of $|\mathfrak{B}|$ onto $|\mathfrak{C}|$ .

It remains to show that $\mathfrak{A}$ is a substructure of $\mathfrak{C}$ . In what we did so far, we did not use the fact that $h$ is an isomorphism of $\mathfrak{A}$ into $\mathfrak{B}$ , we only used the fact that it is bijective. To show that $\mathfrak{A}$ is a substructure of $\mathfrak{C}$ , according to (a) and (b) on page 95, we need to show the following.

(a) $P^{\mathfrak{A}}$ is the restriction of $P^{\mathfrak{C}}$ to $|\mathfrak{A}|$ . Indeed, $<a_{1},\ldots,a_{n}>\in P^{\mathfrak{A}}$ iff $<h(a_{1}),\ldots,h(a_{n})>\in P^{\mathfrak{B}}$ iff $<g(h(a_{1})),\ldots,g(h(a_{n}))>\in P^{\mathfrak{C}}$ iff $<a_{1},\ldots,a_{n}>\in P^{\mathfrak{C}}$ .

(b) $f^{\mathfrak{A}}$ is the restriction of $f^{\mathfrak{C}}$ to $|\mathfrak{A}|$ (including constants). Indeed, $\begin{align*} f^{\mathfrak{A}}(a_{1},\ldots,a_{n}) & =g(h(f^{\mathfrak{A}}(a_{1},\ldots,a_{n})))\\ & =g(f^{\mathfrak{B}}(h(a_{1}),\ldots,h(a_{n})))\\ & =f^{\mathfrak{C}}(g(h(a_{1})),\ldots,g(h(a_{n})))\\ & =f^{\mathfrak{C}}(a_{1},\ldots,a_{n}), \end{align*}$ and $c^{\mathfrak{A}}=g(h(c^{\mathfrak{A}}))=g(c^{\mathfrak{B}})=c^{\mathfrak{C}}$ .

Subpages

Section 2.2: Problem 24 Solution

Section 2.2: Problem 24 Solution