1
$\begingroup$

Is it possible to write a sentence (formula) that expresses successor function being injective?

And in general, is it possible to state injectivity or surjectivity of a function in first-order?

1 Answers 1

5

Suppose that $f$ is an unary function symbol, write:

$\text{Injectivity: }\forall x\forall y(f(x)=f(y)\rightarrow x=y)\\ \text{Surjectivity: }\forall y\exists x(f(x)=y)$

For functions with several variables we simply have to quantify several variables. Note that we do not care for the interpretation of the symbol, only that it is a function.