Question on a proof of Fraisse's theorem

315 Views Asked by At

On page 13 of this note, Fraisse's theorem (theorem 2.2.4) (a countable class of $\mathcal{L}$-structures is an amalgamation class if and only if it is the skeleton of a countable homogeneous $\mathcal{L}$-structure) is proved as follows.

Assume that $\mathcal{K}$ is an amalgamation class. We will construct a structure as required whose domain is a subset of $\mathcal{N}$. Let $\bar{K} = \langle K_l: l\in \Bbb{N}\rangle$ enumerate $\mathcal{K}$ and let $\langle {a_l}, {b_l},f_l: l\in \Bbb{N}\rangle$ enumerate all triples of the form $(\bar{a_l}, \bar{b_l},{f})$ such that each triple appears infinitely often, where $\bar{a}$ and $\bar{b}$ are tuples in $\mathcal{N}$ and $f : \mathcal{N}\to\mathcal{N}$ is a partial function with domain $\bar{a}$ and range $\bar{b}$.

We will construct the required structure as a union of an increasing sequence $\bar{C} = \langle C_n:n\in \Bbb{N}\rangle$ of elements of $\mathcal{K}$, starting with $C_0 = K_0$. We now assume that $C_n$ is already constructed. If $n = 2l$ is even, we apply the joint embedding property to $C_n$ and $K_l$ and obtain an element $C_{n+1}$ of $\mathcal{K}$. We now assume that $n = 2l + 1$ is odd. If at least one of $\bar{a_l}$ or $\bar{b_l}$ is not a subset of $C_n$, let $C_{n+1} = C_n$. If on the other hand both $\bar{a_l}$ and $\bar{b_l}$ are subsets of $C_n$, then we apply the amalgamation property to $id_{A_l} : A_l \to C_n$ and the embedding $f : A_l \to B_l$ that is induced by $f_l$ from the substructure $A_l$ of $C_n$ generated by $\bar{a_l}$ to the stubstructure $B_l$ of $C_n$ generated by $\bar{b_l}$, and obtain an element $C_{n+1}$ of $\mathcal{K}$. Moreover we can choose $C_{n+1}$ such that the embedding from $C_{n}$ to $C_{n+1}$ is equal to $id_{C_{n}}$ and $C_{n}$ is a substructure of $C_{n+1}$. Finally, Let $C =\bigcup \bar{C}$. The even steps of the construction ensure that $\mathcal{K}$ is the skeleton of $C$.

My question is that exactly what is $(\bar{a_l}, \bar{b_l},{f})$? (It does not explain in the proof clearly. ) So I am lost at "If at least one of $\bar{a_l}$ or $\bar{b_l}$ is not a subset of $C_n$".

1

There are 1 best solutions below

14
On

I think the author is being a bit imprecise. For the purpose of this proof $\mathcal N$ should be any countably infinite set (well, I suppose it would technically work with any infinite $\mathcal N$, but then it would be slightly more difficult to show that the resulting structure is countable).

The point is that since $\mathcal N$ is infinite and $\mathcal K$ is an amalgamation class of finite structures, the solution to any instance of JEP or AP problem can be found as a structure whose domain is a finite subset of $\mathcal N$ (and in fact even better, it can be realised by extending an existing structure contained in $\mathcal N$ --- this is important to ensure that $\bigcup C_n$ is a structure), so we can choose each $C_n$ to have domain contained in $\mathcal N$. Thus, it makes sense to compare $\bar a_l,\bar b_l$ and $C_n$ (as subsets of $\mathcal N$).