4.1 Bare Basics

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

Definition 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.

A similar, yet distinct concept is given in the next definition.

Definition 2 (Partition of a set) A partition of a set 𝒜 is a set 𝒫 of non-empty subsets pi ⊂ 𝒜 , which fulfil 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 definition is of high utility.

Definition 3 (Cartesian Product) The Cartesian product 𝒳 ×  𝒴 of two sets 𝒳 and 𝒴 is defined 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 1 .

Definition 4 (Relation) Considering two sets 𝒜 and ℬ , a relation R is defined as a subset of the Cartesian product 𝒜 × ℬ .

R  ⊂ 𝒜  × ℬ                                  (4.4)

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

Relations can be further qualified with attributes in case they conform to certain requirements. A selection of qualifiers is provided in order to keep subsequent definitions from becoming unnecessarily convoluted.

Definition 5 (Reflexive relation) A binary relation R on a set 𝒳 is called reflexive, if every element is related to itself

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

Definition 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)

Definition 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)

Definition 8 (Equivalence relation) A binary relation which is reflexive, 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 defined in the following.

Definition 9 (Equivalence class) Given an equivalence relation ∼ , equivalence classes [x]  are defined 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 (Definition 8) ensure that a set of equivalence classes (Definition 9) is indeed a partition of the set 𝒳 (Definition 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 sufficient to cover theoretical considerations.