# Recursive definitions (a couple questions based on them)

From the book Logic, laws of truth, by Nicholas J.J Smith:

1. What does Smith mean by recursive definitions?

2. Why does it matter?

3. How do you make recursive definitions for something such as: a) the set of all odd numbers, b) the set of all numbers divisible by five.
I am not asking for recursive definitions for questions 1 and 2, but examples of how to make recursive definitions which could explain using these in questions 1 and 2.

Here are the questions:

1. What does Smith mean by recursive definitions?

Smith provides an example of the recursive process by defining wff as a recursive definition. He writes (page 41)

"Recursive" means "characterized by recurrence or repetition" (as in "recur").

What is repeating is the recursive clause in the definition of wff should we be asked to check if a string of basic symbols is a wff.

If one has a string of basic symbols with a connective, one can apply the recursive clause to break up that string until we run out of strings with connectives. If we do that and all the remaining strings are basic propositions, then the original string of basic symbols is a wff.

For example, suppose we have this string of basic symbols:

((A ∧ B) ∨ C)

Now ask the question: Is this a wff? The recursive definition allows us to determine that.

By the recursive clause we can split this string of basic symbols into two strings of basic symbols: (A ∧ B) and C. Are each of these two strings wff?

Again we apply the recursive clause to the first because it has a connective. We can split (A ∧ B) into two strings because it has the connective separating the strings A and B. For the second, it does not have a connective so we check to see if the string C is a basic proposition. It turns out that it is, so C is not merely a string of basic symbols, it is a wff. Similarly we note that A and B do not have connectives but they are symbols for basic propositions. They also are wff. So the original string, by this recursive definition, is a wff.

We started with a string of basic symbols, repeatedly applied the recursive clause until we reached basic propositions which by the base clause are wff. Hence we conclude by this that the original string of basic symbols, ((A ∧ B) ∨ C), is a wff.

Consider an example where this fails. Suppose we have this string:

(A ∧ ∨ C)

Although this is a string of basic symbols, we do not have a single connective separating A and C, so we cannot proceed further. This string of basic symbols is not a wff.

1. Why does it matter?

Smith provides the answer for this: (page 41)

In only a small number of clauses, this definition characterizes an infinite number of strings of basic symbols as wffs.

Although this may be more than one needs, to get a deeper overview of recursive functions see Odifreddi, Piergiorgio and Cooper, S. Barry, "Recursive Functions", The Stanford Encyclopedia of Philosophy (Winter 2016 Edition), Edward N. Zalta (ed.), URL = https://plato.stanford.edu/archives/win2016/entries/recursive-functions/.

1. How do you make recursive definitions for something such as: a) the set of all odd numbers, b) the set of all numbers divisible by five.

It is easy to write definitions for these that are not recursive. For example, an integer is odd if it leaves a remainder of 1 modulo 2. Similarly an integer is divisible by 5 if it leaves a remainder of 0 modulo 5.

That is not what is wanted. A recursive definition has two clauses, a base clause and a recursive clause. To define an odd integer using a recursive definition one might do the following. The set of all of these would be the desired set.

Let us restrict "number" to "integer". If the integer is negative convert it to its absolute value. This allows us to consider only "positive integers". We can write the base case as

• 1 is odd.

The recursive clause might look like this:

• If a positive integer n is greater than 1 then it is odd if n - 2 is odd.

For example, suppose we have n = 5. Is 5 odd? That's what we want to check. By the definition since 5 is greater than 1, 5 is odd if 5 - 2 = 3 is odd. But 3 is odd if 3 - 2 = 1 is odd. At this point we have reached the base clause and so we declare by this recursive definition, that 5 is odd.

One can write a similar recursive definition to tell if an integer is divisible by 5, but first convert any negative integer to its absolute value so we can define a base case:

1. 0 is divisible by 5. (Base clause)
2. A positive integer n is divisible by 5 if n - 5 is divisible by 5. (Recursive clause)

Smith, N. J. (2012). Logic: The laws of truth. Princeton University Press.

Recursive definition is a mathematical term: it is used in mathematical logic and computer science is used to define the elements in a set in terms of other elements in the set.

Thus, it means what it means.

Try with some simple examples and practice with them.

The definition of Wffs of PL in Smith's book (page 41) is a very siple example of recursive defintion.

As you can see, the author uses it to define the basic syntactical object of Propositional Logic : the well-formed formula, i.e. what counts as a "syntactical correct" (and thus meaningful) expression of the language.

The definition provides a rule (or procedure) to manufacture wffs :

(i) we start from an initial stock of expressions that are wffs : the atoms or basic propositions; put them into the "bag" of formulas.

Then :

(ii) for every wff α, also ¬α is a wff; i.e. for every wff formula already into the "bag", we can add to the bag its negation.

(iii) for every pair α and β of wffs, also (α ∧ β) is a wff.

And so on for the remaining connectives.

It is not always useful to use recursive definitions everywhere...

The protoptype of all recursive definitions is exactly the set N of natural numbers :

(i) 0 is a natural number:

(ii) if n is a natural number, then its successor s(n) is a natural number.

Having defined N and the basic operations of sum and product (also these are defined recursively), the set of Odd numbers is easily definable without recursion :

a natural number n is Odd iff n=2k+1 for some k.