# Set-builder notation and the notion of function

My understanding of set-builder notation is that given a set $A$ and a function $P:A\to\{true,false\}$, one can define the subset $$B=\{a\in A:P(a)\} .$$ However, a function $f:A\to C$ is defined as a special kind of subset of the product set $$A\times C= \{(a,c):a\in A,\,c\in C\}.$$ I was wondering if there is any circularity here, since we are using the set-builder notation to define the Cartesian product of two sets. I also imagine that in order to define the set of functions from $A$ to $C$ one needs to use set-builder notation.

• Generally, we work with a formula in some formal logic rather than with a function $P : A \to \{\text{true}, \text{false}\}$. We can define formulae in a recursive fashion without needing to define set-builder notation, avoiding this problem. Commented Jun 5, 2016 at 2:21
• @qaphla: Thanks a lot! Are you saying that some preliminary version of the set-builder notation must be defined before defining the full notation? Commented Jun 5, 2016 at 2:33
• Usually, the set-builder notation is an abbreviation; thus, it is part of the syntax. Commented Jun 5, 2016 at 12:17
• MO copy of the question: mathoverflow.net/questions/241517/set-builder-formula Commented Jun 6, 2016 at 4:18
• @timur - no, I'm not saying that. We introduce it as an abbreviation to "name": the set of those $x$ such that $\varphi(x)$ holds of them, provided that that set exists. Commented Jun 6, 2016 at 5:54

In axiomatic set theory, what you described as set-builder notation corresponds to axiom schema of specification (also called axiom schema of separation).

As already said in the comments, $P(a)$ in this axiom schema does not stand for function but for a formula in the language of set theory.

Axiom schema of replacement is related to the notion of function.

In fact, if you want to define Cartesian product in axiomatic set theory you

• Use Kuratowski definition of ordered pair, i.e., $(a,b)=\{\{a\},\{a,b\}\}$. It can be shown that for any $a$, $b$ the ordered pair $(a,b)$ exists; that $(a,b)=(a',b')$ iff $a=a'$ and $b=b'$; that $(a,b)\in\mathcal P(\mathcal P(A\cup B))$ if $a\in A$ and $b\in B$.
• Then you can define $$A\times B = \{x\in \mathcal P(\mathcal P(A\cup B)); (\exists a\in A)(\exists b\in B) x=(a,b)\}.$$

This means that the Cartesian product is defined using axiom schema of separation (which is written using set-builder notation). And, as you rightly said, function is then defined as a subset of Cartesian product which has some additional properties.

If you want to see a formal definition of formula (as used in the ZFC), for example, it is described nicely in Encyclopedia of Mathematics. Basically, you have the following rules:

1. For any variables $x$, $y$, the atomic formulas $x=y$ and $x\in y$ are formulas.
2. If $\varphi$ and $\psi$ are formulas, then so are $\neg\varphi$, $\varphi\land\psi$, $\varphi\lor\psi$, $\varphi\Rightarrow\psi$ and $\varphi\Leftrightarrow\psi$.
3. If $\varphi$ is formula, then so are $(\forall x) \varphi(x)$ and $(\exists x) \varphi(x)$.

Anything constructed by applying the above rules finitely many times is considered a formula. And nothing else is considered a formula.

So an example of a formula would be $$(\forall x) (x\in A \Rightarrow x\in B).$$ This formula corresponds to $A\subseteq B$.

• Yes. You are allowed to use atomic formulae $x=y$ and $x\in y$ (where $x$ and $y$ are variables.) And you can combine them using logical connectives and quantifiers. Commented Jun 6, 2016 at 12:55
• I don't think that you are allowed quantifiers in Boolean functions. For example, you want $A\subseteq B$ expressed as $(\forall x) (x\in A \Rightarrow x\in B)$ to be a formula. Commented Jun 6, 2016 at 12:58
• If you want see formal definition of formula (as used in the ZFC), it should not be difficult to find some resources. For example, searching for ZFC language formula returns some reasonable hits. Commented Jun 6, 2016 at 13:00
• @timur I have posted a more precise definition of formula in chat. (I did not want to post too many comments here.) If further clarifications are needed, we can continue our discussion there. Commented Jun 6, 2016 at 13:11
• Thanks a lot! I took the liberty of editing your answer to include the discussion about formulas, in case other people find it useful. Commented Jun 6, 2016 at 13:49