Extensionality

A set is a collection of objects. The objects in the set are called elements of the set.

If $x$ is an element of a set $S$ , we write $x \in S$ ;
If not, we write $x \notin S$ .
The set which has no elements is called empty set and denoted $\emptyset$ .

It does not matter how we specify the set, or how we order its elements or how many times we count its elements. All that matters are what its elements are.

Definition Extensionality

If $A$ and $B$ are sets, then $A = B$ if and only if every element of $A$ is also an element of $B$ , and vice versa.

In general, when we have objects $a_1, \ldots, a_n$ , then $\{ a_1, \ldots, a_n \}$ is the set $S$ whose elements are $a_1, \ldots, a_n$ . We emphasise the word the, since extensionality tells us that there can be only one such set. Indeed, extensionality also licenses the following:

S = \{ a, a, b \} = \{ a, b \} = \{ b, a \}

We usually don't write out duplicate elements since they have no meaning as extensionality reduces them to same set. In $\LaTeX$ the symbols related to sets are:

Symbol	LaTex
$\{$	`\{`
$\}$	`\}`
$\in$	`\in`
$\notin$	`\notin`
$\emptyset$	`\emptyset`

Example Color palette

Colors used in a website design can be thought as a set. Choosing two blues of the same tone would result in one blue. If two websites use same colors, they use same set of colors.

S_1 = \{

#c74c0e

#3da4db

\}

S_2 = \{

#6b2b54

#3da4db

\}

S_3 = \{

#3da4db

#c74c0e

\}

The color palettes $S_1$ and $S_3$ are same because the elements (colors) are same and the order does not matter. The set $S_2$ is different as only one color matches.

We will later use the sets in relational algebra which is the foundation of SQL databases. For now, we use sets to handle data that are not quantified. One such case is product labels which lists the ingredients used e.g. the amount of milk does not change the fact that a product indeed contains dairy.

def contains_dairy(ingredients: set[str]) -> bool:
    return "milk" in ingredients or "butter" in ingredients

print(contains_dairy({ "flour", "milk", "butter" }))
# True

Problem

Prove that there is at most one empty set.

Authentication Required

Set Builder

Frequently, we’ll specify a set by some property that its elements share. We’ll use the following shorthand notation for that:

\{ x \mid f(x) \}

where the $f(x)$ stands for the property that $x$ has to have in order to be counted among the elements of the set. The property can be thought as a function that generate the elements. The symbol $\mid$ is written as \mid.

Example Generating serving sizes

We want to serve potatoes to our guests. The head cook decided to serve them in multiples of $1.5$ where base amount is $100\text{g}$ . The maximum serving is no more than $500\text{g}$ . To generate all sizes we write

S = \{ x \cdot 1.5 \mid x \in \mathbb{N} \land x \cdot 1.5 \le 500 \} = \{ 150, 225, 337.5 \}

In programming, it is useful to generate values that follow certain rules. Were we writing a program of the previous example to make it possible to calculate servings for any other foods, the program would look like

def calculate_serving_sizes(base_amount: float, multiplier: float, max_amount: float) -> set[float]:
    return { base_amount * multiplier ** i for i in range(1, 10) if base_amount * multiplier ** i <= max_amount}

print(calculate_serving_sizes(100, 1.5, 500))
# {337.5, 225.0, 150.0}

This kind of notation is called set comprehension. Typical use cases may be related to business logic where certain values need to be generated e.g. price classes. The notation in programming languages tend to get longer and more complex than in math so use it only for simple cases.