From an abstract definition to a concrete set

The students will now use the three axioms trying to construct $\cal{S}$. For the objective of this paper it is important to point out that by thinking of the construction of the set $\cal{S}$ we have already invoked the algorithmic mode of thought. We were not satisfied with only an understanding of the abstract set definition, we wanted to actually construct the set.

It looks simple enough to use the first two axioms as an algorithm for producing a list of numbers, satisfying them. The first axiom provides the first element $0$. We mark the $0$, and add the element $1$, by means of the second axiom. We then move to the next unmarked element - $1$, which by means of A2, yields $3$ and $4$. The next unmarked element is $3$, and it yields $7$ and $10$. When proceeding we finally get the list $\cal{L}$: $0, 1, 3, 4, 7, 10, 9, 13, 15, 22, 21, 31, 19, 28, 27...$ Here is the algorithm in pseudo-code:

Algorithm Algor


write $0$;

while you have time or patience do the following:


find the first unmarked element $x$;


mark the element $x$;


add $2x+1$ and $3x+1$ to the end of the list;

Clearly, this algorithm generates a ``theoretically" infinite list of non-negative integers. It is worth noticing that this procedure does not generate all the natural numbers, i.e. the set $\cal{N}$; it generates a subset of $\cal{N}$. This again must be proven mathematically, and the teacher might prefer to rephrase this as an exercise, and ask the students to prove it.

Interestingly enough, this straightforward way of generating the set $\cal{S}$, using the first two axioms to produce a list of numbers, is not simple at all. Some understanding of basic concepts of computer science, like the concept of a queue as a data structure, is needed. We will however, not go into the details of the implementation here.

Before proceeding we should ask if this algorithm really generates the set $\cal{S}$. To be more specific, we should ask: If we had let $Algor$ run forever, would it produce the infinite set $\cal{S}$? Here a mathematical proof is needed. This is the first opportunity to introduce the notion of correctness. The teacher will decide how much effort (time) to devote to this notion here. It should be pointed out that this is not just an exercise in writing down the algorithm and later hopefully running it on a machine; we want, rather, to be sure that the algorithm is correct - that it actually does what it is expected to. We formulate this as a claim:

Claim 1:
The list generated by the algorithm $Algor$, $\cal{L}$, equals the mathematically defined set $\cal{S}$.

Proof: $\cal{L}$ satisfies the axioms A1 and A2 (this is how it was constructed), and since by definition $\cal{S}$ is the minimal set satisfying A1 and A2, hence $\cal{S} \subseteq \cal{L}$.
For convenience we now denote the elements of $\cal{L}$ by $a_0, a_1, a_2,...,a_i,...$. Let $l$ be an element in $\cal{L}$. For some $i, i\geq 0, l=a_i$. It can now be proven by induction that for every $i, i\geq 0, a_i \in \cal{S}$. Hence $l \in \cal{S}$, hence $\cal{L} \subseteq \cal{S}$, and $\cal{L} = \cal{S}$. Q.E.D.

Having proven the correctness of the algorithm, we can now refer to our set as $\cal{S}$ or as $\cal{L}$, since we have seen that both consist of actually the same elements. As a consequence we have another important claim with the aid of which our set becomes much more concrete.

Claim 2:
Let $x$ be a non-negative integer, $x \in \cal{S}$ iff
$x=0$ or there exists an element $y$, $y \in \cal{S}$, such that $x=2y+1$ or $x=3y+1$.

Now, the algorithm Algor can be used to show that there are many more sets that satisfy axioms A1 and A2, but do not satisfy A3. As a matter of fact there are infinitely many such sets. For example, if we add the number $2$ to the list generated above, and all the numbers ``generated" from $2$, by means of A2, that is by means of Algor, we will get the additional numbers: 2, 5, 7, 11, 16, 15, 22, 23, 34, 33, 49... The union of the new generated sequence and $\cal{L}$ satisfies axioms A1 and A2, but it does not satisfy axiom A3.

Following the example above, the teacher can now raise a more general question: Given an element $a$, $a \notin \cal{S}$, will replacing A1 with $a \in \cal{S}$ yield a different set? We will probably get a new and different list. To find out how many different lists we can produce, we ask how many different such elements $a$ are there? The students will be guided to find out that there is an infinite number of such elements, by observing that the complement of $\cal{S}$, $\cal{N}-\cal{S}$ is an infinite set.

What we have done by now is defining a set, and trying to get the feeling of it. We have done this by writing an algorithm which generates the elements of this set. Now, we would like to ask where does the computer come in? What is its role? Let us turn to the next section.