Question

Let \(L\) be a language with one unary function symbol \(f\). Find a sentence \(\tau_{n}\), which says that " \(f\) has a loop of length \(n\) ", i.e. \(\mathfrak{A} \vDash \tau_{n} \Leftrightarrow\) there are \(a_{1}, \ldots, a_{n} \in|\mathfrak{Q}|\) such that \(f^{\mathfrak{2}}\left(a_{i}\right)=a_{i+1}(i\aleph_{0}\). (hint: consider the partition \(\left\\{\left(f^{2}\right)^{i}(a) \mid i \in \omega\right\\}\) in a model \(\left.\mathfrak{A}\right)\). Is \(T \aleph_{0}\)-categorical? Show that \(T\) is complete and decidable. Is \(T\) finitely axiomatisable?

Short answer

\(T\) is \(\kappa\)-categorical for \(\kappa > \aleph_0\), but not \(\aleph_0\)-categorical. \(T\) is complete and decidable but not finitely axiomatizable.

Step-by-step solution

Define the Sentence

We need to construct the sentence \(\tau_n\) to express that \(f\) has a loop of length \(n\). This can be expressed using existential quantifiers: \[\exists a_1, \ldots, a_n \left( f(a_i) = a_{i+1} \wedge f(a_n) = a_1 \right).\] Here, \(a_{i+1}\) where \(i < n\) and \(a_1\) acts as a cycle where \(f(a_n) = a_1\). This expresses the loop of length \(n\).

Define the Theory and Axioms

The theory \(T\) given by the axiom set \(\{ \beta, eg \tau_1, eg \tau_2, eg \tau_3, \ldots \}\) considers that \(f\) is bijective and there are no loops of length \(n\) for any natural number \(n\). Here, \(\beta\) is an axiom indicating \(f\) is a bijection.

Demonstrate \(T\) is \(\kappa\)-categorical for \(\kappa > \aleph_0\)

For infinite \(\kappa\), we consider partition \(\{(f^2)^i(a) \mid i \in \omega\}\). Given every countably infinite structure must be identical, we reason that every element can be reached by a chain of finite applications of \(f\) from some element, so \(\{(f^2)^i(a)\}\) partitions into this infinite sequence. This means any two structures of size \(\kappa\) are isomorphic, hence \(T\) is \(\kappa\)-categorical for \(\kappa > \aleph_0\).

Check if \(T\) is \(\aleph_0\)-categorical

For \(\aleph_0\)-categoricity, we need a unique countable model. However, because \(f\) is bijective but does not allow finite loops, it forms infinitely countable sequences. Hence, multiple non-isomorphic countable models can exist, so \(T\) is not \(\aleph_0\)-categorical.

Verify Completeness and Decidability of \(T\)

Since \(T\) axioms determine exactly all the properties of \(f\) and no finite loops exist, for any model, the truth or falsity of any statement can be determined. Therefore, \(T\) is complete. The finitely axiomatized basis allows us to algorithmically decide any query, hence \(T\) is decidable.

Determine if \(T\) is Finitely Axiomatisable

\(T\) is not finitely axiomatizable because forbidding loops of length \(n\) for every natural number \(n\) is inherently infinite (as each \(eg \tau_n\) is a separate requirement for each \(n\)). Therefore, \(T\) requires infinitely many axioms to fully define.

Key concepts

Bijective Function

In mathematics, a bijective function, or bijection, is a fundamental concept that connects sets in a one-to-one correspondence. It is a type of function that is both injective (one-to-one) and surjective (onto). This means every element in the domain is mapped to a unique element in the codomain, and every element of the codomain is the image of an element from the domain.
A simple way to visualize a bijective function is as a perfect pairing between two sets. Imagine you have a set of keys and a set of locks, and each key opens exactly one lock, and each lock is opened by exactly one key.
In model theory, when examining transformations or functions in logical structures, bijections ensure predictability and consistency across structures. In the exercise, the function symbol \( f \) is bijective, implying that for any structure, \( f \) maps elements in a way that can help us determine properties like loops, shown by the lack of cycles of various lengths.

Categoricity

Categoricity in logic refers to the property of a theory being categorical if, for a particular cardinality, all models of the theory in that cardinality are isomorphic.
In other words, if a theory is \( \kappa \)-categorical for some cardinality \( \kappa \), any two models that have a size \( \kappa \) look the same in structural terms. They are essentially identical, except perhaps for a change in the names of their elements.
For the exercise at hand, the theory \( T \) is \( \kappa \)-categorical for cardinals greater than \( \aleph_0 \), the smallest infinite cardinal. This means that for any infinite structure larger than countable infinity, all models of the theory are structurally the same. However, \( T \) is not \( \aleph_0 \)-categorical because it allows multiple non-isomorphic models in the countable size. These models can vary because they do not allow any finite loops, yet can organize elements in uncountably diverse sequences.

Completeness

A theory is said to be complete if, for any given statement in the language of the theory, the theory can affirm whether that statement is true or false.
Completeness suggests that there are no gaps in the theory's coverage of its subject matter. It can answer any question you pose that fits within its logical language.
In the context of the exercise, theory \( T \) is complete because the axioms fully describe how the function \( f \) behaves within models. The axioms specify that \( f \) is bijective and exclude any finite loops. This completeness allows us to resolve every query about \( f \)'s behavior within the theory.
When all structurally possible models share this behavior, every proposition on the function's properties becomes provable within \( T \).

Decidability

Decidability is the property of a theory where there exists an algorithmic process that can determine whether any given statement pertaining to the theory is true or false.
In simple terms, if a theory is decidable, you can hand a question to a computer program, and it will correctly inform you whether that statement is true or not.
Theory \( T \) from the exercise is decidable because the axioms clearly state the properties of \( f \). The function is bijective, and each potential loop is methodically excluded. Due to these precisely defined rules, an algorithm can decide the truth or falsity of any statement in \( T \).
However, despite its completeness and decidability, \( T \) is not finitely axiomatizable because excluding loops of every possible length \( n \) necessitates infinitely many axioms.