Exercise 1151Logic, sets and proofs › Quantifiers and negationL1Added 3 Nov 2026

Renaming bound variables

#alpha-conversion#bound variable#renaming

Statement

Show that $\forall x,\ P(x)$ and $\forall y,\ P(y)$ are equivalent ( $\alpha$ -conversion).

Hint

Both express that every element of the domain satisfies $P$ .

Show solutionHide solution

Meaning. $\forall x,\ P(x)$ : every element satisfies $P$ . $\forall y,\ P(y)$ : same.

Conclusion. Renaming bound variables preserves meaning; this is called $\alpha$ -conversion.

Caution. Renaming a free variable is not allowed; e.g. $\forall x,\ P(x,y)$ is not equivalent to $\forall x,\ P(x,z)$ in general.