Question: Prove/Disprove that there exists a statement A in the signature $\{c,f^1, R^2\}$ that is satisfiable in a structure M $\iff $ for every element in $a\in D^M$ there is a closed term t s.t. $t^M=a$.
My proof:
(I believe it's true)
- Assume that such a statement b exists.
- Denote $a_n = \exists x f^n(c)=x$ (= there's an element in the domain which is "reachable" via $f^n$.
- So $\neg a_n$ (= for every element in the domain - it's "unreachable" by $f^n$)
- Denote $T= \lbrace \neg a_n \mid n \in \mathbb N \rbrace \cup \lbrace b \rbrace$
- On one hand $T$ isn't satisfiable because it means (from b) that every element can be "reached" by some $f^n$, but the set of $a$s says that no element can be reached via $f^n$.
On the other hand every subset $T' \subset T$ is satisfiable because:
if $T'$ is a subset of the a's then it can be satisfied by a structure that defines $f$ to never reach some element no matter how many times it's applied.
If $T'$ is $b$ then it can be satisfied by a structure that its domain is of size $1$ ($c$ itself) and $f^M=\operatorname{Id}$.
If $T'$ is a mix of both $a$s and $b$ then we can define a structure in which $f$ reaches all elements only after the applying $f$ $q$ times ($q$ being maximal $n$ appearing in $T'$).
This leads to a contradiction using the compactness theorem on $T$.
My problem with this proof is this - how can I define $f$ s.t it'll satisfy the requirements I've made in my proof (that it will reach all elements only after $n$ applies and not reach them before)?
You are heading in the right direction but haven't quite got there. Suppose the sentence $A$ holds in a structure $M$ for the given signature iff any element $a \in D^M$ is equal to $f^n(c)$ for some $n \in \Bbb{N}$. (We don't believe such an $A$ exists, so we want to derive a contradiction.) Now consider the model $M$ with $D^M = \Bbb{N}$, $c = 0$ and $f(n) = n + 1$ ($R$ is not relevant). $A$ must hold in $M$ (because if $n \in \Bbb{N}$, then $n = f^n(0)$). Now add a new constant symbol $d$ to our signature and consider the sentences $B_n \equiv A \land d \neq f^n(c)$. Any finite subset of the sentences $B_n$ is satisfiable in $M$. Hence, by compactness, there is a model $M'$ that satisfies every $B_n$. But then in $M'$, $A$ holds, but $d \neq f^n(c)$ for any $n$. This contradicts our assumption on $A$.