Basics of sets

A school of fish, a flock of birds, a bunch of grapes, a kit of tools — we use different words, but their meaning is, in fact, almost the same. All these words describe collections of objects. In math, every collection of objects is called a set. You can imagine a set as a "bag" that contains its objects.

This doesn't sound like a precise definition — and, in fact, it is not. The rigorous treatment of the concept of set involves a lot of intricate and sometimes tedious work. Luckily, most applications require only an intuitive understanding — and that's what you are going to build now. Sets and functions serve as a common language shared among all mathematicians and computer scientists. For example, the concept of a datatype in computer science builds upon the concept of a set. In fact, a datatype is a set together with a list of operations that you can perform on objects from that set.

Well, let's learn the basics of the language of sets!

What is a set?

A set is an unordered collection of distinct objects, called elements, or members of the set. For instance, a set of learners of programming, a set of learners of math, a set of books on the shelf, a set of decimal digits, and a set of lowercase Latin letters. A convenient way of specifying a set is by listing its members within braces (curly brackets):

$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 0\} \text{ is the set of decimal digits}\\ \{\text{Jupiter}, \text{Saturn}, \text{Uranus}, \text{Neptune}\} \text{ is the set of giant planets of the Solar System}$

A usual practice is to denote sets by capital Latin letters. For example, you may use $D$ and $G$ for the sets above (the set of digits and the set of giant planets, respectively).

Sometimes, you can list just enough elements of a set to understand the general pattern and use ellipses (...) to denote the rest. For example,

$F = \{\text{a}, \text{b}, \ldots, \text{h}\}$is the set of Latin letters from a to h (corresponding to vertical rows, or files, on the chessboard), and

$N = \{1, 2, 3, 4, 5, \ldots\}$is the set of all positive integers (also known as natural numbers).

It is also possible to characterize all the elements in a set by stating the property or properties they must have to be members of this set. The general form of this notation is the following:$\{x \ |\ x \text{ has property } P\} \ or \ \{x\ | \ P(x)\}$You can read it as "the set of all $x$, such that $x$ has the property $P$" for the former, and "the set of elements $x$ that satisfy some property $P(x)$" for the latter.

For example, if $E = \{0, 2, 4, 6, 8, 10\}$, you could write the following:$E = \{n | n \text{ is an even integer and } 0 \leqslant n \leqslant 10\}$You can read it as "$E$ is equal to the set of even integers $n$, such that $n$ is greater or equal to 0, but less or equal to 10".

Note that although in most applications you would use sets whose elements have some common properties, it is entirely possible for a set to contain seemingly unrelated elements. For instance,

$\{\text{L}, 14, \text{chocolate}, \text{Beethoven}\}$is a valid set containing four elements: L, 14, chocolate, and Beethoven.

As an example of the alternative notation we could have $S=\{ \text{blue, orange, yellow, pink}\}$, then we would write something like this:

$S =\{x| x \ \text{is \ a \ color\} }$

This would read as "$S$ is equal to the set of elements, such that they describe colors".

The cardinality of a set

As you already know, objects in a set are called members or elements of a set. For example, 2 is an element of the set $\{1, 2, 3\}$, football is an element of the set $\{\text{tennis, football, hockey}\}$. Naturally, a set contains its elements. The symbol $\in$ shows that an element belongs to the given set, and $\not \in$ shows that the element doesn't belong to the set. For example,$\text{JavaScript} \not \in \{\text{Python, C++, R}\}$. If a set $S$ contains exactly $n$ elements, where $n$ is a non-negative integer, we say that $S$ is a finite set and that $n$ is the cardinality of $S$. The cardinality of $S$ is denoted by $|S|$: for instance, the cardinality of the set $\{-1, 1\}$ is equal to 2.

A set is said to be infinite if it is not finite. For example, the set of integers is infinite.

Sets can have other sets as members. For example, $\{1,\{1\}\}$ has two elements: the number 1 and the set $\{1\}$.

An important type of set you are going to meet is an empty set. It is a set that has no members. You can denote an empty set as $\emptyset$ or $\{ \}$. The cardinality of an empty set is equal to 0. Thus, $|\emptyset| = 0$. It is critical to note that $\{0\}$ is not empty! It is a set with an element 0 in it, and $|\{0\}| = 1$. The set $\{\emptyset\}$ is also non-empty, it has a single element, which is, in turn, an empty set!

Equality

Two sets are considered equal if they have exactly the same members. For example, $A = \{2, 4, 6\}$ and $B = \{6, 2, 4\}$ are equal. They both contain exactly the elements 2, 4, and 6. Also, two sets $A$ and $B$ are equal if $A \subseteq B$ and $B \subseteq A$.

If sets $A$ and $B$ are equal, you can write $A = B$.

Only the elements of a set determine it: the order of recording these elements is irrelevant. For instance, you can write a set of three elements a, b, and c in six different ways:

$\{a, b, c\} = \{a, c, b\} = \{b, a, c\} =\{c, b, a\} =\{c, a, b\} = \{b, c, a\}$. As you can see, it doesn't matter what order the members are in. Besides, remember that all the elements of a set are distinct. In some programming languages that implement the concept of a set, you can add new elements to it. However, if you want to insert the same element into the set again, the set will not change. For instance, if you take the set $\{1, 2, 3\}$ and try to insert the numbers 2, 2, 3, 3, 3, and 4 into this set, you will get the set $\{1, 2, 3, 4\}$ – with no duplicated 2's or 3's.

Subsets

Sometimes, all the elements of a set are also contained in some larger sets. Informally, the first set is a part of the second. The precise terms for such a relationship are subset and superset.

The set $A$ is called a subset of $B$ if every element of $A$ is also an element of $B$. In this case, $B$ is called a superset of $A$.

For example, $\{1, 3\}$ is a subset of $\{1, 2, 3, 4\}$. However, $\{2, 9\}$ is not a subset of this set, since it has an element 9, which is not in the set $\{1, 2, 3, 4\}$. If $B$ is a subset of $A$, you can denote that by $B \subseteq A$ or $A \supseteq B$. If $A$ is not a subset of $B$, denote that as $A \not \subseteq B$.

In these kinds of situations, a universal quantifier may come in handy. Depicted as $\forall$ and meaning "for all" it is really useful when describing characteristics of elements of a set. For example, if we would like to say that all the elements of $A$ satisfy a certain property we would write it as:

$\forall x\in A \ P(x)$

Translating this into plain English we have: "for all the elements in set A, they satisfy the property $P(x)$".

$A$ is a proper subset of $B$ if and only if every element of $A$ is also an element of $B$, and there exists at least one element in $B$ that is not in $A$. You can denote it by $A \subset B$ or $B \supset A$.

For example, $\{\text{Ruby, Scala}\}$ is a subset of $\{\text{Ruby, Scala}\}$, but it is not a proper subset of $\{\text{Ruby, Scala}\}$. On the other hand, $\{a_1, a_2, a_7\}$ is a proper subset of $\{a_0, a_1, a_2, a_5, a_7, a_9\}$.

Conclusion

In this topic, you have covered the following theory:

• A set is an unordered collection of distinct objects, called elements or members.

• Two sets are considered equal if they have exactly the same members.

• The size of the set is called its cardinality; there exist finite and infinite sets.

• The set $A$ is a subset of $B$ if every element of $A$ is also an element of $B$.