[Math] How to set-builder notation be used to create a set from a function

elementary-set-theorynotation

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.

Best Answer

$$ 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.)

Related Question