Proof Using Compactness Theorem

106 Views Asked by At

Given the class $\{(A,f): \text{ for all } a\in A \text{ exists an } n \in N\setminus\{0\} \text{ with } f^n(a)=a\}$ I have to show that this class is not axiomatizable. I know I can use the compactness theorem, but I can't think of which Axiom-System to use to start off the proof. Any hints would be greatly appreciated.

1

There are 1 best solutions below

0
On

This is an answer to the question : "Is the following property : 'There exists $n\in \mathbb{N}^*$ such that $(K,f) \models \forall a, f^n(a) = a$' axiomatizable ?", where $f^n$ is an abbreviation for $f...f$ where the symbol $f$ appears $n$ times.

Were this class axiomatizable, you could find a theory $T$ such that $(K,f) \models T$ if and only if for some $n\in \mathbb{N}^*$, for all $a \in K$, $f^n (a) = a$

Then let $T' = T\cup \{ \exists a, f^n(a) \neq a \mid n \in \mathbb{N}^*\}$.

Clearly, any model of $T'$ is a model of $T$, and $T'$ is clearly finitely consistent, therefore by the compactness theorem, it is consistent. But a model of $T'$ $(K,f)$ clearly has $(K,f) \models f^n (a) \neq a$ for all $n \in \mathbb{N}^*$.

The answer is similar if the property was "There exists $n\in \mathbb{N}^*$ such that $(K,f) \models \exists a, f^n(a)=a$", instead of the one I understood, but the question isn't precise enough for me to make a distinction.

EDIT : the editing of your question makes neither of my answers valid. But a very similar idea would work, for instance you can add a constant symbol $c$ to the language and consider the theory $T\cup \{f^n(c)\neq c\mid n\in\mathbb{N}^*\}$