# Syntax question about iteration in set builder notation

In Python, list comprehension notation can be used to easily describe sophisticated lists succinctly. They are of the form

[expression(x) for x in iterable if predicate(x)]


Setting s = [1,2,3,4], examples might include the square of odd members of s or the sine of members of s which are greater than 1.

[x*x for x in s if x % 2 == 1]
[sin(z) for z in s if z > 1]


This is clearly inspired by set builder notation in mathematics. However, one difference is the general format of set builder notation there is no for statement. That is a typical set builder expression might be $$\{\ f(x) : p(x)\ \}$$ where $f(x)$ is an expression dependent on $x$ and $p(x)$ is some predicate on $x$.

The syntax doesn't have a clear way of denoting the set from which $x$ came. Sometimes this is shoe-horned into the expression or predicate $$a\mathbb{Z} = \{\ an : n \in \mathbb{Z}\ \}$$ $$\mathbb{N} = \{\ n \in \mathbb{Z} : n > 0 \ \}$$ $$X = \{\ mn : m \in \mathbb{Z} \wedge n \in \mathbb{Z} \wedge n > 0\ \wedge m < 5\}$$

I would like to know if there is an established notation that serves the same role as for? I have taken to writing in my notes $$X = \{\ mn : m \in \mathbb{Z} \wedge n \in \mathbb{Z} : n > 0\ \wedge m < 5\}$$ but this is an invention not convention. This feels like a stupid question, but sticking the $x \in S$ statement into the predicate feels almost like $x$ is being selected from a universal set then whittled down to being contained in $S$, which must be wrong.

## 2 Answers

In official set theory there's no $\{f(x):p(x)\}$. The two officially legal forms are {$x\in S: p(x)\}$ and $\{f(x):x\in S\}$.

People do write $\{x:p(x)\}$, and in practice that typically causes no harm. But when you do that there had better be a set $S$ around such that it's the same as $\{x\in S:p(x)\}$. The point, or anyway a point, to the restrictions is to rule out things like $R=\{x:x\notin x\}$, which as you probably know leads to the contradiction $R\in R$ if and only if $R\notin R$.

Roughly, any time you use "set builder notation" there has to be another set that the set is built from.

• So officially you would have to combine those two forms $\{f(x) : x \in \{y \in S : p(y)\}\}$? – yberman Oct 28 '17 at 20:58
• In formal set theory, yes. In fact there's no hard in writing just $\{f(x): x\in S, p(x)\}$ because it's clear what you mean and it's also easy to justify the existence of this set from the officially allowed forms. – David C. Ullrich Oct 28 '17 at 21:06

I don't think there is a really standard way of doing this. Mathematical notation which is read by humans doesn't have to be as precise as code which is read by computers. Your examples illustrate several commonly understood notations and if you stick with them, you should be fine. The last one might be condensed to $X = \{mn : m,n \in \mathbb{Z}, n>0, m<5 \}$.

Note that they are not entirely consistent: the example of $\mathbb{N}$ has the predicate $n \in \mathbb{Z}$ on the left of the colon, while the others have that predicate on the right.

The Python notation has an expression, an iterable, and a filter condition. But the mathematical notation leaves one of them out under certain conditions: if there is no filter, or if the expression is the trivial identity function. This gives rise to slight inconsistencies.