6
$\begingroup$

Let $\mathcal{L}$ be a signature (or language), and let $\mathcal{A}$ be a finite $\mathcal{L}$-model (or $\mathcal{L}$-structure). Show that there is a homomorphism from an $\mathcal{L}$-model $\mathcal{B}$ into $\mathcal{A}$ if and only if there are homomorphisms from each finitely generated substructure of $\mathcal{B}$ into $\mathcal{A}$.

Here's what I have so far: I think the "$\Rightarrow$" direction is simple, as you can just take the given homomorphism restricted to the substructure; this should still be a homomorphism.

I initially thought the "$\Leftarrow$" was trivial as well, as you can just take $\mathcal{B}$ as one of the finitely generated substructures. But then I realised that $\mathcal{B}$ may not be finitely generated from a substructure (is that possible?). I feel like I might have to use compactness or ultraproducts (given the phrase "finitely generated substructure"), but I'm not really sure how.

Apologies if what I'm saying doesn't make sense, I'm still trying to get a grasp of model theory. Any help would be appreciated!

$\endgroup$
11
  • 1
    $\begingroup$ I think instead of "into" you should be saying "to" - "into" suggests injectivity, and the only structures that inject into finite structures are finite. $\endgroup$ Nov 1, 2017 at 4:52
  • $\begingroup$ @NoahSchweber I never knew that "into" suggests injectivity. $\endgroup$
    – bof
    Nov 1, 2017 at 5:12
  • 2
    $\begingroup$ @bof It's not universal (and may not even be widespread?), but I've definitely been cautioned against using "into" in papers when the function I'm talking about isn't injective. $\endgroup$ Nov 1, 2017 at 5:49
  • 1
    $\begingroup$ @bof Here's an example: mathforum.org/library/drmath/view/52454.html. I think using "into" for "injective" is bad practice, but it's widespread enough that it's better to avoid it. $\endgroup$ Nov 1, 2017 at 16:31
  • 1
    $\begingroup$ @bof Look, we agree that "into" is not a synonym of "injective". All I'm saying is that a lot of people believe that it is, so it's best to avoid confusion by not using it. Citing a single source, however reputable, isn't good evidence that another usage isn't widespread (albeit in less reputable sources). Plus, there's a convenient alternative to "into" that has the advantage of being two characters shorter! $\endgroup$ Nov 2, 2017 at 3:05

1 Answer 1

5
$\begingroup$

I suppose the operations and relations of $L$ are finitary. Let $A$ and $B$ be the underlying sets of $\mathcal A$ and $\mathcal B.$ Let $[B]^{\lt\omega}$ be the set of all finite subsets of $B.$ Let $\mathcal U$ be an ultrafilter on $[B]^{\lt\omega}$ such that $\{X\in[B]^{\lt\omega}:b\in X\}\in\mathcal U$ for each $b\in B.$

For each $X\in[B]^{\lt\omega}$ choose a homomorphism $f_X:\langle X\rangle\to\mathcal A,$ where $\langle X\rangle$ is the substructure of $\mathcal B$ generated by $X.$ For each $b\in B,$ define $f(b)$ as the unique element $a\in A$ such that $f_X(b)=a$ for $\mathcal U$-almost all $X\in[B]^{\lt\omega},$ that is, $\{X\in[B]^{\lt\omega}:f_X(b)=a\}\in\mathcal U.$ (Such an element $a$ exists because $A$ is finite, and because of the special property of the ultrafilter $\mathcal U$ which guarantees that $f_X(b)$ is defined for $\mathcal U$-almost all $X.$) This function $f:\mathcal B\to\mathcal A$ is a homomorphism.

To see that $f$ is a homomorphism, observe that, if $k\lt\omega$ and $b_1,\dots,b_k\in B,$ then $f|\{b_1,\dots,b_k\}=f_X|\{b_1,\dots,b_k\}$ for some (in fact for almost all) $X\in[B]^{\lt\omega}.$

Example: If $\mathcal B$ is a (simple, undirected, not necessarily finite) graph, and if $\mathcal A=K_n$ (the complete graph of order $n$) for some natural $n,$ then a homomorphism of the graph $\mathcal B$ into $\mathcal A$ is just a proper $n$-coloring of the vertices of $\mathcal B.$ In this case we have the De Bruijn–Erdős theorem which says that a graph is $n$-colorable iff every finite subgraph is $n$-colorable.

$\endgroup$
1
  • $\begingroup$ Very nice answer, by the way! $\endgroup$ Nov 2, 2017 at 3:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .