Back Matter

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Appendix A: Gödel’s Theorems

Hilbert’s program was formulated by the mathematician David Hilbert in the early twentieth century. The main goal of this program was to establish the foundations for all mathematics, that is, to define all of mathematics in a single formal system. In other words, the program sought to find a formal system from which one could deduce all possible truths about mathematics. In this appendix, we will show the mathematical answer that was found to address this program.

Definition 1 Gödel numbering is a function that assigns a natural number to each symbol or well-formed formula in a formal system.

For example, within Peano’s axioms, using Definition 1, we can express self-referential expressions at the object level. With this, the system gains additional power of expressiveness; that is, in a way, the formal system becomes “aware” of itself by being able to refer to its own symbols and formulas.

Considering Table A-1 (where ? is the successor function), the following holds, which is a formula about the system within the system itself:¹

Table A-1

Example of Gödel numbering

Symbol	Number
0	1
1	2
S	3
=	4
+	…
…	…

1 = ?(0) ≡ (2, 4, 3, 1) ≡ (?(?(0)), ?(?(?(?(0)))), ?(?(?(0))), ?(0))

As mentioned, the system gains more power of expressiveness, but it is this power that causes the theorems of incompleteness. Let’s now consider the following two statements:

1.
Snow is white.
2.
Snow has four letters.

The first statement is correct, while the second is incorrect. Snow as such does not have four letters (in fact, it does not have a single letter), but “Snow” has four letters. This difference regarding quotation is significant in the proof of Gödel’s theorems of incompleteness.

Definition 2 For an expression P in which the variable ? appears, its diagonalization D (P(?)) is the replacement of the variable ? with the whole expression in quotation marks.

For example, for the expression ? (?) = Boro is reading x, the diagonalization would be ?(? (?)) = Boro is reading “Boro is reading ?”. This allows expressing self-referential statements; consider the following statements:

1.
? (?) – Boro is reading the diagonalization of x
2.
?(?) – Boro is reading the diagonalization of “Boro is reading the diagonalization of x”

The second statement expresses that Boro is reading the diagonalization of the first statement, that is, Q(?)= ?(? (?)). But the diagonalization of the first statement is the second statement, that is, D(? (?)) = ?(?). In fact, the second statement refers to itself.

Definition 3 A formal system F is

Incomplete if there are statements that are true but which cannot be proved to be true in F
Complete if all true statements in F can be proved
Inconsistent if there is a theorem in F that is contradictory
Consistent if there are no contradictory theorems in F

With Gödel numbering, the statement “this statement is not provable in F” can be represented in the system F itself, where the word “this” can be represented using the concept of diagonalization by pointing to the same statement. Hence, the given statement can be either true or false. In case it is true, then it is not provable in F, so this truth cannot be proved in F. Alternatively, if it is false, then it is provable in F, but something that is false cannot be proved. Thus, the system is incomplete because some truths are unprovable in it.

Definition 4 A formal system F contains some statements that cannot be proved in F.

Again, Gödel’s numbering can represent the statement “this statement is false in F ”, where diagonalization can represent the word “this” by pointing to the same statement. The given statement is true if it is false, and therefore, it is neither true nor false. The system is inconsistent.

Definition 5 A formal system F cannot prove itself to be consistent in F.

It follows that there is no formal system² that is both complete and consistent. That is, no system can contain all possible truths, because a given system cannot prove some truths about its own structure. Kurt Gödel proves this with Gödel’s theorems of incompleteness and thus answers Hilbert’s program.

In general, the focus is often on which parts of mathematics can be formalized into specific formal systems, rather than looking for a theory in which all of mathematics can be formalized. A historical overview of the formalization and truthfulness of mathematics is given in [1, 6] where it is noted that “patterns of reasoning cannot be defended forever, at some point faith takes over.” Yet, although imperfect, mathematical systems are still useful tools.

Bibliography

[1]
Hofstadter, Douglas R. Gödel, Escher, Bach: an eternal golden braid. Vol. 13. New York: Basic books, 1979.
[2]
Velleman, Daniel J. How to prove it: A structured approach. Cambridge University Press, 2019.
[3]
Hoare, Charles Antony Richard. “An axiomatic basis for computer programming.” Communications of the ACM 12, no. 10, 1969.
[4]
Leino, K. Rustan M. “Dafny: An automatic program verifier for functional correctness.” In International Conference on Logic for Programming Artificial Intelligence and Reasoning, pp. 348–370. Springer, Berlin, Heidelberg, 2010.
[5]
De Moura, Leonardo, and Nikolaj Bjørner. “Z3-a Tutorial.” Microsoft, Albuquerque, NM, USA, Tech. Rep 2012.
[6]
Nelson, Edward. “Mathematics and Faith.” URL: http://math.princeton.edu/~nelson/papers.html, 2002.
[7]
Sitnikovski, Boro. “Tutorial implementation of Hoare logic in Haskell” arXiv preprint arXiv:2101.11320, 2021.
[8]
Herbert, Luke, K. Rustan M. Leino, and Jose Quaresma. “Using Dafny, an automatic program verifier.” In LASER Summer School on Software Engineering, pp. 156–181. Springer, Berlin, Heidelberg, 2011.
[9]
Halmos, Paul. Naive Set Theory. Courier Dover Publications, 1960.
[10]
Smullyan, Raymond M. The Gödelian Puzzle Book: Puzzles, Paradoxes and Proofs. Courier Corporation, 2013.
[11]
Back, Ralph, Jim Grundy, and Joakim Von Wright. “Structured calculational proof.” Formal Aspects of Computing 9, no. 5–6, 1997.
[12]
Pierce, Benjamin C., Arthur Azevedo de Amorim, Chris Casinghino, Marco Gaboardi, Michael Greenberg, Catalin Hriţcu, Vilhelm Sjöberg, and Brent Yorgey. “Logical foundations.” Electronic textbook 2018.
[13]
McCarthy, John. “Recursive functions of symbolic expressions and their computation by machine, Part I.” Communications of the ACM 3, no. 4, 1960.
[14]
Sitnikovski, Boro. Gentle Introduction to Dependent Types with Idris. Leanpub/Amazon KDP, 2018.

Conclusion

In this book, we introduced the mathematical apparatuses and models that allow us to prove the correctness of software. We also introduced Dafny as an example tool that enables software verification. We learned about mathematical logic, how to represent computation, proofs, specifications (preconditions, postconditions, invariants), and how to build a formal system.

We worked through a bunch of exercises, and we managed to prove some properties about specific algorithms. It is useful to know these concepts and how to use them. Even though you may not be using them daily, the very skill gained by learning them will improve your critical thinking. Invariants, preconditions, and postconditions are useful tools, for example, when using a debugger to resolve a bug in a program. Reasoning in terms of invariants and double-checking assumptions is one of the most important characteristics of a programmer.

Besides verifying basic algorithms, there is also a way to add I/O on top of the verified methods by exporting these methods to a standard programming language, such as C# – this would make an application more practical. Dafny already has support for exporting code, and we encourage the reader to research this further.

One challenge that arises with verification is to accurately define formal software specifications. What specifications should we choose so that we can say with confidence that our software is correct? What does it mean for our software to be correct in the first place? In addition, since most software development today is done iteratively and quickly, this is not always easy as providing specifications is a time-consuming task.

One final observation to make is the connection with mathematics and that almost everything had to do with the simplification of mathematical expressions through the use of formal systems.

Index

Algebra

Algebraic data types

Algorithm

Arrays

Assertions

Assignment rule, Hoare logic

Backus-Naur form

Binary tree

Bounded loops

Bound variable

CalculateProduct

Cartesian product

Computation

algorithm

functions

loops

bounded and unbounded

power and power tail

methods

conditionals

mathematical definition

multiple returns

vs. functions

predicates and lemmas

variables and assertions

Constraint programming

Contrapositive rule

Dafny

as an automated theorem prover

error at compile time

extension

first program

formal systems

installation

Main method

shares features and concepts with languages

specifications

Table of Contents for Back Matter

Create new playlist

Sign In

Sign Up

Table of Contents for
Back Matter