How can I describe the set of homomorphisms and what is its cardinality?

Question

There are actually two questions here. Neither of these is a homework question.

Let $\text{hom}(\mathfrak{A},\mathfrak{B})$ (not to be confused with the Hom functor) be the class$^0$ of homomorphisms between two structures (of the same signature) $\mathfrak{A}=(A,(f_i)_{i\in I})$ and $\mathfrak{B}=(B,(g_j)_{j\in J})$ $^1$. If the objects (domains) of $\mathfrak{A}$ and $\mathfrak{B}$ ($A$ and $B$, respectively) are sets, then $\text{hom}(\mathfrak{A},\mathfrak{B})$ is a set.

Question 1

Given two arbitrary structures $\mathfrak{A}$ and $\mathfrak{B}$ over known sets ($A$ and $B$, respectively), what is the cardinality of $\text{hom}(\mathfrak{A},\mathfrak{B})$?

---

My work:

Using the product convention of functional analysis (a summary of which can be found here), it is clear that...

$$\text{hom}(\mathfrak{A},\mathfrak{B})\subseteq\prod_{i\in A}B\cong B^{|A|}$$

...whence,...

$$|\text{hom}(\mathfrak{A},\mathfrak{B})|\le|B|^{|A|}$$

The lower bound of $|\text{hom}(\mathfrak{A},\mathfrak{B})|$ is obviously $0$, so $0\le|\text{hom}(\mathfrak{A},\mathfrak{B})|\le|B|^{|A|}$.$^2$ This is not much help on its own, though.

It is not generally true that the set of functions from $A$ to $B$ is the set of homomorphisms from $\mathfrak{A}$ to $\mathfrak{B}$; but I'm not sure how to reduce the set of functions to just the set of homomorphisms, which leads me to my second question.

---

Question 2

Given two arbitrary structures $\mathfrak{A}$ and $\mathfrak{B}$ over known sets ($A$ and $B$, respectively), characterize the set $\text{hom}(\mathfrak{A},\mathfrak{B})$.

I don't really have a good method for explicitly defining the set of homomorphisms between two structures - at least, not in a way that would let me construct an explicit bijection from the set of homomorphisms to, say, an ordinal. It might be the case that the set of functions from $A$ to $B$ has a cardinality of $\aleph_0^{\aleph_0}$ $^3$ while the set of homomorphisms has a cardinality of $\aleph_0$ - but I wouldn't know that unless I was able to enumerate the elements of $\text{hom}(\mathfrak{A},\mathfrak{B})$ - which I can't do because I have no idea what it looks like.

---

Footnotes

$^0$ "class" here is meant roughly in the sense that it has been used in NBG, Principia Mathematica or the metamath language - e.g. a set is a class, a proper class is a class, a collection of proper classes is a class, etc. but a proper class is not a set, etc.

$^1$ I am ignorant of structures with an uncountable set of operations and/or relations, unless these are more common than I think, you can assume that $I$ and $J$ are countable.

$^2$ The smallest possible set containing all homomorphisms between arbitrary structures is the empty set, since there might not be any homomorphisms between them. $\text{hom}(\mathfrak{A},\mathfrak{B})=\emptyset\implies |\text{hom}(\mathfrak{A},\mathfrak{B})|=0$

$^3$ Depending on the choice of theory and the acceptance or rejection of the continuum hypothesis this may variously evaluate to $\mathfrak{c}$, $2^{\aleph_0}$, or $\aleph_1$. I'm leaving it as $\aleph_0^{\aleph_0}$ because the details of this aren't relevant to the question.

Answer 1

Let $p(x_1,\dots,x_n)$ be your favorite polynomial with integer coefficients. Consider the rings $\mathfrak{A} = \mathbb{Z}[x_1,\dots,x_n]/(p)$ and $\mathfrak{B} = \mathbb{Z}$. Then the set of ring homomorphisms $\text{Hom}(\mathfrak{A},\mathfrak{B})$ is in bijection with the set of integer solutions to $p = 0$. Explicitly, if $f\colon \mathbb{Z}[x_1,\dots,x_n]/(p)\to \mathbb{Z}$ is a ring homomorphism, then $p(f(x_1),\dots,f(x_n)) = 0$, and for any tuple $(a_1,\dots,a_n)\in \mathbb{Z}^n$ such that $p(a_1,\dots,a_n) = 0$, there is a unique ring homomorphism $f\colon \mathbb{Z}[x_1,\dots,x_n]/(p)\to \mathbb{Z}$ such that $f(x_i) = a_i$ for all $1\leq i\leq n$.

Now understanding the integer solutions to the Diophantine equation $p(x_1,\dots,x_n) = 0$ for various polynomials $p$ is a notoriously hard kind of problem in number theory (see e.g. Fermat's last theorem!). There's definitely no simple criterion for determining, for example, whether or not $\text{Hom}(\mathfrak{A},\mathfrak{B})$ is finite, or even nonempty. In fact, in their solution to Hilbert's tenth problem, Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson proved that this problem is computationally undecidable.

Answer 2

In general, nothing can be said, even if we're only looking at a signature consisting of a single unary function symbol $f$. For example, fixing an arbitrary cardinal $\kappa$:

• Let $\mathfrak{A},\mathfrak{B}$ each be the structure with domain your favorite set of cardinality $\kappa$ (say, $\kappa$ itself) and with $f$ interpreted as the identity. Then every map is a homomorphism.

• Let $\mathfrak{A}$ be as above, and let $\mathfrak{B}$ be any structure whatsoever in the same signature where $f$ is never the identity. Then there are no homomorphisms from $\mathfrak{A}$ to $\mathfrak{B}$ at all. (And by using two unary function symbols we can similarly whip up an example where there are no homomorphisms in either direction.)

So in general, there are no better bounds to be found.