The diagonal lemma

Figure 1: Diagonalization (where a code for a function is
fed into the function itself)

The diagonal lemma (or fixed point theorem) is an essential part of several notable mathematical proofs including Gödel's incompleteness theorems and Tarski's undefinability theorem.

The term diagonal is used because it bears some resemblance to Cantor's famous diagonal argument.

Intuitively, the diagonal lemma says that for any property A, there is a self-referential statement B saying that it has property A.[1] The lemma is expressed as a logical equivalence:

\[\boldsymbol{B \Leftrightarrow A(\#B)}\]

A can be any property about numbers such as isPrime or isEven. This means that statement B must be translatable to a number, which is indicated by the # in the lemma above. The translation is achieved by Gödel-numbering which assigns a unique natural number to every possible statement.

A simple way to implement Gödel-numbering is by converting the statement to its ASCII representation. So the statement "isEven(2)" translates to the number 69734576656e283229 in hexadecimal (which can be translated with a text to hex converter). That number is also translatable back to the original statement again. Thus there is a one-to-one mapping between a statement and its Gödel number.

Figure 2: Substitution along the diagonal

We can also represent statements containing free variables. For example, the statement "isEven(x)" translates to the Gödel number 69734576656e287829.[2] Now consider the table in Figure 2 where the rows (j) represent the Gödel numbers of statements and the columns (k) represent the possible values for x (themselves natural numbers). We can define the function sub(j, k) to translate Gödel number j as a statement, then substitute number k in place of x and, finally, translate that statement to a Gödel number. For example, sub(69734576656e287829, 8) will translate Gödel number 69734576656e287829 as "isEven(x)" then substitute 8 for x, producing the evaluable statement "isEven(8)" and finally translate that statement to the Gödel number 69734576656e283829.

Since k can be any natural number, we can also substitute the Gödel number of the statement itself. That is, sub(69734576656e287829, 69734576656e287829) will translate Gödel number 69734576656e287829 as "isEven(x)" then substitute 69734576656e287829 for x, producing the evaluable statement "isEven(69734576656e287829)" and finally translate it to Gödel number 69734576656e2836393733343537363635366532383738323929. This particular kind of substitution (where j = k) is called diagonalization because it shows up on the diagonal (i.e., the blue squares) of the table in Figure 2. This self-referential process is key to what follows.

To simplify, the diagonalization can be defined by a function with one free variable x:

\[\boldsymbol{diag(x) = sub(x, x)}\]

I will now declare one further function, C(x), as logically equivalent to the property A applied to diag(x):

\[\boldsymbol{C(x) \Leftrightarrow A(diag(x))}\]

Function C will also have a Gödel number which I'll call m. So m is the Gödel number of the function C which, on input x, is logically equivalent to interpreting x as a function, running x on itself, and then running A on the result (partially illustrated by Figure 1). For example, suppose input x is the Gödel number of "isEven(x)" and A is the property isPrime, then we would have: [3]

\[\boldsymbol{C(\#''isEven(x)'') \Leftrightarrow ~''isPrime(diag(\#''isEven(x)''))''}\]

As noted earlier, # indicates the Gödel number of the subsequent statement. Now suppose that m (the Gödel number of function C) is itself the input to function C. This will result in:

\[\boldsymbol{C(m) \Leftrightarrow A(diag(m))}\]

The diag function interprets m as a function (i.e., C(x)) and substitutes m for x (i.e., C(m)). So:

\[\boldsymbol{C(m) \Leftrightarrow A(\#C(m))}\]

Now let B = C(m) and the result is the diagonal lemma:

\[\boldsymbol{B \Leftrightarrow A(\#B)}\]

When expanded out, B is A(diag(#"A(diag(x))")) which is logically equivalent to the right-hand-side of A(#'A(diag(#"A(diag(x))"))'). For example, suppose that A is the property isEven. Statement B is then 'isEven(diag(#"isEven(diag(x))"))'. That is, B says that the diagonalization of the inner statement is an even number. But the diagonalization of the inner statement just is B's Gödel number. So, in effect, B says of itself that its Gödel number is even. Further saying that the Gödel number of B is even is, therefore, logically equivalent to what B already says of itself.[4]

The diagonal lemma can also be used to construct the famous Gödel statement where A is the property of being unprovable. That is:

\[\boldsymbol{B \Leftrightarrow isNotProvable(\#B)}\]

If B is true, then B is, as it says, not provable. Whereas if B is false, then it is false that it is not provable. That is, it is provable. Thus either statement B is true and not provable, and so the system is incomplete. Or else statement B is false and provable, and so the system is inconsistent (since it can prove a false statement). That is Gödel's first incompleteness theorem.

The diagonal lemma can also be used to construct the liar sentence where A is the property of not being true. That is:

\[\boldsymbol{B \Leftrightarrow isFalse(\#B)}\]

If B is true, then B is false. Whereas if B is false, then B truthfully asserts that. Either way, the result is a contradiction. The conclusion of Tarski's undefinability theorem is that the truth predicate is not definable in the object language, so the liar sentence cannot be constructed.

Useful references:

• Proof of Diagonalization Lemma - p181 - Professor Anita Wasilewska
• Gödel’s First Incompleteness Theorem explained - A Trivial Knot blog (also the source of Figure 2)
• "Diagonal fixed points are constructed with a weird trick where you feed a code for a function into that function itself. Given a function f, if you can construct a function g, which on input x, interprets x as a function, runs x on itself, and then runs f on the result (i.e. g(x) := f(x(x)).), then g(g) is a fixed point of f because g(g) = f(g(g))." - Fixed Point Discussion - Less Wrong
• Gödel numbering and diagonalization - Greg Restall
• Diagonalization & The Fixed Point Lemma - Brendan Cordy
• Fixed point (mathematics) - Wikipedia

--

[1] Strictly-speaking, that the numeric representation of statement B has property A. This is indicated by the # which translates from the statement to a natural number (termed its Gödel number).

[2] In this post, the term statement indicates both formulas with free variables (e.g., "IsEven(x)", where x can be any natural number) and formulas without free variables (e.g., "isEven(2)" or "isEven(3)" which are sentences that evaluate as true or false).

[3] The right-hand-side statement resolves to "isPrime(69734576656e2836393733343537363635366532383738323929)". You can use the hex to text converter to decode the Gödel number.

[4] To step through the final substitution in detail:

The inner statement says, "isEven(diag(x))", i.e., "the diagonalization of x is even". To diagonalize that statement is to substitute its Gödel number for x. That is:

    'isEven(diag(  #"isEven(diag(x))"  ))'

Which is to say, 'the diagonalization of #"the diagonalization of x is even" is even'. While the final statement just is the diagonalization of the inner statement, it also asserts a property of the diagonalization of the inner statement, namely, that it is even. Thus, in effect, the statement is asserting a property of its own Gödel number (that it is even).

Visualizing general relativity

Figure 1: The equivalence between gravity and acceleration

This post is part of a series on visualizing relativity.

As noted in the previous post, the first postulate of special relativity states that the laws of motion are the same in all inertial reference frames.

An inertial frame has no external forces acting on it, so either remains at rest or moves at a constant speed along a straight path. It would seem, then, that special relativity is applicable to gravity-free space but not to Earth where objects in free fall accelerate due to gravity.

This brings us to Einstein's thought experiment. Suppose you are in a compartment where you release an apple and observe it fall to the floor (see Figure 1). This occurs for a compartment at rest on Earth, due to gravity. But the same motion of the apple would also be observed if you were out in space and the compartment were accelerating upward at a rate of 9.8 m/s. There is an equivalence between these two scenarios - the laws of motion with respect to the apple are the same in both reference frames.

Now suppose you are in a compartment where you release an apple and observe it stay in the same position. This would occur for a compartment in free fall on Earth. The compartment and all the objects in it would be accelerating at the same rate, due to gravity though, relative to you in the compartment, the apple would be motionless. But the same (lack of) motion of the apple would also occur if you were out in space and the compartment were at rest. Again, there is an equivalence between these two scenarios - the laws of motion with respect to the apple are the same in both reference frames.

This is Einstein's equivalence principle which motivates the general theory of relativity. The laws of motion are the same for the compartment in free fall whether on Earth or in space. If this is so then it would seem that the compartment in free fall on Earth is an inertial reference frame. But, if so, then there can be no external force acting on it. That is, rather than accelerating, it is either at rest or moving at a constant speed along a straight path.

But how can this be? The apple certainly appears to be accelerating. Einstein's answer was that spacetime itself is curved and the apple follows a straight path (geodesic) through curved spacetime. This is illustrated in Figure 2 below (from this animation). In the Newtonian diagram, the apple is initially hanging on a branch. An upward force (green) is holding the apple and gravity (red) is pushing it down. When the apple falls off the branch, gravity pushes it down to the ground. In the Einsteinian diagram, only an upward force (green) is holding the apple which results in a curved trajectory through spacetime. When the apple falls there are no longer any external forces acting on it, so it follows a straight path through spacetime. Indeed, an accelerometer in free fall will measure zero since there are no forces acting on it.

Figure 2: Newtonian gravity vs Einsteinian curved spacetime

So that's the basic idea behind general relativity. A free falling frame is locally equivalent to an inertial frame and a gravitational field is locally equivalent to an acceleration. [1] We perceive the falling apple as accelerating downward but it's really us that are being accelerated upward by the Earth (as an accelerometer shows) and the falling apple's reference frame is inertial.

Let's now return to Alice and Bob from the previous post on special relativity and see how spacetime curvature affects one's predicted measurements of time and space. The following Epstein diagrams have been generated from Adam Trepczynski's relativity app.

Figure 3: Alice after 1 second in her rest frame

Suppose Alice (in her rocket) is motionless in space, far enough away from any massive objects so that there are virtually no gravitational effects. That is, local spacetime is flat.

As shown in Figure 3, Alice has traveled 0 light seconds [2] in space and aged by 1 second.

The yellow coloring indicates her rocket which, with respect to her rest frame, is not rotated in spacetime and is not contracted in length.

The clocks at the bottom indicate the elapsed coordinate time of 1 second (cyan) and Alice's elapsed proper time, or aging, also of 1 second (purple).

Figure 4: Bob after 1 second in Alice's rest frame

Figure 4 shows Bob (and his rocket) as measured by Alice in her rest frame. In 1 second of her proper time, Bob has traveled 0.6 light seconds in space and aged by 0.8 seconds (Bob's proper time).

The yellow coloring indicates Bob's rocket which is rotated in spacetime and is contracted to 0.8 of its rest length as measured by Alice.

The clocks at the bottom indicate the elapsed coordinate time of 1 second (cyan) and Bob's elapsed proper time of 0.8 seconds (purple).

Figure 5: Alice is stationary (in curved spacetime)

So far, I have described what Alice and Bob measure in situations that are unaffected by gravity.

Now suppose that Alice and Bob are on a massive planet that curves spacetime (note: the planet is to the right along the space axis, with the proper time axis bending away from it). Alice is on a rocket launch pad on the top floor of a (very tall) tower, while Bob is on a floor 0.6 light seconds below.

Note that Alice and Bob are being accelerated upward by the planet and tower. Since Alice is stationary (with respect to her spatial position on the planet), she moves only through time, aging by 1 second, as shown in Figure 5.

This is analogous to the apple's motion through spacetime while it is still hanging on the tree branch.

Figure 6: Bob is stationary (in curved spacetime)

Figure 6 shows Bob on the lower floor (i.e., to the right of Alice on the space axis). He ages 0.63 seconds as measured by Alice who has aged by 1 second, and he remains 0.6 light seconds lower in altitude than her.

This is an example of gravitational time dilation. Bob ages less than Alice since he is closer to the gravitating planet. [3]

Figure 7: Alice in free fall (in curved spacetime)

Now Bob catches the elevator to meet up with Alice on the top floor. Alice, in her rocket, launches off the top of the tower. She is initially at rest (with respect to the planet) and in free fall. Figure 7 shows that after 1 second of coordinate time, Alice has traveled 0.41 light seconds in space (downward) and aged 0.79 seconds.

That effect is what we call gravity. While Alice traveled in a straight line at a constant rate, the curvature of spacetime changed her direction from purely through time to partly through space as well. [4]

A way to visualize the diagram in Figure 7 is as a three dimensional truncated cone. The cyan line will no longer appear straight, but will increasingly curve down the cone.

This is analogous to the apple in free fall increasing in speed over time (relative to the tree branch).

Figure 8: Bob in free fall (in curved spacetime)

In Figure 8 Bob, not to be left behind, launches off the top of the tower with an initial downward velocity of 0.6 times the speed of light and in free fall. After 1 second of coordinate time, Bob has traveled 0.79 light seconds in space (downward) and aged 0.46 seconds.

As with Alice, even though Bob is traveling in a straight line at a constant rate, the curvature of spacetime changes his direction to be proportionally more through space than time than if spacetime were flat. Which is to say, Bob ages less and moves further through space than in Figure 4.

So that's the geometry of spacetime according to general relativity.

To review, the special theory of relativity states that the laws of motion are the same in all inertial (non-accelerating) reference frames. But what about accelerating reference frames? Einstein's subsequent insight was that acceleration and gravity are equivalent. Suppose Alice is on a train and experiences a jerk forwards as the result of the train braking. She can interpret this as the deceleration of the train. Or, equivalently, she can interpret herself as being permanently at rest while the world around her moves under the influence of a gravitational field. [5] Gravity, in turn, can be understood as curvature in spacetime. Thus acceleration can be understood as curvature in spacetime.

The consequence is that while any frame can serve as a rest frame (thus generalizing special relativity), the presence of spacetime curvature means that other frames may only be inertial with respect to that rest frame when in its local neighborhood and for a limited time. Keeping that in mind, the following principle can be stated:

General principle of relativity: The laws of motion are the same in all reference frames

So with reference to the general theory of relativity, what does this mean for Alice? It means that her frame can always be interpreted as a rest frame. And any frame that is accelerating with respect to Alice can be explained by the curved geometry of spacetime. Those rules apply equally for Bob, or any arbitrary reference frame.

--

[1] The equivalence principle is a local equivalence - globally, gravity exhibits tidal effects. Consider also two free falling observers on opposite sides of the Earth. Both are in inertial frames yet, globally, they are accelerating towards each other. So measurements can only be compared locally where spacetime is approximately flat. Finally, consider that gravitation obeys the inverse square law and so will not be equivalent to uniform acceleration over large distances.

[2] 1 light second - the distance light travels in 1 second - is about 300,000 km (or 186,000 miles). The circumference of the Earth is about 40,000 km (or 25,000 miles), so light can travel around the Earth 7.5 times per second.

[3] For an analysis of the curvature of the time axis, see Gravitation and the Curvature of Space-Time. (See also Relativity Visualized, p145, and gravitational redshift.)

[4] Recall Epstein's myth from the previous post - Alice is moving at the speed of light through spacetime (as represented by coordinate time t). But as she progresses she is moving less in time and more in space, with the limit being the speed of light through space. That limit can't be reached in coordinate time t, but can be reached in a finite amount of proper time τ. (See also Relativity Visualized, p150.)

[5] My example is drawn from the following passage in Einstein's book, Relativity: The Special and General Theory:

'It is certainly true that the observer in the railway carriage experiences a jerk forwards as a result of the application of the brake, and that he recognises, in this the non-uniformity of motion (retardation) of the carriage. But he is compelled by nobody to refer this jerk to a "real" acceleration (retardation) of the carriage. He might also interpret his experience thus: " My body of reference (the carriage) remains permanently at rest. With reference to it, however, there exists (during the period of application of the brakes) a gravitational field which is directed forwards and which is variable with respect to time. Under the influence of this field, the embankment together with the earth moves non-uniformly in such a manner that their original velocity in the backwards direction is continuously reduced."'

Einstein's thought experiment is similar to Galileo's in the sense that visual cues in the environment are discounted. While the frames can't be differentiated experimentally, an observer would normally differentiate them based on those visual cues (i.e., that the ship is moving on the water and that the train is decelerating). On this view, the observer's alternative interpretation in Einstein's thought experiment introduces a pseudo-gravitational field and does not involve actual spacetime curvature. General relativity is then reserved for real gravitational fields (due to matter) that exhibit as curvature in spacetime.

Glossary

The equivalence principle: The local effects of motion in a curved spacetime (gravitation) are indistinguishable from those of an accelerated observer in flat spacetime.

A geodesic is a straightest-possible line in a surface or a more general space. In the plane, the geodesics are straight lines, on the surface of a sphere they are great circles.

Gravitational time dilation: clocks in the vicinity of a mass or other source of gravity run more slowly than clocks which are farther away.

Resources

• Relativity Visualized - book by Lewis Carroll Epstein
• Curved spacetime - Epstein illustrations at UCLA Physics and Astronomy
• Epstein Diagrams for the General Theory of Relativity - Epstein explains Einstein
• Relativity flash player app (may require a flash plugin or an older browser)
• General relativity: Einstein vs. Newton
• Einstein Online Dictionary: inertial observer, equivalence principle, general theory of relativity
• The Twin Paradox: The Equivalence Principle Analysis - Michael Weiss (Physics FAQ)

Visualizing special relativity

The twin paradox

This post is part of a series on visualizing relativity.

As noted in the previous post, special relativity is based on two postulates:

1. The laws of motion are the same in all inertial frames
2. The speed of light is the same in all inertial frames

The conventional view is that we live in a three-dimensional world where time proceeds at a constant rate for all of us independent of motion. But Einstein's theory shows that we instead live in a four-dimensional spacetime where space and time are interdependent. (Note: technical terms are explained in the Glossary at the end of this post.)

Lewis Carroll Epstein in his book Relativity Visualized presents a myth for intuitively understanding the special theory of relativity. As he puts it:

Why can't you travel faster than light? The reason you can't go faster than the speed of light is that you can't go slower. There is only one speed. Everything, including you, is always moving at the speed of light. How can you be moving if you are at rest in a chair? You are moving through time. (pp78-79)

So, according to the myth, each of us are always travelling at the speed of light through 4D spacetime. Since Alice is always at rest with respect to herself, that sets her time direction. The three directions perpendicular to her time direction are the space directions that she perceives. If Alice changes her velocity, she rotates in spacetime such that she is now at rest with a new time direction.

When Bob is travelling at close to the speed of light, Alice measures Bob as aging slowly (time dilation) and shortened in the direction of motion (length contraction). This is simply the effect of Bob being rotated in spacetime relative to her and then projected onto Alice's coordinate system. But in Bob's (at rest) reference frame, his wristwatch is running normally and his shape and size are normal. This is analogous to how a round table appears oval when viewed from an angle. However the difference with relativity is that the projection is not simply perceptual, but is the outcome of collecting measurements from local observers who use clocks and rulers.

Alice's measurements of Bob from her rest frame can be represented by an Epstein spacetime diagram [1] as shown in Figure 1 below.

Figure 1: Bob is travelling at 0.6 times the speed of light in space (relative to Alice)

Alice's proper time is on the vertical axis, while her space dimension is perpendicular to it on the horizontal axis (note: only the x-space dimension appears - the y-space and z-space dimensions are omitted). A radius represents 1 light year in a particular direction - vertical (for Alice at rest), horizontal (for a photon) or an intermediate direction (for Bob).

Alice travels 0 light years in space and 1 light year in time, i.e., she ages 1 year. At the other extreme, a photon travels 1 light year in space and 0 light years in time, relative to Alice.

According to Alice's measurements, Bob travels 0.6 light years in space. Bob's proper time can be calculated using the Pythagorean Theorem (where coordinate time is the length of the red arrow - Bob's worldline, Bob's proper time is the spacetime interval, and coordinate space is the distance Bob has traveled according to Alice's measurements): [1]

coordinate time² = Bob's proper time² + coordinate space²

Solving for Bob's proper time, where the coordinate time (the length of Bob's arrow) is 1:

Bob's proper time = √(coordinate time² - coordinate space²)
                  = √(1² - 0.6²)
                  = √(1 - 0.36)
                  = √(0.64)
                  = 0.8 years (or 9.6 months)

Since Bob has only traveled for 0.8 years at a velocity of 0.6c, the distance he has traveled in his rest frame is less than 0.6 light years. Bob's distance (according to his measurements) can be calculated using the usual distance formula:

Bob's proper space = velocity * Bob's proper time
                   = 0.6 * 0.8
                   = 0.48 light years

Figure 2: Alice is travelling at 0.6 times the speed of light in space (relative to Bob)

In Figure 2, the same situation is shown, but from Bob's (at rest) reference frame. This is achieved by rotating the coordinate system such that Bob's arrow is on the proper time axis. Note that it is now Alice that has aged 0.8 years relative to Bob's 1 year.

These results may seem contradictory - how could it be that Bob has aged less than Alice in Alice's reference frame, but Alice has aged less than Bob in Bob's reference frame? The reason is that the time measurement that each person does of the other is a projection onto their proper time axis. To demonstrate this geometrically, Alice and Bob's reference frames are superimposed in Figure 3. Each observer is at rest, but measures the other moving obliquely. The symmetry is similar to two boats drifting apart from each other, and each perceiving the other as smaller. However, as noted earlier, the difference with relativity is that the projection is measurable, not merely perceptual.

Figure 3: Alice and Bob's reference frames superimposed - the situation is symmetrical

If Alice and Bob meet up and compare notes, they will find no contradiction, i.e., they will be the same age, or just one will be younger than the other. To understand how this works, suppose that Bob returns to Alice at (very close to) the speed of light. His elapsed proper time will then be 0.8 years compared to Alice's now 1.6 years (since Alice ages a further 0.6 years during the return leg, while Bob does not age at all). Symmetrically, suppose that Alice returns to Bob at (very close to) the speed of light. Her elapsed proper time will then be 0.8 years compared to Bob's now 1.6 years. The opposite results in each case are due to the change in reference frames of the traveler (which is, in effect, an acceleration by the traveler that they themselves are able to detect).

These are instances of the famous twin paradox. An Epstein diagram can also show a more common rendering of the twin paradox, where Bob reverses course at the mid-point of his journey and returns to Alice at the same speed.

Figure 4: The twin paradox

In Figure 4, Bob travels the same total distance as in Figure 1, however this time he travels 0.3 light years on the outward journey and 0.3 light years on the return journey (in Alice's frame). As with the example above of Bob returning at the speed of light, Bob ages 0.8 years while Alice ages 1 year.

Figure 5: Alice measures the contracted length of Bob's rocket

In Figure 5, Alice and Bob are part of the way along their respective journeys (note: the solid blue and red arrows are the same length), with the lengths of their respective rockets shown (exaggerated to be visible). Since Bob is traveling relative to Alice, Alice measures Bob's rocket to be shorter than its proper length, as projected on her spatial axis. For example, suppose the proper length of Bob's rocket is 0.1 light years. To calculate the length contraction, Bob's rocket can be rotated a quarter anticlockwise turn to lie along Bob's proper time axis (the red arrow) and projected onto Alice's proper time axis. Since the rocket is 0.1 times the length of the unit line, its projection against the proper time axis is 0.1 * 0.8 = 0.08. Rotating back, its projection against the space axis is also 0.08 light years. [2]

Bob would similarly measure Alice's rocket to be shorter than its proper length. (To see this, rotate the coordinate system such that Bob's arrow is on the proper time axis - then project Alice's rocket onto the spatial axis.)

In summary, both the time dilation and length contraction of an observed entity can be understood as projections onto the observer's proper time and spatial axes respectively. An entity observed by Alice to be travelling very close to the speed of light would be measured as having almost no elapsed time on its clock and almost entirely length contracted.

--

[1] The most common spacetime diagram is the Minkowski diagram. However I've instead used the Epstein diagram here due to its intuitive representation (for a comparison, see Figure 6 below). An Epstein diagram is a space-proper-time diagram that shows the worldlines of objects traveling below the speed of light (i.e., on timelike, but not lightlike or spacelike paths). The basis for the Epstein diagram is explained below.

The Euclidean metric for calculating the total distance between points in 3 dimensional space is:

d² = x² + y² + z²

This is just an application of the Pythagorean Theorem in a Euclidean space. Of interest here is that if a 1 meter ruler is rotated in space, the x, y and z coordinates can all change, but d will remain invariant.

The Minkowski metric for calculating the total "distance" (i.e., the spacetime interval L) between points in 3+1 dimensional spacetime is:

L² = x² + y² + z² - (ct)²
   = d² - (ct)²

It can also be expressed with an imaginary term:

L² = x² + y² + z² + (ict)²
   = d² + (ict)²

Or, as an alternative convention, the signs can be flipped (omitting the negative sign on L²):

L² = (ct)² - x² - y² - z²
   = (ct)² - d²

Minkowski space is non-Euclidean. Of interest here is that if a 1 meter ruler is rotated in spacetime, the x, y, z and t coordinates can all change, but L will remain invariant. Note that when d increases, so does t.

Rearranging the equation:

(ct)² = L² + d²

Which looks just like the Pythagorean Theorem! The spacetime interval L is a measure of the observed object's proper time (τ), d is a measure of the traveled distance, c is the speed of light (normalized to 1 in this post) and t is the elapsed coordinate time. Thus:

t² = τ² + d²

That is the basis for the Epstein diagram. In essence, Minkowski diagrams represent a hyperbolic equation (τ² = t² - d²) that is the difference of squares, whereas Epstein diagrams represent a circular equation (t² = τ² + d²) that is the sum of squares.

Figure 6 compares the Epstein and Minkowski diagrams for the twin paradox.

Figure 6: Comparison of Epstein and Minkowski spacetime diagrams

Epstein diagrams are visually intuitive and quantitatively correct. For example, on the Epstein diagram, it is clear that Bob has aged less than Alice since his proper time is shown as less than Alice's proper time when they reunite. Also, the worldlines are the same length, representing the same elapsed coordinate time. Compare with the Minkowski diagram where Bob's shorter proper time is shown by a longer worldline than Alice's.

[2] The geometry is explained here. In particular, note the similar right-triangles indicated by the angle φ. These triangles can be rotated such that their hypotenuse lies along Bob's arrow, allowing the shorter side lengths to be projected onto Alice's axes.

Glossary

An inertial frame is a reference frame that is either at rest or moving at a constant velocity (i.e., not accelerating).

Proper time (or rest time) is the time τ as measured by a clock in a rest frame. On an Epstein diagram (see Figure 6), proper time is represented on the y-axis. On a Minkowski diagram, proper time is represented by the worldlines. While Bob's proper time is shorter than Alice's, it's shown as longer on a Minkowski diagram.

Proper space (proper length, space displacement, rest length, or rest space) is the distance d as measured using standard length rods in a rest frame. On both Epstein and Minkowski diagrams, the observer's proper space is represented on the x-axis.

Coordinate time (or observer's time) is the time t of a moving object measured by an observer at rest. Thus it is the same for all objects. On an Epstein diagram, coordinate time is represented by the worldlines (which are the same length on the diagram). On a Minkowski diagram, coordinate time is represented on the y-axis.

Coordinate space (or observer's length, coordinate length, or coordinate distance) is the distance d that a moving object travels as measured by an observer at rest. Thus it is the same for all objects. On both Epstein and Minkowski diagrams, coordinate space is represented on the x-axis.

Spacetime is a mathematical model that fuses the three dimensions of space and the one dimension of time into a single four-dimensional manifold.

The worldline of an object is the path that the object traces in spacetime.

The spacetime interval between two events is the length of the segment of the worldline connecting the two events. It is invariant, which means that everyone measures the same value.

Resources

• Relativity Visualized - book by Lewis Carroll Epstein
• In relativity, length contracts at high speeds. But what’s contracting? Is it distance or space or is there even a difference? - Ask a Mathematician
• Epstein explains Einstein
• Epstein Relativity Diagrams - Michael Weiss at Diagonal Argument
• Twin paradox flash player app (may require a flash plugin or an older browser)
• The Twin Paradox - Michael Weiss (Physics FAQ)

Visualizing Galilean relativity

Figure 1: Galileo's ship

This post is part of a series on visualizing relativity.

In 1632, Galileo gave a famous example of a ship travelling at constant velocity, without rocking, on a smooth sea. His claim was that any observer below the deck would not be able to tell whether the ship was moving or stationary.


In Figure 1, an experimenter releases a ball which drops vertically between time t1 and time t2. Does this imply that the boat must be stationary in the water? No, because if the boat is moving at a constant velocity, the ball will also move with that constant velocity (in the boat's direction of movement) and land in the same place, relative to the boat. Thus the experimenter is unable to tell whether the boat is moving at a constant velocity or is stationary.

This result is captured in the following principle:

Galilean relativity: The laws of motion are the same in all inertial frames

An inertial frame is simply a reference frame that is either at rest or moving at a constant velocity (i.e., not accelerating).

Note, however, that from the reference frame of the water (as indicated by the fish at rest between time t1 and time t2), the ball will follow a curved (parabolic) path. That is a measurable relativistic effect (in the Galilean sense).

Figure 2: Adding velocities

In Figure 2, a train is travelling at 100km/h and Bob (on the train) shoots an arrow at 200km/h toward the target. At the same time, Alice (on the ground) also shoots an arrow at 200km/h toward the target.

According to Alice, the velocity of Bob's arrow is the velocity of the train plus the velocity of the arrow according to Bob. That is, Alice would measure the velocity of Bob's arrow to be 100km/h + 200km/h = 300km/h. Thus Bob's arrow would hit the target before hers, even though both arrows had the same velocity in their respective frames of reference.

Figure 3: Adding velocities (light)

In Figure 3, Bob fires a laser that emits photons travelling at the speed of light (c) toward the target. Alice fires her laser at the same time. Alice, it seems, would measure the velocity of Bob's light to be c + 100km/h, and Bob's laser light hitting the target before hers.

However that is not what happens! Instead, the light from both lasers hits the target at the same instant and Alice measures the velocity of Bob's light to be c, just as Bob does.

This surprising result lead Einstein to extend Galilean relativity to include the following postulate:

The Principle of Invariant Light Speed: The speed of light is the same in all inertial frames

Galilean relativity and the principle of invariant light speed together comprise Einstein's special theory of relativity. As you may know, this gave rise to a number of unexpected consequences, including relativity of simultaneity, time dilation, length contraction and a new equation for adding velocities.

The next post will explore those consequences and present a way to intuitively visualize special relativity.

Visualizing relativity

The principle of relativity

Suppose Alice is standing on a train platform waving her friend Bob goodbye as the train he is on moves away from the platform. From Alice's perspective, she is standing still on the platform while the train is moving away from her. But from Bob's perspective, he is standing still on the train while the platform is moving away from him.

We suppose that Alice and Bob are describing the same situation, as governed by the same laws of nature, but just from a different vantage point. This idea is captured by the principle of relativity:

Principle of relativity: The laws of nature are the same in every frame of reference

In the train example, Alice and Bob each represent a frame of reference. Those reference frames are relative to each other, hence the name of the principle. And the train scenario is governed by natural laws that are invariant across those reference frames.

This series of posts will show various applications of this principle and how to visualize their effects:

• Galilean relativity
• Special relativity
• General relativity

A proof of the Pythagorean Theorem

A 3-4-5 triangle

The Pythagorean Theorem states that the area of the square on the hypotenuse of a right-angled triangle equals the sum of the areas of the squares on the other two sides. Algebraically (where c is the length of the hypotenuse and a and b are the lengths of the other two sides):

    c² = a² + b²

I thought it would be fun to attempt to prove the theorem for myself. This post describes my solution.

Figure 1: Draw a right-angled triangle with squares

1. Draw a right-angled triangle with squares

• Draw a right-angled triangle
• Draw the squares extending from each side
• Label the sides a, b and c.

Figure 2: Flip the square on the hypotenuse

2. Flip the square on the hypotenuse

• Flip the square on the hypotenuse over
• Mark dotted lines to indicate the larger square containing the flipped square [1]

Figure 3: Label the segments

3. Label the segments

• Mark the segments on each side of the dotted square and label as follows:
• Label the top and right segments a and b as guided by the red and green squares
• Mark the top segment on the left side b, since it is the third side of a right-angled triangle with a and hypotenuse c as the other two sides
• Mark the bottom segment on the left side a, since it is symmetrical to the right side
• Mark the right segment on the bottom side a, since it is the third side of a right-angled triangle with b and hypotenuse c as the other two sides
• Mark the left segment on the bottom side b, since it is symmetrical to the top side

4. Do some algebra

• The area of the square on the hypotenuse equals the area of the large square minus the areas of the triangles in the four corners:

    c² = (a + b)(a + b) - 4(a * b / 2)
       = a² + b² + 2ab - 2ab
       = a² + b²


Which is the Pythagorean Theorem!

It turns out that there are over a hundred possible proofs. The above proof is similar to proof #4 which is credited to the 12th century Hindu mathematician Bhaskara II.

--

Figure 4: Side and corner collinearity

[1] Note that the outer sides of the red and green squares are on the dotted lines. That each outer side is collinear with its adjacent yellow square corner is shown by rotating and shifting the original blue triangle to construct the sides of the flipped yellow square.

The square in the center has a side length of (b - a). As an alternative proof, the area of the square on the hypotenuse equals the area of the center square plus the area of the four triangles:

    c² = (b - a)(b - a) + 4(a * b / 2)
       = b² + a² - 2ab + 2ab
       = a² + b²

Visualizing quantum computations

Figure 1: Quantum parallelism

You are presented with an opaque box that has two buttons labelled A and B. Each button is programmed to glow either red or green when pressed. Can you determine, without investigating inside the box, whether the two buttons are programmed to show the same color or different colors?

The answer, of course, can be determined by pressing each button to see what it does. And it is necessary to press both buttons - pressing just one button won't convey enough information to determine the answer.

Figure 2: Black box function

This scenario can be represented in an algorithm using two binary digits (bits) to represent the color that glows when each respective button is pressed. Analogous to the opaque box, the function that retrieves information about the bits is a black box (see Figure 2) where our focus (for now) is on the inputs and outputs. The algorithm is outlined in the following code fragment.

 1: // constant bit definitions
 2: bitButtonIndex { A = 0, B = 1 }
 3: bitColorIndex { red = 0, green = 1 }
 4:
 5: // black box function declaration
 6: f(input bitButtonIndex) output bitColorIndex;
 7:
 8: bitColorForButtonA = f(A);
 9: bitColorForButtonB = f(B);
10: if (bitColorForButtonA == bitColorForButtonB) then
11:   bitButtonsShowTheSameColor = yes;
12: else
13:   bitButtonsShowTheSameColor = no;

The important thing to note about the above is that the black box function needs to be called twice to determine whether the buttons show the same color.

This same scenario can also be represented on a quantum computer. However in this case the black box function accepts a qubit as input containing the button information and returns a qubit as output containing the color information. The quantum algorithm is outlined in the following code fragment.

 1: // quantum black box function declaration
 2: Uf(input/output qubitX, qubitY); // |x,y> -> |x,y⊕f(x)>
 3:

 4: // variable declarations

 5: qubit x;  // x holds button or (later) color information
 6: qubit y;  // y facilitates use of the black box function
 7:
 8: x = |0>;  // prepare x in a known state

 9: H(x);     // transform x to |+>, i.e., 1/√2(|0> + |1>)

10:
11: y = |0>;  // prepare y in a known state

12: X(y);     // flip state of y to |1>

13: H(y);     // transform y to |->, i.e., 1/√2(|0> - |1>)

14:

15: Uf(x, y); // transform x to |+> or |->

16. H(x);     // transform x from |+> to |0> or from |-> to |1>

17:

18: bitMeasurementResult = M(x); // measure the value of x
19: if (bitMeasurementResult  == 0) then
20:   bitButtonsShowTheSameColor = yes;
21: else
22:   bitButtonsShowTheSameColor = no;

Note that the quantum black box function only needs to be called once to determine whether the buttons show the same color. While the classical function only processes a single specific button at one time, the quantum function can process both button indexes simultaneously. This is represented by the (superposed) state of x as 1/√2(0> + |1>) prior to the call to Uf, where 0 and 1 have the same meaning as per the classical algorithm (i.e., as button indexes for A and B respectively).[1]

Before going into the details of the above code, this algorithm (called Deutsch's Algorithm) is probably the simplest example demonstrating the parallelism of quantum computing - the ability to evaluate all possible inputs to a function simultaneously. Qubits can also be combined to exponentially increase the parallelism. For example, Figure 1 shows a single four-bit input that is processed by a classical computer to produce a single four-bit output. Compare that to the four-qubit input that allows up to 2⁴, or 16, superposed values to be input and then simultaneously processed by a quantum computer to produce 16 superposed values as output.

But there is a major problem! If the qubit returned by the quantum function is in superposition and it is measured, then the superposed state randomly collapses to just one of the two basis states (|0> or |1>) - a single bit of information! So the quantum function needs to encode the answer to our final question such that it can be successfully extracted by a measurement. While quantum computing promises exponential speedup and memory efficiencies, the challenge is to construct algorithms that amplify the right answer and cancel out wrong answers such that the right answer will be measured with high probability.

In fact, this is what the above algorithm is able to do. Note that unlike the classical algorithm, the black box function does not return the colors associated with the specific buttons. Instead, the function returns a result that represents the relative difference in the button colors (if any), whatever those colors happen to be.

Figure 3: Quantum circuit for Deutsch's Algorithm

Now let's turn to the details of the quantum algorithm. The circuit for this algorithm is illustrated in Figure 3. The circuit shows qubit x on the top wire and qubit y on the bottom wire as they are transformed over time (from left-to-right). In quantum mechanics, the functions (or logic gates) are unitary which means, among other things, that they are reversible. Note that the black box function (also termed a quantum oracle) specifies y⊕f(x) as an output. The ⊕ symbol represents an exclusive or (xor) operation.

Per line 9, input x is in state 1/√2(|0> + |1>), representing a superposition of pressing button A and pressing button B. Recall that 0 represents button A and 1 represents button B. If button A glows green, a 180° phase change is applied to state |0>. Similarly, if button B glows green, a 180° phase change is applied to state |1>. This can be expressed by the following formula (derived in [2]) where f is the original classical black box function:

1/√2((-1)^f(0)|0> + (-1)^f(1)|1>)

This reduces to one of the four output states in the following table which can then be changed back to the computational basis state with a Hadamard transform. Note that the measurement ignores the global phase (i.e., the leading minus signs).

Btn A   Btn B  |                                       Same
 f(0)    f(1)  |     Output x      Hadamard   Measure  color?
---------------+---------------------------------------------
red:0   red:0  |   1/√2(|0> + |1>)    |0>        0      yes
grn:1   grn:1  |  -1/√2(|0> + |1>)   -|0>        0      yes
red:0   grn:1  |   1/√2(|0> - |1>)    |1>        1      no
grn:1   red:0  |  -1/√2(|0> - |1>)   -|1>        1      no

Note that the phase change formula and the color results are a mathematical representation of what is occurring within the quantum black box function. While we can measure the output qubit, we cannot access the specific button color information (which is encoded in the phase of the states). Nonetheless the information we can access is sufficient to determine whether the colors are the same.

Figure 4: MZI with a glass sample representing the
color green when button A is pressed

Our original scenario can be modified to utilize quantum parallelism by using a Mach-Zehnder interferometer as our quantum black box. When the paths of the MZI are equal in length (and no samples are present), a photon entering the MZI (and travelling in a superposition of both paths) will always end up at detector 1. To model our scenario, the upper path will represent the pressing of button A while the lower path will represent the pressing of button B. A glass sample placed on either or both of the paths will represent the color green while its absence will represent the color red. The thickness of the glass sample is such that it will change the phase of the photon passing through it by 180°.

The effect of placing a sample on just one of the paths is that the interference at the final beam splitter will result in the photon always ending up at detector 2. Placing a sample on both paths means the photon will accumulate identical phase changes on each path which cancel out. So the effect is that the photon will always end up at detector 1 just as it would when there are no samples present. The glass samples thus implement the exclusive or (xor) operation in our quantum black box. While we are not able to determine the specific colors of the buttons (without investigating inside the black box), we can determine whether the colors are the same or not by observing which detector the photon arrives at.

References:

• Blog post on visualizing qubits
• Blog post on modeling quantum interference
• Quantum Algorithm with an example - Jonathan Hui
• Lecture on the Deutsch Algorithm - Scott Aaronson
• Q#: A Quantum Programming Language by Microsoft
• Simulating a Quantum Computer with a Mach-Zehnder Interferometer - Frank Rioux

"Suppose you are asked if two pieces of glass are the same thickness. The conventional thing to do is to measure the thickness of each piece of glass and then compare the results. As David Deutsch pointed out this is overkill. You were asked only if they were the same thickness, but you made two measurements to answer that question, when in fact it can be done with one." - Frank Rioux

--

[1] The coefficient of 1/√2 is the probability amplitude which, when squared, gives the probability of measuring the associated state. In this case, there is a 1/2 probability of measuring 0 and a 1/2 probability of measuring 1.

[2] The quantum black box function maps |x,y> to |x,y⊕f(x)) where ⊕ symbolizes xor. The input qubits to the function are:

|x> = 1/√2(|0> + |1>)
|y> = 1/√2(|0> - |1>)

Combining the two inputs (where ⊗ symbolizes the tensor product):

|x,y> = 1/√2(|0> + |1>) ⊗ 1/√2(|0> - |1>)
      = 1/2(|0> + |1>)(|0> - |1>)
      = 1/2(|0>(|0> - |1>) +
            |1>(|0> - |1>))

Substituting y⊕f(x) for y:

|x,y⊕f(x)> = 1/2(|0>(|0⊕f(0)> - |1⊕f(0)>) +
                   |1>(|0⊕f(1)> - |1⊕f(1)>))

When f(x) = 0 (indicating red), the state remains unchanged. When f(x) = 1 (indicating green), the sign is flipped. This effect on the phase can be represented as (-1)^f(x) giving (-1)⁰ = 1 and (-1)¹ = -1 respectively. Continuing:

            = 1/2(|0>((-1)^f(0)|0> - (-1)^f(0)|1>) +
                  |1>((-1)^f(1)|0> - (-1)^f(1)|1>))
            = 1/2((-1)^f(0)|0>(|0> - |1>) +
                  (-1)^f(1)|1>(|0> - |1>))
            = 1/2((-1)^f(0)|0> + (-1)^f(1)|1>)(|0> - |1>)
            = 1/√2((-1)^f(0)|0> + (-1)^f(1)|1>) ⊗ 1/√2(|0> - |1>)

So the separate output qubits of the quantum black box function are:

|x> = 1/√2((-1)^f(0)|0> + (-1)^f(1)|1>)
|y> = 1/√2(|0> - |1>)

Note: The reversible xor operation is implemented using a CNOT gate. When applied in the computational basis { |0>,|1> }, x is the control qubit and y is the target qubit. However when applied in the Hadamard basis { |+>,|-> } as above, y becomes the control qubit and x becomes the target qubit, as explained here.