My understanding of the set-builder notation (from this question), is that the format for defining a set $C$ is as follows:

$ C ::= $ { $x \in S: \varphi(x)$}

read as "C is the set of all $x$ in $S$ such that $\varphi(x)$ is true."

From this explanation, $x$ is iterated over the elements of $S$, and $\varphi(x)$ is a propositional formula that returns a value in the Boolean domain.

How would one use this notation to build a set, for instance, of the values of some function $f(n) $, where $n$ is a non-zero integer? The following -

$ C ::= $ { $f(n) : n \in N $}

does not conform to the notation above.

  • $\begingroup$ $\{f(n) : n \in N\}$ is shorthand as explained below, but $\{f(n) : \forall n \in N\}$ is just meaningless. $\endgroup$ – Trevor Wilson Feb 12 '13 at 2:00

$$ C ::= \{ f(n) : \forall n \in N \}$$

is a shorthand for

$$C ::= \{ m \in M : \exists n\in N \text{ such that } m = f(n) \}$$

where $M$ is the codomain of $f$. Here your predicate $\phi(m)$ is $\exists n\in N $ such that $ m = f(n)$.

This abuse of notation is universal: people do often write things like $\{ f(n) : \forall n \in N \}$ without defining what it means, and depend on the reader to understand what is meant. But it's also no trouble to say that if $f$ is a function with domain $A$ and codomain $B$, and $A'\subset A$, then $\{ f(a) : a\in A' \}$ is defined to mean the same as $\{ b\in B : \exists a\in A' \text{ such that } b=f(a) \}$.

Similarly, one often defines a set of ordered pairs using a notation like

$$D ::= \{ \langle p, q\rangle : p\in P, q\in Q, \phi(p,q)\}$$

when what is really meant is

$$D ::= \{z \in P\times Q : \exists p\in P \text{ and }\exists q\in Q\text{ such that } z = \langle p, q\rangle \text{ and }\phi(p,q)\} $$

and it rarely or never seems to cause confusion.

In my experience this is rarely spelled out, and you are very observant to notice it. The first place I saw it discussed explicitly was in the appendix to John L. Kelley's Topology, which first defines the composition of two relations $r$ and $s$:

57 DEFINITION $r\circ s = \{u : \text {for some $x$, some $y$, and some $z$, $u=\langle x,z\rangle,\langle x,y\rangle\in s \text{ and } \langle y,z\rangle \in r$}\}$

and then explains the shorthand:

To avoid excessive notation we agree that $\{\langle x, y\rangle : \cdots\}$ is to be identical with $\{u: \text{ for some $x$, for some $z$, $u=\langle x,z\rangle$, and }\cdots \}$. Thus $r\circ s = \{\langle x,z\rangle : \text{for some $y$, $\langle x,y\rangle\in s$ and $ \langle y,z\rangle \in r$ } \}$.

(1955 edition, page 260.)


Part of the definition of a function includes its codomain. So if $f: A \rightarrow B$ is a function then the image is $$ \text{Im}(f) = \{b \in B: \exists a \in A, f(a) = b\} $$

  • $\begingroup$ Great answer. In fact, some authors make no distinction between the range of a set and its co-domain, although they really should. $\endgroup$ – jII Feb 17 '13 at 21:00

There are other forms of set builder notation. The one you mention is based on the axiom of replacement rather than the axiom of subsets; given any set $S$ and unary logical function $f$ whose domain includes $S$, there is a set

$$ \{ f(x) \mid x \in S \} $$

defined by the property

$$ y \in \{ f(x) \mid x \in S \} \Longleftrightarrow \exists x \in S : y = f(x)$$

(if $f$ is a function whose graph is a set, one can prove the existence of this set without invoking replacement, but the notation is still useful)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.