This is an episode in a series on mathematical logic approached with some rigour. Here, we will be closely following the book by Peter B. Andrews: An Introduction To Mathematical Logic and Type Theory. In this episode, we will:
- Learn about well-formed formulas.
- Show the equivalence of the well-formed formula definition to that of a formation sequence on a formula.
- Revisit the principle of mathematical induction and complete induction on the natural numbers.
- Learn the principle of induction on the construction of a well-formed formula.
- Learn about substitutions in the context of propositional logic. And use this idea to derive one of De Morgan’s Laws.
The only knowledge this post will assume is a basic knowledge in set theory.
(The Prelude) Before we start with logic, let’s revise two ideas which may serve to be important later on. If one is familiar with the principle of mathematical induction and strong induction, one may skip this.
(S1E01) (Prelude 1) Principle Of Mathematical Induction.
We take it to be true that given any property , if the first member in a list has this property. And if I choose any member at an index of , i.e. , and it happens that the next member also has this property , then all members of this list have the property .
(S1E01) (Prelude 2) Strong Induction
For any property , and for any member in a list I pick, if every other member where has this property means that has this property, then all the members in this list have this property .
Logic and Reasoning
Let us first start by naming our system of reasoning, let’s call it . This system consists of two types of primitive symbols. These are symbols whose meanings aren’t defined, but instead, chosen depending on how the system is intended to be used.
(S1E01) (Scene 1) The Primitive Symbols:
- Proper Symbols : [, ], ~,
- Improper Symbols: These are denumerable propositional variables : . As the name suggests, holds a proposition.
The symbol “~” is called a negation, when applied to a propositional variable (or to a formula which is defined later on) – it negates it. is a disjunction which joins propositional variables or formulas.
A formula is a sequence of primitive symbols. e.g. ~ is a formula, or ] is a formula. But in the context of reasoning what could ~ possibly mean? How does one reason without any proposition? It is for this that we then define a well-formed formula (wff).
(S1E01) (Scene 2) A formula is a well-formed formula its being is a consequence of either one of the following formation rules:
- A propositional variable standing alone is a wff.
- If A a wff, then ~A is a wff.
- If A and B are wff, then [A B] is a wff.
So, we define a wff in the following way: Suppose is an arbitary set containing wffs. Then we define the set containing all wffs as . Where
- , where is a propositional variable.
- If then .
- If then . Where and are formulas.
And thus any wff is member of the set .
(S1E01) (Scene 3) An alternative definition uses the idea of a formation sequence (fs). A formation sequence for a formula Y is a finite sequence of formulas . Where we have that and for each one of the following condition holds:
- is a propositional variable.
- there is such that .
- there are indices and where is
We will now show that Scene 3 and Scene 2 are equivalent, i.e. A formula is a wff it has a formation sequence.
Before we do this, we will reformulate the principle for induction on the construction of well-formed formulas.
(S1E01) (Scene 4) Induction on the construction of well-formed formulas.
Suppose is a property of formulas, and means that a wff has property . Suppose
- for every propositional variable .
- Whenever for every formula , then .
- Whenever and then
Then every wff has the property .
(S1E01) (Climax 1)
Theorem: Suppose is a set that contains all wff. A formula has a formation sequence.
Let be an arbitrary set of wffs and is a set containing all formulas with formation sequences. Furthermore, let . By (scene 2) (1), is possibly a propositional variable and thus have formation sequence of . Therefore . By (scene 2) (2) it could also possibly be a formula where we can construct a formation sequence so . Finally, by (scene 2) (3), if we have . We can then have with a formation sequence . So . So by (S1E01) (Scene 4) All wff in the set have formation sequences. So we have that
Now, again, let be an arbitrary set of wffs and is a set containing all formulas with formation sequences. But now let . By (S1E01) (Scene 3) (1), in a formation sequence can be a propositional variable and thus we have . Or by (S1E01) (Scene 3) (2), we can have the case where where and y proceeds x in a formation sequence, we then have that . Or by (S1E01) (Scene 3) (3), we have that where y and z preceed x in the formation sequence. So, . We can then state that .
Therefore we have that . And since this set was arbitrary, the result follows.
We can assign meanings to the primitive symbols, and generate new meanings as shown in below.
(S1E01) (denouement) For Fun: I was listening to Mrs Potter’s lullaby while writing this, and there’s a part in the lyric that goes “Or the elephants will get out and forget to remember what you said“. Let’s have some fun with this sentence. First, we will define a map that maps any wff to either True or False or both or neither. If but not both and not neither we say is a function with a wff parameter. If it it maps to both for some , then we say is a paradox. We will then define the proposition Elephants never forget, and assert that . Then, we’ll define elephants will forget to remember. And finally, let’s say . What will be? Will be a function?
Well, and it’s thus a function. That’s it, that’s the answer. The lyricist lied to us… or did he? Why or why not?
CAUTION : The above definitions (in (S1E01) (denouement)) may not necssarily be standard in mathematics and nevermind mathematical logical. I just happen to like to think of things in terms of functions and this was just me messing around. Dankie! Ka leboa..
Before we introduce the next idea, it is worth noting that if we have formulas and , we can concatenate the two by writing .
(S1E01) (Scene 5) Definition: Substitutions. A function from a set of formulas into a set of formulas is a substitution if and only if
- is the empty formula if and only if is the empty formula.
- for all formulas and ,
The two questions I had when I first saw this definition was: so in this context, is the empty formula the kernel? And the function a homomorphism? One can read the definitions and convince themselves that this is possibly the case.
And we say that any two substitutions are actually the same if they behave exactly the same way. i.e. for any primitive symbol , if , then . Furthermore, we say that is finite if and only if the set of primitive symbols , such that is finite.
I will personally not be using this notation in this post.
I think it’s worth exploring this idea a bit more. To do this, I will reformulate some of the ideas in Picture(1) in terms of substitutions.
Before we do so though, let us just go through some important results:
Consider a wff with some substitution . If is a wff then we know it must a formulation sequence (S1E01) (Climax 1). Consider a simultaneous substitution on all formulas in the formulation sequence to variables . Here, . So, and . So putting this together, we get . This then tells us that there must exist a substitution , such that gives us the empty formula. The empty formula is otherwise known as the identity. An identity acts like a 1 in multiplication or 0 in addition. Notice I say “an” identity and not “the” identity because I am not quite sure yet if it’s unique. This also means that is the empty formula. So , is a substitution that maps an empty formula, to another instance of the empty formula. We can use this information to show that . We can then define another substitution .
I would like to use these two functions to derive one of De Morgan’s Laws, where . I will simply do this by taking . Where the circle represents a composition. But before we do this, we need to prove two important results:
- For any substitution , we have .
Consider a wff , we know that this wff has a formulation sequence . Where we have , and . So we have that .
- For any substitutions . The composition is also a substitution.
1. We have to check whether if A is an empty. We know is a substitution, so it returns an empty formula which is passed into and that is a substitution, so it returns an empty formula so the result follows.
2. We then have to check . I will leave this for the reader to check, just remember that and are already substitutions and and are formulas.
It would be nice if the reader defined substitutions to derive the other relationships in (picture 1).
I’ve pretty much woven-in my solutions to the exercises of this section into the post, of which they may or may not be right. I’ve tried my best to ensure they make sense to me and have tried to verify them where I can. This textbook does not have solutions, so I am not 100% sure, but I am convinced I have not made a booboo, maybe a typo here and there.
Finally, I will end with another idea which I may or may not have used implicitly in my post.
(S1E01) (Scene 6) Claim : for distinct variables and wffs where we have an arbitrary substitution , with then simultaneously substituting wff in with the variables above yields a wff. I will leave this to the reader to prove.
See you on the next episode. The next episode will be on the axiomatic structure of our system.