Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We want to proof that every class of finite structures is axiomatizable in the infinitary logic $L_{\infty\omega}$.

We fix the signature $\tau$ (is okay to do so?). Thus, we can assume that for every finite $\tau$-structure $c$ there is a finite formula $\varphi_c \in L_{\infty\omega}$ describing it. Now for every class $C$ of finite structures we could define

$\Phi := \{ \varphi_c \mid c \in C\}$

The problem is if we want to combine this class to a formula such as this

$\psi := \lor \Phi$.

We have to assume that $C$ is a set not just a class. At least that $\Phi$ is a set. Any hints?

Here is a sketch to show that $\Phi$ is a set. $\Phi \subset L_{\infty\omega}$ and $\psi(\varrho) := \exists c \in C (\varrho = \varphi_c)$.

$\Rightarrow \Phi = \{\varrho \in L_{\infty\omega} \mid \psi(\varrho)\}$. Thus by the Axiom of Seperation $\Phi$ is a set. Is that correct?

share|cite|improve this question
I guess you should reduce the problem to showing that there is at most a set of isomorphism classes... – Zhen Lin Jan 13 '13 at 15:51
up vote 1 down vote accepted

You have the right idea, except that $L_{\infty \omega}$ is a proper class itself. However each finite structure is described upto isomorphism by an $L_{\omega \omega}$ formula. That is, in fact $\varphi_c \in L_{\omega \omega}$ and $\Phi \subseteq L_{\omega \omega}$.

share|cite|improve this answer
Thanks a lot. Out of curiosity: Why is $L_{\infty\omega}$ a proper class? – joachim Jan 14 '13 at 20:50
@joachim: You can write a formula of any ordinal length. The collection of ordinals is a proper class. – Asaf Karagila Jan 14 '13 at 20:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.