Set comprehension

From CS2800 wiki


The notation [math]\{x \mid \text{property of } x\} [/math] denotes the set of all [math]x [/math] that satisfy the property. You should read [math]\href{/cs2800/wiki/index.php/%5Cmid}{\mid} [/math] as "such that". For example,

[math]A \href{/cs2800/wiki/index.php/Definition}{:=} \{x \mid x\href{/cs2800/wiki/index.php/Even}{\text{ is even}}\} [/math]

indicates the set of all even numbers. [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] because [math]2 [/math] is even, while [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} A [/math] because [math]1 [/math] is not even.

We may want to specify that we're only interested in natural numbers; we often use notation like [math]\{x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \mid x\href{/cs2800/wiki/index.php/Even}{\text{ is even}}\} [/math]. This should be read as "the set of natural numbers which are even".

We can also have more complicated expressions to the left of the vertical bar, for example [math]B \href{/cs2800/wiki/index.php/Definition}{:=} \{2y \mid y \in \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\} [/math] also denotes the set of even natural numbers: [math]8 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math] because [math]8 = 2\href{/cs2800/wiki/index.php?title=%5Ccdot&action=edit&redlink=1}{\cdot}4 [/math] and [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], while [math]7 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} B [/math] because there is no natural number that when multiplied by 2 gives 7.