L-sentence which expresses bijective function

Question

I've stumbled upon this exercise from "Sets, Models, Proofs" and can't seem to find a solution. It goes like this:

Let $L$ be a language with just one 1-place function symbol $F$. Give an $L$-sentence $\phi$ which expresses that $F$ is a bijective function.

Sadly, I'm completely stuck. Any help would be dearly appreciated!

Answer 1

Let us assume that equality is built into the formalism you are using, so that we can use it -- otherwise, the exercise makes no sense.

Now, $F$ is bijective if and only if it is both injective and surjective:

• $F$ is injective iff $F(x) = F(y)$ implies $x = y$ for all $x$ and $y$; equivalently, iff $x \ne y$ implies $F(x) \ne F(y)$.
• $F$ is surjective iff $x = F(y)$ for every $x$.

For injectivity, we can therefore use the following formula:

$$\phi_i:\qquad \forall x: \forall y: F(x) = F(y) \to x = y$$

For surjectivity, we want to express that for every $x$, there exists an $y$ such that $x = F(y)$:

$$\phi_s:\qquad \forall x: \exists y: x = F(y)$$

Therefore, by definition of bijectivity, we may define the formula $\phi$ characterising that $F$ is a bijection as:

$$\phi: \qquad \phi_i \land \phi_s$$