# How can set-builder notation be used to create a set from a function?

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.

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

## 3 Answers

$$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\}$$

• Great answer. In fact, some authors make no distinction between the range of a set and its co-domain, although they really should. – 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)