Thinking like a Computer Scientist - Rigor and Formality

Analyzing the role of two key qualities of sound, logical thinking, and how they can help you improve your reasoning and argumentation skills.

A rabbit coming out of a hat. — generated with SDXL via MonsterAPI.

As a teacher, I always need to emphasize the importance of core foundational computer science courses such as logic and discrete math to my students because sometimes they can lose track of the forest by focusing too much on the trees. These courses do not necessarily provide concrete skills or knowledge that can be applied directly. Instead, they help develop fundamental reasoning skills that are applicable everywhere.

For example, in discrete math, students will make proofs about theorems in number theory, combinatorics, computability, and graph theory. While some of these concepts are useful for computer scientists, the most important takeaway from these courses is the ability to think rigorously and formally. The theorems can be found in books, but the critical thinking skills developed in these courses are invaluable.

In my discrete math course, I tell my students there are two critical components to producing a solid mathematical demonstration: rigor and formality. These two are orthogonal. You can achieve rigor without being overly formal or formality without being rigorous. When it comes to mathematical thinking, these two elements interplay to make your reasoning and argumentation clear and sound.

In this article, we will break down what it means to be rigorous and what it means to be formal. Then, we will examine the relationship between rigor and formality and argue why rigor is typically more crucial than formality.

This is the first of a series of articles I want to write on critical reasoning skills for undergrad students. I will mostly write from the context of math and computer science, but I think these ideas are valuable everywhere a sound and logical argumentation is desirable.

---

Rigor and formality

Rigor and formality are two orthogonal qualities of clear argumentation. In short, formality refers to form, while rigor refers to content —alternatively, we can say formality refers to syntax while rigor refers to semantics. Good arguments, like mathematical proofs, are both rigorous and formal. That is, they are solid in both content and form.

First, let’s examine these two qualities, and then we’ll analyze how they interplay in critical reasoning.

What is formality

In general, formality involves strictly adhering to specific rules of etiquette. In mathematics and computer science, this etiquette is a formal language. This means that what you say is highly restricted, as you must use specific symbols and follow specific syntactic rules with precise meaning.

In mathematical terms, formality means sticking to mathematical notation. Mathematical notation involves using symbols to refer to different objects. For instance, if you want to talk about a number with a particular property, you give it a name like “x” or “y”. You might also use subscripts to refer to a set of numbers with the same property or use more complicated symbols with specific quirks in their allowed syntax.

By naming things consistently, you ensure that anyone following your proof understands precisely what you're discussing. This is better than saying, "Remember I told you there were three numbers; just take the second one and multiply it by the third" because it removes ambiguity.

The benefit of formality is that anyone will understand precisely what you are saying based on the syntax. The advantage of clear syntax is that it removes all friction from decoding what you're talking about. Anyone reading your proof will know exactly which objects you're referring to and what you're trying to say about them. This means that understanding the proof becomes a matter of understanding the semantics and logical validity of the proof rather than figuring out what you're talking about.

What is rigor

In general, rigor refers to the thoroughness and coherence of an argumentation. When reasoning is rigorous, each step follows logically from the previous step without any hidden assumptions or presuppositions. There are no non-trivial premises that one must agree on before following the reasoning.

In mathematical terms, rigor comes from strictly following well-known rules of reasoning without taking unjustified leaps. This involves clearly stating your premises and backing up every claim with the necessary support. All claims must be either a logical consequence of the premises or previously stated claims. This builds a chain of reasoning such that any conclusion can be traced back to the premises via logical reasoning.

Thus, if the reasoning is rigorous, it should be self-evident to anyone following it that if you accept the premises, you must also accept the conclusion. However, this does not necessarily mean you will agree with the premises. The concept of rigor provides validity to your premise, argument, and conclusion. It ensures that your thinking is correct and that the truth you have uncovered is true based on your premises.

The advantage of being rigorous is that it ensures your conclusions are sound —that is, they are necessarily true, given the premises. Rigor also helps focus the discussion on the core of the argument rather than irrelevant elements like who’s doing the argument. If someone argues against a rigorous argumentation, they must either reject the premises or show a flawed logical step somewhere. This helps to uncover red-herring and other fallacies people use to divert a discussion in their favor without providing solid arguments.

The interplay between rigor and formality

It is possible to have rigorous argumentation without formality.

Academic papers often present rigorous argumentation that is not overly formal. Philosophical essays, for example, demonstrate this when the writer is clear, logical, and precise. They define their topic and make careful, logical connections between premises. They justify each statement they make, even if it initially seems trivial. This is most evident in modern analytical philosophy, which attempts to be logical and rational but is prevalent in all good philosophical arguments.

Similarly, natural science research can also demonstrate rigorous yet not overly formal argumentation. In experimental sciences such as physics, chemistry, and biology, well-thought-out experiments are conducted with detailed setups. The hypotheses and goals of the experiment are clearly stated, and data is analyzed to draw conclusions. Scientists rigorously distill their conclusions from the data to ensure the experiments support them. While scientific papers may use semi-formal notation, such as algebra or statistics, and graphs and tables, they are not as formal as a fully-fledged mathematical proof.

The opposite is also true; you can be exceedingly formal but lack all rigor.

Being overly formal in your writing or argumentation does not necessarily guarantee accuracy. For instance, you will have incorrect conclusions if you work on a math or geometry proof and rely on an unexisting theorem without following proper logical steps. Even if you use precise terminology and notation, your argumentation may still be flawed and fail to follow previous steps logically.

Formal but not rigorous argumentations can appear by accident or by malicious manipulation. A typical example is college students, who learn to grasp the syntax of proofs but struggle with their semantics, thus producing invalid proofs that still appear mathematically sound because all the notation is flawless.

On the other hand, sometimes, people trying to convince you of something untrue will use various tactics, including an appeal to formality, to make their argument seem more credible. By using many definitions, symbols, and formulas, they may try to trick you into believing their reasoning is correct.

This may be accidental, but it can also happen intentionally when researchers try to make their assumptions and conclusions seem more reliable by embedding them in a formal framework.

In political discussions, clever people often use rhetorical language to try and persuade you of their “truth”. They might use formal and complex language, mention scientific or technical concepts, and quote well-known personalities to lend themselves credibility. However, much of what they say is meaningless or plain wrong. Quoting some dead philosopher doesn’t make your argument necessarily any more accurate, but many fall prey to this illusion.

Finally, this practice is also pervasive in pseudosciences, which try to appear scientific but do not follow a genuinely scientific approach. They use formal language, define terms, and create complex taxonomies, ontologies, and theories but lack rigor.

By now, it should be clear that while having rigor without formality can sometimes make understanding difficult, having formality without rigor is a complete disaster. Therefore, it is crucial to prioritize rigor over formality, not only in mathematical thinking but also in reasoning in general.

First, make it rigorous, and then make it formal.

How to think rigorously and formally

The final question I want to address is how to approach writing, thinking, or communicating rigorously and formally. When teaching my students, I advise them to approach this kind of writing —e.g., for mathematical proofs— in three layers.

The first layer is intuition: understanding why something is true. By building intuition and seeing connections between different parts of the issue, you can become convinced of the truth of your argument. For example, a mathematical proof uncovers hidden relationships that may initially seem complicated. However, with a solid intuition, these relations become self-evident. The intuition layer is where you reach a deep understanding of why something is true.

Next, you add rigor to your intuition. This involves making your ideas as detailed and coherent as possible, checking every step, and making explicit all intermediate steps that logically follow from previous claims. You should avoid relying on non-trivial assumptions that aren't explicitly stated.

By adding rigor, you may realize that your initial intuition was incorrect. If you're wrong, you should be able to identify where the issue lies. For instance, you may discover that you cannot justify a particular jump between claims. In such a case, you should try to find an opposite proof that shows whether your initial idea was mistaken.

However, if you succeed in making your proof as rigorous as possible, it should be convincing even though it is written in natural language without any formality. Nonetheless, the argument may still be confusing, as it's written in your language and not in a universal language understood by all professionals in your discipline. There may also be some ambiguity in how something is interpreted. For example, if you say “the last number”, it may be unclear who precisely the last number refers to.

Finally, you can rewrite your argument using a stricter, more formal notation. In math, this involves defining every concept you mention, giving them a name, and using variables for referring to objects in your proof. When referring to something previously mentioned, use the name given to it instead of repeating its definition. For example, instead of saying, “That number we just saw”, say, “Let n be the first number that has property p,” and use n in subsequent references.

Formality will also help you identify flaws in your argumentation. If you find it difficult to formalize, your proof sketch is poorly laid out. The formality layer is like a programming language that ensures your proof is sound. If it parses and compiles correctly, it is likely to be true —provided you did the rigorous work first.

An illustrative example

Let me finish with a simple example to illustrate the process of going from intuitive to rigorous to formal argumentation. I will examine the classical proof for the infinite nature of prime numbers. This is one of the fundamental theorems in arithmetic and has a beautiful proof often used to introduce students to the art of mathematical proof-making.

Here’s an intuitive idea of why this must be false.

All numbers are either prime or divisible by some smaller prime(s). If there were finitely many primes, we could build a large number that is not divisible by any of them, multiplying them all together and adding one. But this larger number has to either be prime or have prime factors we didn’t consider.

Now, let’s make that rigorous.

Let’s start by assuming the opposite of what we want to prove. Let’s say there are only finitely many prime numbers. We could list them all out, like this: the first prime number, the second prime number, the third prime number, and so on, until we reach the last prime number.

Now, let’s create a new number. To do this, we multiply all the prime numbers in our list together and then add one to the result. This gives us a big number that is not on our list of primes.

This new number is not divisible by any of the primes in our list. When we divide it by any of our primes, there is always a remainder of one. This is because, by definition, this big number is equal to something multiplied by that prime number plus one.

But every number has some prime divisors, or it is prime. So, either this new number is a prime not in our list, or it has prime factors that were not in our original list.

In either case, we have a contradiction. We assumed that we had a complete list of all the primes, but now we’ve found a prime that wasn’t on our list. This contradiction means that our original assumption (that there are only finitely many primes) must be false. Therefore, there must be infinitely many prime numbers.

The previous proof is rigorous because each claim follows from the previous claims and premises, and there are no hidden assumptions. There is no flawed reasoning, i.e., the logic of the argumentation is sound. However, it is still hard to follow because the lack of formal notation forces us to use phrases like “that number” which may be ambiguous, especially when the argumentation is sufficiently long.

Finally, let’s make it formal:

Due to Substack’s lack of inline math support, we have to put an image here.

It doesn’t matter if you precisely understand every step in this formal demonstration. We can turn a rigorous proof into a formal one simply by carefully naming things and using the proper syntax and notation. However, if the proof is not rigorous, to begin with, no amount of formalization will make it better.

Incidentally, note how, in this formal demonstration, we didn’t need to explicitly differentiate whether m is prime itself or a composite number with a prime divisor not in P. This is just a tiny detail to highlight that, upon formalization, a proof may become more straightforward —if you understand the notation, of course.

Conclusions

Writing is one of the best ways to think clearly. Instead of relying on your faulty memory, if you explicitly lay out your ideas on paper —or electrons, for that matter— you can more easily see if your ideas make sense and discover connections you previously didn’t think of.

However, not all writing is the same. Depending on your purpose, your writing can be more or less detailed and more or less structured. Sometimes, completely unstructured, free-flow writing is precisely what you need to get something out of your mind. However, if your purpose is to be correct and convincing, you’re better off striving to be rigorous and formal.

Formality and rigor are two cornerstones of sound, logically-backed reasoning. By learning to structure and organize your arguments such that they are both rigorous and as formal as necessary —but not overly formal as to make them difficult to understand— you can become a better writer and, ultimately, a better thinker.