Sets

Definition FACT

A set is a collection of well-defined objects called its elements. For example, we write

$A=\{2,4,6\}$A={2,4,6}

and $4\in A$4∈A to say that 4 belongs to $A$A. Conversely, $5\notin A$5∈/A.

Order and repetitions do not change a set: $\{2,4,6\}${2,4,6}, $\{6,4,2\}${6,4,2} and $\{2,2,4,6\}${2,2,4,6} denote the same set. Only one question matters: which elements belong to the collection?

Describing a set FACT

Its elements can be listed by extension:

$B=\{a,e,i,o,u\}$B={a,e,i,o,u}

or defined by a property:

$C=\{n\in\mathbb{N}\mid n<5\}=\{0,1,2,3,4\}$C={n∈N∣n<5}={0,1,2,3,4}

Here we use the convention $0\in\mathbb{N}$0∈N. The vertical bar is read “such that.” The property must decide unambiguously whether an object belongs to the set.

Empty set, equality and cardinality FACT

The empty set, written $\varnothing$∅, contains no element. It must not be confused with $\{\varnothing\}${∅}, which contains one element: the empty set itself.

Two sets are equal if they have exactly the same elements. For a finite set $A$A, its cardinality $|A|$ is its number of elements. Thus, if $A=\{2,4,6\}$A={2,4,6}, then $|A|=3$.

Inclusion and subsets FACT

We write $A\subseteq B$A⊆B when every element of $A$A also belongs to $B$B. For example,

$\{2,4\}\subseteq\{1,2,3,4\}${2,4}⊆{1,2,3,4}

Membership and inclusion are not the same relation: $2\in A$2∈A compares an object with a set; $A\subseteq B$A⊆B compares two sets.

Every set is included in itself, and the empty set is included in every set.

Three fundamental operations FACT

Let $A=\{1,2,3\}$A={1,2,3} and $B=\{3,4\}$B={3,4}.

The word “or” in a union is inclusive: an element present in both sets does belong to the union, but appears there only once.

If a universal set $U$U is fixed, the complement of $A$A in $U$U is $U\setminus A$U∖A. Without an explicitly chosen universe, “the complement of $A$A” is incomplete.

Diagrams help, but do not define FACT

A Venn diagram represents sets as regions. Overlap visualizes intersection, and the combined regions visualize union. It is a reasoning aid, not the definition: a proof must return to membership conditions.

To show $A\cap B\subseteq A$A∩B⊆A, take an arbitrary element $x\in A\cap B$x∈A∩B. By definition of intersection, $x\in A$x∈A and $x\in B$x∈B; therefore $x\in A$x∈A. The inclusion is proved.

Why the abstraction is useful FACT

Sets provide a common vocabulary for mathematics and computer science. A domain of values, query results, graph vertices or cases accepted by a rule can all be treated as sets. Relations then become sets of ordered pairs, and functions rely on a domain and a codomain.

This idea is therefore a direct prerequisite for studying relations, functions, databases, probability and graphs.

Summary

A set is determined by its elements: membership connects an object to a set; inclusion compares two sets; union, intersection and difference build new sets.

Educational references FACT

• ACM/IEEE-CS/AAAI — Computer Science Curricula 2023, Mathematical and Statistical Foundations
• National University of Singapore — CS1231S, Discrete Structures
• Australian National University — MATH1005, Discrete Mathematical Models