Introduction to Sets

Defining sets

Set theory is the foundation of modern mathematics. Every mathematical notion is built on some set. What is a set? This is a very deep question beyond the scope of this lecture. Instead, we give the following very rough, informal definition.

Definition (very informal)

A set is a collection of distinct objects. Objects of a set are called elements of the set.
To denote a set, we can enumerate its elements, enclosed by curly brackets. For example, $$\{1,2,3\}$$ denotes a set consisting of three elements that are 1, 2, and 3. We may give a set a name as in $$S=\{1,2,3\},$$ and say, for example, "the set $S$ contains the elements 1, 2, and 3. Suppose $S$ is any set. To denote that an object $x$ is an element of $S$, we write $$x\in S$$ and say "$x$ is in $S$" and so on. To denote that $x$ is not in $S$, we write $$x\notin S.$$
It is important that the elements of a set are distinct. For example,
$$\{a,a,b,c\}$$
is not a set because there are two $a$'s that are not distinguishable from each other. A collection with redundant elements such as this is sometimes called a multiset (they play a central role in database theory). If we force ourselves to interpret the above collection as a set, we interpret it as $$\{a,b,c\}$$ by removing the redundant elements. 
In a set, we don't care about the order of elements. For example,
$$\{1,2,3\}$$
and
$$\{2,3,1\}$$
and
$$\{3,1,2\},$$
and so on, are all the same set.

Definition (Cardinality of a set)

If the number of elements of the set $S$ is finite, say $n$, then we say the set is of cardinality $n$, and write $|S|=n.$ If the set $S$ does not have a finite number of elements, then we say it is a set of infinite cardinality.

Example. For the set $S=\{a,b,c,d\}$, its cardinality is $|S|=4$. $|\mathrm{\varnothing }|=0.$ □

Subsets and set equivalence

A set may be contained completely in another set. This is the notion of subsets. But what does it mean, exactly? Here's the definition.

Definition

Let $A$ and $B$ be sets. If $x\in A$ implies $x\in B$, then we say that $A$ is a subset of $B$, and write $$A\subset B.$$ In this case, the set $B$ is said to be a superset of $A$.

Example:

$$\{1,2\}\subset \{1,2,3\},\{2\}\subset \{1,2,3\}.$$

"$\subset$" may be regarded as a relation between sets. 

Lemma 

The subset relation $\subset$ is transitive. That is, if $A\subset B$ and $B\subset C$, then $A\subset C$.

Proof

Since $A\subset B$, $x\in A$ implies $x\in B$, which, in turn, implies $x\in C$ because $B\subset C$. Hence, $x\in A$ implies $x\in C$. ■

Here is what we mean by "two sets are equal":

Definition

If $A\subset B$ and $B\subset A$, then we say that the sets $A$ and $B$ are equal and write $A=B$.

That is, two sets are equal if each set is a subset of the other set. You should try to validate that the two sets, say, $\{1,2,3\}$ and $\{2,1,3\}$ are indeed equal according to the above definition.

Remark: Note that $A\subset B$ may mean the sets $A$ and $B$ are actually equal sets (that is, if $B\subset A$ also holds). For this reason, some people prefer $A\subseteq B$ to $A\subset B$ to denote the subset relation. When we want to express that $A$ is a subset of, but not equal to, $B$, we specifically write 

$$A⊊B.$$

Definition

If $A\subset B$ and $A\ne B$, we say that $A$ is a proper subset of $B$ and write $A⊊B$.

This definition means that $A$ is a proper subset of $B$ if $A\subset B$ and there exists an element $x\in B$ such that $x\notin A$.

Definition

The set with no elements is called the empty set and is denoted $\mathrm{\varnothing }$. That is, $$\mathrm{\varnothing }=\{\}.$$ The empty set is a subset of any set.

Note that $\mathrm{\varnothing }$ and $\{\mathrm{\varnothing }\}$ are two different sets. The former is the empty set, and the latter is a non-empty set, the only element of which is the empty set.

An alternative way to specify a set

When a set contains a finite number of elements, we can specify it by enumerating all the elements enclosed in curly brackets. For example, $$S=\{1,2,3\}$$ is a set of three integers, 1, 2, and 3. When a set contains infinitely many elements, how can we specify it? Let's consider the set $E$ of even natural numbers. In this case, we can exploit the regularity so we may write $$E=\{2,4,6,8,\cdots \}$$ to indicate that the "$\cdots$" are the rest of the elements with the same regularity (i.e., even natural numbers). But, what if there are no simple regularities? In such cases, we can use the following notation: $$S=\{x\in U|P(x)\}$$ where $U$ is some set that is already defined and $P(x)$ is a logical proposition that depends on the value of $x$ (such propositions are called predicates). Sometimes, we may omit the superset $U$. This expression reads:

$S$ consists of elements $x$ of $U$ such that the predicate $P(x)$ is true.

That is, we pick each element, say $x$, of $U$, and if $P(x)$ is true, then it is included in $S$; otherwise, it is not included in $S$.

 For example, we may specify the set of even natural numbers is the following way: $$E=\{x\in \mathbb{N}|\mathrm{\exists }k\in \mathbb{N},x=2k\}$$ where $\mathbb{N}$ is the set of natural numbers. This definition says: 

$E$ is a subset of $\mathbb{N}$, for each element $x$ of which, there exists a natural number $k$ such that $x=2k$ holds. The predicate here could be written as $P(x)=[\mathrm{\exists }k\in \mathbb{N},x=2k]$ For example, $P(1)$ is false because we cannot express $1=2k$ for any natural number $k$; thus, 1 is not an element of $E$. $P(56)$ is true because $56=2\times 28$ and $28\in \mathbb{N}$; thus, $56\in E$. And so on...

See also: If you are interested in a more rigorous treatment of set theory, refer to, for example, Zermelo-Fraenkel set theory (Wikipedia).