In our previous article, we presented some mathematical terms which are also found in literature. Those were polysemantic words, which have remarkably similar meanings in two fields which may not strike everyone as related. Here we take a similar approach, but we focus on a single word: induction, whose meanings span mathematical logic, philosophy, arithmetic, physics, engineering, programming, and even everyday language. We find induction when answering broad questions such as:
How can we program a computer to prove mathematical theorems?
How are observations used to formulate general theories?
What is a natural number, such as 0, 1, 2, 3, etc.?
Is there any connection between all these and… induction stoves in our kitchen?
Inductive Reasoning
The dictionary defines induction as a process of bringing about, starting something and as an inference law. We will soon see that these meanings are connected, and we start by describing induction as a method of logic.
Loosely speaking, inference (or logical reasoning) laws are classified by the connection they establish between the particular and the general. As such, we distinguish three types.
Deduction is the most popular and it proceeds from the general to the particular. When deducing something, we usually find applications or special cases to a general law or rule. For example, if we know that in general water freezes at 0 C, then we can deduce that in particular, the water in my bottle will freeze if I store it outside and during the night the temperature drops below 0 C. Therefore, by means of deduction, we get special information, applications of general, abstract laws.
Induction proceeds in reverse: it starts by recording particular observations, following an experiment or some case study and tries to formulate general, abstract conclusions. For example, say we observe with our telescope some astronomical phenomenon on February 1st, then the same occurs on February 4th, 9th, and 13th. We use induction to draw the general conclusion that the phenomenon occurs every 4 days. We will see that not just the number of particular observations matters, but also the method used for drawing the conclusion.
Abduction is the rarest of the three, as it is sometimes wrong. It also draws general conclusions from particular premises, like induction, but they are not always the correct ones. Here’s an example: say on a summer morning we notice the road is wet. By abduction, we conclude that it must have rained during the night. But this is not always the case, and the conclusion is rushed: some public cleaning vehicle may have wetted the road or perhaps it’s just the morning dew. Mathematically speaking, abduction draws conclusions from sufficient premises, but which are not always necessary; it does suffice to have rained for the street to get wet, but it is not necessary.
Mathematical Induction
The principle of mathematical induction adds an essential requirement: a proof for the fact that we can add one more case where the observed property still holds. In the case of the astronomical observations above, we need formal proof (hence one that is abstract, independent of any telescope precision) that the phenomenon will occur on February 17th as well. Only after that can we draw the general conclusion that the phenomenon has, indeed, a frequency of 4 days, regardless of the month.
Instead of adding more technical details, let us mention that a form of inductive reasoning appears first at Plato, in his Parmenides dialogue, written in 370 BC. His form is somewhat in reverse: he starts with a pile made of one million grains of sand, then says that by removing one grain, we still have a pile. Hence, 999,999 grains make a pile, so do 999,998 and 999,997, and so on. Plato presents this as a paradox (named after the Greek word for piles, sorites, σωρείτης), because we reach the conclusion that even one grain makes a pile. The origin of the problem, says Plato, is not in inductive reasoning, but in the careless definition of the term “pile”.
Natural Numbers
The simpler, the more obvious a concept is, the harder it is to define—not only in mathematics or science. What is a number? What is a set? How would you define seeing, heat, spring?
The same holds true for natural numbers[1]. Since they are fundamental in mathematics, logic and more, a rigorous definition for them is mandatory. Although history shows that the Mesopotamians and the Egyptians used natural numbers, as well as the more complicated rationals (fractions) and square roots around 5000 BC, the definition of a natural number came no sooner than the last decades of the 1800s. Mathematicians and philosophers such as Bertrand Russell, Gottlob Frege, Giuseppe Peano, Richard Dedekind and others have formulated a definition so abstract, that it took more than 300 pages for Russell and Alfred N. Whitehead to prove that 1 + 1 = 2 in their magnum opus, Principia Mathematica, published between 1910 and 1913.
Therefore, we will not attempt to give such a definition here but do point out that it relies on mathematical induction. The special cases are the numbers 0 and 1, and the method used to add more is called the successor function, which does what the name implies: it associates to each number the one that follows it, in the general order we use for counting. Therefore, 0 does not follow any number, but 1 follows 0, then 2 follows 1 and so forth.
Your Computer Can Prove Theorems
If the term “proof assistant” does not sound familiar, you should know that mathematicians have been looking for automatic methods of checking and even proving theorems for them.
The modern history of proof assistants—as we can also speak of an ancient one and even a science-fiction one—mentions the Russian mathematician Vladimir Voevodsky, the Fields medalist of 2002. In the 1980s, he noticed an error in an old article of his, which eluded the editors of the journal it was published in. Hence, he started working on computerised methods for checking proofs. He assembled a team of mathematicians, programmers and computer scientists and soon discovered that the mathematical foundations of automatic proofs were already a hot topic. They started working on implementations and forty years later, the domain is more active than ever, the most popular proof assistants being Coq, Lean, and Isabelle, with Voevodsky contributing mainly at the first.
Mathematical induction plays an essential role in implementing such software, since the very principle of induction is well suited for algorithmic treatment. The steps for confirming the observations, as well as those for verifying the succession method are easy to follow by a computer, after specifying the requirements in a programming language.
Essentially, a proof assistant uses a logic, made of a set of principles, rules and theorems, and then through iteration and various optimisation techniques, it checks whether the required conclusion can be reached starting from the hypothesis and using only the included logic. Here’s a simple example: assume the “logic” is only made of the law which specifies the order of the days of the week and that the hypothesis is “Today is Sunday.” Assume further the conclusion is “535 days from today is Monday.” Then the computer tries to reach the conclusion by applying 535 times the only rule it knows: the ordering Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday, … It stops with a negative answer[2], hence our “theorem” saying that 535 days from a Sunday is a Monday does not hold true.
Induction Stoves
This last section is seemingly for engineers or cooks and unrelated to the rest of the text. But in fact, there is a connection which we now explore through induction as a physical phenomenon. The electric current has a magnetic effect. That is, when traversed by a current that is strong enough, any device acts as an (electro)magnet. This is how industrial magnets work, and are used to lift cars, containers, and other very heavy objects. The converse is also true: a magnet can produce an electric current—it is the principle used for obtaining alternating current, by rotating a magnet placed in some external electric field. The current thus produced is called induced current and the law of physics that explains it is called Faraday’s law, honouring the British Michael Faraday, who first discovered it in 1831.
The connection with mathematical induction is in the very definition of the word induction, which we presented at the beginning of the article: the bringing about, starting of something. In electromagnetism, an electric current is started by a magnet (under some conditions), whereas in mathematics, general laws are brought about by particular observations (under some succession laws). Furthermore, in the case of induction stoves, it is not only the electric current that is induced, but also the heating effect of electromagnetism. Electric devices build up heat during their operation and some (including stoves) are purposefully built to use this induced heat.
In closing, a cliffhanger: another device which manifests and amplifies the effects that electromagnetism induces, including brainwave influences, is the solenoid. How it was used in a very subtle way by Mircea Cărtărescu in his 2015 novel, Solenoid, will be the subject of a future article.
[1] The set of natural numbers {0, 1, 2, 3, 4, …}, commonly used for counting, is sometimes called the set of positive integers. As such, they are a particular case of the integers, namely the set {…, -3, -2, -1, 0, 1, 2, 3, …}. The latter set is denoted in mathematics by Z, from the German word Zahlen, that simply means “numbers”, which goes to show their fundamental importance.
[2] 535 days from a Sunday is a Wednesday. Here’s a question for you: How would you optimize this search, so that the computer does not have to apply the succession rule 535 times?