Can't find a theory which meets conditions

Question

I'm trying to solve this problem.

There is a language $L = \{f\}$ with equality (we can use '$=$'), where $f$ is a unary function.

Our goal is to decide and prove, whether there is a theory $T$, such that for any realisation $\mathbf{M}$ of language $\mathcal{L}$ stands:

$$ \begin{array}{lrcl} \mbox{(a)} & M \models T &\iff& \mbox{range of f is finite} \\ \mbox{(b)} & M \models T &\iff& \mbox{range of f is infinite} \end{array} $$ I think that I've solved the first question a) finite but I'm not sure:

a) yes, there exists such theory Prove: $ T = \{ \exists y \forall x(f(x)=y) \}$

This theory consists of 1 formula which forces that the range of $f$ is finite.

b) I don't have an idea. The only thing I can say is that $U$ (universe) should be infinite because otherwise, the range of $f(x)$ would be finite.

I suppose that there is no chance to find a theory which satisfies b) but I'm not sure and I can't prove it.

Answer 1

Originally, from your attempts, it seemed that you were looking for a theory that only has (a') finite or (b') infinite models, for which your answer to (a') works and one can answer (b') by noting that a function $f$ from $U$ to $U$ that is one-to-one (injective) and not onto (not surjective) cannot have a finite range.

Now, it seems you want (a) a $T$ that characterises the models where $f$ has a finite range and (b) a $T$ that characterises the models where $f$ has an infinite range. The answer to (a) is that no such $T$ exists, which can be proved using something called the compactness theorem that I suspect you haven't studied yet. For (b) such a $T$ does exist: for $n = 2, 3, \ldots$, let $\phi_n(x_1, \ldots x_n)$ be a frmula with free variables $x_1, \ldots, x_n$ that asserts that the $x_i$ are pairwise distinct. (I leave it to you to design $\phi_n$.) Then take $T$ to comprise the infinite lists of sentences: $$ \exists x_1 \exists x_2\,\phi_2(f(x_1), f(x_2)) \\ \exists x_1 \exists x_2\exists x_3\,\phi_3(f(x_1), f(x_2), f(x_3)) \\ \vdots \\ \exists x_1 \ldots \exists x_n\, \phi_n(f(x_1), \ldots, f(x_n))\\ \vdots $$

Answer 2

Part (b) is possible. Let $T_I$ include, for each $n \in \mathbb{N}$, the formula $$ (\exists x_1)\cdots(\exists x_n)[f(x_1) \not = f(x_2) \land \cdots \land f(x_1) \not = f(x_n) \land f(x_2) \not = f(x_3)\land \cdots ]$$

where every possible nonequality between variables $x_i $ and $x_j$ for $i,j \leq n$ is included. Then any model of $T_I$ will have a function with infinite range, because the range has at least $n$ elements for every $n \in\mathbb{N}$, and conversely if $f$ is any function then the model $M_f$ obtained from $f$ will satisfy $T_I$.

Part (a) is impossible, by compactness. Suppose that $T$ was a theory such that $M_f$ satisfies $T$ if and only if $f$ has finite range. Then every finite subset of $T \cup T_I$ is satisfiable, because we can find functions with arbitrarily large finite ranges. Thus $T \cup T_I$ is satisfiable by some model $M$. Then the function $f$ in $M$ will have infinite range (because $M$ satisfies $T_I$), but $M$ will also satisfy $T$, which is a contradiction.