2
$\begingroup$

I can show using compactness theorem (or even EF Games) that even number of nodes in graphs is not axiomatizable. However, I don't understand some thing: We can express cardinality of universum, so we should be able to express number of nodes with infinity set of formulas (formula for each even number expressing cardinality of universum).

Proof with compactness
Let $\Delta$ states that graph has even number of nodes. Then, $\Delta'=\Delta\cup\{\phi_i = \text{graph has path with at least $i$ nodes}\ |\ i \in \mathbb{N}\}$
of course each finite subset of $\Delta'$ is sastisfable - it is fairly obvious. However, when it comes to $\Delta'$ it it not satisfable. $\Delta'$ requires that graph would be ifnfinite, but after all, even number of nodes is not infinite.

Where am I wrong in this proof ?

$\endgroup$
  • 1
    $\begingroup$ Definability of a set in FOL requires the existence of one formula (which must be of finite length) whose models are precisely the graphs with even number of nodes. Maybe you are thinking of first-order theories, whose set of axioms are not necessarily finite? $\endgroup$ – Fabio Somenzi Feb 1 '17 at 18:12
  • $\begingroup$ " Maybe you are thinking of first-order theories, whose set of axioms are not necessarily finite?" yes, I meant theories. Keep your mind that I wrote "axiomatizaion", not "definition" $\endgroup$ – user343207 Feb 1 '17 at 18:39
  • 1
    $\begingroup$ You use compactness or pebble games to show undefinability, though, don't you? $\endgroup$ – Fabio Somenzi Feb 1 '17 at 18:45
  • $\begingroup$ math.stackexchange.com/questions/2041592/… look, here we conclude that even numbers nodes graphs are not axiomatizable' $\endgroup$ – user343207 Feb 1 '17 at 18:47
  • $\begingroup$ @FabioSomenzi I edited my post and did show proof.... $\endgroup$ – user343207 Feb 1 '17 at 19:06
1
$\begingroup$

There is nothing wrong with your proof. It shows that there is no first-order axiomatization of the class of graphs with even number of nodes, so you've finished the problem that you linked to. $ \def\nn{\mathbb{N}} $

What is going wrong is your assumptions in your first paragraph. Note that you cannot express cardinality of the universe in general. You can make a single axiom that states that the universe has exactly $n$ objects, for any fixed natural number $n$. But you cannot for an infinite cardinality. Your main error is that your next claim , namely that you can use an infinite set of formulae to capture all universes with an even number of objects, since you can do so for any specific even number. This is not true in first-order logic. The axiom set is essentially an infinite conjunction (every one of them must be satisfied), not a disjunction like you want here. This is precisely what goes wrong that allows the compactness argument to go though.

In fact, logic systems that permit formulae to have infinite disjunctions usually do not satisfy the compactness theorem for exactly this reason. To be precise, consider in such systems the set of formulae $\{ \bigvee_{n\in\nn} A_n \} \cup \{ \neg A_n : n \in \nn \}$, where $(A_n)_{n\in\nn}$ is a sequence of distinct propositional variables. Then this set is finitely satisfiable (every finite subset is satisfiable), but not satisfiable. Thus even propositional logic that allows infinite disjunctions fails to satisfy compactness.

$\endgroup$
  • $\begingroup$ Yes, I got it! :) $\endgroup$ – user343207 Feb 2 '17 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy