Sets

Definition

  • A set is a collection of (mathematical) elements.
  • Sets are typically denoted by uppercase italic letters, such as X \mathcal{X} and Y \mathcal{Y} .
  • Sets are a cornerstone of all mathematics, for example to define functions and probability distributions.

Discrete and continuous sets


A discrete set is a set of countable elements. We denote the discrete elements by {..}\{..\}.

Example

– X={0,1,2,..,n} \mathcal{X} = \{0, 1, 2, .., n\} (non-negative integers up to n n )

– X={up,down,left,right} \mathcal{X} = \{up,down,left,right\} (arbitrary elements)

– X={0,1}d \mathcal{X} = \{0,1\}^d (d-dimensional binary space)

A continuous set is a set of connected (uncountable) numbers.

Example

– X=[2,11] \mathcal{X} =[2, 11] (all real numbers between 2 and 11)

– X=R \mathcal{X} = \mathbb{R} (the real line)

– X=[0,1]d \mathcal{X} = [0,1]^d (d-dimensional hypercube)

Conditioning a set

We can condition within a set by using : or |.

Example

The probability k k-simplex, which we use to define a discrete probability distribution over k k categories, is given by:

X={x∈[0,1]k∣∑i=1kxi=1} \mathcal{X}=\{ \mathbf{x} \in [0,1]^k | \sum_{i=1}^k \mathbf{x}_i=1 \}

This means that x \mathbf{x} in this space is a vector of length k k , consisting of entries between 0 and 1, with the restriction that the vector sums to 1.

Cardinality and dimensionality

We need to distinguish the cardinality and dimensionality of a set:

  • The cardinality (size) counts the number of elements in a set, for which we write ∣X∣ |\mathcal{X}| .
  • The dimensionality counts the number of dimensions in the set/space X \mathcal{X} , for which we write Dim(X) \text{Dim}(\mathcal{X}) .

Example

– The discrete set X={0,1,2} \mathcal{X}=\{0,1,2\} has cardinality ∣X∣=3 |\mathcal{X}|=3 and dimensionality Dim(X)=1 \text{Dim}(\mathcal{X})=1 .

– The discrete space X={0,1}4 \mathcal{X}=\{0,1\}^4 has cardinality ∣X∣=24=16 |\mathcal{X}|=2^4=16 and dimensionality Dim(X)=4 \text{Dim}(\mathcal{X})=4 .

Cartesian product

We can combine two sets/spaces by taking the Cartesian product, denoted by × \times , which consist of all the possible combinations of elements in the first and second set:

X×Y={(x,y)∣x∈X,y∈Y} \mathcal{X} \times \mathcal{Y} = \{ (x,y) | x \in \mathcal{X}, y \in \mathcal{Y} \}

We can also combine discrete and continuous spaces through Cartesian products.

Example

– Assume X={20,30} \mathcal{X} = \{20,30\} and Y={0,1} \mathcal{Y} = \{0,1\} . Then the Cartesian product X×Y={(20,0),(20,1),(30,0),(30,1)} \mathcal{X} \times \mathcal{Y} = \{(20,0),(20,1),(30,0),(30,1) \} .

– Assume X=R \mathcal{X} = \mathbb{R} and Y=R2 \mathcal{Y} = \mathbb{R}^2. Then the Cartesian product X×Y=R3 \mathcal{X} \times \mathcal{Y} = \mathbb{R}^3 .