Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$\{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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
Great answer. In fact, some authors make no distinction between the range of a set and its co-domain, although they really should. –  jesterII Feb 17 '13 at 21:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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