6
$\begingroup$

I think you should be able to encode the axioms of a directed, acyclic graph by introducing a strict partial order. Say E(a, b) represents there is an edge from a to b. We introduce a strict partial order $R(\cdot, \cdot)$ and axiomatize acyclicality:

\begin{align*} \forall a, b~E(a, b) \rightarrow R(a, b) \hspace{2cm} &\text{(A1)} \\ \forall a, b, c~R(a, b) \land R(b, c) \rightarrow R(a, c) \hspace{2cm} &\text{(A2)} \\ \forall a~\neg R(a, a) \hspace{2cm} &\text{(A3)} \end{align*}

However, it seems like you can prove via compactness argument that acyclic graphs are not axiomatizable (like they did here). Which of these is correct?

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

You have not axiomatized the class of directed acyclic graphs. You have axiomatized the class of directed acyclic graphs equipped with a strict partial order extending the edge relation. These are different classes because they have different languages: A directed acyclic graph is an $L$-structure, where $L = \{E\}$, while your class consists of $L'$-structures, where $L' = \{E,R\}$.

In general, a class $\mathcal{K}$ of $L$-structures is basic elementary if it is the class of models of an $L$-sentence $\varphi$: $\mathcal{K} = \{M\mid M\models \varphi\}$.

A class $\mathcal{K}$ of $L$-structures is basic pseudo-elementary if there is a language $L'$ extending $L$ and an $L'$-sentence $\varphi$ such that $\mathcal{K}$ is the class of $L$-reducts of models of $\varphi$: $\mathcal{K} = \{M{\restriction} L\mid M\models \varphi\}$.

The class of directed acyclic graphs is not basic elementary, but your argument shows that it is basic pseudo-elementary.

$\endgroup$
5
  • $\begingroup$ But if you looked at the $L'$ structure, wouldn't the compactness argument still work in this case. But this would lead to a contradiction? $\endgroup$
    – Amar Shah
    Commented Jul 8 at 14:59
  • 1
    $\begingroup$ @AmarShah No, it wouldn't. The structures used in the compactness argument are long cycles, which cannot be expanded by a relation $R$ satisfying your axioms. $\endgroup$
    – Alex Kruckman
    Commented Jul 8 at 15:03
  • $\begingroup$ I am a little confused. Say you have a language $L' = \{E, R\}$. Then define the functions $\phi_3, \phi_4, \phi_5, \ldots$ where each of these represents the fact that there cannot be a cycle of length $\leq 3$, 4, 5, etc. Let $\psi$ be my axiomitization of no cycles. By the other mathexchange post $\bigwedge \phi_i \implies \psi $. Then apply compactness and completeness and we get $\phi_n \implies \psi$ for some $n$. But this is a contradiction. I have not used anything specific about $R$ except the fact that it axiomatized that there were non cycles. What is wrong with this? $\endgroup$
    – Amar Shah
    Commented Jul 8 at 15:21
  • 1
    $\begingroup$ @AmarShah But $\bigwedge\varphi_i$ does not entail $\psi$. A model of $\bigwedge\varphi_i$ is an acyclic directed graph with $R$ interpreted arbitrarily (for example, as the empty relation). $\endgroup$
    – Alex Kruckman
    Commented Jul 8 at 15:30
  • $\begingroup$ This makes, thank you Alex! $\endgroup$
    – Amar Shah
    Commented Jul 8 at 15:37

You must log in to answer this question.

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