3

Let $\Gamma$ be the set of sentences containing the formula

$\exists x(x\neq f^n(x)) $

for each $n>0$.

I'm trying to get a feel for the models of $\Gamma$; in particular, is there a single sentence of FOL that true in exactly the models of $\Gamma$. Thanks.

Cookie
  • 13,532
FOL student
  • 31
  • What sort of a function is $f$? And by $f^n$, do you mean iteration? – user128390 May 21 '14 at 11:57
  • Apologies. $f$ is any one place function and $f^nx$ is an abbreviation of $x$ preceded by $n$ occurrences of $f$ – FOL student May 21 '14 at 12:00
  • So yes, iteration, but I'm still thinking the model may depend on the nature of $f$. Your sentences say "there is an $x$ which is not a fixed point of $f^n$". This sentence is only false when $f^n$ is the identity function. – user128390 May 21 '14 at 12:36
  • Thanks. I agree that whether or not a model verifies every sentence in $\Gamma$ will depend upon how it interprets $f$; however, can't we still answer the question of whether there is a single sentence which is true in exactly those models in which every sentence in $\Gamma$ is true? – FOL student May 21 '14 at 13:04
  • I can note that this is roughly the same thing you find in group theory for groups with elements of arbitrarily large order. There should be models where every iterate of $f$ has some point it doesn't fix (though possibly every element is fixed by some $f$-iterate); and there should be models where there's a particular element $x$ that's not a fixed point of any $f$-iterate. Beyond that I have nothing interesting I can say :p – Malice Vidrine May 25 '14 at 20:14
  • It also seems like for any model with more than one element any constant-valued $f$ would do the trick, too? – Malice Vidrine May 25 '14 at 20:53
  • The answer will (obviously) be 'no'. To see this, suppose $\varphi$ were such a sentence and either induct on complexity or put it in some sort of normal form ('prenex normal form' seems to be the phrase used on Wikipedia). The analysis may be tedious, but should come with relative ease. –  May 26 '14 at 01:56

2 Answers2

1

If there were a single sentence $\phi$ that is equivalent to the infinite collection of sentences $\exists x\,(f^n(x)\neq x)$, which I'll abbreviate as $\beta_n$, then, by the completeness theorem for first-order logic, there would be a formal deduction of $\phi$ from the $\beta_n$'s. That deduction, being a finite list of sentences, would use only finitely many of the $\beta_n$'s. Pick a number $m$ bigger than all the finitely many $n$'s such that $\beta_n$ is used in your deduction. Consider a model consisting of $m$ elements and a function $f$ that permutes them cyclically --- a single cycle of length $m$. This model satisfies all the $\beta_n$'s used in your deduction (in fact, it satisfies $\beta_n$ for every $n$ that isn't divisible by $m$), so, thanks to that deduction, it satisfies $\phi$. But it doesn't satisfy $\beta_m$. So $\phi$ is not equivalent to the collection of all your $\beta$'s.

Andreas Blass
  • 71,833
  • 1
    For the experts: I'm well aware that most of this answer is re-proving the compactness theorem. I conjecture that, for the OP, re-proving it is more useful than being efficient and just citing it. – Andreas Blass May 26 '14 at 03:04
0

$$ \forall n \exists x (n > 0 \implies x \neq f^n(x)) $$

For all $n$ bigger than $0$ there exists $x$ which is not equal to $f^n(x)$.

  • 2
    I don't think we can assume this particular language has $>$ or $0$, nor that we have the means to intra-theoretically bind the $n$ in $f^n$. – Malice Vidrine May 25 '14 at 20:00
  • Generally speaking the natural numbers are not part of first-order logic; so as @Malice Vidrine points out, we cannot quantify over them and certainly not in such way that we can talk about iterated compositions like that. – Asaf Karagila May 25 '14 at 20:12