[Part 6] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles First example - Truth table approach

So far in this series, we have been working on the following Knights and Knaves puzzle:

A makes the following statement, "At least one of us is a knave."  

What are A and B?

First, we solved it informally.

Second, we solved it using a rather long, linear formal proof. 

Third, in the previous post, we solved it using a hierarchical, natural deduction-style proof.

In this post, we will solve it using the truth table approach.

A truth table is a two-dimensional representation (as a grid) of all the possible values that a logical formula can take based on the values of the propositions that it contains.

A truth table for formula \(\varphi\) contains one column for each proposition in \(\varphi\). If \(\varphi\) contains \(n\) distinct propositions, the \(n\) leftmost columns of its truth table will correspond to these \(n\) propositions, in arbitrary (usually alphabetical) order.

Each row of the table contains one possible assignment of truth values to all \(n\) propositions in \(\varphi\).

Therefore, the number of rows in a truth table is equal to the total number of distinct assignments of truth values to the propositions in \(\varphi\). 

Since each proposition has exactly two possible values (\(T\) or \(F\), for True or False, respectively), the number of distinct assignments to all \(n\) distinct propositions in a formula is equal to \(2^n\).

The rightmost column in a truth table contains the truth value of the whole formula \(\varphi\) for each assignment of truth values to the propositions in \(\varphi\).

The middle columns of a truth table correspond to sub-formulas of \(\varphi\).

With this layout, the truth table can easily be filled in from left to right, a process that we now illustrate using our Knight and Knaves puzzle.

Recall that our puzzle is represented by the following formula \(\varphi\):

\(A \leftrightarrow (-A\ |\ {-B})\)

In this case, \(\varphi\) contains \(n=2\) propositions, namely \(A\) and \(B\).

We start building our truth table for \(\varphi\) with the two leftmost columns corresponding to \(A\) and \(B\), respectively.

\(A\)	\(B\)
\(F\)	\(F\)
\(F\)	\(T\)
\(T\)	\(F\)
\(T\)	\(T\)

Note that \(n=2\) propositions give use \(2^n = 2^2 = 4\) rows, not counting the header row. 

It is common to order these rows in a systematic way. Here, I ordered them going downward by counting in binary from 0 up to 3 (i.e., 00, 01, 10, 11) while mentally mapping \(F\) to the digit 0 and \(T\) to the digit 1.

Then, since \(-A\) and \(-B\) are the next two smallest sub-formulas in \(\varphi\), we add a column for each one of these sub-formulas based on the truth table for negation:

\(A\)	\(B\)	\(-A\)	\(-B\)
\(F\)	\(F\)	\(T\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)

Next, since \(-A\ |\ {-B}\) is the next smallest sub-formula in \(\varphi\), we add a column for it based on the truth table for disjunction:

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)

Finally, the next smallest sub-formula is \(\varphi\) itself; so we add a final column for it based on the truth table for the biconditional connective:

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)	\(A \leftrightarrow (-A\ |\ {-B})\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)

Looking at the rightmost column in this complete table, we observe that \(\varphi\) is only True in the third row:

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)	\(\varphi\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)

This means that there is only one assignment of truth values to \(A\) and \(B\) that make \(\varphi\) True.

Since \(\varphi\) represents the statement of our puzzle, this means that there is only one solution to the puzzle, namely the one corresponding to the truth values of \(A\) and \(B\) in the third row.

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)	\(\varphi\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)

Not surprisingly, the solution yielded by the truth table approach is the same one yielded by all of our previous proofs:

A is Knight and B is a Knave.

[Part 5] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles First example - A natural-deduction proof

In the previous post, we solved this Knights and Knaves puzzle:

A makes the following statement, "At least one of us is a knave."  

What are A and B?

by writing this formal proof:

Step	True formula	Justification
1.	\(A \leftrightarrow (-A\ |\ {-B})\)	Puzzle statement
2.	\((A \rightarrow (-A\ |\ {-B}))\ \&\  ((-A\ |\ {-B}) \rightarrow A)\)	Formula 1 + Logical equivalence #1 discussed in this post
3.	\((-A\ |\ {-B})\ \rightarrow\ A\)	Formula 2 + Simplification (or Conjunction Elimination)
4.	\(A \rightarrow\ (-A\ |\ {-B})\)	Formula 2 + Simplification (or Conjunction Elimination)
5.	\(-(-A\ |\ {-B})\ |\ A\)	Formula 3 + Logical equivalence #2 discussed in this post
6.	\((-{-A}\ \&\ {-{-B}})\ |\ A\)	Formula 5 + De Morgan's law
7.	\((A\ \&\ {B})\ |\ A\)	Formula 6 + Double negation elimination (applied twice)
8.	\((A\ |\ A)\ \&\ (B\ |\ A)\)	Formula 7 + Distribution of disjunction over conjunction
9.	\(A\ |\ A\)	Formula 8 + Simplification (or Conjunction Elimination)
10.	\(A\)	Formula 9 + Idempotency of disjunction
11.	\(-A\ |\ {-B}\)	Formulas 4,10 + Modus ponens
12.	\(-B\)	Formulas 10,11 + Resolution (generalization of modus ponens)
13.	\(A\ \&\ {-B}\)	Formulas 10,12 + Adjunction (or Conjunction Introduction)

But, as Peter Smith explains, there are several types of proof (or proof system) for propositional logic, including axiomatic systems and natural deduction systems.

An axiomatic system (sometimes called a Hilbert-style deductive system) uses a large number of logical axioms (typically an infinite number of them defined by axiom schemata) and a very small number of (often just one or two) inference rules. 

Note that our proof above does not follow this pattern because it uses a large number of inference rules. Also, the only axiom we use (i.e., the puzzle statement) is not a logical axiom, that is, a formula that is universally true (or true for all possible truth values of A and B).

One feature of our proof that does resemble proofs in axiomatic systems is that it is a linear sequence of formulas that has no internal structure. It does not much look like natural ways of reasoning, e.g., our informal proof in a previous post.

In contrast, natural deduction systems are intended to mimic more closely our informal ways of reasoning. They replace the use of axiom schemata with the application of many inference rules, as we did above. 

Most importantly, natural deduction systems allow us to make temporary suppositions after which we can make inferences "for the sake of argument". These are called "conditional proofs" (denoted by CP below).

For example, a natural way of proving a conditional formula \(A \rightarrow B\) is to suppose, for the sake of argument, that \(A\) is true, making \(A\) a new assumption to be used in the following steps of the proof. Now, if under this assumption, \(B\) can be proved, then we can infer that \(A \rightarrow B\) is true.

When this type of reasoning is allowed, proofs are not linear any longer. They contain (nested) subproofs that give the overall proof a hierarchical (or tree) structure. 

Since we did not use conditional subproofs for our Knights and Knaves puzzle, our proof (repeated above) is rather long and completely linear.

We will now write a natural deduction-style proof for the same puzzle.

First, how are we going to visualize the hierarchical structure of our proof? 

We will use the so-called Fitch notation. Here is an annotated example of this notation taken from page 6 of Peter Smith's write-up, (in which "MP" stands for Modus Ponens, an inference rule that we described earlier in this series):

Smith's example above proves that \(P \rightarrow Q\) and \(Q \rightarrow R\) together imply \(P \rightarrow R\).

Let's now use this approach and this notation to formalize our informal proof by cases presented in this post.

In the first case of that informal proof, we assumed that A was a knave and concluded that this case was impossible. 

Here is a possible, natural deduction-style proof of this reasoning (in which the symbol \(\bot\) denotes "contradiction"):

1.	\(A \leftrightarrow (-A\ |\ {-B})\)		Puzzle statement
2.		\(-A\)	Assumption (Case 1)
3.		\(-A\ |\ {-B}\)	Formula 2 + Disjunction introduction
4.		\(A\)	Formulas 1,3 + Biconditional elimination
5.		\(\perp\)	Formulas 2,4 + Law of non-contradiction
6.	\(-A \rightarrow\, \perp\)		Sub-proof 2-5 + CP

In other words, assuming that A is a knave leads to a contradiction, once we accept the statement of the puzzle as true.

Similarly, we can formalize our reasoning for Case 2 of our informal proof with a natural deduction-style proof like the one below. 

In that case, we assumed that A is a knight and inferred that B must be a knave.

1.	\(A \leftrightarrow (-A\ |\ {-B})\)		Puzzle statement
2.		\(A\)	Assumption (Case 2)
3.		\(-A\ |\ {-B}\)	Formulas 1,2 + Biconditional elimination
4.		\(-B\)	Formulas 2,3 + Resolution
5.	\(A \rightarrow\, {-B}\)		Sub-proof 2-4 + CP

Now, combining both cases, we get:

1. \(-A\) does not hold [Case 1 showed that \(-A\) being true leads to a contradiction]
2. either \(A\) or \(-A\) must hold [law of excluded middle]
3. \(A\) must hold [combining 1. and 2. above] 
4. \(A \rightarrow\, {-B}\) [Case 2]
5. \(-B\) [modus ponens applied to 3. and 4. above]
6. \(A\ \&\ {-B}\) [conjunction introduction applied to 3. and 5. above]

This concludes our natural deduction-style proof by cases of the solution to our first puzzle. Again, the only possible solution is that A must be a knight and B must be a knave.

[Part 4] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles First example - Formal proof

In the previous post, we gave an informal derivation of the solution for the following puzzle:

A makes the following statement, "At least one of us is a knave."  

What are A and B?

In this post, we will present a formal proof of this solution.

First, we must represent this puzzle statement in propositional logic. Applying our representation principle from Part 2 of this series, we represent the first line of this puzzle with the following logical formula:

\(A \leftrightarrow (-A\ |\ {-B})\)

Second, using this formula as our only premise, we must derive one of the following formulas that represent all possible answers to the second line (i.e., the question) in the puzzle:

1. \(A\ \&\ B\)
2. \(-A\ \&\ B\)
3. \(A\ \&\ {-B}\)
4. \(-A\ \&\ {-B}\)

Actually, having already solved the puzzle informally in the previous post, we know that the solution is the third formula above.

Therefore we must build a formal proof of: 

\(A\ \&\ {-B}\) 

assuming only:

\(A \leftrightarrow (-A\ |\ {-B})\)

But what is a formal proof?

It is a sequence of true formulas with the following properties:

1. Each formula in the proof can be true because it is an axiom or an assumption whose truth can be taken for granted with no further justification.
2. Each formula in the proof can be true because it logically follows from one or more formulas that have been proved (or assumed) to be true earlier in the proof.
3. The last formula of the sequence is the one that the proof is meant to establish as a true statement given the agreed upon axioms/assumptions.

In the Knights and Knaves puzzles, the assumptions (part 1 above) will be all of the formulas that make up the statement of the puzzle, that is, all of the facts that are considered to be true if one takes the puzzle statement for granted.

In contrast, the formula to be proved (part 3 above) will be the answer to the puzzle.

Finally, intermediate or inferred formulas (part 2 above) are obtained by applying rules of inference.

A rule of inference is often represented like this:

Premise #1

Premise #2

...

Premise #n

-----------

Conclusion

A rule of inference is a logical step that allows one to infer that a new formula (the conclusion shown below the line) is true based on the truth of one or more premises (previously established true formulas shown above the line). 

For example, modus ponens is the following inference rule:

\(P \rightarrow Q\)

\(P\)

------

\(Q\)

This is a sound inference rule because the conclusion is necessarily true whenever the two premises are true.

There exist many other sound inference rules, some of which we use in the following proof of the solution to our Knights and Knaves puzzle.

Step	True formula	Justification
1.	\(A \leftrightarrow (-A\ |\ {-B})\)	Puzzle statement
2.	\((A \rightarrow (-A\ |\ {-B}))\ \&\  ((-A\ |\ {-B}) \rightarrow A)\)	Formula 1 + Logical equivalence #1 discussed in this post
3.	\((-A\ |\ {-B})\ \rightarrow\ A\)	Formula 2 + Simplification (or Conjunction Elimination)
4.	\(A \rightarrow\ (-A\ |\ {-B})\)	Formula 2 + Simplification (or Conjunction Elimination)
5.	\(-(-A\ |\ {-B})\ |\ A\)	Formula 3 + Logical equivalence #2 discussed in this post
6.	\((-{-A}\ \&\ {-{-B}})\ |\ A\)	Formula 5 + De Morgan's law
7.	\((A\ \&\ {B})\ |\ A\)	Formula 6 + Double negation elimination (applied twice)
8.	\((A\ |\ A)\ \&\ (B\ |\ A)\)	Formula 7 + Distribution of disjunction over conjunction
9.	\(A\ |\ A\)	Formula 8 + Simplification (or Conjunction Elimination)
10.	\(A\)	Formula 9 + Idempotency of disjunction

Let 's take a short breath to rejoice at the fact that we have just proved half of the puzzle's solution, namely the fact that A is a knight!

Luckily, the second half of the solution will be much quicker to prove.

Step	True formula	Justification
11.	\(-A\ |\ {-B}\)	Formulas 4,10 + Modus ponens
12.	\(-B\)	Formulas 10,11 + Resolution (generalization of modus ponens)
13.	\(A\ \&\ {-B}\)	Formulas 10,12 + Adjunction (or Conjunction Introduction)

Which concludes our proof that A must be a knight and B must be a knave!

[Part 3] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles First example - Informal solution

In this post, we will solve our first Knights and Knaves puzzle in a systematic but informal way (the next post in this series will provide a formal proof of this solution).

For our first example, we will use the third puzzle in Chapter 3 (or the \(28^{th}\) puzzle overall) of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". As stated on page 21 of the 2011, paperback Dover Recreational Math edition [ISBN: 9780486481982], the puzzle reads:

A makes the following statement, "At least one of us is a knave."  What are A and B?

One informal, yet systematic approach to solving such a puzzle is to reason by cases. Since each inhabitant is either a knight or a knave, there are only two possible cases for each inhabitant.

Since this puzzle involves two inhabitants, we must pick one of them as a starting point. We'll start with A. [Exercise for the reader: Solve this puzzle with a case analysis based on B instead.]

Case 1: A is a knave

In this case, at least one of the two inhabitants (namely A) is a knave, and thus A's statement is true.

However, it is impossible for A, who is a knave, to make a true statement.

Therefore, this case is impossible.

We could stop here and infer that Case 2 must therefore hold. However, what if Smullyan's alter ego "Sneaky Ray" inserted an unsolvable puzzle into the book without the editor noticing it...

So, we must check that Case 2 is indeed possible!

Case 2: A is a knight 

Since A cannot lie, the statement "At least one of us is a knave." must be true. 

The only way to make it true is for B to be a knave (since A is not one).

Finally, Case 2 is indeed possible and implies that B is a knave.

Solution to the puzzle: A is a knight and B is a knave.

In the next post, we will use propositional logic to demonstrate that this solution is correct using a formal proof.

[Part 2] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles From puzzles to logical formulas

In this post, we discuss how to translate Knights and Knaves puzzles into the formalism of propositional logic, so that, in upcoming posts, we will be able to solve them in a formal way.

As a simple example for this post, we will consider the following puzzle statement:

A said "If B is a knave, then I am a Knight."

If needed, now would be a good time to review the basics of propositional logic given in the first post in this series.

Representing the puzzle in propositional logic

Using the formalism of propositional logic, we can represent the statement "A is a knight." with the proposition \(A\). The choice of this letter for the proposition is completely arbitrary but easy to remember: proposition \(A\) is about person A and it is true when A always tells the truth (i.e., when A is a knight).

Then the negation of \(A\), that is, \(-A\), represents the fact that A is not a knight. Since each inhabitant can only be a knight or a knave, \(-A\) represents the statement "A is a knave.".

Similarly, and for the same reason, we will use the proposition \(B\) to represent the statement "B is a knight." and the formula \(-B\) to represent the statement "B is a knave."

Now, we need to represent A's statement "If B is a knave, then I am a Knight.", in which "I" refers to "A".

This is the conditional \(-B \rightarrow A\).

However, we may NOT add this conditional by itself to our problem statement because we do not know whether or not this formula is true. All we know is that the inhabitant named A said it.

Instead, we must represent the fact that A is the one who made that statement.

Generally speaking, we need a way to represent the fact that person P made statement S. How should we do this? One simple approach is as follows.

Since P is either a knight or a knave, we have two cases to consider: if P is a knight, then everything P says is true, including S. If P is a knave, then everything P says is false, including S.

In other words, the truth value of the proposition \(S\) is always the same as the truth value of the proposition \(P\). They are either both true or both false. 

In propositional logic, we represent this fact with the formula \(P \leftrightarrow S\).

This is the general approach that we will use to represent statements by inhabitants of the island. Hence the following general rule.

---

 Representation principle for Knights and Knaves puzzles

For any person P living on this island and any statement S,
the fact that P said S
will be represented by the formula:

\(P \leftrightarrow S\)

---

Applying this principle to A's statement in our example, we get the formula:

\(A \leftrightarrow (-B \rightarrow A)\)

which is all that we need to represent our puzzle statement in propositional logic.

Solving puzzles with proofs in propositional logic

Next, we will focus on how to use formal reasoning in propositional logic to solve such puzzles, that is, to infer whether A and B are knights or knaves based only on the information given in the puzzle. 

To solve this particular puzzle, we must:

• prove that either \(A\) or \(-A\) is true (and similarly for proposition \(B\)),
• assuming only that \(A \leftrightarrow (-B \rightarrow A)\).

In other words, starting from \(A \leftrightarrow (-B \rightarrow A)\) as an assumption, we must prove that exactly one of the four following formulas is true:

1. \(A\ \&\ B\)
2. \(-A\ \&\ B\)
3. \(A\ \&\ {-B}\)
4. \(-A\ \&\ {-B}\)

In upcoming posts, we will discuss how to solve such puzzles both informally and formally.

[Part 1] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles Quick review of propositional logic

In preparation for a series of posts in which I will discuss Raymond Smullyan's knights and knaves puzzles and how to solve them using logic, this post aims to review a few basics of propositional logic. Note that I will most likely not need first-order (predicate) logic in this series.

Propositional logic represents statements and logical arguments using:

• atomic propositions represented by (propositional) variables that are either true or false, and
• logical connectives, such as:
• AND: we'll use \(\&\) to denote conjunction
• OR: we'll use \(|\) for disjunction
• NOT: we'll use \(-\) for negation
• IF-THEN: we'll use \(\rightarrow\) for implication or conditional
• IF-AND-ONLY-IF: we'll use \(\leftrightarrow\) for biconditional

If needed, you can review logical connectives and their truth tables.

When building proofs, we will use the following well-known logical equivalences (among others).

---

Logical equivalence #1

---

Given any two propositions \(P_1\) and \(P_2\), the following two formulas are equivalent:

\(P_1 \leftrightarrow P_2\)

\((P_1 \rightarrow P_2)\ \&\ (P_2 \rightarrow P_1)\)

In other words, a biconditional is equivalent to the conjunction of two conditionals. 

Informal justification

The fact that 

\(P_1\) if and only if \(P_2\) 

holds is equivalent to the fact that both 

\(P_1\) if \(P_2\) 

and 

\(P_1\) only if \(P_2\) 

hold.

Note that:

\(P_1\) only if \(P_2\)

is represented by

\(P_1 \rightarrow P_2\)

and

\(P_1\) if \(P_2\)

is represented by

\(P_2 \rightarrow P_1\)

Formal justification

Build the truth tables for both formulas \(P_1 \leftrightarrow P_2\) and \((P_1 \rightarrow P_2)\ \&\ (P_2 \rightarrow P_1)\) and check that they have the same truth value in each and every row.

---

Logical equivalence #2

---

Given any two propositions \(P_1\) and \(P_2\), the following two formulas are equivalent:

\(P_1 \rightarrow P_2\)

\( - P_1\ |\ P_2\)

In other words, a conditional is equivalent to a disjunction. 

Justification

The only way to make the formula

\(P_1 \rightarrow P_2\)

false, is to make \(P_1\) true and \(P_2\) false.

This is also true of the second formula

\( -P_1\ |\ P_2\)

Build the truth table for both formulas and check that they have the same truth value in each and every row.

In part 2 of this series, we will use the propositional logic formalism to represent and solve our first knights and knaves problem.

Almost all integers contain the digit 3

This is my last chance to blog this year. However, I did not get back into the proof of Gödel's incompleteness theorem yet. So instead, this post is motivated by this Numberphile video, which explains why almost all integers contain the digit 3. More precisely, the percentage of integers that contain at least one occurrence of the digit '3' in the set \(\mathbb{N}_u = \{0,1,2,3,\cdots,u-1\}\) goes to 100% as the upper bound \(u\) goes to infinity.

We are going to attack this problem with two different approaches. First, we'll use a recurrence relation approach. Second, we'll go over the combinatorial proof discussed in the video. Finally, we'll check that the two approaches do give the same answer.

In both approaches, we will use values of \(u\) that are powers of 10. So if \(u = 10^n\), for \(n \in \mathbb{N}^+\), then the set under consideration \(\mathbb{N}_{10^n}\), which we denote \(A_n\), is the set of all of the (non-negative) integers containing at most \(n\) digits.

Recurrence relation approach

In this approach, we use \(S_n\), for \(n \in \mathbb{N}^+\), to denote the subset of \(A_n\) of all of the integers that contain at least one occurrence of the digit '3' and we use \(T_n\) to denote \(|S_n|\), the cardinality of \(S_n\).

• Since \(A_1=\{0,1,2,3,4,5,6,7,8,9\}\), \(S_1=\{3\}\) and \(T_1=1\).
• Since \(A_2=\{0,1,2,3,4,\cdots,98,99\}\), \(S_2=\{ 3,13,23,30,31,32,33,34,\cdots,39,43,53,63,73,83,93\}\)\(=\{ 3,13,23,43,53,63,73,83,93\}\)\( \cup \{30,31,32,33,34,\cdots,39\}\). In other words, we can split the set \(S_2\) into two subsets, one whose elements all start with the digit '3'  (there are exactly 10 such integers), and the other one whose elements do not start with the digit '3' (there are exactly \(9\cdot T_1\) of those, since if the first digit is not '3' then the least significant digit must belong to \(S_1\)). Thus, \(T_2 = 10 + 9\cdot T_1 = 10 + 9 = 19\).
• Similarly, since \(A_3=\{0,1,2,3,4,\cdots,998,999\}\), \(S_3\) is the union of two sets,  one whose elements all start with the digit '3'  (there are exactly \(10^2\) such integers), and the other one whose elements do not start with the digit '3' (there are exactly \(9\cdot T_2\) of those, since if the most significant digit is not '3' then the number formed by the other digits must belong to \(S_2\)). Thus, \(T_3 = 10^2 + 9\cdot T_2= 100 + 9\cdot 19 = 271\).
• Since this reasoning clearly generalizes to all values of \(n \in \mathbb{N}^+\), we obtain the following recurrence relation:

\[ \left\{ \begin{array}{ll}
                    T_1 = 1 & \\
                    T_n = 10^{n-1} + 9T_{n-1} & \text{if}\ n>1
             \end{array} \right.      
\] Now, let's solve this recurrence relation by iteration to get a closed-form formula for \(T_n\):

\(
\begin{array}{l@{0pt}l}
T_1  & = 1\\
T_2 = 10^1 + 9T_1  & = 10+9 \\
T_3 = 10^2 + 9T_2  & = 10^2+9(10+9) \\
                                 & = 10^2 + 9\cdot 10 + 9^2 \\
T_4 = 10^3 + 9T_3  & = 10^3+9(10^2 + 9\cdot 10 + 9^2) \\
                                 & = 10^3+9\cdot 10^2 + 9^2 \cdot 10 + 9^3\\
T_5 = 10^4 + 9T_4  & = 10^4+9(10^3+9\cdot 10^2 + 9^2 \cdot 10 + 9^3)\\
                                 & = 10^4+9\cdot 10^3+9^2\cdot 10^2 + 9^3 \cdot 10 + 9^4\\
\cdots &\\
T_n = 10^{n-1} + 9T_{n-1} & = 10^{n-1}+9\cdot 10^{n-2}+9^2\cdot 10^{n-3} + \cdots + 9^{n-2}\cdot 10^1 + 9^{n-1}\\
\end{array}
\)

In conclusion, \(\displaystyle T_n = \sum_{i=0}^{n-1} \left(  9^{n-i-1}\cdot 10^i\right) \) for \(n \in \mathbb{N}^+\)

Since this formula is rather ugly, let's turn to the combinatorial approach discussed in the Numberphile video.

Combinatorial approach

It is easy to determine the total number of integers with exactly \(n\) digits without having to enumerate them, namely \(10 \times 10 \times \cdots \times 10 = 10^n\),  since there are exactly 10 digits to choose from for each position in the \(n\)-digit number. Note that this count actually includes all of the numbers with leading zeros, such as 01 and 00023, which are identical to 1 and 23, respectively. In other words, what we really have is  \(\left|A_n\right|= 10^n\).

Similarly, we can compute the total number of integers with at most \(n\) digits that do not contain the digit '3', namely \(9 \times 9 \times \cdots \times 9 = 9^n\), since there are now only 9 digits to choose from at each position in the integer.

In conclusion, \(T_n = 10^n -9^n\).

This is both a much nicer and easier-to-derive closed-form formula than the one we obtained with the recurrence relation approach. But are the two formulas equal?

Let's check our work

Let \(P(n) \), for \(n \in \mathbb{N}^+\), denote: \(\displaystyle \sum_{i=0}^{n-1} \left(  9^{n-i-1}\cdot 10^i\right) = 10^n - 9^n\)

We now prove by mathematical induction that \( P(n)\) holds for  \(n \in \mathbb{N}^+.\)

Basis:

•  \(\displaystyle \sum_{i=0}^{1-1} \left(  9^{1-i-1}\cdot 10^i\right) =  \sum_{i=0}^{0} \left(  9^{1-i-1}\cdot 10^i\right) = 9^{1-0-1}\cdot 10^0 = 9^0 \cdot 10^0 =1 \)
• \( 10^1 - 9^1 = 10 - 9 = 1\)
• Therefore \(P(1)\) holds

Inductive step:

• Assume that \(P(n)\) holds for any \(n \in \mathbb{N}^+\), that is: \[ \sum_{i=0}^{n-1} \left(  9^{n-i-1}\cdot 10^i\right) = 10^n - 9^n \quad \text{[inductive hypothesis]} \]
• Let's compute the left-hand side of \(P(n+1)\):
  \[
  \begin{array}{l@{0pt}l}
  \sum_{i=0}^{n} \left(  9^{n-i}\cdot 10^i\right) & = 9\left(\frac{1}{9}\sum_{i=0}^{n} \left(  9^{n-i}\cdot 10^i\right)\right)\\
      & = 9\left(\sum_{i=0}^{n} \left(  9^{n-i-1}\cdot 10^i\right)\right)\\
     & = 9\left(\sum_{i=0}^{n-1} \left(  9^{n-i-1}\cdot 10^i\right)  + \sum_{i=n}^{n} \left(  9^{n-i-1}\cdot 10^i\right) \right)\\
     & = 9\left(\sum_{i=0}^{n-1} \left(  9^{n-i-1}\cdot 10^i\right)  + \left(  9^{n-n-1}\cdot 10^n\right) \right)\\
   & = 9\left(\sum_{i=0}^{n-1} \left(  9^{n-i-1}\cdot 10^i\right)  + \frac{10^n}{9} \right)\\
  &  = 9\left( \left(10^n - 9^n\right)  + \frac{10^n}{9} \right) \quad \text{by the inductive hypothesis} \\
   & = 9\cdot 10^n - 9\cdot 9^n + 10^n\\
   & = 10\cdot 10^n - 9\cdot 9^n\\
   & = 10^{n+1} - 9^{n+1}\\
  \end{array}
  \]
• Therefore \(P(n+1)\) holds.

Main result

We are now in a position to prove our main result, namely that the percentage of integers that contain the digit '3' in the set \(A_n\)  goes to 100% as \(n\) goes to infinity. This percentage is equal to
\(100\times\frac{T_n}{\left|A_n\right|}=100\times\left(\frac{10^n-9^n}{10^n}\right)=100\times\left(1-\frac{9^n}{10^n}\right)= 100 - 100\left(\frac{9}{10}\right)^n\).
And this percentage goes to 100% as \(n\) goes to infinity, since \(\displaystyle \lim_{n \to \infty}\left( \frac{9}{10}\right)^n = 0\).

Discussion

Of course, all of the proofs above still hold if we had picked the digit '8' (say) instead of the digit '3'. In other words, it is also true that almost all integers contain the digit '8'. So, if we use \(E_n\) to denote the cardinality of the subset of \(A_n\) of all of the integers that contain at least one occurrence of the digit '8', \(E_n = 10^n-9^n\). Similarly for the digit '5' (say): \(F_n = 10^n-9^n\).

But, if both \(100\times\frac{T_n}{\left|A_n\right|}\) and  \(100\times\frac{E_n}{\left|A_n\right|}\) go to 100% as \(n\) goes to infinity, the sum of these two percentages will eventually exceed 100%! That is true. However, this sum double counts all of the integers that contain both the digit '3' and the digit '8'. The correct percentage of such integers is \(100\times\frac{10^n-8^n}{10^n}\), which also goes to 100% as \(n\) goes to infinity.

So there is no paradox here. When \(n\) gets large enough, almost all of the integers will contain all of the digits 0 through 9. Note that all of these results are asymptotic. Indeed, it takes relatively large values of \(n\) for these percentages to get anywhere close to 100%. For example, for the percentage of integers that contain the digit '3' to reach 90%, 95%, 99% and 99.99%, the number \(n\) of digits in the integer must be larger than 21, 28, 43 and 87, respectively.

Robinson Arithmetic is Σ1-complete

Recall that Q (i.e., Robinson Arithmetic) is an axiomatized formal theory (AFT) of arithmetic couched in the interpreted formal language L_A. Let L be a subset of L_A and let T be some AFT of arithmetic.

We say that T is L-sound iff, for any sentence φ in L, if T ⊢ φ, then φ is true.

We say that T is L-complete iff, for any sentence φ in L, if φ is true, then T ⊢ φ.

In chapter 9, Peter Smith defines a subset of L_A, called Σ₁. Then, using the fact that Q is order-adequate, he proves that Q is Σ₁-complete. This is important because the well-formed formulas (wff's) of Σ₁ can express the decidable numerical properties and relations, and therefore Q will be sufficiently strong. Now to the details...

First, let's define a few interesting subsets of L_A:

Robinson Arithmetic is order-adequate

In chapter 9, Peter Smith defines the following concept: A theory T that captures the relation ≤ is order-adequate if it satisfies the following nine properties:

• O1: T ⊢ ∀x (0 ≤ x)
• O2: For any n, T ⊢ ∀x ((x = 0 ∨ x = 1 ∨ x = 2 ∨ ... ∨ x = n) → x ≤ n)
• O3: For any n, T ⊢ ∀x (x ≤ n → (x = 0 ∨ x = 1 ∨ x = 2 ∨ ... ∨ x = n))
• O4: For any n, if T ⊢ φ(0) and T ⊢ φ(1) and ... and T ⊢ φ(n) then T ⊢ (∀x ≤ n)φ(x)
• O5: For any n, if T ⊢ φ(0) or T ⊢ φ(1) or ... or T ⊢ φ(n) then T ⊢ (∃x ≤ n)φ(x)
• O6: For any n, T ⊢ ∀x (x ≤ n → x ≤ Sn)
• O7: For any n, T ⊢ ∀x (n ≤ x  → (n = x  ∨ Sn ≤ x))
• O8: For any n, T ⊢ ∀x (x ≤ n ∨ n ≤ x)
• O9: For any n>0, T ⊢ (∀x ≤ n-1)φ(x) → (∀x ≤ n)(x ≠ n → φ(x))

Then, we have the following theorem:

Robinson Arithmetic captures the "less-than-or-equal-to" relation

In this post, we'll start discussing the material in Chapter 9 of Peter Smith's book, namely up to section 9.3.

Before proceeding, review the definition of Robinson Arithmetic (denoted Q) as well as what it means for a theory to capture a numerical relation.

Now, we'll show that Robinson Arithmetic captures the ≤ numerical relation with the open well-formed formula: ∃x (x + m = n).

In other words, we are going to prove the following two-part theorem:

Theorem: If m and n are natural numbers, then:
1. If m ≤ n, then Q ⊢ ∃x (x + m = n)
2. If m > n, then Q ⊢ ¬ ∃x (x + m = n)

Recall that if m and n are natural numbers, then m and n are the numerical terms representing m and n, respectively, in the formal theory.

Proof sketch of part 1:

Q - Robinson Arithmetic

Now that we are familiar with Baby Arithmetic (BA), we can make its language more expressive by allowing variables and quantifiers back into its logical vocabulary. When we do this, we simply obtain the interpreted language L_A, that was described earlier.

Since we now have variables and quantifiers, we can replace the schemata of BA with regular axioms (see below). The resulting formal system of arithmetic is called Robinson Arithmetic and is often denoted by the letter Q, as described in Chapter 8 of Peter Smith's book. Here is his definition of Q:

Baby arithmetic

Since chapter 7 in Peter Smith's book is so short, I'll summarize it quickly and then start discussing chapter 8.

Chapter 7 starts by comparing the two incompleteness theorems discussed in previous chapters (let's call these "Smith's theorems") to Gödel's first incompleteness theorem as follows:

Consistent, sufficiently strong formal systems of arithmetic are incomplete

In Chapter 6, Peter Smith proves another incompleteness theorem. To place this theorem in context, let's review some definitions about axiomatized formal theories (or AFTs) from earlier posts.

Let T be some AFT.

• T is consistent iff (if and only if) there is no sentence φ such that T proves both φ and ¬ φ.
• T is sound iff every theorem that T proves is true according to the interpretation that is built into T's language.
• T is (negation-)complete iff for every sentence φ in T's language, T proves either φ or ¬ φ.
• T is decidable iff there is an algorithm that, given any sentence φ in T's language, determines whether or not T proves φ.
• If needed, go here to review what it means for T's language to express a numerical property P or a numerical relation R.
• If needed, go here to review what it means for T to capture a numerical property P or a numerical relation R. 
• If needed, go here to review what it means for T's language to be sufficiently expressive.

We'll use the following abbreviations:

Sound formal systems with sufficiently expressive languages are incomplete

In chapter 5, Peter Smith uses a counting argument to prove that sound axiomatized formal theories (AFTs) that can express a good amount of arithmetic are incomplete. In short: since their set of theorems is effectively enumerable but their set of true sentences is not, the two sets must be different. In a sound theory, the theorems are all true. Therefore, some truths must remained unproved in such theories.

Let's start with a definition. The language of an AFT of arithmetic is sufficiently expressive if and only if:

1. It can express quantification over numbers, and
2. It can express every effectively decidable two-place numerical relation.

Now, to the pivotal theorem of this chapter:

An enumerable but not effectively enumerable set

Let's focus on the first half of chapter 5 in Peter Smith's book. First, Smith describes a new characterization of effectively enumerable sets. Second, Smith gives an example of a set of integers that is not effectively enumerable.

Let's define the numerical domain of an algorithm as the set of natural numbers with the following property: when the algorithm takes one of these numbers as input, it terminates and returns a result. Every algorithm has a numerical domain. If the input to some algorithm is not a single natural number, then the numerical domain of this algorithm is the empty set. Otherwise, the numerical domain is the set of those natural numbers on which the algorithm does not crash and does not go into an infinite loop.

It turns out that each numerical domain is effectively enumerable. In fact, the converse is also true, according to the following theorem:

Capturing numerical properties in a formal language of arithmetic

Peter Smith starts Chapter 4 by describing L_A, a formal language that is at the core of several AFTs (axiomatized formal theories) of arithmetic. Then Smith explains what it means for a formal language of arithmetic to "express" a numerical property and the stronger notion of "capturing" a numerical property.

Here is the definition of L_A:

Formal systems or axiomatized formal theories

In chapter 3, Peter Smith defines formal systems or, as he calls them, axiomatized formal theories (I will use AFT as an abbreviation for this phrase).

A theory T is an AFT if...

Effective computability, decidability and enumerability

In Chapter 2, Smith covers familiar ground. So this post will be short. Here is a quick summary, section by section.

Section 1 reviews terminology pertaining to functions, namely the notions of domain and range, as well as special cases of functions, namely injective (or one-to-one) functions, surjective (or onto) functions and bijective functions (or one-to-one correspondences).

Peter Smith's overview of Gödel's incompleteness theorems

Finally! As was my initial goal, I now turn my attention to Peter Smith's book on the proof of Gödel's incompleteness theorems (by the way, I own the first edition of his book; so that is the one I will be referring to). I did not expect to spend that much time on Nagel and Newman's book. But it was worthwhile in getting the big picture.

Chapter 1 is an introductory and user-friendly discussion of topics that were mentioned in earlier posts, such as basic arithmetic, formal systems, (in)completeness, consistency, the statement of Gödel's incompleteness theorems and some of their implications. Therefore, in this post, I will just highlight the points where Smith provides new information or has a different perspective.

Proof sketch of Gödel's incompleteness theorems

In this post, I will follow the outline of the proof given in Section VII of Nagel and Newman's book. Recall that:

• a formal system F is consistent if there is no well-formed formula (wff) w such that F proves both w and ¬ w, and
• a formal system is (semantically) complete if it can prove all of the true wff's that it can express.

Now, Gödel's first incompleteness theorem can be paraphrased as:

Any consistent formal system that is expressive enough to model arithmetic is both incomplete and "incompletable."

and Gödel's second incompleteness theorem can be paraphrased as:

Any consistent formal system that is expressive enough to model arithmetic cannot prove its own consistency.

According to Nagel and Newman, a proof of the first theorem can be sketched in 4 steps:

Mappings and the arithmetization of meta-mathematics

In an earlier post, we discussed mappings in general and then described Gödel numbering, which is a mapping between the set of well-formed formulas (wff's) in a formal system and the set of positive integers.

In part B of section VII, Nagel and Newman describe a more interesting mapping used in Gödel's proof. In this mapping, the domain is the set of meta-mathematical statements about structural properties of wff's, while the co-domain is the set of wff's. This post describes how this mapping enabled Gödel to arithmetize meta-mathematics.

Mappings and Gödel numbering

Section VI of Nagel and Newman's book describes mappings. A mapping is an operation that applies to two sets called the domain and the co-domain. More specifically, a mapping associates to each element of the domain one or more elements of the co-domain.