In Set Theory for the Working Mathematician by Krzysztof Ciesielski, the axiom schema of comprehension is stated in the following way:

For every formula $\varphi(s, t)$ with free variables $s$ and $t$, for every $x$ and for every parameter $p$, there exists a set $y = \{ u \in x : \varphi(u, p) \}$ that contains all those $u \in x$ that have property $\varphi$: $$\forall x \forall p \exists y [ \forall u ((u \in y) \leftrightarrow ((u \in x) \wedge \varphi(u, p)))].$$

I'm not sure what the author means by the word "parameter" in this context.

Maybe the word "parameter" is familiar to people well-versed in first-order logic. But I'm not one of those people. I've never studied first-order logic formally, and it's unlikely that I'm going to find time to study it in the near future. I've always been content to do practical mathematics, getting by with only an intuitive grasp of concepts from first-order logic.

Because of my limited background in logic, I find it difficult to make sense of answers such as this one. I see phrases like "element of a structure", which must have some specific meaning understandable only to people who have studied first-order logic seriously. (Even when I see the word "formula" in this answer, I'm left wondering if I've failed to pick up on some specific meaning, since I would personally have used the word "expression" instead.)

That said, I have a pretty good idea of what the axiom schema of comprehension should say. Usually, when I do practical mathematics, I interpret the axiom schema of comprehension like this:

For every formula $\varphi(s, w_1, \dots, w_n)$ with free variables $s, w_1, \dots, w_n$, we have $$\forall x \forall w_1 \dots \forall w_n \exists y [ \forall u ((u \in y) \leftrightarrow ((u \in x) \wedge \varphi(u, w_1, \dots, w_n)))].$$

This interpretation agrees with the wikipedia article on this subject.

So when my book talks about a "parameter $p$", should I interpret $p$ as a finite collection of free variables $w_1, \dots, w_n$? And should I think of the quantifier $\forall p$ as being synonymous with $\forall w_1 \dots \forall w_n$? Finally, if the book mentions "a formula $\varphi(s, t)$ with free variables $s$ and $t$" and then goes on to write down the expression $\varphi(u, p)$, then should I take this to mean that $\varphi$ depends on $n + 1$ variables (rather than $2$ variables), and that $\varphi(u, p)$ is shorthand for $\varphi(u, w_1, \dots, w_n)$?

Or perhaps, the correct way to connect the statement in the book to the statement in Wikipedia is to equate the $p$ in the book with the ordered tuple $(w_1, \dots, w_n)$, where $w_1, \dots, w_n$ are the variables in Wikipedia? For this to work, the formula $\varphi(u, p)$ would have to contain a clause that asserts that $p$ is an $n$-tuple, but this is fine.


1 Answer 1


I think your understanding is fine. It's just a question of jargon.

First, "formula" is traditional rather than "expression". It's just history. Why do algebraists say "abelian group", but "commutative ring"?

Logicians also traditionally say "sentence" to mean "closed formula". Personally, I think "statement" or "assertion" would have been a better choice, but it is what it is.

"Parameter" has no formal status. As you indicate, formally parameters are just free variables. But the use of that term tells you something about the intention of the author. In the comprehension axiom (which I prefer to call separation), the focus is on the set $x$ which is being "separated" into a subset $y$ and the rest. This division may depend on other variables, the so-called parameters.

This is analogous to the usage in other parts of (pure and applied) mathematics. For example, consider the formula for exponential growth, $Ae^{kt}$. You'd probably say this is function of $t$ with parameters $A$ and $k$, rather than just calling it a function of three variables (which, formally, it is).

Now as to $p$ vs. $w_1,\ldots,w_n$, I haven't seen Separation stated this way with only one parameter. (I'm not familiar with Ciesielski's book.) You might be able to show that it's equivalent to the multi-parameter version, using the tuple trick you mentioned. One would need to prove that the tupling and coordinate-extraction "functions" had the right properties, without using multi-parameter Separation in the proof. (This partly depends on what your other axioms are.) But ZF set theory certainly relies on multi-parameter Separation for its development.

Thinking about it a little, I'm convinced that single-parameter implies multi-parameter in the context of the usual ZF axioms. First, tuples are just iterated pairs, so we just need $\forall s,t\exists p(p=(s,t))$. Here $(s,t)$ is defined by the Kuratowski trick, $(s,t)=\{s,\{s,t\}\}$, which exists by the Pair axiom. So a two-parameter condition $\varphi(u,s,t)$ in an instance of Separation is replaced with the one-parameter $$\forall s,t(p=(s,t)\to\varphi(u,s,t))$$ or alternately $$\exists s,t(p=(s,t)\wedge\varphi(u,s,t))$$ and $p=(s,t)$ in turn can be expanded into a mildly annoying formula (with free variables $p,s,t$) that I won't bother to write out.

  • $\begingroup$ Would it be the case that the parameters aren’t needed? If the schema says that they’re bounded by quantification, what’s to stop someone from making $\forall x \exists y \forall u (u \in y \iff (u \in x \wedge \forall p \phi(u,p)))$ (p is a tuple of parameters)? By moving the quantifier inwards, you just have a one variable formula depending on $u$ and nothing else. What have I missed here? $\endgroup$
    – Lave Cave
    Aug 2 at 5:25
  • $\begingroup$ It's not legitimate to move the $\forall$ quantifier inward like that. The problem is moving it past the $\exists$. An example from number theory: $\forall x\forall p\exists y(y>xp)$ is not equivalent to $\forall x\exists y\forall p(y>xp)$. $\endgroup$ Aug 2 at 12:04

You must log in to answer this question.

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