Abstractions with Set Theory

Like in programming, building abstractions in mathematics is of equal importance.

We will start with the most basic object (the unordered collection) and work our way up to defining functions.

Set

A set is an unordered collection of objects. This might sound too abstract but that’s what it is. The objects can be anything. It is usually denoted by comma separating the list of objects and enclosing them using curly braces.

For example, one set of fruits is \{ apple, banana \}.

Since it is an unordered collection we have that \{ apple, banana \} = \{ banana, apple \}.

For membership, we denote apple \in \{ apple, banana \} to say that apple is in that collection.

Tuples

An n-tuple is an ordered collection of n objects. As with sets, the objects can be anything. It is usually denoted by comma separating the list of objects and enclosing them using parenthesis.

We can represent it using unordered collections as follows: Consider the tuple a = (a_1, a_2, ..., a_n). We can use the set A = \{ \{1, \{a_1\}\}, \{2, \{a_2\}\}, ..., \{n, \{a_n\}\} \}. Note that here I’m using natural numbers and I assume them to be unique atoms. Otherwise, if we represented naturals in terms of set theory, there would be issues with this definition. For that, we’d have to use Kuratowski’s definition, but we can skip that for simplicity’s sake.

Now to extract the k-th element of the tuple, we can pick x s.t. \{k, \{x\}\} \in A.

So now we have that (a, b) = (c, d) \leftrightarrow a = b \land c = d, that is two tuples are equal if their first and second elements respectively are equal. This is what makes tuples ordered.

One example of a tuple is (1 pm, 2 pm, 3 pm) which represents 3 hours of a day sequentially.

Relations

An n-ary relation is just a set of n-tuples with different values. We are mostly interested in binary relations.

One example of such a relation is the “is bigger than”. So we have the following set: \{ (cat, mouse), (mouse, cheese), (cat, cheese) \}.

Functions

Now we can define functions in terms of relations.

To do that we first have to discuss subset. A is a subset of B if all elements of A are found in B (but not necessarily vice-versa). We denote it as such: A \subseteq B. So for example: \{ 1, 2 \} \subseteq \{ 1, 2, 3 \} and \{ 1, 2, 3 \} \subseteq \{ 1, 2, 3 \}. But this doesn’t hold: \{ 1, 2, 3 \} \subseteq \{ 1, 2 \}.

So with this, a function is a mapping from a set A to a set B, or in other words it is a subset of all combinations of ordered pairs whose first element is an element of A and second element is an element of B.

For example, if A = \{ a, b \} \land B = \{ 1, 2, 3 \} then the combinations are: F = \{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) \}. A function f from A to B is denoted f : A \rightarrow B and is a subset of F: f \subseteq F.

This combination of pairs is called a Cartessian product, and is defined as the set: \{ (a, b) \mid a \in A \land b \in B \}.

We have one more constraint to add to a function, namely that it cannot produce 2 or more different values for a single input. So using either of f(a) = 1 or f(a) = 2 or f(a) = 3 is okay, but not all three of them. That means that we only have to use one of \{ (a, 1), (a, 2), (a, 3) \} from our example set above. The same reasoning goes for b. So f = \{ (a, 1), (b, 2) \} with f(a) = 1 \land f(b) = 2 is one valid example.

Conclusion

Matrices (tuples of tuples), lists (sets or tuples), graphs (set of sets), digraphs (set of tuples), trees (graphs) can also be derived similarly.

This is what makes the set a powerful and interesting idea.

Correctness on iterative and recursive processes

Iterative processes are proven using loop invariants, and recursive processes are proven using induction. In some cases it might be trickier to find a good loop invariant, where proving recursive processes is just to follow the very own definitions of the process.


Consider the following recursive definition:

maxList [x] = x
maxList (x:xs) = max(x, maxList xs)

We can prove its correctness using induction:

– Base case: Max element of a list of size 1 is the element itself.

– Inductive step: Assume that maxList of xs is maximum element.

Then for maxList (x:xs) we have 2 cases:
1. maxList of xs is >= x, in which case we select maxList xs
2. x is >= maxList xs, in which case we select x
In either case, we pick the larger element which will be the maximum.


Now consider the following iterative definition:

var max = x[0], i;

for (i = 0; i < x.length; i++) {
     if (x[i] >= max) max = x[i];
}

In this case we need to find a loop invariant to use that will hold pre-, during, and post- processing of that code block.

We can use the following loop invariant: max is the biggest element in the subarray x(0, i).

– Before loop: for array of size 1 we have the same element to be maximum. So the loop invariant holds.

– Within the loop, we have two cases:
1. x[i] >= max, in which we set max to be x[i]
2. x[i] < max, in which we don't change max
In either case, the loop invariant holds.

– After loop: max is the biggest element in the subarray x(0, x.length – 1) which is just x.

Usefulness of algebraic structures

Let’s consider the partial order relation. 

Namely, it’s a relation that has the following properties: reflexive, transitive, antisymmetric.

One example of such a relation is ≤ on naturals.

Another example is ⊆ on sets.

But if we look at these 2 examples from a higher perspective, the first one is about comparing numbers and the second one is about subsets of a set. E.g. 1 ≤ 2 and {1, 2} ⊆ {1, 2, 3}

It might not be immediately obvious that these 2 examples have anything in common, but with partial orders (and algebraic structures in general) we can capture such abstractions.