Can we always have an infinite alternative axiomatization of a finitely axiomatized theory?

81 Views Asked by At

It appears that working in first order logic languages one can always have finite axiomatizations of a theory $T$ defined in some first order language $L$, through defining a suitable convervative extension $T^{+}$ of it in some first order language $L^{+}$ that extends $L$ such that $T^{+}$ is finitely axiomatized.

My question here is about if the opposite is true, that is for any theory $T$ in a a first order language $L$ there is another theory $T^{-}$ in a first order language $L^{-}$ such that $L$ extends $L^{-}$ and $T$ is a conservative extension over $T^{-1}$ and such that $T^{-1}$ is not finitely axiomatizable.

More prudently I'll require that $T$ must speak of infinitely many objects, i.e. the domain of every model of it is infinite.

1

There are 1 best solutions below

0
On

(Below, all theories are satisfiable and deductively closed and have no finite models, and all languages are finite.)

This question is a bit vague; I'm interpreting it in the following way

Suppose $T$ is a theory in a language $L$. Must there be a sublanguage $L'\subseteq L$ such that $T':=T\cap Sent(L')$ is not finitely axiomatizable?

(Note that by explicitly making $T'$ the set of all $Sent(L')$-consequences of $T$, I've trivially ensured conservativity; I'll follow this strategy consistently throughout this answer, which is why the word "conservativity" does not appear in this answer except in this paragraph.)

The answer to this question is trivially yes: if we take $L'=\emptyset$ we get that $T'$ is the theory of an infinite pure set, which is not finitely axiomatizable.

Disallowing the empty language doesn't help: now if we just take any finitely axiomatizable theory $T$ in a language $L$ with a single element, there is no legal candidate $L'$ at all besides $L$ itself, so we trivially get a negative answer to your question.


OK, so is there a way we can de-trivialize the question?

The paragraph two prior points to the biggest issue here: languages, as such, are just too coarse. Instead we should talk about generalized reducts (which are standardly just called "reducts," see e.g. Junker/Ziegler, The 116 reducts of $(\mathbb{Q},<,a)$). Given a theory $T$ in a language $L$, and a set $\Phi$ of $L$-formulas, let $L_\Phi$ be the language consisting of an appropriate-arity relation symbol $R_\varphi$ for each formula $\varphi\in\Phi$ and let $T_\Phi$ be the set of $L_\Phi$-consequences of $T$ when we interpret $R_\varphi$ as $\varphi$. (This is a bit vague but it's hopefully clear what's going on.) Note that there is no structure involved here, so the formulas in $\Phi$ don't have parameters in any sense.

We can then identify different theories by allowing change-of-language and "mutual reduction." For example, replacing $<$ with $>$ in the theory of the rationals as a linear order results in an equivalent theory in this sense. The key point here is that equivalence preserves/reflects finite axiomatizability. So given an arbitrary theory $T$ we can consider the partial order of "generalized reducts of $T$ up to equivalence." Call this $\mathfrak{R}(T)$. The opening of this answer points out that $\mathfrak{R}(T)$ has a least element which is not finitely axiomatizable, and on the other hand it's clear that $\mathfrak{R}(T)$ has a greatest element as well (namely $T$ itself).

At this point your question can be understood as getting at the following:

Given a finitely axiomatizable theory $T$, what can we say about the points in $\mathfrak{R}(T)$ which correspond to non-finitely-axiomatizable theories?

At this point we're in a position to start asking non-trivial questions.