# Section 2.2: Problem 22 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
Assume that $\mathfrak{A}$ is a structure and $h$ is a function with $\mbox{ran}h=|\mathfrak{A}|$ . Show that there is a structure $\mathfrak{B}$ such that $h$ is a homomorphism of $\mathfrak{B}$ onto $\mathfrak{A}$ . Suggestion: We need to take $|\mathfrak{B}|=\mbox{dom}h$ . In general, the axiom of choice will be needed to define the functions in $\mathfrak{B}$ , unless $h$ is one-to-one.
Remark: The result yields an “upward Löwenheim–Skolem theorem without equality” (cf. Section 2.6). That is, any structure $\mathfrak{A}$ has an extension to a structure $\mathfrak{B}$ of any higher cardinality such that $\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent, except for equality. There is nothing deep about this. Not until you add equality.
As suggested, let , and we define the structure having the universe $|\mathfrak{B}|$ . Note that $h:|\mathfrak{B}|\rightarrow|\mathfrak{A}|$ and is onto. For any $b\in|\mathfrak{A}|$ , let $g(b)$ be any point from the non-empty set (here we use the Axiom of Choice). For any predicate symbol $P$ , let $\in P^{\mathfrak{B}}$ iff $\in P^{\mathfrak{A}}$ . For any constant symbol $c$ , let $c^{\mathfrak{B}}=g(c^{\mathfrak{A}})$ . Similarly, for any function symbol $f$ , let $f^{\mathfrak{B}}(a_{1},\ldots,a_{n})=g(f^{\mathfrak{A}}(h(a_{1}),\ldots,h(a_{n})))$ . Then, the homomorphism property holds for any predicate parameter by definition. For any constant parameter, $h(c^{\mathfrak{B}})=h(g(c^{\mathfrak{A}}))\in h(G(c^{\mathfrak{A}}))=\{c^{\mathfrak{A}}\}$ . And for every function parameter, $h(f^{\mathfrak{B}}(a_{1},\ldots,a_{n}))=h(g(f^{\mathfrak{A}}(h(a_{1}),\ldots,h(a_{n}))))\in h(G(f^{\mathfrak{A}}(h(a_{1}),\ldots,h(a_{n}))))=\{f^{\mathfrak{A}}(h(a_{1}),\ldots,h(a_{n}))\}$ . Therefore, $h$ is a homomorphism of $\mathfrak{B}$ onto $\mathfrak{A}$ .