In this paper, we study finitely axiomatizable conservative extensions of a theory U in the case where U is recursively enumerable and not finitely axiomatizable. Stanisław Krajewski posed the question whether there are minimal conservative extensions of this sort. We answer this question negatively.

Consider a finite expansion of the signature of U that contains at least one predicate symbol of arity ≥ 2. We show that, for any finite extension α of U in the expanded language that is conservative over U, there is a conservative extension β of U in the expanded language, such that $\alpha \vdash \beta$ and $\beta \not \vdash \alpha$. The result is preserved when we consider either extensions or model-conservative extensions of U instead of conservative extensions. Moreover, the result is preserved when we replace $\dashv$ as ordering on the finitely axiomatized extensions in the expanded language by a relevant kind of interpretability, to wit interpretability that identically translates the symbols of the U-language.

We show that the result fails when we consider an expansion with only unary predicate symbols for conservative extensions of U ordered by interpretability that preserves the symbols of U.

We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known collapse result for the quantifier alternation of MSO logic over countable linear orderings. Second, we solve an open problem posed by Gurevich and Rabinovich, concerning the MSO-definability of sets of rational numbers using the reals in the background. Third, we establish the MSO-definability of the set of yields induced by an MSO-definable set of trees, confirming a conjecture posed by Bruyère, Carton, and Sénizergues.

We consider ${\cal S}$, the class of finite semilattices; ${\cal T}$, the class of finite treeable semilattices; and ${{\cal T}_m}$, the subclass of ${\cal T}$ which contains trees with branching bounded by m. We prove that ${\cal E}{\cal S}$, the class of finite lattices with linear extensions, is a Ramsey class. We calculate Ramsey degrees for structures in ${\cal S}$, ${\cal T}$, and ${{\cal T}_m}$. In addition to this we give a topological interpretation of our results and we apply our result to canonization of linear orderings on finite semilattices. In particular, we give an example of a Fraïssé class ${\cal K}$ which is not a Hrushovski class, and for which the automorphism group of the Fraïssé limit of ${\cal K}$ is not extremely amenable (with the infinite universal minimal flow) but is uniquely ergodic.

We introduce two Ramsey classes of finite relational structures. The first class contains finite structures of the form $\left( A,\,\left( {{I}_{i}} \right)_{i=1}^{n},\le ,\left( {{\underline{\prec }}_{i}} \right)_{i=1}^{n} \right)$, where $\le$ is a total ordering on $A$ and ${{\underline{\prec }}_{i}}$ is a linear ordering on the set $\left\{ a\,\in \,A\,:\,{{I}_{i}}\left( a \right) \right\}$. The second class contains structures of the form a $\left( a,\le ,\left( {{i}_{i}} \right)_{i=1}^{n},\underline{\prec } \right)$, where $\left( A,\,\le \right)$ is a weak ordering and $\underline{\prec }$ is a linear ordering on $A$ such that $A$ is partitioned by $\left\{ a\,\in \,A\,:\,{{I}_{i}}\left( a \right) \right\}$ into maximal chains in the partial ordering $\le$ and each $\left\{ a\,\in \,A\,:\,{{I}_{i}}\left( a \right) \right\}$ is an interval with respect to $\underline{\prec }$.

Jullien's indecomposability theorem (INDEC) states that if a scattered countable linear order is indecomposable, then it is either indecomposable to the left, or indecomposable to the right. The theorem was shown by Montalbán to be a theorem of hyperarithmetic analysis, and then, in the base system RCA0 plus induction, it was shown by Neeman to have strength strictly between weak choice and comprehension. We prove in this paper that induction is needed for the reversal of INDEC. that is for the proof that INDEC implies weak choice. This is in contrast with the typical situation in reverse mathematics, where reversals can usually be refined to use only induction.