Glossar

Wähle eines der Schlüsselwörter auf der linken Seite…

Sets and functionsSet Builder Notation

Lesezeit: ~15 min

It's often useful to define a set in terms of the properties its elements are supposed to have.

Definition
If S is a set and P is a property which each element of S either satisfies or does not satisfy, then

\begin{align*}\{s \in S : s \textrm{ satisfies } P\}\end{align*}

denotes the set of all elements in S which have the property P. This is called set builder notation. The colon is read as "such that".

Example
Suppose the set S denotes the set of all real numbers between 0 and 1. Then S can be expressed as

\begin{align*}S = \{s \in \mathbb{R} : 0 < s < 1\}.\end{align*}

Counting the number of elements in a set is also an important operation:

Definition (Cardinality)
Given a set S, the cardinality of S, denoted |S|, denotes the number of elements in S.

Exercise
Let S = \{4,3,4,1\}. Then |S| = .

Solution. There are three values s with the property that s \in S. Therefore, |S| = 3.

Not every set has an integer number of elements. Some sets have more elements than any set of the form \{1,2,...,n\}. These sets are said to be .

Definition (Countably infinite)
A set is countably infinite if its elements can be arranged in a sequence.

Example
The set \{1,2,3,4,...\} is . The set of integers is , since they can be arranged sequentially: \{0, 1, -1, 2, -2, 3, -3, ...\}.

The set of rational numbers between 0 and 1 is countably infinite, since they all appear in the sequence

\begin{align*}\frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{3}{4}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \ldots\end{align*}

The set of all real numbers between 0 and 1 is , because any infinite sequence of real numbers will necessarily fail to include all real numbers. This may be demonstrated using an idea called Cantor's diagonal argument, which you can read more about here if you're interested.

Exercise
Show that the set of all ordered pairs of positive integers is countably infinite.

Solution. We visualize the pairs as a grid of points in the first quadrant. We arrange the points in a sequence by beginning in the lower left corner at (1,1) and snake through the grid: we go right to (2,1), then diagonally northwest to (1,2), then up to (1,3), then diagonally southeast to (2,2) and through to (3,2), and so on.

Bruno
Bruno Bruno