Introduction to sets

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Sets
        Foundations of mathematics
      

Introduction

Sets are a primitive foundational concept in mathematics. Advanced concepts such as counting, probability, relations, functions, groups, and rings rely on a solid understanding of sets.

Sets

A set is an unordered collection of distinct objects. The objects that make up a set are called its elements or members.

Example

The collection of all even natural numbers less than 10 is a set. It consists of the elements $ 2, 4, 6, $ and $ 8 $.
The set of all vowels in the English alphabet contains the members $ a, e, i, o, u $.

Set notation

It is customary to use uppercase letters such as $ A, B, C, \ldots $ to denote sets. Lowercase letters such as $ a, b, c, \ldots $ are used to denote the elements of a set.

Example

Consider a set $ S $ consisting of the elements $ a $, $ b $, and $ c $. This set definition is denoted as $ S = \lbrace a, b, c \rbrace $ to show the membership.

Sets are unordered containers

The specific ordering of elements in a set does not matter. By definition, they are unordered collections. So, the set $ S = \lbrace a, b, c \rbrace $ can also be written as $ S = \lbrace b, c, a \rbrace $.

However, note that it is mathematically more elegant to write them in an order that avoids confusion and enables intuition to the reader. Hence, the preferred form is $ S = \lbrace a, b, c \rbrace $.

Cardinality of a set

The number of elements in a set is known as the cardinality of the set. The cardinality of the set $ S = \lbrace a, b, c \rbrace $ is 3.

In set notation, the cardinality of a set S is usually denoted as $ | S | $. In our example, $ | S | = 3 $.

Set membership

Consider the set $ S = \lbrace a, b, c \rbrace $.

In our example, the element $ a $ belongs in the set $ S $. This relationship is denoted as $ a \in S $. It is read as "$ a $ in $ S $".

The element $ d $ does not belong in the set $ S $. This relationship is denoted as $ d \not\in S $. It is read as "$ d $ not in $ S $".

Set builder notation

Sometimes it is infeasible to describe a set by explicitly listing its elements. In such circumstances, it is common to describe sets based on shared properties of its elements. In other words, it is easier to give a recipe to build the set.

Such notation, known as the set builder notation is written as

$$ S = \lbrace x : \text{a property that defines which } x\text{'s are included} \rbrace $$

Example

The set of all real numbers that are less than 5 can be described as

$$ S = \lbrace x : x < 5 \rbrace $$

Set equality

Two sets are considered equal if and only if they contain the exact same elements. This relationship is denoted as $ A = B $. Conversely, if two sets are not equal, the relationship is denoted as $ A \ne B $.

Sets contain unique elements

By definition, a set contains distinct elements. Having duplicates in a set is meaningless because of the definition of set equality.

Consider the sets $ A = \lbrace 1, 1, 2, 3 \rbrace $ and $ B = \lbrace 1, 2, 3 \rbrace $. Two sets are considered equal if they contain the same elements. Because any element in $ A $ is also in $ B $, it is the case that $ A = B $.

In this example, the duplicates in the set $ A $ were shown to explain the futility of a set with repetitions, since it turns out to be equal to another without them. Multi-sets are a general concept that allow for repetitions. $ A $ would be considered a multi-set in this case.

Subsets

A set $ A $ is known as a subset of the set $ B $, if every element in the set $ A $ is also in the set $ B $. The subset relationship is denoted as $ A \subseteq B $. Note that $ A \subseteq B $ includes the possibility of the sets being equal, or $ A = B $.

If $ A \ne B $ and $ A \subseteq B $, then it means that all elements of $ A $ are present in $ B $, but it has strictly fewer elements than in $ B $. In this case, $ A $ is considered to be a proper subset of the set $ B $. This relationship is denoted as $ A \subset B $.

Examples

Consider the sets $ A = \lbrace 1, 2, 3 \rbrace $, $ B = \lbrace 1, 2, 3 \rbrace $, and $ C = \lbrace 1, 2, 3, 4 \rbrace $.

Every element of the set $ A $ is also contained in the set $ B $. Moreover, $ A = B $. Thus, $ A \subseteq B $.
The set $ C $ contains every element of the set $ A $ and those of set $ B $. Also, $ A \ne C $ and $ B \ne C $. Therefore, $ A \subset C $ and $ B \subset C $.

Subsets demo

Enter a comma-separated list of elements for the two sets $ \sA $ and $ \sB $ and see if they are related by the subset relationship.

Subset relationship is transitive

Consider the sets $ A $, $ B $, and $ C $, such that $ A \subseteq B $ and $ B \subseteq C $. This implies that all elements of the set $ A $ are also in set $ C $. Thus, $ A \subseteq C $.

The empty set

A set devoid of any elements is known as the empty set. It is also alternatively known as the null set or the void set.

It is usually denoted as $ \emptyset = \lbrace \rbrace $.

The power set

The set consisting of all possible subsets of a set $ A $ is known as the power set of $ A $.

For example, if $ A = \lbrace 1,2 \rbrace $, then its power set is $ \lbrace \lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 1, 2 \rbrace \rbrace $.

Note that the null set is part of the power set.

Powerset demo

Enter a comma-separated list of elements for the set $ \sA $ to view its powerset.

Some oft-used sets

The set of all positive integers, also known as natural numbers, is denoted as $ \natural = \lbrace 1, 2, 3, \ldots \rbrace $.

The set of all integers (positive, negative, and zero) is denoted by $ \mathbb{Z} = \lbrace \ldots, -2, -1, 0, 1, 2, 3, \ldots \rbrace $.

The set of all real numbers is denoted by $ \real $. The set of positive real numbers is usually denoted as $ \real^+ $.

The set of all rational numbers are real numbers that can be expressed in the form $ \frac{m}{n} $ where $ m, n \in \mathbb{Z} $ and $ n \neq 0 $, is denoted by $ \mathbb{Q} $.

Real numbers that are not rational, are known as irrational numbers. They are represented as $ \mathbb{I} $.

Finally, the set of complex numbers, those that can be expressed as $ a + bi $ where $ a, b \in \real $ and $ i = \sqrt{-1} $, is denoted as by $ \mathbb{C} $.

Note the relationship among these special sets

$$ \natural \subset \mathbb{Z} \subset \mathbb{Q} \subset \real \subset \mathbb{C} $$

Open interval

The set of all real numbers between $ a $ and $ b $, excluding $ a $ and $ b $ is known as the open interval between $ a $ and $ b $. It is denoted as $ (a,b) $.

$$ (a,b) = \lbrace x \in \real: a < x < b \rbrace $$

Closed interval

The set of all real numbers between $ a $ and $ b $, including $ a $ and $ b $ is known as the closed interval between $ a $ and $ b $. It is denoted as $ [a,b] $.

$$ [a,b] = \lbrace x \in \real: a \le x \le b \rbrace $$

Half-open interval

The set of all real numbers between $ a $ and $ b $, such that one of the boundaries is included in the set is known as half-open or half-closed interval.

Depending on the boundary being included in the set, they are denoted and defined as follows

$$ [a,b) = \lbrace x \in \real: a \le x < b \rbrace $$ $$ (a,b] = \lbrace x \in \real: a < x \le b \rbrace $$

Set union

There are several ways to combine sets to form another set.

The union of two sets $ A $ and $ B $, denoted as $ A \cup B $, results in a set that includes all elements belonging to either $ A $ or $ B $.

$$ A \cup B = \lbrace x : x \in A \text{ or } x \in B \rbrace $$

Note that the order of the operands does not matter for the set union. So, $ A \cup B = B \cup A $.

Set union generalizes to more than two sets to include elements contained in any of those sets. The union of $ n $ sets $A_1, A_2, \ldots, A_n$ is denoted as

\begin{align} \bigcup\limits_{i=1}^n A_i = &~ A_1 \cup A_2 \ldots \cup A_n \\\\ = &~ \lbrace x: x \text{ in any of } A_i, \forall i \in \lbrace 1, 2, \ldots, n \rbrace \rbrace \end{align}

Example

Consider the set $ A = \lbrace 1, 2, 3 \rbrace $ and the set $ B = \lbrace 2, 3, 4 \rbrace $. Then, $ A \cup B = \lbrace 1, 2, 3, 4 \rbrace $.

Set union demo

Enter a comma-separated list of elements for the two sets $ \sA $ and $ \sB $ and understand the composition of their union, $ \sA \cup \sB $.

Set intersection

The intersection of two sets $ A $ and $ B $, denoted as $ A \cap B $, results in a set that includes all elements belonging to both the sets.

$$ A \cap B = \lbrace x : x \in A \text{ and } x \in B \rbrace $$

Note that the order of the operands does not matter for the set intersection. So, $ A \cap B = B \cap A $.

Set intersection generalizes to more than two sets to include elements contained in all of those sets. The intersection of $ n $ sets $A_1, A_2, \ldots, A_n$ is denoted as

\begin{align} \bigcap\limits_{i=1}^n A_i = &~ A_1 \cap A_2 \ldots \cap A_n \\\\ = &~ \lbrace x: x \text{ in all of } A_i, \forall i \in \lbrace 1, 2, \ldots, n \rbrace \rbrace \end{align}

Example

Consider the set $ A = \lbrace 1, 2, 3 \rbrace $ and the set $ B = \lbrace 2, 3, 4 \rbrace $. Then, $ A \cap B = \lbrace 2, 3 \rbrace $.

Set intersection demo

Enter a comma-separated list of elements for the two sets $ \sA $ and $ \sB $ and understand the composition of their intersection, $ \sA \cap \sB $.

Set difference

The set difference of two sets $ A $ and $ B $, denoted as $ A \setminus B $ or as $ A - B $, results in a set that includes all elements of the set $ A $ that do not belong to the set $ B $. $$ A \setminus B = \lbrace x : x \in A \text{ and } x \not\in B \rbrace $$

Note that the order of the operands matters for the set difference. So, $ A - B \ne B - A $.

Example

Consider the set $ A = \lbrace 1, 2, 3 \rbrace $ and the set $ B = \lbrace 2, 3, 4 \rbrace $. Then, $ A \setminus B = \lbrace 1 \rbrace $ and $ B \setminus A = \lbrace 4 \rbrace $.

Set difference demo

Enter a comma-separated list of elements for the two sets $ \sA $ and $ \sB $ and understand the composition of their difference, $ \sA \setdiff \sB $.

Symmetric difference of sets

The symmetric difference of two sets $ A $ and $ B $, denoted as $ A \setsymmdiff B $ results in a set that contains elements that are either in A or in B, but not both. Intuitively, it is the union of the relative complement of $ A $ and $ B $.

$$ A \setsymmdiff B = (A \setdiff B) \cup (B \setdiff A) $$

Example

Consider the set $ A = \lbrace 1, 2, 3 \rbrace $ and the set $ B = \lbrace 2, 3, 4 \rbrace $. Their symmetric difference $ A \setsymmdiff B = \lbrace 1, 4 \rbrace $.

Symmetric difference of sets demo

Enter a comma-separated list of elements for the two sets $ \sA $ and $ \sB $ and understand the composition of their symmetric difference, $ \sA \setsymmdiff \sB $.

Venn diagrams

Venn diagrams are a convenient way to visualize sets and their relationships. In a Venn diagram, sets are usually denoted as ellipses containing their elements.

For example, the following chart shows the sets $ \sA, \sB, $ and $ \sC $.

$Venn Diagram$

In the above Venn diagram, the set operations that we studied before are evident.

Union: $ \sA \cup \sB = \set{2,0,6,8,5,1,7} $
Intersection: $ \sA \cap \sB = \set{1,6} $
Difference: $ \sA \setdiff \sB = \set{2,0,5} $
Symmetric difference: $ \sA \setsymmdiff \sB = \set{2,0,5,8,7} $
Subsets: $ \sA \not\subset \sB $

Similar relationships can be drawn involving $ \sC $

Disjoint sets

Sets with no common elements among them are known to be disjoint.

With no common elements, the intersection of disjoint sets is empty. In other words, $ A \cap B = \lbrace \rbrace $ if $ A $ and $ B $ are disjoint.

Of course, if the sets are disjoint then the set difference $ A - B = A $.

Universal set

When dealing with several sets, it is sometimes necessary to talk about the all-encompassing set consisting of union of all the sets under consideration. This special set is known as the universal set.

Complement of a set

If $ U $ denotes the universal set under consideration, then all the elements of $ U $ that are not in $ A $ is known as the complement of the set $ A $. It is denoted as $ \complement{A} $.

Thus, the set difference $ U - A = \complement{A} $.

Owing to this definition, the set difference $ A - B $ is sometimes also known as the relative complement of the set $ B $ in $ A $.

Indexed collection of sets

Sometimes, when dealing with unions and intersections over numerous sets, it is convenient to index the set notation using an index set, say $ C $. Each element $ c \in C $ is an index into a set $ S_c $ that we wish to include in our operations. Such a collection of sets is known as an indexed collection of sets. Thus, the union and intersection over such an indexed collection is defined as

$$ \bigcup_{c \in C} = \lbrace x : x \in S_c \text{ for some } c \in C \rbrace $$ $$ \bigcap_{c \in C} = \lbrace x : x \in S_c \text{ for all } c \in C \rbrace $$

Pairwise disjoint collection

A collection $ C $ of subsets of a set $ A $ is said to be pairwise disjoint if every two distinct subsets that belong to $ C $ are disjoint.

Example

Consider a set $ A = \lbrace w, x, y, z \rbrace $ and the collections $ C_1 = \lbrace \lbrace x,y \rbrace, \lbrace z \rbrace \rbrace $ and $ C_2 = \lbrace \lbrace x, y \rbrace, \lbrace y,z \rbrace \rbrace $.

Of these, the collection $ C_1 $ is pairwise disjoint, but the collection $ C_2 $ is not, because the element $ y $ repeats in both subsets of $ C_2 $.

Partition of a set

A pairwise disjoint collection of the subsets of a set $ A $ such that each element of $ A $ is contained in some subset of the collection is known as a partition of the set $ A $.

In other words, a partition of a set $ A $ is a collection $ S $ of nonempty subsets of $ A $ such that each element of $ A $ belongs to exactly one subset in $ S $.

Example

Consider a set $ A = \lbrace w, x, y, z \rbrace $ and the collections $ C_1 = \lbrace \lbrace x,y \rbrace, \lbrace z,w \rbrace \rbrace $ and $ C_2 = \lbrace \lbrace x, y \rbrace, \lbrace z \rbrace \rbrace $.

Of these, the collection $ C_1 $ is a partition, but the collection $ C_2 $ is not a partition because the element $ w $ does not appear in any of the subsets.

Sets: Identity laws

For a set $ A $, the empty set $\emptyset$, and the universal set $ U $, the following laws are known as the identity laws because the set $ A $ retains its identity after these operations with the universal set and the empty set.

$ A \cup \emptyset = A $
$ A \cap U = A $

Sets: Domination laws

For a set $ A $, the empty set $\emptyset$, and the universal set $ U $, the following laws are known as the domination laws, because the set $ A $ gets dominated after these operations with the universal set and the empty set.

$ A \cup U = U $
$ A \cap \emptyset = \emptyset $

Sets: Idempotent laws

For a set $ A $, the following laws are known as the idempotent laws because these operations when applied on the set itself does not affect the set.

$ A \cup A = A $
$ A \cap A = A $

Sets: Complementation law

The complement of a complement is the original set is known as the complementation law.

$$ \complement{(\complement{A})} = A $$

Sets: Commutative laws

The following laws are known as the commutative laws because the union and intersection operations do not depend on the order of the operands.

For sets $ A $ and $ B $

$ A \cup B = B \cup A $
$ A \cap B = B \cap A $

Sets: Associative laws

The following laws are known as the associative laws because repeated application of the union or the intersection operation does not depend on the order of operands.

For sets $A, B, C $

$ A \cup (B \cup C) = (A \cup B) \cup C $
$ A \cap (B \cap C) = (A \cap B) \cap C $

Sets: Distributive laws

The following laws are known as distributive laws because the intersection of a union is a union of the intersections and vice versa.

For sets $A, B, C $

$ A \cup (B \cap C) = (A \cap B) \cup (A \cap C) $
$ A \cap (B \cup C) = (A \cup B) \cap (A \cup C) $

Sets: De Morgan's laws

The De Morgan's laws for sets state that the complement of a union is the intersection of complements of the sets involved and vice versa.

For sets $ A $ and $ B $

$ \complement{(A \cup B)} = \complement{A} \cap \complement{B} $
$ \complement{(A \cap B)} = \complement{A} \cup \complement{B} $

Sequences

The order of elements in a set does not matter. Thus, $ \lbrace x, y \rbrace = \lbrace y, x \rbrace $.

In mathematics, an ordered collection of objects is known as a sequence. Unlike sets, repetitions of the same object are allowed in a sequence. Sequences are encapsulated by parentheses as $ (a_1, a_2, \ldots, a_n) $, to distinguish them from sets.

Example

A sequence of squares of all natural numbers $ A = (1, 4, 9, \ldots, \infty) $, or succinctly as $ A = (n^2)_{n \in \natural} $

$n$-tuples

A sequence of finite length $ n $ is known as an $n$-tuple.

The $k$-th element of an $n$-tuple is known as its $k$-th coordinate.

Ordered pair

An $n$-tuple with 2 elements is known as a $2$-tuple or ordered pair. It is denoted as $ (x,y) $.

In this case, $ x $ is the known as the first coordinate and $ y $ is known as the second coordinate.

Cartesian product of sets

The Cartesian product of two sets $ A $ and $ B $, denoted as $ A \times B $, is the set of all ordered pairs whose first coordinate belongs to $ A $ and whose second coordinate belongs to $ B $.

$$ A \times B = \lbrace (x,y) : x \in A \text{ and } y \in B \rbrace $$

A Cartesian product of $ n $ sets $A_1, A_2, \ldots, A_n$ is denoted as $ A_1 \times A_2 \times \ldots \times A_n $ and defined as

$$ A_1 \times A_2 \times \ldots \times A_n = \lbrace (a_1,a_2,\ldots,a_n) : a_i \in A_i \forall i \in \lbrace 1, 2, \ldots, n \rbrace \rbrace $$

Example

If $ A = \lbrace x, y \rbrace $ and $ B = \lbrace 1, 2, 3 \rbrace $, then their Cartesian product

$$ A \times B = \lbrace (x,1), (x,2), (x,3), (y,1), (y,2), (y,3) \rbrace $$

Cartesian product of sets demo

Enter a comma-separated list of elements for the two sets $ \sA $ and $ \sB $ and understand the composition of their Cartesian product, $ \sA \times \sB $.

Numerically equivalent sets

Two sets with the same number of elements are said to have the same cardinality or to be numerically equivalent sets.

Example

Consider the sets $ A = \lbrace 1, 2, 3 \rbrace $, $ B = \lbrace 7, 8, 9 \rbrace $, and $ C = \lbrace 4, 5 \rbrace $.

Note that none of these sets are equal to each other. $ A \ne B \ne C $.

However, the sets $ A $ and $ B $ are numerically equivalent, because $ |A| = |B| = 3 $.

The set $ C $ is not numerically equivalent to $ A $ or $ B $, because $ |C| = 2 $.

Denumerable sets

A set $ A $ is called denumerable if $ |A| = |\natural| $, that is, if the set $ A $ has the same cardinality as the set of natural numbers. Of course, if a set is denumerable, then it is also infinite. All denumerable sets are numerically equivalent.

Examples

The following are all denumerable sets

The set of all integers
The set of all even integers
The Cartesian product of two denumerable sets, for example $ \natural \times \natural $
$ A = \lbrace x^2 : x \in \natural \rbrace $

The following are not denumerable sets

The set of all real numbers
A set with finite number of elements such as $ A = \lbrace 1, 2 \rbrace $.

Countable and Countably infinite sets

A set is said to be countable if it is denumerable or finite. Countable sets that are also denumerable are known as countably infinite.

Examples

The following are all countable sets, and all but the finite set are also countably infinite.

The set of all integers
The set of all even integers
The Cartesian product of two denumerable sets, for example $ \natural \times \natural $
$ A = \lbrace x^2 : x \in \natural \rbrace $
A set with finite number of elements such as $ A = \lbrace 1, 2 \rbrace $.

The following sets are not countable.

The set of all real numbers
The set of all rational numbers
The real interval $ (0,1) $

Uncountable sets

A set that is not countable is uncountable. An example is the real interval $ (0,1) $.

An uncountable set is infinite. But, uncountable sets are not numerically equivalent to denumerable sets.

However, uncountable sets such as any open interval $ (a,b) $ are numerically equivalent to $ \real $, the set of reals.

With a sound understanding of sets, we continue our journey to mathematical expertise with an introduction to Relations. Supplemented with numerous interactive demos, the article is self-contained and builds intuition about everything you need to know about relations to understand more advanced concepts like functions.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Subscribe for article updates

Stay up to date with new material for free.

Sets

Foundations of mathematics

Introduction

Sets

Example

Set notation

Example

Sets are unordered containers

Cardinality of a set

Set membership

Set builder notation

Example

Set equality

Sets contain unique elements

Subsets

Examples

Subsets demo

Subset relationship is transitive

The empty set

The power set

Powerset demo

Some oft-used sets

Open interval

Closed interval

Half-open interval

Set union

Example

Set union demo

Set intersection

Example

Set intersection demo

Set difference

Example

Set difference demo

Symmetric difference of sets

Example

Symmetric difference of sets demo

Venn diagrams

Disjoint sets

Universal set

Complement of a set

Indexed collection of sets

Pairwise disjoint collection

Example

Partition of a set

Example

Sets: Identity laws

Sets: Domination laws

Sets: Idempotent laws

Sets: Complementation law

Sets: Commutative laws

Sets: Associative laws

Sets: Distributive laws

Sets: De Morgan's laws

Sequences

Example

\(n\)-tuples

Ordered pair

Cartesian product of sets

Example

Cartesian product of sets demo

Numerically equivalent sets

Example

Denumerable sets

Examples

Countable and Countably infinite sets

Examples

Uncountable sets

Next article

Please support us

Subscribe for article updates