next up previous
Next: From an abstract definition Up: A Mathematical-Algorithmic Approach to Previous: Introduction

The set $\cal{S}$ - an abstract definition

We start with an abstract definition of a set $\cal{S}$.
A set $\cal{S}$ is defined by the following three axioms:
A1. $0 \in \cal{S}$,
A2. $x \in \cal{S}$ $\rightarrow 2x + 1 \in \cal{S}$ and $3x+1 \in \cal{S}$,
A3. $\cal{S}$ is the minimal set satisfying A1 and A2.

This definition is taken from Engel's book: ``Exploring Mathematics with Your Computer" ([E]). Engel introduces this mathematical example, and then uses the computer as a machine to help solve a specific membership problem: ``Which of the numbers 511, 994, 995, 996, 997, 998, 999 do belong to $\cal{S}$ ?" Two different computer programs which provide a solution to the problem follow the presentation of the problem.

Engel incorporates the computer into a mathematics course, a set theory course. This, we believe, is a meaningful step in the right direction. However, we would like to take this approach a little further. We want to incorporate algorithmic thinking into mathematical thinking. Mathematical thinking and mathematical reasoning, play an essential part in all areas of computer science. So that mathematical thinking is almost always incorporated into the computer science curriculum. What we want to exhibit here is how to take an algorithmic approach while discussing a mathematical subject, or while trying to solve a problem from the mathematics curriculum. Let us proceed.

Considering the abstract definition of $\cal{S}$, it seems quite natural to consider first, well known sets like $\cal{N}$ - the natural numbers including $0$, or $\cal{Z}$ - the integers, and check whether they satisfy axioms A1 - A3. It can very easily be shown that $\cal{N}$ or $\cal{Z}$ satisfy the first two axioms but not the third one. We can take out the number $2$ for example, and still the axioms A1 and A2 are satisfied by the new set $\cal{N} - \{ $2$ \}$ . This has to be proven mathematically, of course. Teachers might prefer to choose a more formal way of teaching, in which case they can rephrase what has just been said as an exercise in this way: Prove that the sets $\cal{N}$, $\cal{Z}$ and $\cal{N} - \{ $2$ \}$ satisfy the axioms A1 and A2.
The students should be given time to ``play around" a little, and get the feeling that there are many sets that satisfy axioms A1 and A2. It can be proven that actually there are an infinite number of such sets. At this point the teacher will explain the role of axiom A3. It should be made clear that axiom A3 is necessary in order to specify one and only one set from the infinite number of sets defined by the two axioms A1 and A2. This one set will be referred to hereafter as $\cal{S}$.

The teacher will elaborate a little on the concept of ``the minimal set" - a somewhat abstract concept, which does not really help in "feeling" what the actual set looks like. As we will show in the next section, here is where the algorithmic approach comes in.

next up previous
Next: From an abstract definition Up: A Mathematical-Algorithmic Approach to Previous: Introduction
2004-01-05