Modal logic, knowledge, and an old joke

Recently, I posted about necessary truth and about the logic of belief. I would like to follow up on that by discussing epistemic logic, the logic of knowledge. Knowledge is traditionally understood as justified true belief (more on that below), and we can capture the concept of knowledge using the 4 rules of S4 modal logic. These are in fact the same 4 rules that I used for for necessary truth, and the first 3 rules are the same as those I used for belief (the fourth rule adds the fact that knowledge is true).

Knowledge is specific to some person, and I am replacing the previous modal operators with  Ⓚ  which is intended to be read as “John knows” (hence the K in the circle):

• if P is any tautology, then  Ⓚ P
• if  Ⓚ P  and  Ⓚ (P ⇒ Q)  then  Ⓚ Q
• if  Ⓚ P  then  Ⓚ Ⓚ P
• if  Ⓚ P  then  P

For those who prefer words rather than symbols:

• if P is any tautology, then John knows P
• if John knows both P and (P implies Q), then John knows Q
• if John knows P, then John knows that he knows P
• if John knows P, then P is true

Epistemic logic is useful for reasoning about, among other things, electronic commerce (see this paper of mine from 2000). How does a bank know that an account-holder is authorising a given transaction? Especially if deceptive fraudsters are around? Epistemic logic can highlight which of the bank’s decisions are truly justified. For this application, the first rule (which implies knowing all of mathematics) actually works, because both the bank’s computer and the account-holder’s device can do quite sophisticated arithmetic, and hence know all the mathematical facts relevant to the transaction they are engaged in.

But let’s get back to the idea of knowledge being justified true belief. In his Theaetetus, Plato has Theaetetus suggest exactly that:

“Oh yes, I remember now, Socrates, having heard someone make the distinction, but I had forgotten it. He said that knowledge was true opinion accompanied by reason [ἔφη δὲ τὴν μὲν μετὰ λόγου], but that unreasoning true opinion was outside of the sphere of knowledge; and matters of which there is not a rational explanation are unknowable – yes, that is what he called them – and those of which there is are knowable.” (Theaetetus, 201c)

Although he also uses essentially this same definition in other dialogues, Plato goes on to show that it isn’t entirely clear what kind of “justification” or “reason” is necessary to have true knowledge. In a brief 1963 paper entitled “Is Justified True Belief Knowledge?,” the philosopher Edmund Gettier famously took issue with the whole concept of justified true belief, and provided what seemed to be counterexamples.

My personal opinion, which I have argued elsewhere, is that “justified true belief” works fine as a definition of knowledge, as long as the justification is rigorous enough to exclude beliefs which are “accidentally correct.” For analysing things like electronic commerce, a sufficient level of rigour would involve the use of epistemic logic, as described above.

One of Gettier’s supposed counterexamples involves a proposition of the form  P ∨ Q  (P or Q) such that:

• Smith believes and knows  P ⇒ (P ∨ Q)
• Smith believes P
• P is false
• Q is true, and therefore so is  P ∨ Q

From these propositions we can use doxastic logic to infer that Smith believes the true statement  P ∨ Q,  but we cannot infer (using epistemic logic) that Smith knows  P ∨ Q. A famous old joke is perhaps relevant here:

“A physicist, a philosopher, and a mathematician are travelling through Scotland by train. Through the window, they observe a black sheep in a field. ‘Aha,’ says the physicist, ‘I see that Scottish sheep are black!’ The philosopher responds, ‘No! Some Scottish sheep are black!’ The mathematician, looking shocked, replies: ‘What are you guys saying? All we know is that at least one sheep in Scotland is black on at least one side.’”

---

In this post series: logic of necessary truth, logic of belief, logic of knowledge, logic of obligation

---

Brouwer and his fixed point theorem

    

The Brouwer fixed-point theorem is one of my favourite mathematical theorems. It is named after the Dutch mathematician Luitzen Egbertus Jan Brouwer (above right). Brouwer is also known for his work in Intuitionism. I have mentioned the Brouwer fixed-point theorem before.

The theorem states that any continuous function f on a compact convex set (and specifically, on a disc in the plane) will have at least one fixed point – that is, there will be at least one point p such that f(p) = p. The picture below is intended to illustrate the theorem; it is explained further down.

In the case of a disc, the theorem can be proved by contradiction. Assume that f(p) ≠ p for every point p. Then the pair of f(p) and p always defines a continuous mapping g from p to the boundary of the disc, as illustrated above (left). However, such a continuous mapping is impossible (for complex reasons, but in simple terms, because it creates a hole, which continuous mappings cannot do).

So what about that picture? It shows a continuous function f from the disc to itself, combining an irregular rotation about the centre (rotating least towards the east of the disc) with a “folding” operation that leaves the centre and boundary untouched. The picture below shows a cross-section of the folding in action. The shades of blue in the picture above show how far each point p is from f(p), with lighter colours representing smaller values. Arrows show the action of the function on 6 randomly chosen points. There are two fixed points, marked with black dots: the centre and one other point where the folding and the irregular rotation cancel each other out.

The three-dimensional version of the theorem tells us that, when I stir my morning cup of coffee, at least one speck of liquid will wind up exactly where it started.

---

Fast Fibonacci numbers

There was some discussion on reddit recently of the Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1,597, 2,584, 4,181, 6,765, 10,946, 17,711, 28,657, 46,368, 75,025, 121,393, 196,418, 317,811, 514,229, 832,040, …) and efficient ways of calculating them.

One way of doing so is using numbers of the form a + b σ where  σ is the square root of 5. Multiplication of such numbers satisfies:

(a + b σ) × (c + d σ) = ac + 5bd + (ad + bc) σ.

We can define the golden ratio φ = (1 + σ) / 2 and also ψ = 1 − φ = (1 − σ) / 2, in which case the n^th Fibonacci number F_n will be exactly (φⁿ − ψⁿ) / σ. This is known as Binet’s formula.

We can use this formula to calculate Fibonacci numbers using only integer arithmetic, without ever evaluating the σ. We will have:

(2 φ)ⁿ − (2 ψ)ⁿ = (1 + σ)ⁿ − (1 − σ)ⁿ = 0 + p σ

for some integer p, and division by a power of two will give F_n = p / 2ⁿ.

I am using the R language, with the gmp package, which provides support for large integer matrices, and this allows us to use the relationship:

If we call this matrix A and calculate Aⁿ⁻¹, the first number in the resultant matrix will be the n^th Fibonacci number F_n. The following R code calculates F₁₀ = 55 using a combination of multiplication and squaring:

n <- 10

A <- matrix.bigz(c(
	1, 1,
	1, 0), 2)

p <- function(n) {
	if (n == 1) A
	else if (n %% 2 == 1) A %*% p(n-1)
	else {
		b <- p(n/2)
		b %*% b
	}
}

p(n-1)[1,1]

This same code will calculate, for example:

The time taken to calculate F_n is approximately proportional to n^1.156, with the case of n = 1,000,000,000 (giving a number with 208,987,640 digits) taking about a minute.

---

The High School Solar Car Challenge: some physics

This year I am covering the (High School) Solar Car Challenge, as well as the upcoming university competitions. The high school event will take place at the Texas Motor Speedway on July 15–22 (with Covid protocols in place), and will be live-streamed via the event’s YouTube channel. Today I want to say something about high school solar cars in comparison to world-class cars.

 
Left: Cougar Spirit from Covenant Christian Academy is a high school car in the Advanced Classic Division / Right: Nuna11 is a world-class car from Delft University of Technology in the Netherlands (picture by @lightatwork)

The two main drag forces operating on cars are rolling resistance and aerodynamic drag. The former is indicated in the chart below by red lines. It is a function of the product of the rolling resistance C_rr of the tyres times the mass M of the car in kilograms.

The aerodynamic drag is indicated in the chart below by blue lines. It is a function of the product of the drag coefficient C_d of the body shape, the frontal area A of the car in square metres, and the square of the velocity.

The chart at the bottom of the page expresses the same information in terms of the power (in watts) required to overcome drag at various speeds.

At the world-class level, where special low-rolling-resistance tyres are available and cars glide through the air like a hot knife through butter (low values of C_rr M and C_d A), the aerodynamic drag is much greater than the rolling resistance at race speeds, and shaving a few percent off the C_d A value becomes critical to winning. At high school level, with cars that students can afford and racing speeds from 15 to 50 km/h (10 to 30 mph), aerodynamic drag and rolling resistance are roughly similar, and reducing the weight of the car becomes especially important. Some of the high school classes do not permit hub motors, and for those cars, reducing drive train losses is also critical.

A few high school cars in the Advanced Division are both under 200 kg and quite aerodynamic this year (e.g. Invictus from the Iron Lions and Lumidos from Oregon Solar Car Team), so it will be very interesting to see how they perform.

---

Some knots

I have been reading up on knots recently, so here is a table of 8 knots with up to 6 crossings (plus 2 extras), along with their Conway polynomials. These are polynomials that can be associated with each knot. Different polynomials imply different knots, but sometimes different knots have the same polynomial. Some examples are shown in red below. I have also included pictures of the ten knots mentioned (not drawn by me).

Knot	Conway polynomial
01 (Unknot)	1
31 (Trefoil knot)	z2 + 1
41 (Figure-eight knot)	1 − z2
51 (Cinquefoil knot)	z4 + 3 z2 + 1
52 (Three-twist knot)	2 z2 + 1
61 (Stevedore’s knot)	1 − 2 z2
62 (Miller Institute knot)	− z4 − z2 + 1
63	z4 + z2 + 1
946	1 − 2 z2
10132	z4 + 3 z2 + 1

---

The pancake theorem

A previous post mentioned the Borsuk–Ulam theorem. A corollary (for the case of a circle) is the pancake theorem: given two plane regions, there is a cut (line) which divides both in half by area.

The example shows a cut dividing both South America and Africa in half (the theorem doesn’t tell us how to find the cut; I used simulated annealing).

The corollary for the 2-sphere is the ham sandwich theorem: given three 3-dimensional objects, there is a cut (plane) which divides all three in half by volume.

---

The Borsuk–Ulam theorem

The mathematical tidbit for today is the Borsuk–Ulam theorem, which states that every continuous function f from the n-dimensional sphere to n-dimensional space must satisfy f(p) = f(−p) for some point p.

In particular, every continuous function f from a 2-dimensional sphere (say, the Earth’s surface) to the plane must satisfy f(p) = f(q) for some antipodal pair of points p and q.

Thus, if we can describe weather by a pair of numbers (say, temperature and rainfall), there must be an antipodal pair of points p and q with the same weather (because two numbers specify a point in the plane).

The maps above (for average maximum temperature) and below (for rainfall) show July weather at various places on Earth, and a pair of points with the same weather is highlighted.

It’s a miracle that it works in this case, of course, because the maps only define temperature and rainfall on the land; I would not have been able to recognise a suitable antipodal pair of points if one or both were at sea.

---

The Projective Plane

I have been thinking some more about the famous Möbius strip (see also my post on the Klein bottle). The so-called “Sudanese Möbius Band” in the video above is a Möbius strip stretched so as to make the boundary perfectly circular (it is not named after the country, but after the topologists Sue E. Goodman and Daniel Asimov, and you can purchase a plastic one here).

If we glue two of these Möbius strips together (not actually possible in 3 dimensions), we get a Klein bottle. If we glue one to a disc (also not possible in 3 dimensions), we get a projective plane.

Just for fun, the video below shows a Game of Life glider on the projective plane. The top and bottom of the square are considered to be joined, as are the left and right sides. In both cases, there is a reversal of orientation (a manoeuvre not really possible in 3 dimensions). The glider changes colour as it changes orientation.

Video produced using the R animation package.

---

The Klein Bottle

I have been thinking about the famous Klein bottle (above). To quote a limerick by Leo Moser:

A mathematician named Klein
Thought the Möbius band was divine.
Said he: “If you glue
The edges of two,
You’ll get a weird bottle like mine.”

Just for fun, here is a Game of Life glider on a Klein bottle. The top and bottom of the square are considered to be joined, so as to form a tube. The ends of the tube (vertical sides of the square) are also joined, but with a reversal of orientation (a manoeuvre not really possible in three dimensions). The glider changes colour as it changes orientation.

Video produced using the R animation package.

---

2 + 2 = 4 and mathematical models

One of the strangest aspects of 2020 was a number of people arguing that 2 + 2 = 4 wasn’t necessarily true, and that it might be the case that 2 + 2 = 5. In fact, 2 + 2 = 4 is not only true throughout the universe, it is true in every possible alternate universe as well. A great many silly arguments were made by people trying to defend 2 + 2 = 5. But there is a deeper response here that relates to how applied mathematics works, and a few people have been trying to express that.

In general, applied mathematics questions have the form A → B, where A is some real-world situation, and B our desired but unknown answer. We abstract our real-world situation A to the mathematical object X, so that X → Y is the mathematical analogue of our real-world A → B. Mathematical questions have clearly-defined answers (although finding them is not always easy). We can then take our mathematical answer Y and reverse-translate it to the real world, giving something that we claim is a good approximation to B.

In the mathematical world of X and Y, everything is crisp and clear (and 2 + 2 = 4). In the real world, things are messy and ill-defined. Furthermore, in going from A to X we introduce simplifications and approximations which may mean that the mathematical answer Y is not “fit for purpose.”

For example, our real-world question might be “what is the distance from Melbourne to Sydney?” There are three ambiguities here: What is “Melbourne”? What is “Sydney”? And what is “distance”?

The conventional location marker for the city of Melbourne, Australia is the Old Melbourne General Post Office (now a shopping centre, at 37°48′49″S, 144°57′48″E). Likewise, the conventional location marker for the city of Sydney is the Sydney General Post Office (at 33°52′4″S, 151°12′27″E). Let’s use those coordinates. But what is “distance”? If “distance” means “as the crow flies,” then a simple answer might be to find the great-circle distance on a sphere approximating the Earth (let’s use the equatorial radius of 6,378.137 km). This distance can be calculated fairly easily as 714.2 km, which might be a close enough answer for many purposes.

A better mathematical model might be distance on the WGS reference ellipsoid model of the Earth. This gives the slightly lower value 713.8 km (according to Google Earth or raster::pointDistance).

Alternatively, “distance” might mean “by road,” in which case we need a computer representation of Australia’s road network. For this question, Google Maps reports a distance of 878 km via the M31. The expected travel time by car (9 hours and 7 minutes when I looked) might be even more useful.

It may therefore be the case that out of various mathematical answers Y, many are not “what you wanted.” But that failure to abstract correctly does not invalidate the mathematical truths involved in X → Y. In particular, it does not invalidate 2 + 2 = 4. It just means that you picked up the beautiful crystal knife of mathematics and cut yourself with it.

As Korzybski liked to say, “the map is not the territory.”

---