4.4.2.2 - Sets, countability and Cartesian products

Sets and comprehension notation

A set is an unordered collection of distinct elements: each value occurs at most once. Thus $\{1,2,3\}=\{3,1,2\}$, and repeating 2 in a written list does not create a second set element. Braces specify the collection; commas separate its elements.

The empty set is different from $\{0\}$, which contains one element, and from $\{\varnothing\}$, whose one element is itself the empty set.

A set can be specified by listing its elements or by set comprehension, which states the rule an element must satisfy. For this course $\mathbb{N}=\{0,1,2,3,\ldots\}$. Then

Read the vertical bar as “such that”, $\in$ as “is a member of”, and $\land$ as AND. The bounded condition is essential: $\{x\mid x\in\mathbb{N}\land x\ge1\}$ is the infinite set of positive natural numbers, not just the first five. An ellipsis must have a clear pattern.

Comprehension can transform elements as well as select them. $\{2x\mid x\in\{1,2,3\}\}=\{2,4,6\}$. Evaluate the expression for each allowed x, then keep distinct results. This is mathematical notation shared across language routes, rather than a task in any particular programming language.

Compact sets of strings

A set's elements may be strings rather than numbers. In string notation, $0^n$ means n copies of the symbol 0, not the arithmetic value zero raised to a power. Juxtaposition concatenates strings, so $0^n1^n$ has a block of n zeros followed by a block of n ones.

For example,

Every member has an equal positive number of zeros and ones in that order. The string 0101 has equal totals, but it is not a member because its zeros do not all precede its ones. The string 00011 is not a member because its block lengths differ. The empty string, denoted $\varepsilon$, is excluded by $n\ge1$. Changing the condition to $n\ge0$ would include it.

To test membership, check both the permitted arrangement and the condition on n. To generate an example, select an allowed n and substitute it consistently into both blocks. For n = 3, the member is 000111; selecting 3 for one block and 2 for the other violates the shared n.

Finite, infinite and countable sets

A finite set has a final element when its distinct elements are counted off: its size is a non-negative integer. Its cardinality, written $|A|$, is the number of distinct elements. For $A=\{2,5,9\}$, $|A|=3$; $|\varnothing|=0$.

An infinite set has no finite total number of elements. Both the natural numbers $\mathbb{N}$ and real numbers $\mathbb{R}$ are infinite, but they are not the same kind of infinity.

The even natural numbers $\{0,2,4,6,\ldots\}$ are countably infinite: natural index n identifies the even number $2n$, with no repeats or omissions. Having gaps on the number line does not prevent counting. The integers are also countably infinite: one possible listing is 0, 1, −1, 2, −2, 3, −3, and so on. It does not need to be in numerical order.

A countable set has the same cardinality as some subset of $\mathbb{N}$. This includes finite sets as well as countably infinite sets. The empty set is countable. The real numbers are uncountable: no natural-number indexing lists every real number exactly once. It is not enough to say there are “too many to finish counting”, because the natural numbers also never finish.

The strings in $\{0^n1^n\mid n\ge1\}$ are countably infinite: list the string for n = 1, then n = 2, then n = 3, and so on. Every member is reached. This gives a constructive reason, rather than just the observation that the set is infinite.

Subsets and ordered Cartesian products

A is a subset of B, written $A\subseteq B$, when every element of A is also an element of B. Equality is allowed. A is a proper subset, written $A\subset B$, when A is a subset of B and B contains at least one element absent from A.

For $A=\{1,2\}$ and $B=\{1,2,3\}$, both $A\subseteq B$ and $A\subset B$ are true. $B\subseteq B$ is true, while $B\subset B$ is false. The empty set is a subset of every set; it is a proper subset of every non-empty set.

Membership and subset relations concern different things. $2\in A$ says that the number 2 is an element. $\{2\}\subseteq A$ says that every element of the set containing 2 is in A. Do not interchange these symbols.

The Cartesian product $X\times Y$ is the set of all ordered pairs $(x,y)$ with $x\in X$ and $y\in Y$. For $X=\{A,B\}$ and $Y=\{1,2,3\}$:

The outer set is unordered, but the positions inside each pair matter. In $Y\times X$, the number comes first, so $(1,A)$ is a member. $(A,1)$ is not. In general $X\times Y\ne Y\times X$.

For finite sets, each of the $|X|$ first choices pairs with each of the $|Y|$ second choices, so $|X\times Y|=|X||Y|$. If either set is empty, the product is empty: there is no way to choose both elements. A Cartesian product can describe possibilities, such as every permitted combination of size and colour; it does not assert that every combination is actually in stock.

Membership, union, intersection and difference

Set operations describe which elements meet a condition. Suppose $A=\{1,2,4\}$ and $B=\{2,3,4\}$. Membership is written $x\in A$; non-membership is $x\notin A$. Thus $1\in A$ and $3\notin A$.

Union does not duplicate the shared values 2 and 4. Intersection retains only shared values. Difference is directional: $B\setminus A=\{3\}$, which differs from $A\setminus B$. It removes elements, rather than subtracting their numerical values.

For example, if A contains students taking computing and B contains students taking physics, union means taking at least one of those subjects; intersection means taking both; $A\setminus B$ means computing but not physics. The element type can be a student identifier rather than a number.

To compute a result reliably, test each candidate against the operation's membership condition. $A\cap\varnothing=\varnothing$, whereas $A\cup\varnothing=A$ and $A\setminus\varnothing=A$. These follow from the conditions, without requiring a new rule for each example.