Question

Show that the class of trees cannot be axiomatised. Here we define a tree as a structure \(\langle T, \leq, t\rangle\), where \(\leq\) is a partial order, such that for each \(a\) the predecessors form a finite chain \(a=a_{n}

Short answer

The class of trees cannot be axiomatized because first-order logic cannot express the finiteness of the chains, violating axiomatization constraints via Compactness Theorem.

Step-by-step solution

Understanding the Axiomatisation of Trees

To show that the class of trees cannot be axiomatised, first recognize what axiomatisation means. A class of structures is axiomatisable if there exists a set of first-order logical sentences such that a structure satisfies these sentences if and only if it is in that class. This means we should be able to describe all and only trees using first-order logic.

Analyze a Tree in Logical Terms

A tree can be defined logically as a structure \(\langle T, \leq, t\rangle\) where \(\leq\) is a partial order, with \(t\) as the distinguished element (the top). Each element \(a\) in the tree has predecessors forming a finite chain from \(t\). In logical terms, this means for every element, its predecessors can be totally ordered into a finite sequence ending at \(t\).

Attempt to Define Properties in First-Order Logic

Consider the condition that for each element \(a\), there exists a finite sequence of predecessors ending at \(t\). While first-order logic can express concepts like 'for all elements there exists another element such that...', it cannot express finiteness or the concept of a 'finite chain'. Thus, a first-order logic formula cannot capture the condition that predecessors must form a finite chain.

Use Compactness Theorem Argument

The Compactness Theorem states that if every finite subset of a set of sentences has a model, then the whole set has a model. Suppose trees were axiomatisable with a first-order set of sentences. Consider extensions to infinitely long chains attached to what would be the top \(t\), all satisfying any given first-order properties of trees. Because these do not form finite predecessors ending at \(t\), they cannot be true trees, yet would satisfy our supposed axioms due to the inability to rule out such structures nondeterministically.

Conclude Axiomatisability is Impossible

The inability to use first-order logic to restrict models to only those where each element has predecessors forming a finite chain, combined with the Compactness Theorem leading to possible infinite models, demonstrates that the class of trees cannot be described accurately by any set of first-order sentences. Thus, the class of trees is not axiomatisable.

Key concepts

first-order logic

First-order logic is a powerful formalism used in mathematics and computer science to describe structures in a precise and logical manner. It involves quantifiers such as "for all" (denoted as \( \forall \)) and "exists" (denoted as \( \exists \)). These quantifiers allow us to construct sentences that can be universally or existentially quantified over the elements of a structure. Elements in first-order logic are typically related to each other using predicates, functions, or constants that specify relationships. They can express definitions and properties within a given domain, but there are some limitations. While they can specify numerous properties, they struggle with certain concepts, like finiteness. In the context of trees, a structure comprised of a set \(T\) with a partial order \(\leq\) and a distinct top element \(t\) is typically described using first-order sentences. However, first-order logic lacks the ability to express properties that require an inherently finite nature, such as the finite length of chains from any element up to the top \(t\). This limitation is a crucial barrier when attempting to axiomatize trees.

partial order

A partial order is a fundamental concept in mathematics, especially within the structure of trees. It is a binary relation \( \leq \) over a set \( T \) that satisfies three key properties: reflexivity, antisymmetry, and transitivity. These properties are essential for defining hierarchical structures where some elements may not be directly related, unlike in total orders.

• Reflexivity: Every element is related to itself. For any element \( a \) in \( T \), \( a \leq a \) holds true.
• Antisymmetry: If two elements are mutually related, they are identical. That is, if \( a \leq b \) and \( b \leq a \), then \( a = b \).
• Transitivity: If an element is related to a second, which in turn is related to a third, the first is related to the third. So, if \( a \leq b \) and \( b \leq c \), then \( a \leq c \).

In trees, a partial order helps define the hierarchical relationship between elements, where each element's predecessors form an ordered chain. Notably, only a top element \( t \) exists where the chains terminate. This structured hierarchy is critical, but partial orders themselves do not inherently enforce finiteness, which is vital to understanding why first-order logic struggles with tree axiomatisation.

Compactness Theorem

The Compactness Theorem is a cornerstone result in model theory, an area of mathematical logic that deals with the relationship between formal languages and their interpretations. This theorem essentially states that if every finite subset of a set of logical sentences has a model, then the entire set also has a model. This theorem captures the intuition that you can't have a logical inconsistency hiding in a large but finite-sized logic problem if none is found in any finite piece. In terms of first-order logic, this theorem has intriguing implications, particularly about tree structures. Suppose a class of trees were axiomatisable using first-order logic. In that case, the Compactness Theorem suggests that we could construct structures that only respect the finite logical parts, unexpectedly extending certain tree properties to infinite dimensions. In practice, even if each element in a tree structure theoretically has a finite predecessor chain by first-order logic, the Compactness Theorem opens the potential for infinite chains being considered alongside trees. This is problematic because these infinitely extended successor structures can't fulfill the tree's inherent characteristic of having a finite chain leading to a top \( t \), showcasing why trees defy such simple logical description.

finite chain in logic

In the world of trees, a finite chain refers to a sequence of elements where each is related to the next up to a distinguished top element, known as \( t \). This chain is described formally as \( a = a_n < a_{n-1} < \ldots < a_0 = t \), indicating a descending path from any element back to the top. While it's straightforward to understand that finite chains are not inherently problematic, their representation in logical terms brings challenges. First-order logic inherently lacks the tools to capture the notion of finiteness. It can predicate relationships between elements but cannot enforce a specific number of such relationships or explicitly define bounds. Because of this limitation, when attempting to define an entire class of structures like trees, first-order logic fails to distinguish between structures with genuinely finite chains ending in \( t \) and structures that could theoretically be infinite. This inability to restrict possible models effectively illustrates why the class of trees cannot be successfully axiomatised if using only first-order logic. It leaves the first-order logical framework unable to capture the essence of what makes a tree—a graph without cycles where pathways have a definite endpoint—in other words, a top.