Here are the questions:
- 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.
- 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/.
- 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 a 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 restring "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:
- 0 is divisible by 5. (Base clause)
- A positive integer n is divisible by 5 if n - 5 is divisible by 5.
Smith, N. J. (2012). Logic: The laws of truth. Princeton University Press.