Bare Basics

Silently assuming basic familiarity with the entity known as a set [74], several distinctions connected to sets should not go undeﬁned, especially as later concepts build on these very basic deﬁnitions and the lack of a clear distinction can be nothing but detrimental. Among others, Deﬁnition 36 is a higher level representative of the concept provided in the following deﬁnition.

Deﬁnition 1 (Open cover) An open cover $𝒞$ of a set $𝒳$ is a family of open sets $𝒰i$ , whose union results in $𝒳$ :

⋃ 𝒳 = 𝒰i (4.1) i∈A

with $A$ being an arbitrary index set.

Deﬁnition 2 (Partition of a set) A partition of a set $𝒜$ is a set $𝒫$ of non-empty subsets $pi ⊂ 𝒜$ , which fulﬁl the following conditions

⋃ 𝒫 = 𝒜 (4.2a) pi ∩ pj = ∅,∀pi,pj ∈ 𝒫, pi ⁄= pj (4.2b)

Thus a partition implies that every element of the set $𝒜$ is assigned to exactly one element of the partition $𝒫$ .

To extend the simple notion of sets and their partitions, the following deﬁnition is of high utility.

Deﬁnition 3 (Cartesian Product) The Cartesian product $𝒳 × 𝒴$ of two sets $𝒳$ and $𝒴$ is deﬁned as the set of all ordered tuples of the form

𝒳 × 𝒴 = {(x,y)|x ∈ 𝒳 ∧ y ∈ 𝒴 } (4.3)

It is through this simple mechanism represented by the Cartesian product that extensions to higher dimensions are available not only in a theoretical, but especially in an applied setting.

Sets alone present elements and very basic predicates such as testing, if a given element is contained within a set. It is, however, important to provide a more involved mechanism which is readily found in relations ¹ .

Deﬁnition 4 (Relation) Considering two sets $𝒜$ and $ℬ$ , a relation $R$ is deﬁned as a subset of the Cartesian product $𝒜 × ℬ$ .

R ⊂ 𝒜 × ℬ (4.4)

A relation is not only an important step for further theoretical reﬁnement, but has also been a driving abstraction for digital data storage systems such as databases.

Relations can be further qualiﬁed with attributes in case they conform to certain requirements. A selection of qualiﬁers is provided in order to keep subsequent deﬁnitions from becoming unnecessarily convoluted.

Deﬁnition 5 (Reﬂexive relation) A binary relation $R$ on a set $𝒳$ is called reﬂexive, if every element is related to itself

∀x ∈ 𝒳 : (x,x) ∈ R (4.5)

Deﬁnition 6 (Symmetric relation) A binary relation $R$ on a set $𝒳$ is called symmetric, if the following is always true:

∀x,y ∈ 𝒳 : (x,y) ∈ R ⇒ (y,x ) ∈ R (4.6)

Deﬁnition 7 (Transitive relation) A binary relation $R$ on a set $𝒳$ is called transitive, if it follows that:

x, y,z ∈ 𝒳 : (x, y) ∈ R ∧ (y,z) ∈ R ⇒ (y,z) ∈ R (4.7)

Deﬁnition 8 (Equivalence relation) A binary relation which is reﬂexive, transitive and symmetric is called an equivalence relation.

The application of an equivalence relation to the elements of a set leads to the concept of equivalence classes, as deﬁned in the following.

Deﬁnition 9 (Equivalence class) Given an equivalence relation $∼$ , equivalence classes $[x]$ are deﬁned as the sets

[x] = {y ∈ 𝒳 |y ∼ x } (4.8)

Equivalence classes are of special interest as they provide a means to partition a set $𝒳$ . The demands placed on equivalence relations (Deﬁnition 8) ensure that a set of equivalence classes (Deﬁnition 9) is indeed a partition of the set $𝒳$ (Deﬁnition 2):

In other words, two elements are either in the same equivalence class, or in disjoint classes. An element $x∈[x]$ is called a representative of the equivalence class $[x]$ .

The memory within digital computers is conceptually a set, because every cell of memory can be distinctly addressed even without having to resort to querying the contents of the cells, thus it is really the structure of the cells that forms a set. The presented relations are only a small fraction of the relations available and indeed required to represent modern memory management, but are at least suﬃcient to cover theoretical considerations.

4.1 Bare Basics