So far we talked a lot about "rewriting to normal form" as a model of computation. We also discussed how to give meaning to formal languages by mapping them to a semantics. All these notions can be connected, clarified and formalised with the help of a little discrete maths, which we will review now. [1]
In fact, we only need to understand the concept of reflexive and transitive (and symmetric) closure of a relation. So lets get started.
I assume that we all understand what a set is, so feel free to jump to the next section.
The basic statement about a set we can make is that it contains an element , which is written as
We also need to be able to say that is a subset of , which can be written in set-theoretic notation as
We also need to review different ways of defining sets. The simplest one is just to list the elements of a set as in
To illustrate the notation reviewed so far, we have and , where
is the standard notation for the natural numbers.
Above, I am taking for granted, but we can also define it ourselves by saying that and if then also . Note that this definition avoids the and instead uses only two rules. We say then say that is the smallest set closed under the rules. This style of defining sets is called definition by induction and we will see more about this in a later lecture.
Defining infinite sets inductively is very common and we have seen another example of this when we defined the language exp
of arithmetic expressions.
Another way of defining sets is called comprehension. A definition by comprehension has the form
For example, we may define the set of even numbers as
Here is short for "there is such that "
Exercise: Define the set of odd numbers in the same style.
We can also use comprehension to define the so-called cartesian product [2]
which is just the set of pairs that can be built by taking elements of in the first component and elements of in the second.
Example: Fractions are pairs where we use the special notation "" just to indicate that we want to think of this pair of numbers as a fraction and not, eg, as the coordinates of a point in the plane.
More Notation (not so important now, but useful later): If in the above definition we have then we may abbreviate as . Similarly, we abbreviate , usually written just as , by . This notation extends to for any . The set is called the empty product and has exactly one element, often called the empty word. The empty word has not standardized notation and one may find different symbols for it such as and and and and (epsilon) and (lambda). The set always has exactly one element, whatever is. For this reason, is sometimes written just as . We then obtain the equation , which is similar to a familiar equation for numbers, namely that for all numbers (possibly restricted to ).
If you are familiar with databases then a relation is really very nuch the same as a table in a database. For our purposes, we actually only need tables that have two columns (attributes).
Anyway, we don't need to think about databases at all. The mathematical definition is that a relation[3] on a set is a subset of , in symbols
Notation: By convention, we also write instead of , or also , which in turn may be abbreviated to . When drawing pictures we also write this as
which we abbreviate to
if there is only one relation discussed at that moment.
Remark: Later we will take to be the relation of "one-step computation", or rewriting, as we called it, but for now we make no assumptions on and .
We need to know what it means for a relation to be reflexive, symmetric, and transitive.
Defininition: Assume that .
is reflexive if
for all .
is symmetric if
for all .
is transitive if
for all .
Example:
The Wikidata Graph Builder is a fun way to explore relations, for example all descendant students of Beethoven.
Homework/Exercise: Make up your own examples. Family relationshiops are a great source. Try parent, child, ancestor, etc and check each of them for reflexivity, transtivity and symmetry.
Without any doubt, equivalence relations and equivalence classes are one of the most important concepts in all of mathematics. It was discovered surprisingly late, as far as I know by Dedekind around 1880. [4]
Definition: An equivalence relation is a relation that is reflexive, transitive and symmetric.
If is an equivalence relation on , then every partitions into equivalence classes. For , the equivalence class of is denoted by or and defined as
To say that the equivalence classes partition is to say that equivalences classes are disjoint and cover all of . We will come back to this below.
We can now form the set of equivalence classes which is written as and defined as
Remark (Partition): Equivalence relations on are in bijective correspondence with partitions of . A partition of is a set of subsets of that are pairwise disjoint and cover all of .[5] Given an equivalence relation, its equivalence classes form a partition. Conversely, every partition defines the equivalence relation of "being in the same part".
Remark (Equivalence relation/partition of a function): Every function defines an equivalence relation via . In other words, partitions into the subsets of elements that are identified by .
Example: Equality is an equivalence relation. In fact, equality is the smallest equivalence relation. There is also a largest equivalence relation (which is it?).
Notation and Terminology: If is an equivalence relation it is often written as or or any other symbol that emphasises the analogy with equality. The set is also called modulo or quotiented by or the quotient of by .
Example: On the integers , the relation of congruence modulo is an equivalence relation. The set of equivalence classes is denoted by . The operation of "dividing by " has some properties similar to division, see eg the Chinese Remainder Theorem which explains some of the terminology just introduced.
Example of fractions and integers: Two famous examples of sets that are sets of equivalence classes are the integers and the fractions.
The following exercise is crucial to understand equivalence classes.
Exercise: Show that every equivalence relation on partitions , that is,
We are almost done. Before we can relate the last lecture about syntax and semantics to the idea of computation as rewriting to normal form, we still need to define the notions of transitive closure and equivalence closure.
The idea of transitive closure is easily explained. Transitive closure is an operation on relations. Given a relation , two elements are in the transitive closure of if there is a sequence of elements such that
or, shorter,
There is an elegant way to define the transitive closure that does not require the use of .
Definition: Assume that .
Remark: Let us now think of as a relation of "one-step computation". To indicate this intention we write now instead of and for the reflexive and transitive closure and for the equivalence closure. The good situation we are interested in, and which we will explore in the next lecture, is where reflects the equations that hold on the semantic side and where allows us to rewrite any element into a unique normal form. We then can compute with equivalence classes, even though they are sets, by instead computing with the normal forms they contain.
Exercise: Make sense of the last sentence, by reviewing the laws of fractions you learned at school. Explain in our terminology why you were asked at school to cancel fractions.
As I said, I assume that the notion of a function is familiar, either form high-school or from a first semester discrete maths course. But we can review some terminology quickly.
To begin at the beginning, a function is often defined to be a relation , which, moreover, is
These two properties together say that for all there is one and only one related and this is the element that is, by convention, written as .
We will also need further properties that functions may have. A function is called
If we have a bijection between two sets, then the two sets can be considered equal up to the names of their elements. Intuitively, a bijection is like a dictionary that relates every word in one language to exactly one corresponding word in the other.
We will also need that a function
can be extended to subsets of and . We define
Remark (Partition of a function): Every function defines a partition on . The sets are sometimes known as the fibres over .
I assume that students had a one semester course on discrete maths. But in many discrete-maths-texts relations only appear in the "second semester" part. For example in the widely used book "Discrete Mathematics and Its Application" by Rosen, relations only start on page 374. Btw, the book could be a good place to review some discrete maths. ↩︎
This is called "cartesian" product in honour of Descartes, who, in his "Geometry", about which we talked already, invented the represenation of points in the plane by and -coordinates, that is, the representation of points as elements of . ↩︎
It is common to abbreviate by . If we need to emphasise that is a susbset of as opposed to a subset of for some other , we call a "2-ary" relation or a binary relation. ↩︎
More information is available in this article on The Early Development of Set Theory. By the way, Dedekind was also the guy who defined integers and rationals as equivalence classes. You are asked to work on this in this exercise. ↩︎
In symbolic notaion, a partition of is a collection of subsets of such that and . ↩︎