Specification of a set

Naive set theory: Elementary notions and notations

Specification of a set

We do not provide definitions of sets and their objects, nor do we discuss axioms. Instead, we work with an intuitive description and primarily try to give a good impression of what we are talking about through examples.

Intuitive definition of a set

Intuitive definition

A set can be viewed as a collection of objects such that you can unambiguously

determine whether each object belongs to that collection or not;
identify each object. This means you can check when two objects are equal to each other and thus are in fact the same object.

A special set is the empty set, which—nomen est omen—contains no objects.

A finite set is a set that contains only a finite number of elements. We denote the number of elements of the finite set $X$ with $\# X$ and $|X|$. This is called the cardinality of $X$.

Examples

Odd numbers less than 10;
Place-names in the Netherlands;
Vowels in the Dutch alphabet;
Fibonacci numbers (0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...);
The set consisting of all sets that can be constructed with the objects $a$, $b$, and $c$, including the empty set;
The real numbers.

If $X=\{a,b\}$ then $\hash X=|X|=2$.

You may wonder why the objects in a set must be distinguishable from one another. Well, without this characteristic, determining the size of a set becomes problematic. It is a pragmatic choice: in an alphabet, you will not include the letter a twice; in a stamp collection, on the other hand, you do want to include duplicates.

Explicit specification and notation

Explicit specification (enumeration) and notation

We usually denote sets with uppercase letters $A, B, C,\ldots$ and use lowercase letters $a, b, c,\ldots$ to refer to the objects, also called elements, in the set.

When we explicitly specify (or enumerate) a set by listing the elements, we use curly brackets. The order in which we group the objects does not matter.

The empty set is denoted by $\emptyset$ or $\{\}$.

If $x$ is an element of the set $X$, we denote this as $x\in X$. If $x$ is not an element of the set $X$, we denote this as $x\notin X$.

Examples

$\{1,3,5,7,9\}$ is the set of odd numbers less than 10. \[\{1,2,3\}=\{3,2,1\}\] \[4\in \{2,4,6\}\] \[\text{Corneel}\notin \{\text{Jan}, \text{Piet}, \text{Joris}\}\] \[a\in \{a\}\] \[a \notin \bigl\{\{a\}, \{b\}, \{a,b\}\bigr\}\] \[\{1,1,2\}=\{1,2\}\]

Word choice Instead of "$x$ is an element of $X$", we also use the phrases "$x$ belongs to $X$" and "$x$ is a member of $X$."

Index notation If there are multiple sets specified in the same way, we can still use one uppercase letter by adding a so-called index. An example is \[N_i\overset{\text{def}}{=}\text{the set of all natural numbers less than or equal to }i\text.\] In this case, $N_0=\{0\}$, $N_1=\{0,1\}$, $N_2=\{0,1,2\}$, $N_3=\{0,1,2,3\}$, and so on.

Notations for commonly used sets Some sets have fixed names and notations, such as the following sets of numbers: the natural numbers ($\mathbb{N}$), the integers ($\mathbb{Z}$), the rational numbers ($\mathbb{Q}$), the real numbers ($\mathbb{R}$), the complex numbers ($\mathbb{C}$), and the quaternions ($\mathbb{H}$). The set of positive real numbers is denoted as $\mathbb{R}^{+}$. Thus, $\mathbb{R}^{+}=\{x\in \mathbb{R}\mid x>0\}$ In the same way are defined $\mathbb{Z}^{+}=\{1,2,3,\ldots\}$ and $\mathbb{Q}^{+}=\{r\in \mathbb{Q}\mid r>0\}$. The set of nonzero real numbers is denoted as $\mathbb{R}^{*}$. Thus, $\mathbb{R}^{+*}=\{x\in \mathbb{R}\mid x\neq 0\}$ In the same way are defined $\mathbb{Z}^{*}=\{\ldots, -3, -2, -1, 1,2,3,\ldots\}$, $\mathbb{Q}^{*}=\{r\in \mathbb{Q}\mid r\neq 0\}$ and $\mathbb{C}^{*}=\{z\in \mathbb{C}\mid z\neq 0\}$.

Implicit specification and notation

Implicit specification (description, construction)

An explicit specification of a set is inconvenient when the number of elements is large or infinite, or when it obscures the structure of a set. In this case, you better use an implicit specification by stating a defining property. Two common notations are: \[X=\{x\mid P(x)\}\text,\] which indicates that all $x$'s for which $P(x)$ holds are elements of the set $X$.

Before you can explore whether $P(x)$ hold for a particular $x$, you must first be able to choose an object $x$. To do this, we assume another set, which we call the universe and sometimes denote by the letter $U$. You can (implicitly) mention the universe in the property or place it before the separator \[X=\{x\in U\mid P(x)\}\text.\]

You can also use a constructive specification using a function $f$ : \[X=\{f(x)\mid P(x)\}\text,\] denotes the set of function values $f(x)$ for those values of $x$ for which $P(x)$ holds.

Examples

\[\{n \mid n=1\text{ of }n=2\}= \{0,1\}\] \[\{n\in\mathbb{N} \mid 0\le n\le 1\}= \{0,1\}\] \[\{n\in\mathbb{N} \mid n \text{ number divisible by }2\}\] \[{}= \text{even natural numbers}\\\] \[\{n^2\mid n\in\mathbb{Z}\}={}\] \[\text{all squares of whole numbers}\\\] \[\bigl\{n^3\mid n\in\{0,1,2,3,4,5\}\bigl\}\] \[{}=\{0,1,8,27,64,125\}\phantom{xxxxx}\,\,\] \[{}=\text{first 6 third powers in }\mathbb{N}\\\] \[\{10n\mid n\in\mathbb{N}\text{ and } -10<n<10\}\] \[{}=\text{tens between }-100\text{ and }100\\\] \[\{n \mid n\neq n\}= \emptyset\]

Colon Instead of $\{f(x)\mid P(x)\}$, some books also write $\{f(x) : P(x)\}$, which means that a colon is used as separator instead of a vertical bar.

The naive comprehension principle, which we use in this theory page, can be formulated as follows:

"Let $P$ be a property of objects (sets), then there exists a set consisting of exactly those objects that have the property $P$."

But later (in Cantor's paradox and in Russell's paradox) this naive comprehension principle turned out to be untenable. Only axiomatic set theory offers a solution here, but this falls outside the scope of the course material.

Russell's paradox can be described as follows:

Let $X$ be the set of all sets that do not contain themselves as a member. Consider the question: Does $X$ contain itself? If the answer to this question is no, then $X$, by definition must contain itself. If the answer to this question is yes, then $X$ must contain itself. However in both cases, if $X$ contains itself, then it is by definition unable to contain itself. We have derived a contradtion.

Interval notation Often the universe consists of the set of real numbers and an interval is specified in it. An interval is a contiguous collection of real numbers, a part of a number line. Below are intervals with the usual notation and the corresponding part of the number line. For example \[\ivoo{a}{b}=\{x\in \mathbb{R}\mid a<x<b\}\] and \[\ivoo{a}{\infty}=\{x\in \mathbb{R}\mid x>a\}\]

Interval notation	Notation with inequality signs	Piece of the number line
\[\ivoo{a}{b}\]	\[a<x<b\]
\[\ivco{a}{b}\]	\[a\le x<b\]
\[\ivoc{a}{b}\]	\[a< x\le b\]
\[\ivcc{a}{b}\]	\[a\le x\le b\]
\[\ivoo{a}{\infty}\]	\[x> a\]
\[\ivco{a}{\infty}\]	\[x\ge a\]
\[\ivoo{-\infty}{b}\]	\[x< b\]
\[\ivoc{-\infty}{b}\]	\[x\le b\]
\[\ivoo{-\infty}{\infty}\]	(all real numbers)

IIn the interval notation you write the boundary values (the smallest and the largest values, the smallest first) of the interval between two brackets. The shape of the brackets determines whether the boundary value still belongs to the interval or not: A square bracket indicates that the boundary value does belong to the interval, a round bracket indicates that the limit value does not belong to the interval. For intervals that have no boundary on one side, use the infinity symbol and a round bracket. $〈$

The interval notation for all real numbers in the last row of the above table is less commonly used than the $\mathbb{R}$ notation.