1
$\begingroup$

In my book "The Foundations of Mathematics" by Kenneth Kunen, the following sentence is written:

In Comprehension [referencing the Comprehension Schema axiom], $\varphi$ can even have $z$ free - for example, it's legitimate to form $z^*=\{x \in z: \exists u (x \in u \land u \in z)\}$

I am slightly confused as to why $z$ is considered free in this set. The Comprehension Schema reads as follows:

Comprehension Schema: $\forall z \Big ( \exists y \forall x (x \in y \leftrightarrow x\in z \land \varphi(x) \big) \Big)$.

Swapping out $\varphi (x)$ for $\exists u (x \in u \land u \in z)$ we would create:

$\forall z \Big ( \exists y \forall x \big (x \in y \leftrightarrow x\in z \land \exists u (x \in u \land u \in z) \big ) \Big)$

The $z$ in the $\varphi$ formula is in the scope of the first universal quantifier at the beginning of this sentence. So why exactly is $z$ "free", as stated by Kunen? Does "free" mean different things depending on the context?

Thank you~


Edit: I figured I would put this here in case anyone else had a similar question.

The terms "bound" and "free" are always relative to a particular formula.

Consider the following:

Let $\psi_1 := \forall z \Big ( \exists y \forall x \big (x \in y \leftrightarrow x\in z \land \exists u (x \in u \land u \in z) \big ) \Big)$. In $\psi_1$, all variables are bound (i.e. no variable is free).

Let $\psi_2: = \exists y \forall x \big (x \in y \leftrightarrow x\in z \land \exists u (x \in u \land u \in z) \big )$. In $\psi_2$, variables $y,x,$ and $u$ are all bound but variable $z$ is free.

Let $\psi_3: = \forall x \big (x \in y \leftrightarrow x\in z \land \exists u (x \in u \land u \in z) \big )$. In $\psi_3$, variables $x$ and $u$ are bound, but variables $z$ and $y$ are free.

Let $\psi_4: = x \in y \leftrightarrow x\in z \land \exists u (x \in u \land u \in z)$. In $\psi_4$, variable $u$ is bound, but variable $z, y,$ and $x$ are free.

$\endgroup$
2
  • $\begingroup$ @MauroALLEGRANZA but isn't $z$ quantified by the $\forall z$ quantifier in the comprehension schema? $\endgroup$
    – S.C.
    Oct 30, 2020 at 13:15
  • $\begingroup$ Now I'm even more confused hah. How is $x$ a free variable when it is within the scope of the $\forall x$ quantifier? $\endgroup$
    – S.C.
    Oct 30, 2020 at 13:18

1 Answer 1

2
$\begingroup$

Variable $z$ is free in formula $∃u(x∈u ∧ u∈z)$ because there is no quantifier binding it, while the two occurrences of variable $u$ are bound because they are in the scope of the quantifier $∃u$

The general form of the axiom schema is $A = \{ x \mid \varphi(x) \}$ where $x$ must be free in the formula $\varphi(x)$ specifying the condition that defines the set.

Thus, Kunen's formula amounts to:

$A_z = \{x \mid x∈z \land ∃u(x∈u ∧ u∈z) \}$.

The formula $\varphi(x)$ is $(x∈z \land ∃u(x∈u ∧ u∈z))$ with $x$ free.

The formula has an additional free variables (a parameter): $z$.

This means that we are defining a "families" of sets $A_z$: one for each value of $z$.


The set-forming operator $\{ x \mid \varphi(x) \}$ maps a formula ($\varphi$) into a term (a "name") denoting a set.

It binds the variable $x$. Thus, if there are no other free variables in the formula, it is a closed term.

The key-property of the operator is:

$\forall z [z \in \{ x \mid \varphi(x) \} \leftrightarrow \varphi (z)]$.


Having said that, how to apply it to Kunen's example ?

We have:

$∀z(∃y∀x(x∈y ↔ x∈z∧∃u(x∈u ∧ u∈z)))$.

We have a "specifying condition": $\psi(x,z) := x∈z ∧ ∃u(x∈u ∧ u∈z)$, with two free variables.

The axioms schema asserts that there is a set $y$ with all and only those elements $x$ that satisfy the condition:

$y = \{ x \mid x∈z ∧ ∃u(x∈u ∧ u∈z) \}$.

Thus, applying the above formula:

$\forall x [x \in y \leftrightarrow (x∈z ∧ ∃u(x∈u ∧ u∈z))]$.

$\endgroup$
5
  • $\begingroup$ Could you please clarify if the following is correct? Consider two formulas. $\psi_1 = \forall x \varphi (x)$ and $\psi_2 = \varphi(x)$ (where the $\varphi$ in $\psi_2$ refers to the same $\varphi$ in $\psi_1$). When I am speaking about $\psi_1$, $x$ is not free. However, when I speak about $\psi_2$, even though I am still referring to the same $\varphi$, I would say that that x in $\varphi(x)$ is free. Is that right? $\endgroup$
    – S.C.
    Oct 30, 2020 at 13:29
  • 1
    $\begingroup$ @S.Cramer - correct. See my first line in the answer above. $\endgroup$ Oct 30, 2020 at 13:35
  • $\begingroup$ Great. Thank you very much. I added something to my post (Edit section) that I would love for you to comment on. Is my edit correct? (i.e. that the terms "free" and "bound" are always relative to a particular formula, even if that particular formula is "embedded" within another 'larger' formula) $\endgroup$
    – S.C.
    Oct 30, 2020 at 13:51
  • 2
    $\begingroup$ @S.Cramer - to be precise, free and bound are always relative to a particular occurrence in a particular formula. In $\forall x (z \in x \land \exists z (z=z))$ we have that the 1st (from left) occurrence of $z$ in the complete formula is free while the remaining are bound. $\endgroup$ Oct 30, 2020 at 13:58
  • 1
    $\begingroup$ And yes, in the sub-formula ∃z(z=z) (of the complete formula) the occurrences of $z$ are bound. $\endgroup$ Oct 30, 2020 at 13:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .