1
$\begingroup$

For my thesis in finite model theory I'm considering some basic classes of structures, and I want to show in which logical systems they can or cannot be axiomatized. I now consider the class $$\text{EVEN}=\{\mathcal{A}=(A)\mid|A|\text{ is even}\}$$ of structures with no constants/relations and an even domain. It is easily seen, using an Ehrenfeucht-Fraïssé-game, that $\text{EVEN}$ is not first-order-axiomatizable.

Considering a second-order language, one can give the axiom $$\exists R[\forall a\exists b[aRb\wedge bRa\wedge\forall c[aRc\rightarrow c=b]]]$$ which indicates I can make pairs in my structure.

What I am now interested in, is proving or disproving the axiomatizability of $\text{EVEN}$ in monadic-second-order logic, i.e. second order logic with only 1-ary relation symbols. Is there an easy/intuitive way to see this?

$\endgroup$

1 Answer 1

1
$\begingroup$

The answer is no. This follows from a result of Skolem, which implies that any sentence of monadic second order logic is equivalent to a (finite) propositional combination of sentences $L_n$, $n = 1, 2, \ldots$, where $L_n$ means the universe has at least $n$ elements. See my answer to Is there any formula of monadic second-order logic that is only satisfied by an infinite set? for a reference and a bit more detail.

$\endgroup$
6
  • $\begingroup$ I have been thinking about your answer for some time, and I understand that the answer follows from Skolem's result. For a complete understanding, I'd like some more detail on his result, which I couldn't really find in your SEoP-link. Is there an article/book that proofs this result? I have not been able to find one at least. $\endgroup$
    – konewka
    Commented Jun 10, 2015 at 11:16
  • $\begingroup$ It's in Skolem's collected works. I wrote up the proof and a couple of related results for my own interest a few years ago. Here is a link to my write-up lemma-one.com/papers/logmisc.pdf (which I hope should work from here, unlike the Dropbox link I posted 15 minutes ago). $\endgroup$
    – Rob Arthan
    Commented Jun 10, 2015 at 20:11
  • $\begingroup$ Thanks a lot, I will take a look at your results! $\endgroup$
    – konewka
    Commented Jun 10, 2015 at 20:12
  • 1
    $\begingroup$ No problem. I should have said that the three sections of my paper are independent (but connected conceptually in my mind, because they all boil down to Venn diagrams). So you can just dive into the proof os Skolem's result. $\endgroup$
    – Rob Arthan
    Commented Jun 10, 2015 at 21:56
  • 1
    $\begingroup$ Of course, but now having read Skolem's original article as well, I think your version of it is very clarifying. $\endgroup$
    – konewka
    Commented Jun 10, 2015 at 22:12

You must log in to answer this question.

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