If you’ve never heard of Mad Libs before, it is a game that presents the player with a skeleton of a short story, with blank spaces interspersed throughout that are each labelled with certain types of words (noun, verb, adjective, etc.). The player fills in the blanks with words of their choice, and is generally rewarded with a humorously absurd story for their efforts. But how does this relate to logic?
Consider a statement like “All men are mortal”. I could phrase the same sentiment with the more awkward, but equivalent “For any something, if that something is a man, then that something is mortal”. Since I’m a math guy, I like referring to “something”‘s with variables, so I’ll rephrase again to “For any X, if X is a man, then X is mortal”.
Ignoring the variable for now, there are four parts to this assertion: we have “for any X”, “X is a man”, “X is mortal”, and then the underlying “if something, then something else” (or “if then”) structure. The middle two assertions are saying something about properties of X. Let’s assume for the sake of simplicity that each assertion is binarily either true or false depending on what we choose X to be. Because the truth or falsity of “X is a man” and “X is mortal” depend on what X is, we call these phrases predicates.
As in the above example, predicates can be linked together in certain ways to create more complex assertions. In addition to the “if then” connective, there are also “and” and “or” connectives. We can think of these connectives as conjunctions, hooking up predicates to become longer, more complex logical statements.
I should also say something about the “for any X” part at the beginning. This tells us how the variable X is being quantified in the statement; in a sense, it tells us what the flavour of the variable X is. Broadly speaking, there are two flavours of variable: the “universal” flavour, used above, in which X is a placeholder for an arbitrary thing from some underlying collection, and the “existential” flavour, in which X is a placeholder for a particular thing that we don’t have a proper name for yet. An example using existential quantification would be “There exists some Y such that Y is a man and Y is immortal”. Notice that this sentence doesn’t name a specific individual for whom this statement is true; it merely asserts that such an individual exists.
So, by joining together predicates with various connectives, we can get formulas, but remember that they’re all still full of variables, so they’re still skeletons in a sense. One could think of one of these formulas as a Mad Lib, a shell of a statement that is waiting to be filled in and given some concrete interpretation.
What words are we allowed to use to fill in these blanks? In principle, we could use whatever words we want, but if you read my previous post on how algebra can be thought of as a language, you can probably guess where I’m going to go with this.
As a quick refresher, by an algebraic “word” I mean a string of symbols built from (i) some previously defined collection of “letters” (usually numbers) that serve as the basic building blocks for words, and (ii) a collection of operations that “glue” letters together in order to build up longer words (think of addition, and all the different strings of symbols one can build just by sticking “+” signs between numbers).
As I mentioned earlier, in principle one could stick any word into any predicate, but if our words are coming from some mathematical language, we probably want to choose some predicates that meaningfully describe the words that we’re using, i.e. things like “X is a man” and “X is mortal” are out. What, then, are some interesting or useful mathematical predicates?
The most ubiquitous example is simply “X = Y”. Equality is on a fundamentally different level than numbers and operations, because while 3+2 and 4+1 are just words, 3+2 = 4+1 is an assertion of truth, which happens to be true under the usual understanding of addition. I could equally well write 2+2=5, which is also an assertion of truth; it just happens to be false under the usual understanding of addition. So “X = Y” is an assertion that can be either true or false depending on what we choose to plug in for X and Y; in other words, it’s a predicate.
If the algebraic words that we defined in my last post are the nouns of some mathematical language, then predicates, connectives and quantifiers give us the descriptors to be able to talk about how the nouns (and the operations) behave. But what kinds of behaviour do we care about?
In my last post, after describing how one builds out all possible algebraic words of a given language, I noted that dealing with this entire collection was unwieldy, mainly because it likely contains words that are spelled differently but which we want or understand to be equal. For example, 3+2 and 4+1 are “spelled differently”, but if we know that “+” means addition, we would want these words to mean the same thing. To get around this, we could use a set of rules that tells us which words mean the same thing, and the language of choice that we use to write these rules is that of predicates, connectives, and quantifiers.
As it turns out, most of the important properties that mathematicians care about have the common form “For all, X, Y, etc. [word 1] = [word 2]”, to the point where there are entire branches of mathematics dedicated to the study of structures that can be described by rules like this. In fact, it is known that collections of rules of this form can be described in terms of categories.
This intersection between logic and category theory is my main area of interest, and I’ll start exploring it in more detail next time.
Photo by GDJ via Open Clipart
