Quadratic forms over finite fields (of characteristic other than 2)

An n-dimensional quadratic form over a field K is a polynomial in n variables with coefficients in K that is homogeneous of degree 2. More abstractly, a quadratic form on a vector space V is a function V\rightarrow K that comes from a homogeneous degree-2 polynomial in the linear functions on V.

I’ll start off with some comments on why quadratic forms are a natural type of object to want to classify. Then I’ll review well-known classifications of the quadratic forms over \mathbb{R} and \mathbb{C}. Then I’ll give the classification of quadratic forms over finite fields of odd characteristic. Then I’ll go over some counting problems related to quadratic forms over finite fields, which might get tedious. Finally, and perhaps most interestingly, I’ll tell you how \mathbb{R} and \mathbb{C} are secretly related to finite fields, and what this means for quadratic forms over each of them.

I’ll actually just focus on nondegenerate quadratic forms. A quadratic form Q is degenerate if there is a nonzero vector \vec{x} that is “Q-orthogonal” to every vector, meaning that Q(\vec{x}+\vec{y})=Q(\vec{y}) for every vector \vec{y}. In this case, we can change coordinates so that \vec{x} is a standard basis vector, and in these coordinates, Q doesn’t use one of the variables, so the same polynomial gives us an n-1-dimensional quadratic form. We can iterate this until we get a nondegenerate quadratic form, so n-dimensional quadratic forms are in some sense equivalent to at-most-n-dimensional nondegenerate quadratic forms (in terms of abstract vector spaces, a quadratic form on a vector space is a nondegenerate quadratic form on some quotient of it). Because of this, the interesting parts of understanding quadratic forms is mostly just understanding the nondegenerate quadratic forms.

An important tool will be the fact that quadratic forms are essentially the same thing as symmetric bilinear forms. An n-dimensional symmetric bilinear form over a field K is a function \left<-,-\right>:K^n\times K^n\rightarrow K that is symmetric (i.e. \left<\vec{x},\vec{y}\right>=\left<\vec{y},\vec{x}\right>), and linear in each component (i.e., for any \vec{x}, the function \vec{y}\mapsto\left<\vec{x},\vec{y}\right> is linear). From any symmetric bilinear form \left<-,-\right>, we can get a quadratic form Q by Q(\vec{x})=\left<\vec{x},\vec{x}\right>, and from any quadratic form Q, that symmetric bilinear form can be recovered by \left<\vec{x},\vec{y}\right>=\frac{1}{2}\left(Q(\vec{x}+\vec{y})-Q(\vec{x})-Q(\vec{y})\right). This means that there’s a natural bijection between quadratic forms and symmetric bilinear forms, so I could have just as easily said this was a post about symmetric bilinear forms over finite fields (of characteristic other than 2). Throughout this post, whenever Q denotes some quadratic form, I’ll use \left<-,-\right>_Q to denote the corresponding symmetric bilinear form. Of course, this bijection involves dividing by 2, so it does not work in characteristic 2, and this is related to why the situation is much more complicated over fields of characteristic 2.

In coordinates, quadratic forms and symmetric bilinear forms can both represented by symmetric matrices. A symmetric matrix A represents the quadratic form Q(\vec{x}):=\vec{x}^TA\vec{x}, and the corresponding symmetric bilinear form \left<\vec{x},\vec{y}\right>_Q:=\vec{x}^TA\vec{y}. From the symmetric bilinear form, you can extract the matrix representing it: A_{i,j}=\left<\vec{e}_i,\vec{e}_j\right>_Q, where \vec{e}_1,\ldots,\vec{e}_n are the standard basis vectors.

Two quadratic forms are equivalent if you can turn one into the other with an invertible linear transformation. That is, Q_1 and Q_2 are equivalent if there’s an invertible linear transformation \varphi such that Q_2(\vec{x})=Q_1(\varphi(\vec{x})) for every vector \vec{x}. In coordinates, quadratic forms represented by matrices A and B are equivalent if there’s an invertible matrix M such that B=M^TAM. When I said earlier that I would classify the quadratic forms over \mathbb{R}, \mathbb{C}, and finite fields of odd characteristic, what I meant is classify nondegenerate quadratic forms up to this notion of equivalence.

Why quadratic forms?

Quadratic forms are a particularly natural type of object to try to classify. When I say “equivalence” of some sort of linear algebraic object defined on a vector space K^n (over some field K), one way of describing what this means is that \text{GL}_n(K) naturally acts on these objects, and two such objects are equivalent iff some change of basis brings one to the other. Equivalence classes of these objects are thus the orbits of the action of \text{GL}_n(K).

\text{GL}_n(K) is n^2-dimensional, so if we have some m-dimensional space of linear algebraic objects defined over K^n, then the space of equivalence classes of these objects is at least m-n^2-dimensional. So, if m>n^2, then there will be infinitely many equivalence classes if K is infinite, and even if K is finite, the number of equivalence classes will grow in proportion to some power of |K|.

For example, for large n, the space of cubic forms, or symmetric trilinear forms, on K^n is approximately \frac{1}{6}n^3-dimensional, which is much greater than n^2, so the space of equivalence classes of symmetric trilinear forms is also approximately \frac{1}{6}n^3-dimensional, and counting cubic forms up to equivalence rather than individually barely cuts down the number of them at all, leaving us with no hope of a reasonable classification. The same issue kills pretty much any attempt to classify any type of tensor of rank at least 3.

The space of (not necessarily symmetric) bilinear forms is n^2-dimensional. But bilinear forms can be invariant under certain changes of coordinates, so the space of bilinear forms up to equivalence is still positive-dimensional. It isn’t enormously high-dimensional, like the space of cubic forms up to equivalence, so this doesn’t necessarily rule out any sort of reasonable classification (in fact, linear maps, which are also n^2-dimensional, do have a reasonable classification. There’s the Jordan normal form for linear maps defined over algebraically closed fields, and the Frobenius normal form for arbitrary fields). But it does mean that any such classification isn’t going to be finitistic, like Sylvester’s law of inertia is.

Classifying objects is also not too interesting if there’s very few of them for very straightforward reasons, and this tends to happen if there’s far fewer than n^2 of them, so that it’s too easy to change one to another by change of coordinates. For instance, the space of vectors is n-dimensional, and there’s only two vectors up to equivalence: the zero vector, and the nonzero vectors.

To get to the happy medium, where there’s a nontrivial zero-dimensional space of things up to equivalence, you want to start with some space of objects that’s just a bit less than n^2-dimensional. Besides quadratic forms / symmetric bilinear forms, the only other obvious candidate is antisymmetric bilinear forms. But it turns out these are already fairly rigid. The argument about classifying symmetric bilinear forms reducing to classifying the nondegenerate ones applies to antisymmetric bilinear forms as well, and, up to equivalence, there’s not that many nondegenerate antisymmetric bilinear forms, also known as symplectic forms: Over any field, there’s only one of them in each even dimension, and none at all in odd dimensions.

Classification of quadratic forms over certain infinite fields

Let’s start with \mathbb{R} (though the following theorem and proof work just as well for any ordered field containing the square root of every positive element). We’ll use this same proof technique for other fields later.

Theorem (Sylvester’s law of inertia): For an n-dimensional nondegenerate real quadratic form Q, let n_+ denote the maximum dimension of a subspace on which Q takes only positive values, and let n_- denote the maximum dimension of a subspace on which Q takes only negative values. Then n_+ + n_- = n, and Q is equivalent to the quadratic form represented by the diagonal matrix whose first n_+ diagonal entries are 1 and whose last n_- diagonal entries are -1. All pairs of nonnegative integers (n_+,n_-) summing to n are possible, and (n_+,n_-) completely classifies nondegenerate real quadratic forms up to isomorphism. Thus, up to equivalence, there are exactly n+1 nondegenerate n-dimensional real quadratic forms.

Proof: First we’ll show that every quadratic form can be diagonalized. We’ll use induction to build a basis \vec{b}_1,\ldots,\vec{b}_n in which a given quadratic form Q is diagonal. For the base case, it is trivially true that every 0-dimensional quadratic form can be diagonalized (and 1-dimensional quadratic forms are just as straightforwardly diagonalizable, if you prefer that as the base case). Now suppose every n-1-dimensional quadratic form is diagonalizable, and let Q be an n-dimensional quadratic form. Let \vec{b}_1 be any vector with Q(\vec{b}_1)\neq0 (if this is not possible, then Q=0, and is represented by the zero matrix, which is diagonal). Then \vec{b}_1^\perp := \left\{\vec{x}\mid\left<\vec{b}_1,\vec{x}\right>_Q=0\right\} is an n-1-dimensional subspace disjoint from \vec{b}_1. Using the induction hypothesis, let \vec{b}_2,\ldots,\vec{b}_n be a basis for \vec{b}_1^\perp in which Q\restriction_{\vec{b}_1^\perp} is diagonal. Then \vec{b}_1,\ldots,\vec{b}_n is a basis in which Q is diagonal (its matrix has Q(\vec{b}_1) in the upper left entry, the diagonal matrix representing Q\restriction_{\vec{b}_1^\perp} in the basis \vec{b}_2,\ldots,\vec{b}_n in the submatrix that excludes the first row and column, and the fact that \left<\vec{b}_1,\vec{b}_i\right>_Q=0 for i\neq1 means that the rest of the first row and column are zero).

Now that we’ve diagonalized Q, we can easily make those diagonal entries be \pm1, assuming Q is nondegenerate (otherwise, some of them will be 0). If Q(\vec{b}_i)>0, then Q\left(\frac{\vec{b}_i}{\sqrt{Q(\vec{b}_i)}}\right)=1. If Q(\vec{b}_i)<0, then Q\left(\frac{\vec{b}_i}{\sqrt{-Q(\vec{b}_i)}}\right)=-1. Either way, we can replace \vec{b}_i with some scalar multiple of it such that Q(\vec{b}_i)=\pm1.

The ordering of the diagonal entries doesn’t matter because we can permute the basis vectors so that all the +1‘s come before all the -1‘s. So all that remains to show is that any two quadratic forms whose \pm1 diagonal matrices have different numbers of +1‘s are not equivalent. Let n_+ be the number of +1‘s and let n_- be the number of -1‘s, so that our diagonalized quadratic form can be written as x_1^2+\ldots+x_{n_+}^2-y_1^2-\ldots-y_{n_-}^2. There is an n_+-dimensional subspace P on which it only takes positive values (the subspace defined by y_1=\ldots=y_{n_-}=0), and an n_--dimensional subspace N on which it only takes negative values (the subspace defined by x_1=\ldots=x_{n_+}=0). It can’t have an (n_++1)-dimensional subspace on which it takes only positive values, because such a subspace would have to intersect N, and similarly, it can’t have an (n_-+1)-dimensional subspace on which it takes only negative values, because such a subspace would have to intersect P. Thus the number of +1‘s and -1‘s are the maximum dimensions of subspaces on which the quadratic form takes only positive values and only negative values, respectively, and hence quadratic forms with different numbers of +1‘s are not equivalent. \square

Over \mathbb{C}, things are simpler.

Theorem: All n-dimensional nondegenerate complex quadratic forms are equivalent to each other.

Proof: As in the real case, we can diagonalize any quadratic form; the proof of this did not depend on the field. But in \mathbb{C}, every number has a square root, so each basis vector \vec{b}_i can be scaled by \frac{1}{\sqrt{Q(\vec{b}_i)}}, to get a vector that Q sends to 1 (of course, Q(\vec{b}_i) has two square roots, but you can just pick one of them arbitrarily). Thus every nondegenerate complex quadratic form is equivalent to the quadratic form defined by the identity matrix. \square

Note that this proof works just as well over any quadratically closed field not of characteristic 2.

Over other fields, things get a bit complicated. One class of fields you might want to consider is the p-adic numbers, and there is a known classification (called the Hasse invariant) of quadratic forms over \mathbb{Q}_p (and its finite extensions), but it involves Brauer groups, for some reason.

Over the rationals, things are even worse. The best result about classifying rational quadratic forms we have is the Hasse-Minkowski theorem: Over any finite extension of \mathbb{Q}, two quadratic forms are equivalent iff they are equivalent over every non-discrete completion of the field (so, they are equivalent over \mathbb{Q} itself iff they are equivalent over \mathbb{R} and over \mathbb{Q}_p for every prime p). An interesting result, but not one that lets you easily list out equivalence classes of rational quadratic forms.

But over finite fields, things go back to being relatively straightforward.

Classification of nondegenerate quadratic forms over finite fields of odd characteristic

Let q be a power of an odd prime, and let \mathbb{F}_q denote the field with q elements.

\mathbb{F}_q has a certain feature in common with \mathbb{R}: exactly half of its nonzero elements are squares. For \mathbb{F}_q, you can show this with a counting argument: every nonzero square is the square of exactly two nonzero elements, and there are finitely many nonzero elements. For \mathbb{R}, it might not be obvious how to formally make sense of the claim that exactly half of nonzero reals are squares (i.e. positive). One way is to notice that the positive reals and negative reals are isomorphic as topological spaces. But what matters in this context is that the quotient group \mathbb{R}^\times/(\mathbb{R}^\times)^2 has order 2, just like \mathbb{F}_q^\times/(\mathbb{F}_q^\times)^2 (here K^\times means the group of units of a field K). Now let’s see how this relates to quadratic forms.

The part of the proof of Sylvester’s law of inertia that shows that every nondegenerate real symmetric form can be diagonalized with diagonal elements \pm1 can be generalized to an arbitrary field:

Lemma 1: Let K be a field, and let X be a set of elements of K^\times consisting of one element from each coset of (K^\times)^2. Then every nondegenerate quadratic form over K is equivalent to one represented by a diagonal matrix with elements of X on the diagonal.

Proof: As in the proof of Sylvester’s law of inertia, with \{1,-1\} replaced with the set X. \square

Since (\mathbb{F}_q^\times)^2 has exactly 2 cosets in \mathbb{F}_q^\times, this means there is a set X of size 2 (if q\equiv3\pmod4, then -1 is nonsquare, and you could use X=\{1,-1\} again) such that every n-dimensional nondegenerate quadratic form over \mathbb{F}_q is equivalent to one represented by a diagonal matrix with elements of X on the diagonal, and thus there are at most n+1 of them up to equivalence. However, we have not shown that these quadratic forms are inequivalent to each other (that part of the proof of Sylvester’s law of inertia used the fact that \mathbb{R} is ordered), and in fact, this is not the case. Instead, the following lower bound ends up being tight over finite fields of odd characteristic:

Lemma 2: Let K be a field. Any two invertible symmetric matrices whose determinants are in different cosets of (K^\times)^2 represent inequivalent quadratic forms (that is, if their determinants are a and b, and \frac{a}{b} is nonsquare, then the matrices do not represent equivalent quadratic forms). Thus, for n\geq1, there are at least \left|K^\times/(K^\times)^2\right| nondegenerate n-dimensional quadratic forms over K up to equivalence.

Proof: If invertible symmetric matrices A and B represent equivalent quadratic forms, then there is some change of basis matrix M such that B=M^TAM. \frac{\det(B)}{\det(A)}=\det(M)^2. If n\geq1, then for every element of K^\times, there is a symmetric matrix that has that determinant, so the fact that symmetric matrices whose determinants are in different cosets of (K^\times)^2\right| represent inequivalent quadratic forms implies that there are inequivalent nondegenerate quadratic forms for each coset. \square

What’s going on here is that there’s a notion of the determinant of a bilinear form that doesn’t depend on a matrix representing it in some basis. For every n-dimensional vector space V, there’s an associated 1-dimensional vector space \wedge^n V, called the space of volume forms on V. Elements of \wedge^n V are called volume forms because, over \mathbb{R}, they represent amounts of volume (with orientation) of regions in the vector space. This is not exactly a scalar, but rather an element of a different 1-dimensional vector space, because, in a pure vector space (without any additional structure like an inner product), there’s no way to say how much volume is 1. I won’t give the definition here, but anyway, a bilinear form f on a vector space V induces a bilinear form \det(f) on \wedge^n V. A basis for V induces a basis for \wedge^n V, in which \det(f) is represented by a 1\times1 matrix (i.e. scalar) that is the determinant of the matrix representing f. An automorphism \sigma of V induces an automorphism of \wedge^n V, which is multiplication by \det(\sigma), and thus induces an automorphism of the space of bilinear forms on \wedge^n V given by division by \det(\sigma)^2. Thus if the ratio of the determinants of two nondegenerate bilinear forms is not a square, then the bilinear forms cannot be equivalent. This also applies to quadratic forms, using their correspondence to symmetric bilinear forms.

Theorem: Up to equivalence, there are exactly two n-dimensional nondegenerate quadratic forms over \mathbb{F}_q (for n\geq1).

Proof: Lemma 2 implies that invertible symmetric matrices of square determinant and invertible symmetric matices of nonsquare determinant represent inequivalent quadratic forms. It remains to show that any two invertible symmetric matrices with either both square determinant or both nonsquare determinant represent equivalent quadratic forms.

Let \alpha,\beta\in \mathbb{F}_q^\times be square, and nonsquare, respectively. By lemma 1, every nondegenerate quadratic form over \mathbb{F}_q can be represented with a diagonal matrix whose diagonal entries are all \alpha or \beta. The determinant is square iff an even number of diagonal entries are \beta. It suffices to show that changing two \alpha‘s into \beta‘s or vice-versa doesn’t change the equivalence class of the quadratic form being represented. Thus this reduces the problem to show that the 2-dimensional quadratic forms represented by \alpha I_2 and \beta I_2 are equivalent. If we can find a,b\in\mathbb{F}_q such that a^2+b^2=\frac{\beta}{\alpha}, then the change of basis matrix \left(\begin{array}{cc} a & -b\\ b & a \end{array}\right) will do, because \left(\begin{array}{cc} a & b\\ -b & a \end{array}\right)\left(\begin{array}{cc} \alpha & 0\\ 0 & \alpha \end{array}\right)\left(\begin{array}{cc} a & -b\\ b & a \end{array}\right)=\left(\begin{array}{cc} \beta & 0\\ 0 & \beta \end{array}\right). This reduces the problem to showing that there are such a,b.

The squares in \mathbb{F}_q cannot be an additive subgroup of \mathbb{F}_q, because there are \frac{q+1}{2} of them, which does not divide q. Thus there are \tilde{a},\tilde{b}\in\mathbb{F}_q such that \tilde{a}^2+\tilde{b}^2 is nonsquare. Since \mathbb{F}_q^\times/(\mathbb{F}_q^\times)^2 has order 2, and \frac{\beta}{\alpha} is also nonsquare, it follows that \frac{\beta/\alpha}{\tilde{a}^2+\tilde{b}^2} is a square. Let c^2=\frac{\beta/\alpha}{\tilde{a}^2+\tilde{b}^2}, and let a=c\tilde{a} and b=c\tilde{b}. Then a^2+b^2=\frac{\beta}{\alpha}, as desired. \square

Note, as a consequence, if we count the degenerate quadratic forms as well, there are 2n+1 n-dimensional quadratic forms over \mathbb{F}_q up to equivalence: 2 for every positive dimension that’s at most n, and 1 more for dimension 0 (this is the zero quadratic form; there are no zero-dimensional quadratic forms of nonsquare determinant).

Counting

Given an n-dimensional quadratic form Q over \mathbb{F}_q, and some scalar \alpha\in\mathbb{F}_q, how many vectors \vec{v} are there such that Q(\vec{v})=\alpha? There are q^n vectors \vec{v}, and q possible values of Q(\vec{v}), so, on average, there will be q^{n-1} vectors with any given value for the quadratic form, but let’s look more precisely.

First, note that we don’t have to check every quadratic form individually, because if two quadratic forms are equivalent, then for any given scalar \alpha, each form will assign value \alpha to the same number of vectors. And it’s enough to check nondegenerate forms, because every quadratic form on a vector space V corresponds to a nondegenerate quadratic form on some quotient V/W, and the number of vectors it assigns a given value is just q^{\dim(W)} times the number of vectors the corresponding nondegenerate quadratic form assigns the same value. So we just have to check 2 quadratic forms of each dimension.

And we don’t have to check all q scalars individually because, if \frac{\alpha}{\beta} is a square, then multiplication by its square root is a bijection between \{\vec{v}\mid Q(\vec{v})=\alpha\} and \{\vec{v}\mid Q(\vec{v})=\beta\}. So there’s only 3 cases to check: \alpha=0, \alpha is a nonzero square, or \alpha is nonsquare. If the dimension is even, there’s even fewer cases, because a quadratic form is equivalent to any nonzero scalar multiple of it, so each nonzero scalar \alpha has the same number of vectors that Q sends to \alpha. Thus, for any 2n-dimensional quadratic form Q, there will be some number c such that, for each \alpha\neq0, \left|\{\vec{v}\mid Q(\vec{v})=\alpha\}\right|=q^{2n-1}+c, and \left|\{\vec{v}\mid Q(\vec{v})=0\}\right|=q^{2n-1}-(q-1)c.

And it turns out that in odd dimensions, for any nonzero quadratic form Q, the probability that Q(\vec{v})=0 for a randomly selected vector \vec{v} is exactly \frac{1}{q}. To see this, we can reduce to the 1-dimensional case (which is clear because there’s q vectors and only \vec{0} gets sent to 0 by Q): Given a 2n+1-dimensional quadratic form Q, let L be a 1-dimensional subspace on which Q is nonzero, and let H=\left\{\vec{v}\mid\left<\vec{v},\vec{\ell}\right>_Q=0\,\forall\ell\in L\right\}. Then every vector is uniquely a sum \vec{\ell}+\vec{h} for some \vec{\ell}\in L and \vec{h}\in H, and Q(\vec{\ell}+\vec{h})=Q(\vec{\ell})+Q(\vec{h}). Since Q\restriction H is a quadratic form on the 2n-dimensional space H, there’s some number c such that for each \alpha\neq0, \left|\{\vec{h}\in H\mid Q(\vec{h})=\alpha\}\right|=q^{2n-1}+c, and \left|\{\vec{h}\in H\mid Q(\vec{h})=0\}\right|=q^{2n-1}-(q-1)c. For \vec{\ell}\in L and \vec{h}\in H, Q(\vec{\ell}+\vec{h})=0 iff Q(\vec{\ell})=Q(\vec{h})=0 (1\cdot(q^{2n-1}-(q-1)c) ways for this to happen) or Q(\vec{h})=-Q(\vec{\ell})\neq0 ((q-1)\cdot(q^{2n-1}+c) ways for this to happen), for a total of q^{2n-1}-(q-1)c + (q-1)(q^{2n-1}+c) = q^{2n} vectors \vec{v} such that Q(\vec{v})=0. Since there’s the same number of nonzero squares as nonsquares, it follows that there is some number d such that for each \alpha\neq0, \left|\{\vec{v}\mid Q(\vec{v})=\alpha\}\right|=q^{2n-1}+d if \alpha is square, and \left|\{\vec{v}\mid Q(\vec{v})=\alpha\}\right|=q^{2n-1}-d if \alpha is nonsquare.

We can compute these offsets c and d recursively. We can represent quadratic forms of square determinant with the identity matrix (i.e. x_1^2+\ldots+x_n^2). The number of vectors (x_1,\ldots,x_n) such that x_1^2+\ldots+x_n^2=\alpha is \sum_{\beta\in\mathbb{F}_q}\left|\left\{(x_{n-1},x_n)\mid x_{n-1}^2+x_n^2=\alpha-\beta\right\}\right|\cdot\left|\left\{(x_1,\ldots,x_{n-2})\mid x_1^2+\ldots+x_{n-2}^2=\beta\right\}\right|. (Why do I suggest decrementing n by 2 at a time? You could also try decrementing n by 1 each step, but I think 2 is easier because of the significance of the parity of the dimension). We can represent quadratic forms of nonsquare determinant with a matrix that is the identity except for the last diagonal entry being replaced with a nonsquare, and then compute how many vectors it assigns each scalar in terms of the square-determinant quadratic forms of one lower dimension.

It turns out that it matters whether -1 is a square in \mathbb{F}_q. To see this, consider the case of a 2-dimensional quadratic form of square determinant: x^2+y^2, and let’s see how many solutions there are to x^2+y^2=0. Assuming (x,y) is nonzero, x^2+y^2=0 iff \left(\frac{x}{y}\right)^2=-1. If -1 is not a square, then this is not possible, so (x,y)=(0,0) is the only solution. But if -1 is a square, then it has two square roots that \frac{x}{y} could be, and q-1 choices of overall scale, so there’s 2(q-1) nonzero solutions, and thus 2q-1 total solutions. -1 is a square iff q\equiv1\pmod4, so we can phrase this as that it matters whether q is 1 or -1 \mod 4.

If you state and solve the recurrence, you should find that:
\left|\left\{ \vec{v}\in\mathbb{F}_{q}^{2n}:Q\left(\vec{v}\right)=\alpha\right\} \right|=\begin{cases} q^{2n-1}+\text{\ensuremath{\epsilon}\ensuremath{\ensuremath{\left(Q\right)}}}\left(q-1\right)q^{n-1} & \alpha=0\\ q^{2n-1}-\text{\ensuremath{\epsilon}\ensuremath{\ensuremath{\left(Q\right)}}}q^{n-1} & \alpha\neq0 \end{cases}
\left|\left\{ \vec{v}\in\mathbb{F}_{q}^{2n+1}:Q\left(\vec{v}\right)=\alpha\right\} \right|=\begin{cases} q^{2n} & \alpha=0\\ q^{2n}+\text{\ensuremath{\epsilon}\ensuremath{\ensuremath{\left(Q\right)}}}q^{n} & \alpha\in\left(\mathbb{F}_{q}^{\times}\right)^{2}\\ q^{2n}-\text{\ensuremath{\epsilon}\ensuremath{\ensuremath{\left(Q\right)}}}q^{n} & \alpha\in\mathbb{F}_{q}^{\times}\setminus\left(\mathbb{F}_{q}^{\times}\right)^{2} \end{cases}
Where \epsilon\left(Q\right)\in\{\pm1\} is defined as follows:
If q\equiv1\pmod4, then \epsilon\left(Q\right)=1 if Q has square determinant, and -1 if Q has nonsquare determinant.
If q\equiv-1\pmod4, then \epsilon\left(Q\right) is defined as in the previous case if n is even, but is reversed if n is odd. Remember that the dimensions above were 2n and 2n+1, so, by n, I mean half the dimension (rounded down).

It turns out that counting how many vectors a quadratic form assigns each value is useful for another counting problem: Now we can determine the order of the automorphism group of a quadratic form.

If Q is an n-dimensional quadratic form of square determinant, it can be represented by the identity matrix. A matrix with columns (\vec{b}_1,\ldots,\vec{b}_n) is an automorphism of Q iff Q(\vec{b}_i)=1 and \left<\vec{b}_i,\vec{b}_j\right>_Q=0 for i\neq j. Once \vec{b}_1,\ldots,\vec{b}_i have been chosen, the space that’s Q-orthogonal to all of them is (n-i)-dimensional, and Q restricts to a quadratic form on it of square determinant, so the number of options for \vec{b}_{i+1} is the number of vectors that an (n-i)-dimensional quadratic form of square determinant assigns value 1 (which is square). Thus the order of the automorphism group of Q is the product of these over all 0\leq i<n.

If Q is an n-dimensional quadratic form of nonsquare determinant, we can do a similar thing, representing Q with a matrix like the identity, but with the first diagonal entry replaced with a nonsquare. Then the number of options for \vec{b}_1 is the number of vectors that a quadratic form of nonsquare determinant assigns some particular nonsquare value, and the rest of the product is unchanged.

If you evaluate these products, you should get:
\dim=2n: \left|\text{Aut}\left(Q\right)\right|=2q^{n(n-1)}\left(q^n-\epsilon(Q)\right)\prod_{k=1}^{n-1}(q^{2k}-1)
\dim=2n+1: \left|\text{Aut}\left(Q\right)\right|=2q^{n^2}\prod_{k=1}^{n}(q^{2k}-1)

You may notice that, in odd dimensions, the size of the automorphism group of a quadratic form does not depend on its determinant. In fact, the groups are the same. This is because multiplication by a nonsquare scalar sends a quadratic form of square determinant to a quadratic form of nonsquare determinant, and does not change its automorphism group.

As a sanity check, \text{Aut}(Q) is a subgroup of the general linear group, so its order should divide the order of the general linear group. \left|GL_n(\mathbb{F}_q)\right|=q^{n \choose 2}\prod_{k=1}^{n}(q^k-1) (which can be shown with a similar recursive computation). And indeed:

\dim=2n: \frac{\left|GL_{2n}(\mathbb{F}_q)\right|}{\left|\text{Aut}\left(Q\right)\right|}=\frac{1}{2}q^{n^2}\left(q^n+\epsilon(Q)\right)\prod_{k=0}^{n-1}(q^{2k+1}-1)
\dim=2n+1: \frac{\left|GL_{2n+1}(\mathbb{F}_q)\right|}{\left|\text{Aut}\left(Q\right)\right|}=\frac{1}{2}q^{n(n+1)}\prod_{k=0}^{n}(q^{2k+1}-1)

By the orbit-stabilizer theorem, these count the number of quadratic forms of each equivalence class.

The sum of the sizes of the two equivalence classes is the total number of (individual, not up to equivalence) nondegenerate quadratic forms on a vector space, or equivalently, the number of invertible symmetric matrices. This sum is
\dim=2n: q^{n(n+1)}\prod_{k=0}^{n-1}(q^{2k+1}-1)
\dim=2n+1: q^{n(n+1)}\prod_{k=0}^{n}(q^{2k+1}-1)

The leading terms of these are q^{2n \choose 2} and q^{2n+1 \choose 2}, respectively, which are the numbers of symmetric 2n\times2n and (2n+1)\times(2n+1) matrices, respectively. And the second terms of each are negative, which makes sense because we’re excluding singular matrices. You could compute the sizes of all equivalence classes of quadratic forms on an n-dimensional vector space, not just the nondegenerate ones, and add them up, and you should get exactly q^{n \choose 2}.

Fields of well-defined Euler characteristic

\left|\mathbb{R}\right| is, of course, infinite, but if you had to pick a finite number that acts most like the size of \mathbb{R}, it turns out that -1 is a decent answer in some ways. After all, \mathbb{R}_{>0} and \mathbb{R}_{<0} each are homeomorphic to \mathbb{R}, so they should probably all have the same size, and \mathbb{R}=\mathbb{R}_{<0}\sqcup\{0\}\sqcup\mathbb{R}_{>0}; \{0\} has size 1, and size should probably be additive, which would imply that, if we’re denoting the “size” of \mathbb{R} by \chi(\mathbb{R}), \chi(\mathbb{R})=2 \chi(\mathbb{R})+1, which implies \chi(\mathbb{R})=-1. Then, of course, \mathbb{R}^n should have “size” \chi(\mathbb{R}^n)=(-1)^n.

This might seem silly, but it’s deeper than it sounds. This notion of “size” is called Euler characteristic (this is actually different from what algebraic topologists call Euler characteristic, though it’s the same for compact manifolds). A topological space X has an Euler characteristic, denoted \chi(X), if it can be partitioned into finitely many cells, each of which is homeomorphic to \mathbb{R}^n for some n. If X can be partitioned into cells X_1,\lots,X_k, and X_i is homeomorphic to \mathbb{R}^{n_i}, then \chi(X_i)=(-1)^{n_i} and \chi(X)=\sum_i \chi(X_i)=\sum_i (-1)^{n_i}. This is well-defined, in the sense that multiple different ways of partitioning a space into cells that are homeomorphic to \mathbb{R}^n will give you the same Euler characteristic. Roughly speaking, this is because partitions of a space can be refined by splitting an n-dimensional cell into two n-dimensional cells and the n-1-dimensional boundary between them, this does not change the Euler characteristic, and any two partitions into cells have a common refinement.

Euler characteristic has a lot in common with sizes of finite sets, and is, in some ways, a natural generalization of it. For starters, the Euler characteristic of any finite set is its size. Some familiar properties of sizes of sets generalize to Euler characteristics, such as \chi(X\sqcup Y)=\chi(X)+\chi(Y), and \chi(X\times Y)=\chi(X)\chi(Y).

In fact, all of the counting problems we just did over finite fields of odd size applies just as well to fields of well-defined odd Euler characteristic. There are only two infinite fields that have an Euler characteristic: \mathbb{R}, with \chi(\mathbb{R})=-1, and \mathbb{C}, with \chi(\mathbb{C})=1.

Recall that in the counting problems in the previous section, we needed to know whether or not \mathbb{F}_q contains a square root of -1, and that it does iff q\equiv1\pmod4. This extends to fields with Euler characteristic just fine, since \chi(\mathbb{C})\equiv1\pmod4 and \mathbb{C} contains a square root of -1, and \chi(\mathbb{R})\not\equiv1\pmod4 and \mathbb{R} does not contain a square root of -1. In fact, this generalizes a bit. \mathbb{F}_q contains the primitive nth roots of unity iff q\equiv1\pmod n. \chi(\mathbb{C})\equiv1\pmod n for every n, and \mathbb{C} contains all roots of unity. \chi(\mathbb{R})\equiv1\pmod n only for n=1 and n=2, and the only roots of unity in \mathbb{R} are 1 itself and its primitive square root -1.

Anyway, let’s start with positive-definite real quadratic forms (i.e. those only taking positive values). If Q is an n-dimensional positive-definite real quadratic form, then
\left\{\vec{v}\mid Q(\vec{v})=\alpha\right\}\cong \begin{cases} \emptyset & \alpha<0\\ \left\{ \vec{0}\right\} & \alpha=0\\ \mathbb{S}^{n-1} & \alpha>0 \end{cases}
For negative-definite quadratic forms, of course, the positive and negative cases switch.

Now let’s try the indefinite quadratic forms. Recall that for every nondegenerate quadratic form Q on a real vector space V, there are Q-orthogonal subspaces P,N\subseteq V such that Q\restriction P is positive-definite, Q\restriction N is negative-definite, and P\oplus N=V. Let n_+=\dim P and n_-=\dim N. For \alpha>0, in order for \vec{x}\in P,\vec{y}\in N to satisfy Q(\vec{x}+\vec{y})=\alpha, \vec{y} can be anything, and then \vec{x} must lie on the (n_+-1)-dimensional sphere Q(\vec{x})=\alpha-Q(\vec{y}). If \alpha<0, then P and N switch roles. In order for \vec{x}\in P,\vec{y}\in N to satisfy Q(\vec{x}+\vec{y})=0, either \vec{x}=\vec{y}=\vec{0}, or there’s some \beta>0 such that \vec{x} lies on the (n_+-1)-dimensional sphere Q(\vec{x})=\beta and \vec{y} lies on the (n_--1)-dimensional sphere Q(\vec{y})=-\beta. Thus
\left\{\vec{v}\mid Q(\vec{v})=\alpha\right\}\cong \begin{cases} \mathbb{S}^{n_{-}-1}\times\mathbb{R}^{n_{+}} & \alpha<0\\ \mathbb{S}^{n_{+}-1}\times\mathbb{S}^{n_{-}-1}\times\mathbb{R}\cup\left\{ \vec{0}\right\} & \alpha=0\\ \mathbb{S}^{n_{+}-1}\times\mathbb{R}^{n_{-}} & \alpha>0 \end{cases}
With \mathbb{S}^{-1}=\emptyset, this also works for definite quadratic forms.

If you remove one point from \mathbb{S}^n, you get \mathbb{R}^n, so \chi(\mathbb{S}^n)=\chi(\mathbb{R}^n)+1=(-1)^n+1; that is, 2 if n is even, and 0 if n is odd. Thus the Euler characteristics of the above level sets of Q depend only on the parities of n_+ and n_-. The parity of n_- is equivalent to the sign of \det(Q), and n_++n_- is the dimension. So the Euler characteristics of the level sets of Q depend only on the parity of its dimension and the sign of its determinant, and
\det(Q)>0,\,\dim(V)\text{ even}: \chi\left(\left\{\vec{v}\in V\mid Q(\vec{v}=\alpha\right\}\right)=\begin{cases} 1 & \alpha=0\\ 0 & \alpha\neq0 \end{cases}
\det(Q)<0,\,\dim(V)\text{ even}: \chi\left(\left\{\vec{v}\in V\mid Q(\vec{v}=\alpha\right\}\right)=\begin{cases} -3 & \alpha=0\\ -2 & \alpha\neq0 \end{cases}
\det(Q)>0,\,\dim(V)\text{ odd}: \chi\left(\left\{\vec{v}\in V\mid Q(\vec{v}=\alpha\right\}\right)=\begin{cases} 0 & \alpha<0\\ 1 & \alpha=0\\ 2 & \alpha>0 \end{cases}
\det(Q)<0,\,\dim(V)\text{ odd}: \chi\left(\left\{\vec{v}\in V\mid Q(\vec{v}=\alpha\right\}\right)=\begin{cases} 2 & \alpha<0\\ 1 & \alpha=0\\ 0 & \alpha>0 \end{cases}
In comparison, if you take our earlier formula for the sizes of these level sets over \mathbb{F}_q and plug in q=-1, you get
\chi\left(\left\{\vec{v}\in\mathbb{R}^{2n}\mid Q(\vec{v})=\alpha\right\}\right)=\begin{cases} -1+2\epsilon(Q)(-1)^n & \alpha=0\\ -1+\epsilon(Q)(-1)^n & \alpha\neq0 \end{cases}
\chi\left(\left\{\vec{v}\in\mathbb{R}^{2n+1}\mid Q(\vec{v})=\alpha\right\}\right)=\begin{cases} 1-\epsilon(Q)(-1)^n & \alpha<0\\ 1 & \alpha=0\\ 1+\epsilon(Q)(-1)^n & \alpha>0 \end{cases}
\epsilon(Q)(-1)^n is the sign of the determinant, so these two calculations agree.

Now let’s look at complex quadratic forms. Since every complex number is square and \chi(\mathbb{C})=1\equiv1\pmod4, \epsilon(Q)=1 for every nondegenerate complex quadratic form Q. Thus our formulas for sizes of level sets of quadratic forms over finite fields predicts
\chi\left(\left\{\vec{v}\in\mathbb{C}^{2n}\mid Q(\vec{v})=\alpha\right\}\right)=\begin{cases} 1 & \alpha=0\\ 0 & \alpha\neq0 \end{cases}
\chi\left(\left\{\vec{v}\in\mathbb{C}^{2n+1}\mid Q(\vec{v})=\alpha\right\}\right)=\begin{cases} 1 & \alpha=0\\ 2 & \alpha\neq0 \end{cases}
In the odd-dimensional case, I’ve left out the nonsquare case, and relabeled the case where \alpha is a nonzero square as \alpha\neq0, because all complex numbers are squares.

It’s easy to verify that the zero-sets of complex quadratic forms have Euler characteristic 1. This is because, besides the origin, all of the other solutions to Q(\vec{v})=0 can be arbitrarily rescaled to get more solutions, and \chi(\mathbb{C}^\times)=0. That is, let X be the space of 1-dimensional subspaces on which Q is zero. Then \left\{\vec{v}\neq0\mid Q(\vec{v})\right\}=0\cong X\times\mathbb{C}^\times, so \chi\left(\left\{\vec{v}\mid Q(\vec{v}\right\}\right)=\chi(\{\vec{0}\})+\chi(\mathbb{C}^\times)\chi(X)=1+0\chi(X)=1.

The Euler characteristics of the other level sets of complex quadratic forms can be checked by induction. A 0-dimensional quadratic form takes no nonzero values, so \chi(\{\vec{v}\in\mathbb{C}^0\mid Q(\vec{v})=\alpha\})=\chi(\emptyset)=0. An n+1-dimensional quadratic form Q can be diagonalized as x_1^2+\ldots+x_{n+1}^2. For \alpha\neq0, the solutions to x_1^2+\ldots+x_{n+1}^2=\alpha can be partitioned into three pieces:
1. x_1^2+\ldots+x_n^2=0,\,x_{n+1}^2=\alpha. This has Euler characteristic \chi(\{x_1^2+\ldots+x_n^2=0\})\chi(\{x_{n+1}^2=\alpha\})=1\cdot2=2.
2. x_1^2+\ldots+x_n^2=\alpha,\,x_{n+1}^2=0. This has Euler characteristic \chi(\{x_1^2+\ldots+x_n^2=\alpha\})\chi(\{x_{n+1}=0\})=\chi(\{x_1^2+\ldots+x_n^2=\alpha\}).
3. For some \beta\notin\{0,\alpha\}, x_1^2+\ldots+x_n^2=\beta,\,x_{n+1}^2=\alpha-\beta. This has Euler characteristic
\chi(\mathbb{C}\setminus\{0,\alpha\})\chi(\{x_1^2+\ldots+x_n^2=1\})\chi(\{x_{n+1}^2=1\})=(-1)\cdot\chi(\{x_1^2+\ldots+x_n^2=1\})\cdot2=-2\cdot\chi(\{x_1^2+\ldots+x_n^2=1\}) (I’ve replaced \beta and \alpha-\beta with 1 where they appear, since both are nonzero, and all the nonzero level sets are homeomorphic).
Thus, summing these up, we get \chi(\{x_1^2+\ldots+x_{n+1}^2=\alpha\})=2-2\chi(\{x_1^2+\ldots+x_n^2=\alpha\}), explaining the alternation between 0 and 2.

There are some apparent disanalogies between finite fields and infinite fields with Euler characteristics. For instance, it is not true that exactly half of nonzero complex numbers are squares, at least in the sense that \left|\mathbb{C}^\times/\left(\mathbb{C}^\times\right)^2\right|=1\neq2. However, it is still true (vacuously) that the ratio between any two nonsquare complex numbers is square. And the spaces of nonzero square and nonsquare complex numbers have the same Euler characteristic, since \chi(\mathbb{C}^\times)=0=\chi(\emptyset). This had to be the case, because sufficiently non-pathological bijections preserve Euler characteristic, so sufficiently non-pathological two-to-one maps cut Euler characteristic in half, since the domain can be partitioned into two pieces in non-pathological bijection with the range.

And, while finite fields of odd characteristic have two nondegenerate n-dimensional quadratic forms up to equivalence, \mathbb{C} has just one, and \mathbb{R} has n+1 of them. \mathbb{C}‘s missing second nondegenerate quadratic form of each dimension can be addressed similarly to its missing nonsquare elements. The number of nondegenerate n-dimensional quadratic forms over \mathbb{F}_q in each equivalence class is a multiple of q-1, so, with q=1, this correctly predicts that the Euler characteristic of each equivalence class of n-dimensional complex quadratic form is 0, and one of the equivalence classes being empty is consistent with that.

The oversupply of equivalence classes of real quadratic forms is a little subtler. Our analysis of nondegenerate quadratic forms over finite fields of odd characteristic predicts that any two nondegenerate real quadratic forms whose determinants have the same sign should be equivalent, and this is not the case. To address this, let’s look at the heap of isomorphisms between two nondegenerate quadratic forms whose determinants have the same sign. A heap is like a group that has forgotten its identity element. The heap of isomorphisms between two isomorphic objects is the underlying heap of the automorphism group of one of them. In particular, if the automorphism group of some object is a Lie group, then the heap of isomorphisms between it and another object it is isomorphic to is homeomorphic to the automorphism group, and thus they have the same Euler characteristic. In the finite case, this is just saying that the heap of isomorphisms between two isomorphic objects has the same size as the automorphism group of one of them. So when we computed the sizes of automorphism groups of nondegenerate quadratic forms over \mathbb{F}_q, we were also computing sizes of isomorphism heaps between isomorphic pairs of nondegenerate quadratic forms over \mathbb{F}_q. Plugging in q=-1, this should also tell us the Euler characteristic of the heap of isomorphisms between two real quadratic forms whose determinants have the same sign. Notice that (with the exception of the cases where \dim=2 and \epsilon=-1, or where \dim=1), the order of the automorphism group of a nondegenerate quadratic form over \mathbb{F}_q is a multiple of q^2-1, so plugging in q=-1 predicts that the automorphism group of a nondegenerate real quadratic form has Euler characteristic 0, and hence so does the heap of isomorphisms between two nondegenerate real quadratic forms of the same dimension whose determinants have the same sign. This is consistent with said heap of isomorphisms being empty! The exceptions, the quadratic forms whose automorphism groups do not have Euler characteristic 0, are when \dim=2 and \det<0, or when \dim=1. These are exactly the cases when knowing the dimension of a nondegenerate real quadratic form and the sign of its determinant actually does tell you what the quadratic form is up to equivalence.

High Ground

One day the ground shook. It was scary, but it was over soon, and none of us were injured. Two days later, we saw water in the distance. At first we thought it was a mirage, but later in the day, not only was it still there, it had grown. Our first instinct, once we realized it was real, was to migrate towards it; it would be a godsend if it’s fresh, so we figured we’d better check. But it kept getting closer, and not just because we were going closer to it. We soon realized the implications, and turned around and fled for the mountains. The mountains were far away; we weren’t sure exactly how far away, as neither my husband nor I had ever been to the mountains.

We walked just about as far as we could each day, but we could see that the water was catching up. And then, one day, we woke up before dawn, because we were wet. We all got up and started walking again, but first I tried a taste of the water. It was salty. We reached dry ground just after dawn, but the water caught up to us again around noon. By dusk, it was up to our ankles. We’d moved especially quickly that day, and were exhausted, but we couldn’t rest, because we’d drown, so we pressed on through the night. Our son was too exhausted to keep walking, so my husband carried him on his back while he rested through the night. The water kept rising through the night and the next day. By the end of the day, I felt like I could barely go on. It wasn’t just the sleep deprivation and overexertion, but also the pain in my feet from them being immersed in cold water the whole time, and worst of all, the dehydration. It was impossible to get any fresh water, because any source of fresh water we could reach got drenched in saltwater before we could reach it. We couldn’t go on much further, and could only hope we wouldn’t have to; the mountains were noticeably closer now, and perhaps we’d reach steeper ground soon, and be able to outrun the water. But for now, we had to keep walking, so we did.

Our son’s sleep cycle got desynched from the sun, and my husband started carrying him on his back again in broad daylight. The water reached our knees, and I figured our son would likely have trouble walking once he woke up anyway. My husband collapsed, and our son fell into the water, woke up, and shrieked. I grabbed our son, helped him get on his feet, and then tugged on my husband’s arm to help him up. My husband stirred, but didn’t get up. I slapped him, in case that helped wake up, but he didn’t move. I abandoned him, helped our son onto my back, and kept moving, hoping my husband would get up and start moving again on his own. He didn’t.

Just before dusk, I started to wonder if it was my imagination, or if the water line ahead of me was a bit closer than it was earlier. I looked down, and saw that the water wasn’t reaching my knees anymore. I hadn’t felt it because my legs were too numb. I was beating the water, now, and the mountains were so much closer. I kept walking through the night. Was I still beating the water? I thought I probably was, but I couldn’t tell for sure, because my legs were too numb, and the moon was almost new, so I couldn’t see well. I didn’t want to waste any time reaching down to check the water level with my hands. In any case, I wasn’t beating the water fast enough. I could feel that I would collapse soon, just like my husband did. My son had had a fair amount of rest, and the water might be shallow enough for him now, so I thought about letting him off and making him walk. It was tempting, but I knew it wouldn’t save me; if I stopped to put him down, I wouldn’t be able to start walking again. So I kept going, hoping that by the time I drop, we’d be close enough for my son to make it to the mountains.

Cardinality and the axiom of choice

If the axiom of choice is false, then there are two sets which are not the same size, but neither one of them is larger than the other. This, and similar seemingly absurd results, are sometimes used as motivation for the axiom of choice. But this is not so absurd when you unpack what it means: A set X is said to be at least as large as a set Y if there is an injection from X into Y, the same size as Y if there is a bijection between X and Y, and strictly larger than Y if it is at least as large as Y but not the same size. So all this result is saying is that if the axiom of choice is false, then there are two sets, neither of which can be injected into the other. It’s not hard to find two groups without an injective homomorphism between them in either direction, and not hard to find two topological spaces without any injective continuous maps between them in either direction. So why not sets?

The usual reason to think this shouldn’t happen for sets is that cardinalities of sets are supposed to correspond to an intuitive notion of size. But this intuitive interpretation is not God-given; it is an interpretation that people came up with because it seemed to fit. If the axiom of choice is false, this interpretation fits less well. The axiom of choice can be viewed as saying that sets are so flexible that the possibility of fitting one inside another is limited only by their relative sizes, whereas the negation of the axiom of choice says that sets have some essential structure that can’t be adequately interpreted as size.

But it gets worse. Without the axiom of choice, it’s possible to have an equivalence relation \sim on a set X such that there are strictly more equivalence classes of \sim than there are elements of X. For instance, if all subsets of \mathbb{R} are Lebesgue measurable, then this can be done with an equivalence relation on \mathbb{R}, namely x\sim y iff x-y\in\mathbb{Q}.

Surely this is still absurd? Again, I think it is not. It only sounds absurd because of the inappropriate language we used to describe the situation in which there’s an injection from X to X/\sim but no bijection between them. Instead, you can think about it as X and X/\sim being flexible in the ways that allow X to fit inside X/\sim, but rigid in ways that prevent X/\sim from fitting inside X, rather than in terms of bigness.

I suspect that, to many people, “X/\sim has strictly larger cardinality than X” sounds more absurd than “X and X/\sim have incomparable cardinalities” does, but it really shouldn’t, since these are almost the same thing. The reason these are almost the same is that an infinite set can be in bijection with the union of two disjoint copies of itself, another phenomenon that could be thought of as an absurdity if the identification of cardinality with size is taken too literally, but which you have probably long since gotten used to. If X and X/\sim have incomparable cardinalities and X can be put into bijection with two copies of itself, then, using such a bijection to identify X with two copies of itself, mod out one of them by \sim while leaving the other unchanged. The set of equivalence classes of this new equivalence relation looks like (X/\sim)\sqcup X, which X easily injects into.

And it shouldn’t be surprising that there could be an equivalence relation \sim such that X/\sim can’t inject into X; the only obvious reason X/\sim should be able to inject into X is that you could pick an element of each equivalence class, but the possibility of doing this is a restatement of the axiom of choice. For instance, in the example of \mathbb{R} and \mathbb{R}/\mathbb{Q}, a set consisting of one element from each equivalence class would not be Lebesgue measurable, and thus doesn’t exist if all sets are Lebesgue measurable.

The sense in which cardinality can be about structure more general than size can become even more apparent in more austere foundations. Consider a mathematical universe in which everything that exists can be coded for somehow with natural numbers, and every function is computable. There’s a set of real numbers in this universe, which we know of as the computable real numbers: they’re coded by numbers representing programs computing Cauchy sequences that converge to them. It doesn’t really make sense to think of this universe as containing anything “bigger” than \mathbb{N}, since everything is coded for by integers. But Cantor’s theorem is constructive, so it applies here. Given a computable sequence of computable reals, we can produce a computation of a real number that isn’t in the sequence. So the integers and the (computable) reals here have different “cardinalities” in the sense that, due to their differing computational structure, there’s no bijection between them in this computability universe.

I think that it can be helpful to think of cardinalities as potentially being about inherent structure of sets rather than simply “size” even if you’re assuming the axiom of choice the whole time. Fun fact: if there’s any model of ZFC at all, then there’s a countable model. This often strikes people as absurd; ZFC asserts the existence of uncountable sets, like \mathbb{R}, so how could something countable be a model of ZFC? The answer is that an infinite set being uncountable just means that there’s no bijection between it and \mathbb{N}. A countable model of ZFC can contain a countable set but not contain any of the bijections between it and \mathbb{N}; then, internally to the model, this set qualifies as uncountable. This is sometimes described as the countable model of ZFC “believing” that some of its sets are uncountable, but being “wrong”. I think this is a little sloppy; models of ZFC are just mathematical structures, not talk radio hosts with bad opinions. Restricting attention to a certain model of ZFC means imposing additional structure on its elements; namely that structure which is preserved by the functions in the model. This additional structure isn’t respected by functions outside the model, just like equipping a set with a topology imposes structure on it that isn’t respected by discontinuous maps.

To give a couple concrete examples of how I visualize cardinality as being about structure: When we encounter mathematical objects of cardinality 2^{\aleph_0} in practice, they often naturally carry separable topologies on them, so I think of 2^{\aleph_0} as being thicker than \aleph_0, but no longer. Since smaller ordinals are initial segments of larger ordinals, I think of \aleph_1, the cardinality of the first uncountable ordinal, as longer than \aleph_0, but no thicker. \mathbb{R} being well-orderable would mean we can rearrange something thick into something long.

It’s interesting to note that you can forge something long (\aleph_1) out of something thick (2^{\aleph_0}) by modding out by an equivalence relation. (This gives another example of a quotient of \mathbb{R} that, axiom of choice aside, it’s perfectly reasonable to think shouldn’t fit back inside \mathbb{R}). This is because \aleph_1 is the cardinality of the set of countable ordinals, each countable ordinal is the order-type of a well-ordering of \mathbb{N}, and well-orderings on \mathbb{N} are binary relations on \mathbb{N}, aka subsets of \mathbb{N}\times\mathbb{N}. So, starting with 2^{\mathbb{N}\times\mathbb{N}} (with cardinality 2^{\aleph_0}), say that any two elements that are both well-orderings of the same order-type are equivalent (and, if you want to end up with just \aleph_1, rather than \aleph_1+2^{\aleph_0}, also say that all the left-overs that aren’t well-orderings are equivalent to each other). The set of equivalence classes then corresponds to the set of countable ordinals (plus whatever you did with the leftovers that aren’t well-orderings).

The idea behind this post was a specific instance of the general principle that, when a result seems absurd, this doesn’t necessarily refute the foundational assumptions used to prove it, but rather means that your way of thinking isn’t well adapted to a mathematical universe in which those assumptions are true. Another example of this is that the Banach-Tarski theorem and similar results often strike people as patently absurd, but people get used to it, and one could try explaining why such results shouldn’t be seen as as absurd as they first seem, as a way of conveying intuition about what a mathematical universe in which the axiom of choice holds looks like.

While I don’t find the allegedly counterintuitive things that are likely to happen without the axiom of choice compelling, this doesn’t undercut other arguments for the axiom of choice. I think the strongest is that every \Sigma^1_3 statements (a broad class of statements that arguably includes everything concrete or directly applicable in the real world) that can be proved in ZFC can also be proved in ZF, so assuming the axiom of choice isn’t going to lead us astray about concrete things regardless of whether it is true in some fundamental sense, but assuming the axiom of choice can sometimes make it easier to prove something even if in theory it could be proved otherwise. This seems like a good reason to assume the axiom of choice to me, but that’s different from the axiom of choice being fundamentally true, or things that can happen if the axiom of choice is false being absurd.

Terrestrial Astrogation

“Signal from Bumblebee. Bogey spotted, bearing .40-.13, estimated range 300 miles,” said Sam, Killjoy’s signalman.

Amelia, the pilot, quickly turned so that they’d have a good view in that general direction. While the ship was turning, Nate, the navigator, worked out exactly which direction to expect to see the bogey. Once the turn was complete, he pointed the telescope in that direction, and hunted around for it. It didn’t take long to find it, and he reported the bearing. Having bearings to the bogey from two ships rather than one gave them a more precise idea where it was; Bumblebee’s range estimate had only been a wild guess, though it had turned out not to be far off.

Sam relayed the bearing back to Bumblebee with the light gun. Contrary to popular belief, the light gun, rather than Killjoy’s real gun, was the second-most energy-intensive machine on the ship, behind only the engine. Space ships are fragile, so it doesn’t take much punch to kill them, and they have no reason for their guns to pack more punch than that. Being able to yell for help is just as essential for survival in space warfare as being able to shoot. Since as far as anyone can tell, sound doesn’t transmit through space at all, that means you need others to be able to see you yelling for help, from a vast distance away. Hence the extremely powerful light gun.

Bumblebee and Killjoy each took another set of bearings on the bogey, and passed them over to each other, which meant they now had enough information to determine the bogey’s velocity. Nate ran the numbers on his slide rule.

“It’s on an intercept course with Bumblebee,” he said, “They’ll make contact in about 12 minutes, and I don’t think Bumblebee has any chance of running away from them.”

Bumblebee was carrying some extremely valuable cargo from Habitat 6 back to Habitat 1. Habitat 6 had just been captured right after Bumblebee had departed it, so if Bumblebee and its cargo were lost, there was no going back for more. If anyone was on an intercept course for Bumblebee, there’s a good chance they knew all of this, and were targeting Bumblebee because of it.

Nate continued, “There’s no way anyone else can make it there to rescue them. We can probably do it, though. Turning, uh… .83-.25 or so, and accelerating at about an eighth of a g would be a good way to start.”

Amelia immediately followed those directions. Those directions were similar to her intuition, which was famously good regarding maneuvering in orbit (she had set a record for how far a trip she could take and return from alive, back in the early days of space travel when people first discovered how to get out of Habitat 1, before the math behind orbital mechanics was known), but it still generally works better to wait for input from the guy with the charts and a slide rule when possible.

The course change was Nate’s signal to calculate a more precise intercept course. “Do we want to engage them simultaneously with Bumblebee, or before?” he asked.

“Before,” said Amelia.

The rest of the crew simultaneously cursed under their breaths at that. Normally, you want to coordinate with your squadronmates to fight enemies simultaneously, rather than one at a time. The only way it could possibly make sense to try to fight a one-on-one dual with the bogey before Bumblebee was close enough to help was if Bumblebee getting out of the fight in one piece was more than four times as important as Killjoy doing the same, a value judgement that no one in Killjoy’s crew could endorse with much enthusiasm.

“Maybe push the acceleration to a sixth of a g, then,” said Nate, “and tell Bumblebee to run away.”

Bumblebee is already doing that,” said Sam.

Nate got to work plotting the intercept course, and when he was done, he gave Amelia a course correction and an even higher acceleration.

When they got close to the bogey, Joan, Killjoy’s gunner and engineer, fired a tracer at it, and, predictably, missed, but seeing the path of the tracer was helpful for lining up the next shot. The tracer rounds were a recent invention, having been invented during the current war, and caused an enormous improvement in gunnery accuracy outside of habitats. Their side had been on the verge of victory when the other side developed the tracers, and they would have lost if they hadn’t managed to reverse engineer the tracers and produce some themselves as soon as they did.

Nevertheless, Joan missed the next couple shots as well, though the last one was close. There was a loud cracking sound.

“We’re hit!” said Joan, unnecessarily. Usually, a ship falls apart instantly when it gets hit; the projectile must have just barely grazed them. Joan more usefully continued, “We’ve lost one oxygen tank and we’re losing fuel. I’ll patch up the fuel tank.”

“You’ll what?” Sam asked incredulously, as Joan grabbed a bag of leak repair equipment and jumped towards the door.

She unlocked the door (which was designed to seal against a habitat airlock, and was very much not designed to be opened in a vacuum), yanked it open, quickly propelled herself through it, grabbed the handle on the other side, and slammed it shut.

The air inside the ship was noticeably thin by the time she’d finished that step, but not dangerously so. The oxygen tanks were automatically releasing more air, with an audible hissing sound.

The exterior of the ship was not designed to be crawled across, and as such, did not have handholds. Joan had no way to get traction without being pressed against the ship. Luckily, Amelia caught on to what she was trying to do, and used maneuvering thrusters to push the whole ship towards Joan, so Joan could climb across it, and across from Joan so it would be like Joan was climbing downhill.

“What’s she doing? There’s no way she’ll make it back before losing consciousness!” said Sam.

“She knows,” said Nate.

“But then we’ll have no way to recover her before she dies!” said Sam.

“She knows,” Nate repeated.

Joan reached the fuel leak, and the rest of the crew watched her work through the window, while Amelia continued to push the ship towards her with maneuvering thrusters so she wouldn’t float away. Joan finished patching the leak just before passing out.

“That was lucky,” Nate commented, “I counted 16 seconds since she opened the door, though I might have been off slightly because I was distracted by Sam talking. That’s longer than people usually last, and it was a very efficient patch job.” Meanwhile Killjoy was tumbling a bit as a result of Amelia’s hasty maneuvering, and Amelia was busy straightening the ship out.

“Where can we get to now?” Amelia asked after stopping the tumbling, in a grim tone of voice that suggested she had a hunch about the answer.

Nate looked around with the telescope to get a good sense of their position and velocity.

“While I’m figuring that out, you’ll want to boost us .45-.40 by 50 feet per second,” said Nate. That would prevent them from getting too far away from where the habitats tended to orbit.

Nate checked the time by pointing his telescope at Earth’s terminator line, checked the fuel gauge, checked the charts for where all the known habitats should be, and started running the numbers for all the habitats it was even remotely plausible they could make it to, including enemy-controlled habitats where they could surrender. This took several minutes.

“Nowhere,” he finally announced.

“Okay, let’s look around for a new habitat. Sam, ask Bumblebee, if they’re still alive, and whoever else is in signal range, Queen of the Angels, maybe, to help us out,” said Amelia.

“Will do,” said Sam, “Bumblebee is alive, by the way. They just messaged that they destroyed the bogey.”

Nate and Amelia started looking around for undiscovered habitats, and Sam joined them once he was done sending the message. Searching for habitats was tricky, because from a distance, a habitat looks like a dim star when it’s in sunlight (and is nearly invisible when shadowed), so even when there’s a habitat in plain view, it doesn’t stand out from its surroundings very well. But they all knew their constellations decently well, so they’d know when they saw something out of place.

“Over there! I see something!” Sam said excitedly, pointing, after they’d been looking for several minutes.

“You’re pointing at Mercury,” said Nate, “Is there something else next to it?”

“No. Uh, I guess it’s just Mercury,” said Sam, dejected.

It was almost an hour later that Sam again saw something. “Please don’t tell me that’s Venus over there,” he said.

Nate took a look through Sam’s telescope. “Hm, no, that’s not anything I know about,” he said, “Looks promising. Send the bearing over to Bumblebee and Queen of the Angels; see if they can find it.”

From looking at how the unidentified object was moving, Nate became convinced it must be a habitat, even before Queen of the Angels replied with a bearing on an unidentified object that was a potential match for the one Killjoy had reported.

After a couple more bearing reports on the object from Queen of the Angels, Nate had a pretty precise picture of the presumed-habitat’s orbit. “We can definitely make it, but it will take a while. Bring us to .75-.25 at a twenty-fifth of a g.”

“Okay. Now, when you say ‘we can definitely make it’, do you mean we have enough fuel and oxygen to make it there, or just that we have enough fuel?” asked Amelia, while following Nate’s directions.

“Oh shit, uh, hold on. Let’s see if I can make this work,” said Nate.

After recalculating, he said, “Okay, we can’t get there before the oxygen tanks nominally run out, but the time the oxygen tanks are rated for is less than the amount of time before we lose consciousness, and I’m not sure exactly how much less, so I’ll just give you the fastest route we can do with the fuel we have and hope for the best.”

Amelia returned to the controls and brought Killjoy to the new course Nate had planned out, while Nate jotted down notes about what the rest of the course should look like. When they were done, the three of them joined hands and Amelia led them in a slow-breathing meditation exercise. After a few minutes of this, Amelia stopped, and said, “Sleep.”

Sam and Nate strapped themselves in and tried to sleep, and Amelia dimmed the lights for them. It wasn’t easy falling asleep when you didn’t know if you were going to wake up again, even when knowing that falling asleep sooner would make that more likely. But they both eventually managed; it helped that it had been a long day.

Amelia continued meditating, while being careful not to fall asleep so that she could keep the ship on course. It was unclear to her whether they were going to make it. The possibility occurred to her of throwing someone out the door to conserve oxygen, though she quickly rejected this idea. There were many drawbacks: She and Nate needed to stay, because they needed to take shifts piloting, since the journey would take too long for one of them to do it, and Sam didn’t know how to fly. Sam needed to stay, because he was the only one of them with any wilderness survival skills worth speaking of, so Amelia and Nate might not fare very well on their own even if they did make it to the habitat. Air escaping through the door as someone gets tossed through it would limit how effective an oxygen-conserving measure it would be. And, of course, she greatly preferred all three of them making it.

About a third of the way through the trip, Amelia woke Nate up for a shift, and went to sleep herself. About three-fourths of the way through, He woke her up again to take the last shift, and went to sleep again himself.

She made it most of the rest of the way. The oxygen tanks were long since empty, and she was very, very tired. She entered a confused, dreamlike state, and then jolted herself back into reality.

Had she fallen asleep? She didn’t know. Was Killjoy in the same place it had been when she’d last been paying attention? That one was supposed to be easy, but she didn’t know. A wave of panic washed over her as she realized how disoriented she was, and then she remembered where the habitat was supposed to be, she looked in that direction, and there it was. She could even make out its toroidal shape through the telescope. So close. How much longer?

It took her a while to think of a way to answer that question. She looked for Earth’s terminator line, and then looked at Nate’s notes on their course. Then she looked back at Earth’s terminator line again and wrote down the time so she wouldn’t immediately forget it again. She hadn’t missed any maneuvers, and there was just over 20 minutes to go. She wasn’t going to make it.

Maybe Nate could make it, if he had a higher tolerance for oxygen deprivation than she did, she thought. Of course, maybe not, and maybe even if Nate could stay awake long enough he wouldn’t be able to dock at the habitat, since they were cutting it down to the wire on fuel and he wasn’t an experienced pilot. But it was a risk she’d have to take, because she knew she wasn’t going to make it herself.

Amelia pushed herself over to where Nate was strapped in, grabbed him, and shook. He didn’t wake up. She punched him, and he stirred. She punched him harder. Nate awoke, they made eye contact, and then Amelia passed out.

Nate felt groggy as hell, and part of him wanted to just go back to sleep. But he understood what was happening. He slowly unstrapped himself, and made his way to the controls. It took him longer than it should have to get himself oriented, but soon enough he worked out where in space Killjoy was, and when.

They were a tiny bit off course. He worked out how to correct for this, reached for the controls, and hesitated. He was forgetting something; what was it? He looked behind him. Aha! Amelia was unconscious and not strapped in. She could get thrown across the ship and get injured if he adjusted the thrusters. He went over and strapped her in before returning to the controls, orienting himself again (he’d already forgotten which direction they were off course in), and correcting their course.

The habitat drew closer, to the point where Nate could see its toroidal shape with naked eye, and then to the point where he could see that it was large. He needed to make several more course corrections to make sure that Killjoy would come to a stop just in front of the habitat’s airlock. He was getting nauseous, despite usually being pretty impervious to spacesickness.

His terminal maneuvering was slightly sloppy, and by the end, the engine was sputtering and not producing as much thrust as it was supposed to, but he made it. He fired the docking harpoons and reeled them in, successfully sealing Killjoy’s door against the habitat’s airlock.

He went to the door, opened it, opened the airlock behind it, and took in a deep breath of fresh air.

Uniqueness of mathematical structures

This post is an introduction to model theory, of sorts. Occasionally I get asked what model theory is, and I generally find it quite difficult to give someone who doesn’t already know any model theory a good answer to this question, that actually says anything useful about what model theory is really about without leaving them hopelessly lost. This is my attempt to provide a real taste of model theory in a way that should be accessible to a math grad student without a background in logic.

Warm-up exercise

Let’s say I make a graph with the following procedure: I start with a countably infinite set of vertices. For each pair of vertices, I flip a fair coin. If the coin lands heads, I put an edge between those two vertices; if the coin lands tails, no edge.

Now you make another graph in a very similar manner. You also start with a countably infinite set of vertices. But instead of flipping a coin, you roll a fair standard six-sided die for each pair of vertices. If the die comes up 6, you put an edge between those two vertices; if it comes up anything from 1 through 5, no edge.

What is the probability that these two graphs are isomorphic?

For the numerical answer, paste “Gur zhygvcyvpngvir vqragvgl” into https://rot13.com/. An explanation will appear later in this post.

Introduction

There are several cases in which we can identify a mathematical object up to isomorphism with a list of first-order properties it satisfies (I’ll tell you what that means in a sec) and some data about cardinality. Here’s a couple examples: All countable dense linear orders without endpoints are isomorphic. Any two algebraically closed fields of the same characteristic, which have transcendence bases of the same cardinality, are isomorphic. It turns out that the possibility of uniquely specifying a mathematical structure in this way corresponds to interesting structural properties of that structure.

First, the basic definitions:

A first-order language consists of a set of relation symbols, each of which is labeled with a number representing its arity (number of inputs it takes), a set of function symbols, each of which is also labeled with a number representing its arity, and a set of constant symbols (which could also just be thought of as 0-ary function symbols). For example, the language of linear orders has one binary relation < and no functions or constants. The language of fields has constants 0 and 1, binary functions + and \cdot, a unary function - (no unary function for reciprocal, because the functions should be total), and no relations.

A first-order structure in a given language is a set X in which each constant symbol is interpreted as an element of X, each n-ary function symbol is interpreted as a function X^n\rightarrow X, and each n-ary relation symbol is interpreted as a subset of X^n (or alternatively, as a function X^n\rightarrow\{\text{True},\text{False}\}). So linear orders and fields are examples of structures in their respective languages.

We can compose function symbols, constant symbols, and variables into ways of pointing to elements of a structure, called terms. We have as many variables as we want, and they are terms. Constant symbols are terms. And for each n-ary function symbol f and terms t_1,...,t_n, f(t_1,...,t_n) is a term. So in the language of fields, we can construct terms representing integers by adding however many 1s together (and then negating to get negative numbers), and then combine these with variables using addition and multiplication to get terms representing polynomials in however many variables with integer coefficients. In the language of linear orders, since we have no functions or constants, the only terms are variables.

A first-order formula is a way of actually saying things about a first-order structure and elements of it represented by variables. If R is an n-ary relation and t_1,...t_n are terms, then R(t_1,...,t_n) is a formula. If t_1,t_2 are terms, then t_1=t_2 is a formula (you can think of this as just meaning that languages always have the binary relation = by default). Boolean combinations of formulas are formulas (i.e. if \varphi and \psi are formulas, then so are \varphi \& \psi, \varphi\text{or}\psi, and \neg\varphi), and if \varphi is a formula that refers to a variable x, then \forall x\,\varphi and \exists x\,\varphi are formulas. Any variable that appears in a formula without being bound to a quantifier \forall or \exists is called a free variable, and if each free variable is assigned to an element of a structure, the formula makes a claim about them, which can be either true or false. For example, in a ring, \exists y\, x\cdot y=1 is true iff x is a unit.

A first-order formula with no free variables is called a sentence. These are true or false statements about a first-order structure. Many types of mathematical objects are defined by listing first-order sentences that are true of them. For instance, a linear order is a structure with a < relation satisfying transitivity (\forall x \forall y \forall z\, x<y \& y<z \implies x<z), antisymmetry (\forall x \forall y \neg(x<y \& y<x)), and totality (\forall x \forall y\, x<y \text{ or } y<x \text{ or } x=y), and a linear order is dense without endpoints if it also satisfies \forall x \forall y \exists z \, x<z \& z<y and \forall x \exists y \exists z \, y<x \& x<z. These are all first-order sentences. Algebraically closed fields of a given characteristic are another example. The field axioms are first-order sentences. For each positive integer n, we can formulate a first-order sentence saying that every polynomial of degree n has a root: \forall y_0 \forall y_1 ... \forall y_{n-1} \exists x \, y_0 + y_1x + ... + y_{n-1}x^{n-1}+x^n = 0 (the y_is represent the coefficients, with the leading coefficient normalized to 1). So we just add in these infinitely many sentences, one for each n. And we can say that the field has characteristic p by saying 1+...+1=0 (with p ones), or say that it has characteristic 0 by, for each prime p, saying \neg(1+...+1=0).

First-order sentences can tell us a lot about a structure, but not everything, unless the structure is finite.

Löwenheim–Skolem theorem: Given a countable set of first-order sentences (in particular, any set of sentences if the language is countable), if there is any infinite structure in which they are all true, then there are first-order structures of every infinite cardinality in which they are all true.

This is why the uniqueness results all have to say something about cardinality. You might also think of some examples of ways to identify an infinite mathematical object up to isomorphism with a list of axioms without saying directly anything about cardinality, but in all such cases, you’ll be using an axiom that isn’t first-order. For instance, all Dedekind-complete ordered fields are isomorphic to the reals, but Dedekind-completeness isn’t a first-order sentence. Same goes for any way of characterizing the natural numbers up to isomorphism that says something like “every set of natural numbers that contains 0 and is closed under successor contains all of the natural numbers”.

Countable structures

Let’s go back to the example of countable dense linear orders. If you don’t know the proof that all countable dense linear orders are isomorphic, here it goes: suppose we have two countable dense linear orders, X and Y. Since they’re countable, we can label the elements of each of them with distinct natural numbers. We’re going to match elements of X to elements of Y one at a time such that we get an isomorphism at the end. To ensure that every element of X gets matched to something in Y, on odd-numbered steps, we’ll take the lowest-numbered element of X that hasn’t been matched yet, and match it with an element of Y. Similarly, to ensure that every element of Y gets matched to something in X, on even-numbered steps, we’ll take the lowest-numbered element of Y that hasn’t been matched yet, and match it with an element of X. As for what we do on each step (suppose it’s an odd-numbered step; even-numbered steps are the same but with the roles of X and Y reversed), at the start of the step, finitely many elements of X have already been matched. We take the first element that hasn’t yet been matched. Call it x. x is either greater than all previously matched elements, less than all previously matched elements, or between two previously matched elements that don’t already have previously matched elements between them. Since Y is dense and has no endpoints, we know that in the first case, there will be something greater than all previously matched elements of Y, so we can match x to it; in the second case, there will be something less than all previously matched elements of Y for us to match x to; and in the third case, there will be something between the elements matched to the elements on either side of x, which we can match x to. By doing this, we continue to preserve the ordering at each step, so the bijection we get at the end is order-preserving, and thus an isomorphism.

Now let’s get back to the warm-up exercise. A graph can be viewed as a first-order structure whose elements are the vertices, with a single binary relation E (the edge relation) that is symmetric and anti-reflexive (symmetry and anti-reflexivity are both first-order conditions). There are some more first-order sentences satisfied by both of our random graphs with probability 1. Given any two finite disjoint sets of vertices, we can find another vertex that’s connected to everything in the first set and not connected to anything in the second set. This is because each vertex has the same positive probability of having this property, they’re all independent, and there’s infinitely many of them, so there also must be some (in fact, infinitely many) that have all the desired edges and none of the undesired edges. To write this condition using first-order sentences, for each natural number n and m, we have a sentence \forall x_1 ... \forall x_n\forall y_1 ... \forall y_m \, (x_1\neq y_1 \& ... \& x_n\neq y_m) \implies \exists z \, E(z,x_1)\&...\&E(z,x_n)\&\neg E(z,y_1)\&...\&\neg E(z,y_m)
(the big conjunction before “\implies” includes x_i\neq y_j for each 1\leq i\leq n and 1\leq j\leq m, so that this says \{x_1,...,x_n\} and \{y_1,...,y_m\} are disjoint).

This is enough for us to construct an isomorphism, using essentially the same proof as for countable dense linear orders. Since we each started with countably many vertices, we can label each of our vertices with natural numbers, and then iteratively match the next available unmatched vertex in one graph to a vertex on the other, alternating between which graph we take the next available unmatched vertex from on each step, just like before. On each step, only finitely many vertices have been matched. The new vertex shares edges with some of the already matched vertices and doesn’t share edges with some others. We need to match it with a vertex in the other graph that shares exactly the same pattern of edges with previously matched vertices. And we know that somewhere in that graph, there must be such a vertex. So we can match the new vertex and keep going, and the bijection we get at the end preserves the edge relation, and is thus an isomorphism.

For the general argument that these are both special cases of, we’ll need the concept of a type (not to be confused with the identically-named concept from type theory). Given a first-order structure X and c_1,...,c_n\in X, say that a,b\in X have the same type over A if for every first-order formula \varphi(x,y_1,...,y_n) (where x,y_1,...,y_n are its free variables), \varphi(a,c_1,...,c_n) holds iff \varphi(b,c_1,...,c_n) does. So, for example, in a dense linear order without endpoints, if c_1<a<c_2, then, in order for b to have the same type as a over c_1,c_2, it must be the case that c_1<b<c_2 as well, since y_1<x<y_2 is a first-order formula, and a and b must satisfy exactly the same first-order formulas with parameters in c_1,c_2. And as it turns out, this is enough; if c_1<a<c_2 and c_1<b<c_2, then a and b have the same type over c_1,c_2. In an infinite random graph, if vertices a and b have the same type over some other vertices c_1,..,c_n, then a must have an edge to each c_i that b has an edge to, and vice-versa. Again, this turns out to be enough to guarantee that they have the same type.

In both of these cases, for any finite set of elements c_1,...,c_n, there are only finitely many types over c_1,...,c_n. Let’s count them. Each c_i is its own type, since x=y_i is a formula, so if a and c_i have the same type over c_1,...,c_n, then, since c_i=c_i, a=c_i as well. Let’s ignore these and count the rest. In a dense linear order without endpoints, we can assume WLOG that c_1<c_2<...<c_n. There are n+1 nontrivial types over c_1,...,c_n: \{a\mid a<c_1\}, \{a\mid c_n<a\}, and, for each 1\leq i<n, \{a\mid c_i<a<c_{i+1}\}. In an infinite random graph, there are 2^n nontrivial types over n vertices c_1,...,c_n: for each S\subseteq\{c_1,...,c_n\}, there’s a type of vertices that have edges to everything in S and no edges to anything in \{c_1,...,c_n\}\setminus S.

Theorem: Let X be a countably infinite first-order structure such that for every n\in\mathbb{N} and c_1,...,c_n\in X, there are only finitely many types over c_1,...,c_n. Then every countable structure Y satisfying the same first-order sentences that X does is isomorphic to X.

That is, our ability to specify a countable structure (up to isomorphism) by its first-order properties corresponds exactly to the condition that there are only finitely many different behaviors that elements of the structure can have in relation to any given finite subset. The proofs that all countable dense linear orders without endpoints are isomorphic and that all countable random graphs are isomorphic look the same because they both follow the proof of this theorem, which goes like so:

Suppose there are only finitely many types over c_1,...,c_n. Let p be one of those types, and let q_1,...,q_k be the others. For each q_i, there’s some formula \varphi_i(x,c_1,...,c_n) that’s true for x\in p but not for x\in q_i. Then \varphi_1(x,c_1,...,c_n) \& ... \& \varphi_k(x,c_1,...,c_n) is a formula that holds only for x\in p. That is, the entire type is specified by a single formula; it wasn’t just coincidence that we were able to find such a formula for the types in each of our two examples.

Lemma: If X and Y are two first-order structures in the same language which satisfy all the same sentences, c_1,...,c_n\in X and d_1,...,d_n\in Y satisfy all the same formulas (i.e., for any \varphi(x_1,...,x_n), \varphi(c_1,...,c_n) is true in X iff \varphi(d_1,...,d_n) is true in Y), and X has only finitely many types, then there’s a natural bijection between types in X over c_1,...,c_n and types in Y over d_1,...,d_n. A formula \varphi(x,c_1,...,c_n) is true for x in some type over c_1,...,c_n iff \varphi(x,d_1,...,d_n) is true for x in the corresponding type over d_1,...,d_n.

Proof: Let p_1,...,p_k be the types in X over c_1,...,c_n, and for each 1\leq i\leq k, let \varphi_i(x,c_1,...,c_n) be a formula specifying that p_i is the type of x. These formulas \varphi_i specify types in Y over d_1,...,d_n as well; for any other formula \psi(x,y_1,...,y_n), either \forall x\, \varphi_i(x,c_1,...,c_n)\implies\psi(x,c_1,...,c_n) or \forall x\, \varphi_i(x,c_1,...,c_n)\implies\neg\psi(x,c_1,...,c_n) in X. These are first-order formulas, so again since d_1,...,d_n satisfy the same first-order formulas that c_1,...,c_n do, one of \forall x\, \varphi_i(x,d_1,...,d_n)\implies\psi(x,d_1,...,d_n) or \forall x\, \varphi_i(x,d_1,...,d_n)\implies\neg\psi(x,d_1,...,d_n) is true in Y as well. So \varphi_i(x,d_1,...,d_n) determines the truth value of every such formula; that is, it specifies the type of x over d_1,...,d_n, and formulas are true in this type iff they are true in the corresponding type in X over c_1,...,c_n. To show that these are all of the types in Y over d_1,...,d_n, consider the formula \forall x\, \varphi_1(x,y_1,...,y_n)\text{ or ... or }\varphi_k(x,y_1,...,y_n). In X, when we plug in c_1,...,c_n, the formula is true. And d_1,...,d_n satisfies all the same formulas as c_1,...,c_n, so the same formula must also be true in Y when we plug in d_1,...,d_n. That is, for any b\in Y, there’s some i such that \varphi_i(b,d_1,...,d_n) is true, so every element of Y must have one of the above types.

Armed with this lemma, we can prove the theorem. Let X and Y be countable structures satisfying the same first-order sentences, and suppose for every c_1,...,c_n\in X, there are only finitely many types over c_1,...,c_n. We’ll match elements of X to elements of Y one at a time, using the same back-and-forth trick from our two examples to ensure that we get a bijection at the end. After n steps, we’ll have c_1,...,c_n from X matched with d_1,...,d_n from Y, and we’ll want to ensure that c_1,...,c_n and d_1,...,d_n satisfy exactly the same first-order formulas. If we’ve done this, then on step n+1, we’ll have an element either of X or of Y, which we need to match with some element of the other one. We can match it to an element that has the corresponding type; that is, we’re matching c_{n+1}\in X and c_{n+1}\in Y such that the type of c_{n+1} over c_1,...,c_n corresponds to the type of d_{n+1} over d_1,...,d_n. Then c_1,...,c_{n+1} satisfy the same formulas that d_1,...,d_{n+1} do, so by induction, c_1,...,c_n and d_1,...,d_n satisfy the same formulas for every n (the assumption that X and Y satisfy the same first-order sentences provides a base case). Thus, the bijection we get at the end preserves the truth-values of all formulas, so it is an isomorphism, and we’re done.

As it turns out, the converse of the theorem is also true. Given a set of first-order sentences for which there is, up to isomorphism, only one countable model, all models have only finitely many types over any finite list of elements. Whenever there’s infinitely many types, there will be some types (which cannot be specified by a single formula) that appear in some models but not in others.

Uncountable structures

Let’s turn to the other example I introduced at the beginning: any two algebraically closed fields of the same characteristic with transcendence bases of the same cardinality are isomorphic. Every field has a transcendence basis, so a corollary of this is that any two uncountable algebraically closed fields of the same characteristic and cardinality are isomorphic.

A sketch of the proof: Given algebraically closed fields F and K of the same characteristic, with transcendence bases B_F and B_K of the same cardinality, any isomorphism between a subfield of F and a subfield of K extends to a maximal such isomorphism (by Zorn’s lemma). Since B_F and B_K have the same cardinality, there’s a bijection between them, and since F and K have the same characteristic, this bijection extends to an isomorphism between the fields they generate. Thus there is a maximal isomorphism between subfields of F and of K which restricts to a bijection between B_F and B_K. Now we just need to show that these subfields are all of F and K. This is because, given any such isomorphism between subfields F'\subseteq F and K'\subseteq K with B_F\subseteq F' and B_K\subseteq K', if F'\neq F, then let a\in F\setminus F', and let f(x) be the minimal polynomial of a. Applying the isomorphism to the coefficients gives us an irreducible polynomial over K', which must have a root b\in K, and then by matching a with b, we get an isomorphism F'[a]\cong K'[b], contradicting maximality of the isomorphism.

Here’s another example: Any two vector spaces over the same vector space, with bases of the same cardinality, are isomorphic. Since every vector space has a basis, a corollary of this is that, over a countable field, any two uncountable vector spaces of the same cardinality are isomorphic. Citing Zorn’s lemma is overkill, since there’s only one way to extend a bijection between bases to an isomorphism. But the basic idea is the same in each case: We have an appropriate notion of basis, and we extend a bijection between bases to an isomorphism. And vector spaces are also first-order structures; the language has a binary operation +, a constant 0, and, for each scalar \alpha, a unary operation for multiplication by \alpha.

The thing that unites both these cases is called strong minimality. A first-order structure is called minimal if every set defined by a first-order formula is either finite, or the complement of a finite set. More formally: X is minimal if for every formula \varphi(x,y_1,...,y_n) and b_1,...,b_n\in X, one of \{a\in X\mid\varphi(a,b_1,...,b_n)\} or \{a\in X\mid\neg\varphi(a,b_1,...,b_n)\} is finite. We call a structure strongly minimal if every structure satisfying the same first-order sentences is also minimal. (This turns out to be equivalent to, for each \varphi(x,y_1,...,y_n), there’s a finite upper bound on the size of whichever of \{a\in X\mid\varphi(a,b_1,...,b_n)\} or \{a\in X\mid\neg\varphi(a,b_1,...,b_n)\} is finite, as b_1,...,b_n vary.)

Let’s go over the general notion of “basis” we’ll be using: Say that a is algebraic over b_1,...,b_n if there is a formula \varphi(x,y_1,...,y_n) such that \varphi(a,b_1,...,b_n) holds, and \{a'\in X\mid\varphi(a',b_1,...,b_n)\} is finite. In algebraically closed fields, this corresponds to the usual notion of a being algebraic over the subfield generated by b_1,...,b_n. In vector spaces, this corresponds to a being a linear combination of b_1,...,b_n. Call B\subseteq X independent if no element of B is algebraic over any other elements of B. In other words, you can’t pin down an element of B to one of finitely many possibilities by using a single formula and other elements of B. In a vector space, independence is linear independence. In an algebraically closed field, independence is algebraic independence. Now call B a basis if it is a maximal independent set. If X is minimal, this turns out to imply that every a\in X is algebraic over some b_1,...,b_n\in B. An increasing union of independent sets is independent, so by Zorn’s lemma, every structure has a basis.

Now let’s look at type spaces in minimal structures. Let X be a minimal structure and b_1,...,b_n\in X. If a is algebraic over b_1,...,b_n, then there’s some formula \varphi(x,y_1,...,y_n) such that \varphi(a,b_1,...,b_n) holds and \{a'\in X\mid\varphi(a',b_1,...,b_n)\} is as small as possible. Then a and a' have the same type iff \varphi(a',b_1,...,b_n). So this type is implied by a single formula, and there are only finitely many elements of this type. There’s only one remaining type: the type of elements that aren’t algebraic over b_1,...,b_n. If a and a' are both non-algebraic over b_1,...,b_n, then for every formula \varphi(x,y_1,...,y_n), since X is minimal, one of \varphi(x,b_1,...,b_n) and \neg\varphi(x,b_1,...,b_n) must have only finitely many solutions x; a and a', being non-algebraic, must both be solutions to the other one. This shows they have the same type over b_1,...,b_n. This non-algebraic type is optional; in some cases, there might not be any elements that aren’t algebraic over b_1,...,b_n.

Let X and Y be minimal structures in the same language, which satisfy the same first-order sentences. They each have a basis. If those bases have the same cardinality, then X and Y are isomorphic. Say a “partial isomorphism” between X and Y is a bijection between a subset of X and a subset of Y, such that whenever a formula is true about some elements of the subset of X, then it is also true about the corresponding elements of the subset of Y, and vice-versa. If B_X and B_Y are bases for X and Y, respectively, then a bijection between B_X and B_Y is a partial isomorphism (this is because if b_1,...,b_n\in B_X and c_1,...,c_n\in B_Y satisfy all the same formulas, and b_{n+1}\in B_X\setminus\{b_1,...,b_n\} and c_{n+1}\in B_Y\setminus\{c_1,...,c_n\}, then b_{n+1} must have the unique non-algebraic type over b_1,...,b_n, c_{n+1} has the unique non-algebraic type over c_1,...,c_n, and these unique non-algebraic types satisfy the same formulas, so it follows by induction on the number of variables that a formula is true of distinct elements of B_X iff it is true of distinct elements of B_Y). An increasing union of partial isomorphisms is a partial isomorphism, so by Zorn’s lemma, there’s a maximal partial isomorphism extending a bijection between B_X and B_Y. If this maximal partial isomorphism is a bijection between X'\subseteq X and Y'\subseteq Y, and X'\neq X, then let a\in X\setminus X'. a is algebraic over X' (since B_X\subseteq X'), so there’s a single formula \varphi(x,b_1,...,b_n) (b_1,..,b_n\in X') that is true for x=a, and which determines its type over X' (meaning, determines its type over b_1',...,b_m' for every b_1',...,b_m'\in X'). Then, where d_1,...,d_n\in Y' correspond to b_1,...,b_n under the partial isomorphism, there must be c\in Y such that \varphi(c,d_1,...,d_n) (since d_1,...,d_n satisfies the same formulas b_1,...,b_n do, and \exists x \varphi(x,b_1,...,b_n)). c\notin Y', because this can be expressed as part of the type of c over Y', which is the same as the type of a over X'. Thus we can extend the partial isomorphism by matching a with c. Thus, in our maximal partial isomorphism, X'=X, and for the same reason, Y'=Y, so it is an isomorphism.

So for a strongly minimal structure, the structures satisfying the same sentences are classified by the cardinality of a basis. This isn’t quite the end of the story; in some cases, a structure with too small a basis would be finite, and we could thus distinguish it from the rest with a first-order sentence saying that there are n distinct elements (for large enough n). This isn’t the case for algebraically closed fields, which are infinite even when the empty set is a transcendence basis. But for vector spaces, the empty basis generates a one-element vector space, so an infinite vector space must have basis of size at least one.

And if the vector space is over a finite field, then its basis must be infinite. Another case where where the basis must be infinite is an infinite set. A set is a first-order structure in the language with no relations, no functions, and no constants. Every subset of a set is independent, so a basis for the set is just the entire set. In these cases where a basis must be infinite; there’s only one (up to isomorphism) countable model: the model with a countably infinite basis. You can check that both of these examples satisfy the finitely-many-types condition from the previous section for having a unique countable model.

So the general story, for a strongly minimal structure X, is that there is some n\in\mathbb{N}\cup\{\aleph_0\} such that structures satisfying the same sentences as X are classified by cardinalities that are at least n, that being the cardinality of a basis. In a countable language, the cardinality of a structure is the maximum of \aleph_0 and the cardinality of a basis, so it follows that an uncountable strongly minimal structure is isomorphic to all structures of the same cardinality satisfying the same sentences.

In the previous section, we had a converse, so you may ask, if an uncountable structure is isomorphic to all structures of the same cardinality satisfying the same sentences, is it strongly minimal? This is not quite true. For example, consider a vector space V over a countable field, where we add two unary relations W and U to the language, each of which define subspaces of V, which are disjoint and span V, and then add a unary function T to the language, which is a linear function such that T^2=id_V, and T\restriction_W is an isomorphism between W and U. Vector spaces like this are classified by the dimension of W, so there is a unique one (up to isomorphism) of any given uncountable cardinality. It is not strongly minimal because W itself is a formula picking out a set that is neither finite nor the complement of a finite set. But it is almost strongly minimal, in the sense that it is basically just the vector space W^2, and W is strongly minimal. It turns out that for any uncountable structure (in a finite or countable language) that is isomorphic to every structure of the same cardinality and satisfying the same sentences, there’s a formula defining a subset that is strongly minimal in an appropriate sense, such that the rest of the structure can be parameterized somehow using the subset.

Supply and Demand

Until recently, I thought I understood the concept of supply and demand functions pretty well: for each possible price of a good, we look at how much of the good consumers would collectively purchase if it was offered at that price, and how much of it producers would sell if offered that price for it. Sounds simple enough.

Ambiguity

Problem is, the amount of something that a consumer will buy or that a producer will sell depends on more factors than just its price. So in order to determine how much of a good would be demanded or supplied in a counterfactual where its price changes, we also need to know about these other factors. You might want to let everything else stay the same, but this cannot be done. Changing the price of a good must come with some other changes as well. For instance, if the good has a substitute, then the price and quantity of the substitute cannot both stay the same when the price of the good changes.

So for supply and demand functions to be well-defined, we need a counterfactual model, which tells us what exactly is happening in the counterfactual where we set the price of a good and ask how much is demanded or supplied.

Given multiple goods (for simplicity, two goods, x and y), we could consider joint supply and demand functions for them, which take as input a pair consisting of the price of the first good and the price of the second, and outputs a pair consisting of the quantities of each good supplied (for the supply function) or demanded (for the demand function) given those prices. So if p_x and p_y are the prices of x and y, respectively, then D(p_x,p_y)_x and D(p_x,p_y)_y are the quantities demanded of x and y, respectively, and S(p_x,p_y)_x and S(p_x,p_y)_y are the quantities supplied of x and y, respectively. Given joint supply and demand functions, how should we extract supply and demand functions for each good individually? That is, how do we determine the demand function D_x(p_x) and supply function S_x(p_x) for the good x? To answer this question, we need to know what we mean by supply and demand functions, and answering this question provides similar information about what we mean by supply and demand functions as providing a counterfactual model does.

Possible answers

I’m going to make a couple simplifying assumptions for this discussion, not because they are true, but because they are convenient. First, producers and consumers are two entirely separate groups of people. Consumers don’t get the money they spend on consumption by producing something, and producers don’t spend the money they get for production on consuming anything else. Consumers just magically have money, and producers just hoard money so they can swim in it like Scrooge McDuck. Second, a system of equations has exactly one solution whenever I want it to.

Wikipedia suggests that in the counterfactuals considered for demand functions, prices of substitutes and complements should stay the same. This gives an answer to the question of how to extract individual demand functions from a joint demand function. Let p_y^* be the equilibrium price of y (i.e. the price such that there is some p_x^* such that D(p_x^*,p_y^*)=S(p_x^*,p_y^*)). Then D_x(p_x)=D(p_x,p_y^*)_x. A counterfactual model to go along with this is that all producers disappear, and then a monopoly enters the market and offers to the consumers an unlimited supply of the same goods for the same prices that were being offered previously, except for the price of the good in question, which they change. The analogous assumption to make for supply functions is that the prices of other goods that the producers could be making instead (and any goods that can be most efficiently produced along with the good in question) stay the same. Then individual supply curves can be obtained from joint supply curves by S_x(p_x)=S(p_x,p_y^*)_x. And a counterfactual model is that all consumers disappear, and a monopsony enters the market and offers to purchase from the producers unlimited quantities of goods for the same prices the consumers were previously paying, except for the good in question, which they offer a difference price for.

End of story? No; there are other answers that could be given to these questions. You may have noticed that the counterfactual models I suggested were not especially realistic, which could be considered a drawback, so let’s look at some other possibilities.

Suppose the government plans to tax or subsidize a good, and we want to know what effect this will have on the quantity of the good, the price paid by consumers, and the price received by the producers. The usual story for how to figure this out from supply and demand functions S and D is that, where t is the amount of tax (or negative the amount of subsidy) on each unit of the good, if p is the price paid by the consumer, then p-t is the price received by the producer, and the quantity demanded is D(p) and quantity supplied is S(p-t); since quantities supplied and demanded must be equal, then we can just solve the equation D(p)=S(p-t) for p to get the price paid by the consumer, and the common value of D(p) and S(p-t) will be the quantity traded. What do we have to mean by supply and demand functions in order for this story to be correct? The counterfactual model here is clear: the government institutes a tax or subsidy of exactly the right amount so that the consumer/producer ends up paying/receiving a price equal to the input of the demand/supply function, respectively. In other words, D(p) means quantity traded if the tax or subsidy is adjusted so that the price paid by consumers is p, and S(p) means the quantity traded if the tax or subsidy is adjusted so that the price received by producers is p. To figure out the corresponding way to extract individual supply and demand functions from joint supply and demand functions, note that if the government taxes or subsidizes the good x such that the price paid by consumers is p_x^d and the price received by producers is p_x^s (using superscripts as indices, not exponents), and p_y is the price of the good y, then S(p_x^s,p_y)=D(p_x^d,p_y), as these are the pairs consisting of quantities supplied of x and y, and quantities demanded of x and y, respectively. So D_x(p_x)=D(p_x,p_y)_x, where (p_y,p_x^s) is the solution to S(p_x^s,p_y)=D(p_x,p_y), and S_x(p_x)=S(p_x,p_y)_x, where (p_y,p_x^d) is the solution to S(p_x,p_y)=D(p_x^d,p_y).

Another possible counterfactual model is that a new agent enters the market and offers to buy or sell unlimited amounts of a good for a fixed price p, thus forcing p to be the new market price. D(p) is then the quantity purchased by the original consumers, and S(p) is the quantity sold by the original producers. This happens, for example, with backing currency, where a government promises to sell as much of some good as anyone will buy at some fixed price, as a way of ensuring that money remains valuable. A related example is a fixed exchange rate, where a government pegs the price of its currency relative to a foreign currency at a fixed rate by exchanging the currencies in both directions at the pegged price with anyone who wants to trade them at that price, though this example is atypical in that the good being exchanged for money is also money. To figure out the way of extracting individual supply and demand functions from joint supply and demand functions corresponding to this counterfactual model, note that if the government pegs the price of a good x but doesn’t get involved in the market for another good y, then supply and demand for y still must balance; that is, D(p_x,p_y)_y=S(p_x,p_y)_y, where p_x is the pegged price of x and p_y is the market price of y. So the supply and demand functions for x should be given by D_x(p_x)=D(p_x,p_y)_x and S_x(p_x)=S(p_x,p_y)_x, where p_y is such that D(p_x,p_y)_y=S(p_x,p_y)_y.

Cases in which the appropriate notion of supply and demand functions is unclear

There are other situations that economists use supply and demand functions to describe, and each situation may need a different notion of what supply and demand functions mean, and the right way to define them for a given purpose might not always be obvious. For instance, suppose we want to predict the effects of price controls. This may only give meaning to the demand function on prices greater than or equal to the market price, and the supply function on prices less than or equal to the market price, since if supply and demand aren’t equal due to price controls, then whichever one is smaller will determine the quantity traded, so it isn’t clear that there’s an objective way to say what the larger one should be.

Supply and demand functions are supposed to help us understand the effects of changes to supply or demand on price and quantity. The demand curve describes the set of (price, quantity) pairs that can be obtained by changes to how easy the good is to produce, and the supply curve describes the set of (price, quantity) pairs that can be obtained by changes to how desirable the good is. This is not completely well-specified, so what the supply and demand functions should be depends on which sorts of shocks should be considered to only affect demand for the good, or to only affect supply of the good. This isn’t as straightforward as it might sound, since, for instance, two supply shocks might have different effects on demand because of having different effects on the market for a complement or substitute for the good; the supply shock can’t have no effect on the market for the complement or substitute, because it affects the market for the original good, and the markets are linked, so some decision must be made about what assumptions to make about how a supply shock is supposed to affect the markets for other goods, which will depend on, for example, the extent to which the supply shock is due to producers leaving the market for a substitute or complement in order to produce the good in question instead, or vice-versa.

The area of the region bounded by the supply and demand curves and the price axis is used as an estimate of how much wealth is created by the market for the good (neglecting externalities). It isn’t clear to me what way of defining supply and demand functions makes this the best metric, and it’s not going to be perfect in any case, as it measures wealth in units of money, and the value of a certain amount of money to someone can vary depending on circumstances (for instance, on how much money they already have). Another problem is that areas of smaller regions in a supply and demand graph are used as measures of deadweight loss caused by market distorsions, but the nature of the market distorsion in question would require us to use one particular meaning of supply and demand functions in order to correctly describe the effects of the distorsion; if this meaning is not one for which area in the supply and demand graph accurately represents value, then accurately representing deadweight loss as the area of a region in a graph isn’t possible.

Example

A possible explanation for why these subtleties are not emphasized is that they don’t make much difference in practice, as supply and demand functions tend to not depend too much on how exactly they’re defined. But we can construct examples in which they are quite different.

Consider the supply function in the market for left shoes. Assume no one actually buys one shoe at a time, so no matter what the prices of left and right shoes are, the demand for each will be the same. Also assume that making left shoes and making right shoes is always equally easy for the producers, so they would shift entirely to producing just the more expensive chirality of shoe if the prices differed. That is, there is a demand function for pairs of shoes, D_{pair}, and the joint demand function for left shoes and right shoes is given by D(p_{left},p_{right})=(D_{pair}(p_{left}+p_{right}),D_{pair}(p_{left}+p_{right})), since p_{left}+p_{right} is the price of a pair of shoes. And there is a supply function for total shoes, S_{shoes}, and the joint supply function for left shoes and right shoes is given by S(p_{left},p_{right})=(S_{shoes}(p_{left}),0) if p_{left}>p_{right}, (0,S_{shoes}(p_{right}) if p_{right}>p_{left}, and, if p_{left}=p_{right}=p, can be any (q_{left},q_{right}) such that q_{left}+q_{right}=S_{shoes}(p) (if you don’t like multi-valued functions, you can pretend we’re working with a continuous approximation to this joint supply function).

The market prices for left shoes and for right shoes must be the same, since otherwise the producers would only make shoes of one chirality. Let p^* be this market price for shoes, and now let’s figure out the supply function S_{left} for left shoes according to each of the three conventions I described in the section on possible answers.

If we are to assume that the prices of right shoes are constant, then S_{left}(p_{left})=0 for p_{left}<p^*, and S_{left}(p_{left})=S_{shoes}(p_{left}) for p_{left}>p^*, since all production shifts to the more expensive chirality of shoe when we vary the price of left shoes.

If we assume that the government taxes or subsidizes left shoes such that the price received by the producer for left shoes is p_{left}, then the price received by the producer for right shoes must also be p_{left}, since consumers will still be buying both chirality of shoe, which means prices must adjust so that producers will still make both chiralities of shoe (this will mean that consumers will pay different prices for left and right shoes, with the difference being the amount of the tax or subsidy). So the producers will make S_{shoes}(p_{left}) shoes in total. Since the consumers will buy equal numbers of each, the producers must make equal numbers of each in order to sell them all, so S_{left}(p_{left})=\frac{1}{2}S_{shoes}(p_{left}).

If we assume a new agent offers to buy or sell unlimited numbers of left shoes for p_{left}, then again right shoes are going to end up going for the same price (except in the extreme cases where the original producers don’t end up making any left shoes, or the original consumers don’t end up buying any shoes, but let’s suppose that doesn’t happen). The original producers will supply S_{shoes}(p_{left}) shoes in total. The original consumers will buy D_{pairs}(2p_{left}) pairs of shoes. In particular, the original consumers will buy D_{pairs}(2p_{left}) right shoes, which is the same as the number of right shoes sold by the original producers, since the new agent does not buy or sell any right shoes. Thus, the original producers make S_{left}(p_{left})=S_{shoes}(p_{left})-D_{pairs}(2p_{left}) left shoes.

Of these three purported supply functions, the first is radically different from the others, in that the latter two are continuous (if S_{shoes} and D_{pairs} are), but the first is discontinuous at p_{left}=p^*. The relationship between the latter two supply functions for left shoes depends on the relationship between S_{shoes} and D_{pairs}, but they certainly can be quite different.

One could argue that this example doesn’t count, because a pair of perfect complements can just be considered a single good sold as a bundle (as left and right shoes typically are in practice). But complements that are not perfect complements also exist, and producers do sometimes have some ability to shift between markets, so approximate versions of this example should exist in real life.

Joint supply and demand functions for infinitely many types of goods

We can, of course, consider joint supply and demand functions of arbitrarily many goods, instead of just two. For n goods, D(p_1,...,p_n) and S(p_1,...,p_n) would be the n-tuples consisting of the quantities demanded or supplied of each good when p_i is the price of the ith good. But sometimes goods can vary across a continuum of possibilities, and in such cases, it might not be appropriate to think of the market as just involving finitely many types of goods. For example, goods may vary by quality, with higher-quality goods being both more preferred by the consumers and harder to produce, and goods of different qualities substituting for each other. Or in the case of goods that can’t easily be moved, like buildings, consumers may have preferences about their location, and location may affect how easily the goods can be produced. Quality and location can each be modeled as varying across a continuum of possibilities.

Where X is some space of goods, prices can be represented as a function p:X\rightarrow\mathbb{R}_+, where p(x) is the price of the good x. Quantity can be represented as a finite measure \mu on X, where for Y\subseteq X, \mu(Y) is the combined quantity of all goods in Y.

So, where \mathbb{R}_+^X is the set of measurable functions X\rightarrow\mathbb{R}_+ and M(X) is the set of finite measures on X, joint supply and demand functions for X should be functions S:\mathbb{R}_+^X\rightarrow M(X) and D:\mathbb{R}_+^X\rightarrow M(X). The market equilibrium price function is the solution p^* to S(p^*)=D(p^*) (S and D should satisfy some conditions which should ensure that this exists), and the common value of S(p^*) and D(p^*) is the measure representing the market equilibrium quantities traded of types of goods in X.

Green Bus

[Inspired by this map]

“Everyone up! Company meeting in thirty minutes! Breakfast available in the mess hall until then,” yelled Sergeant Tucker. Even in my groggy state, I realized instantly that something unusual was happening. Getting woken up after no where near enough sleep wasn’t unusual; in fact, it was becoming the norm. I suspected that the Californian Peoples’ State’s attacks had been carefully timed to fuck up our sleep as much as possible. They might not even have been seriously trying to capture territory, just wearing us down.

But the lack of urgency in Sergeant Tucker’s voice was unprecedented, and he was giving us time to eat breakfast before doing anything else. There was no sound of gunfire, too.

I dressed and followed the rest of the platoon out of the barracks and into the mess hall. It was bright out already, but was in the middle of my sleep anyway because of a grueling firefight we’d had in the middle of the night, in which we’d repelled an attack that had threatened to cut off our last remaining access to the canal.

After a breakfast that was no more appetizing than what we’d been eating, though oddly generous in quantity compared to the carefully rationed meals we’d been getting, we were hurried out of the mess hall and into the briefing room.

Captain Smith began the briefing, “We have surrendered to the Californian Peoples’ State.” Hearing that was a relief, to be honest. We should have surrendered months ago, but Colonel Fitch was such a hardass I’d thought it was never going to happen.

Captain Smith continued, “We’ve reached a deal where, in exchange for surrendering the Sutter pocket, we will be given transportation to Reno instead of being taken prisoner. The first of the buses will be arriving in Sutter in about an hour. Bring your gun on the bus with you, and for God’s sake don’t ruin the deal by firing at any Californian soldiers. UN peacekeeping forces will be present to ensure the Peoples’ State doesn’t break the deal. The Californians will try to convince you to surrender individually to be taken prisoner instead of coming with the rest of us to Reno. Do not listen to them. Conditions in Reno are much better than here, so don’t think you’re better off in a prison camp than in Reno or anything foolish like that. If you have a family here in the Sutter pocket, they’ll be coming with you; you’re dismissed now, so you can go get them. Everyone else, pack up and reassemble here in twenty minutes. We’ll be marching to the bus stop together. Dismissed!”

I was in shock. Why would the Peoples’ State offer us this deal? If they’d just kept up the attacks for another couple weeks, we would have collapsed, and I would’ve thought the Californians would’ve caught onto this. Maybe the Californians were afraid that Free States of America forces in the Tahoe area would break the siege on the Sutter pocket soon? But at the rate the war’s been going, that didn’t seem likely, and besides, if Colonel Fitch suspected the same thing, there’d be no way he would have accepted the deal. Maybe the Californians were just bending over backwards to avoid incurring a few casualties (some of which would inevitably be civilians) in the process of taking the pocket by force. Or maybe it was a trick and we were all going to get taken prisoner anyway. The promise of UN peacekeepers made that last possibility seem somewhat unlikely; we all figured the UN was a bit biased in favor of the Peoples’ State, but it was unlikely they’d let them get away with breaking an evacuation agreement.

Like most of us, I didn’t have family with me in the Sutter pocket (or family at all, for that matter). I packed my things and regrouped with the others, and we marched into town. Another group of soldiers were already waiting at the bus stop when we arrived, and more groups joined us shortly thereafter. Soon, six green buses pulled up and stopped in front of us. It looked like the buses collectively just about fit all of us gathered in front of them, which was a small fraction of the total number of Free States of America soldiers in the pocket, even accounting for the fact that those with families in the pocket weren’t present. Probably others were getting picked up in the small portion of Yuba City we still controlled instead of consolidating us all in Sutter first.

Some Californian soldiers and UN peacekeepers got out of the buses. There weren’t very many UN peacekeepers; not enough to make much of a difference in a fight if anyone broke the agreement, anyway. But their presence was still useful, since no one wanted to piss off the UN.

A Californian officer held up a megaphone, and spoke, “To encourage you all to give up your arms instead of going to Reno, we’re sweetening the deal. If you stay, instead of becoming a prisoner of war, you will gain the rights of California citizens, able to live and work freely in California, and exempt from the draft, with the only additional restrictions being that, until the war ends, you will not be able to own weapons, and someone’ll check in on you occasionally to make sure you’re not up to anything fishy. If you’d like to go to the war zone in Reno anyway, you may now board the buses. If you’d like to stay, you can just walk right past the buses and hand over your weapons to any Californian officer on the other side of the buses.”

The bus doors opened, and we were ordered onto the bus, officers and senior NCOs standing to the side and glaring at us lest anyone think of not boarding. For the most part, this seemed to work. Everyone near the front of the lines boarded the buses, though once someone walked past the buses, a few more people down the line followed them. I got on the bus. Looking out the window, I saw that the proportion of people choosing to stay was increasing towards the end of the line, but still most people got on the buses. After the rank and file boarded, the officers and NCOs followed. Most of them anyway; many stayed behind, not to give up their arms, but because they had civilian family in the Sutter pocket and would take a later bus with them (a higher fraction of officers and NCOs than rank-and-file soldiers were married, so in particular, more of them had family in the pocket, though still most didn’t). Though I did see one sergeant in another company approach a bus, hesitate, and then run past it, to a visibly negative reaction from his company’s officers.

The bus’s engine started and the doors closed. “All right, let’s go,” said the bus driver, “We’ll be taking a slightly roundabout route so that we can stay within California-controlled territory until we reach the front line in Reno, but we will get you there in a few hours.” That sounded slightly suspicious, but the officers didn’t seem worried, and there were a couple UN peacekeepers on the bus, so I was pretty sure we weren’t getting kidnapped.

The bus pulled away, and we were on our way. It was a slow, very bumpy ride across the Sutter pocket and through Yuba City; the war had not been kind to highway 20. But once we left Yuba City and turned South, the ride was pretty smooth. Many of the other soldiers fell asleep. I wished I could do that, but I’ve never been able to sleep on the road, apparently not even in my current exhausted state.

Just past Placerville, the bus pulled over and stopped. “We’re gonna have to stop for about 45 minutes to recharge the bus,” announced the bus driver, “Meanwhile, you can get out, stretch your legs, and have some lunch.” Most people had woken up, and I could tell by looking around at everyone’s faces that I wasn’t the only one to be surprised by that announcement. It wasn’t surprising that these silly electric buses would have to regularly stop to recharge for an extended period of time, but no one had mentioned that they’d feed us, and I wouldn’t’ve expected the Californians to give enemy soldiers free food if the deal didn’t require them to. I don’t think even the officers on board had seen this coming.

The doors opened, and the food aroma was overpowering. Whatever it was, it smelled delicious. I was ravenous despite having had a larger than usual breakfast about three hours previously, and I think everyone else was too. Some soldiers at the front didn’t feel the need to wait for the officers to confirm to us that it was okay to leave the bus, and once they got up, the rest of us followed.

We were parked near what appeared to be an impromptu outdoor kitchen staffed by beautiful young women. We approached them, and were each handed generous servings of food, and immediately started scarfing them down. I stood in silence while I ate, next to Jones and Johnson, who were making small chat while they ate, though I wasn’t listening to what they were saying. When I was about three-quarters of my way through the meal and starting to slow down noticeably, a lady with a dazzling smile approached the three of us.

“Hey, I’m Trisha,” she introduced herself, extending her hand. We each shook her hand and introduced ourselves. “How y’all doing?” she asked. There was a bit of a pause as we all processed how to answer that.

I came up with an answer first. “Relieved, but also exhausted,” I said.

“Yup, that,” echoed Johnson, and Jones nodded.

“We’ve got some cots nearby if you want to lie down for a bit,” she said.

“Sure, that’d be great,” I said. She glanced at Jones and Johnson, but they both declined, and Jones mumbled something about not wanting to miss the bus.

Trisha gestured for me to follow her, and I did. “Do you want to be woken up before the bus leaves?” she asked. I thought about it for a while without answering.

“If I say no, is it the same deal we were offered back in Sutter?” I asked.

“Mhm,” she said.

“What about all my stuff that’s still on the bus?”

“We’ll get it for you.”

I didn’t say anything after that, and she didn’t press for a real answer until we reached the door of a building that I gathered was where the promised cots were, and she gave me a questioning glance.

“I’m not getting back on that bus,” I said.

Trisha smiled, said “welcome to the Californian Peoples’ State,” and left. I entered the building, fell onto a cot, and fell asleep almost instantly.

I awoke, feeling only somewhat refreshed, but desperately needing to pee. There were several other Free States soldiers on other cots now. I got up, I found a bathroom, and relieved myself. I saw there were showers, with a sign saying “10 MINS MAX” by them. I used to take showers twice that long all the time, but now being able to take a shower for 10 whole minutes sounded like unbelievable luxury. I wasn’t sure whether the showers were for me or not, but I decided to just go for it instead of trying to find someone to ask. A clock started counting down from 10 minutes when I turned the water on. I used up almost the whole 10 minutes, and when I got dressed again, it struck me how much my uniform stank. I’d already known we’d been filthy, but I guess I’d adjusted to it and it was only apparent again now that it contrasted with my clean body.

I left the building and immediately ran into a Californian official who asked my name, told me to fill out some paperwork (which fortunately wasn’t too long), took a picture of me, and printed out and handed me an ID hard.

“Your duffle bag’s right over there,” he said, pointing to my belongings (sans gun) in a pile of luggage, “You can take it now or leave it and come back for it whenever. You can stay in this building again tonight. Tomorrow morning, some of those buses’ll be heading back to Yuba City, and others’ll be going to Sacramento and the bay. There will be job and housing fairs in all those locations, and also one in Placerville in case you decide to just stay here. We’ve got some pamphlets here summarizing what the available options will be in case that helps you decide where you want to go. And if you want to go somewhere else in the Peoples’ State, let me know, and it is likely we will be able to help you out. Any questions?”

“Not right now. Thanks,” I said. I took a pamphlet, folded it up and put it in my pocket without reading it, and walked back to the bus charging station. The outdoor kitchen was still in operation, or perhaps in operation again. But the people there were different. Most of them were older than the women who had been there when I’d first arrived, and there were also some children present. Their genders were much more balanced, though still majority female. There were also some recently former Free States soldiers like me hanging around.

A woman waved at me as I approached, and it took me a second to realize it was Trisha; apparently not all the women who had been here earlier were gone. She was dressed much more conservatively than she had been earlier.

“This is how you dress when you’re not trying to manipulate enemy soldiers?” I guessed.

“Um, not really. There’s actually another bus coming soon with the families from your company,” she said.

“Oh, so you’re dressing to manipulate a different demographic of enemy soldier.”

“Yes, exactly.”

“Hm, I didn’t exactly sign up to stand here so my fellow soldiers on their way to Reno could stare at me on their way by and judge me for abandoning them.”

“Well, you better scram quick, then. The bus’ll be here any moment now. Some of your comrades who joined us are hanging out over that hill,” she said, pointing.

I thought about it. “Actually, you know what, my buddy Kyle and his wife Ashley would probably be on that bus, and as awful as telling them I defected to their faces sounds, letting them find out later in Reno without the chance to say goodbye sounds worse. I’ll stick around.”

“Alright.”

“I bet you don’t eat like this every day,” I said, gesturing at the kitchen.

“Not quite,” she said, “Though there haven’t really been food shortages, so we’ve been eating pretty well. The main limitation is that anything that takes a lot of water to grow is a bit expensive, since we can’t grow it in California, and the war hasn’t been great for trade. If you’re wondering about shortages causing problems, the main thing is water. There’s enough to drink, of course, but the water rationing is tight enough that I usually don’t get to shower and wash my clothes as much as I’d like. We got a water bonus for participating in these greeting parties, so everyone around here is a bit cleaner than usual. Though we always get to shower and do laundry more than it looks like you guys have been, no offense, so I’m not sure if we really needed to bother cleaning up more than usual. Anyway, I usually shower for about 5 minutes every 3 days and use up my water ration.”

“So that 9-minute show I just took…?” I asked.

“Was part of your defection bonus. You didn’t just use up all your water for the week; don’t worry. I’m just warning you about what things will be like once you settle in. Though not for too long, hopefully. We expect the water crisis to end this year, so it’s really only a short term problem.”

If they expected the water crisis to end this year, that meant that they expected to capture sources of water from Free States of America. Holding sources of water and denying them to California had been a deliberate strategy by the Free States of America to try to weaken California, which hadn’t yet been terribly effective. We were all starting to figure California would recapture most of those water sources from us instead of collapsing, but if the Californians thought that was going to happen this year, then they were feeling even more optimistic than we thought they should.

A green bus pulled up. Trisha excused herself and ran off to take care of something. I watched people file out of the bus, looking for Kyle and Ashley. Instead, I saw Sergeant Tucker, Lieutenant Dan, their wives, and Sergeant Tucker’s five-year-old daughter get off the bus and walk vaguely in my direction. I looked away and pretended I didn’t see them. They kept walking closer.

“Private Carlson!” said Lieutenant Dan, “What the hell are y’all doing still in Placerville?” Dammit!

“Goddammit, Carlson! You defected, didn’t you?!” said Sergeant Tucker, with a stern look. I nodded sheepishly. This was even more uncomfortable than telling that to Kyle and Ashley would have been. Fortunately, the tension was interrupted by a Californian boy, maybe about eleven or so, carrying boxes of food and handing them out to us. I took one even though I wasn’t sure if it was only intended for the newcomers.

The kid stuck around and introduced himself as Ben, and we took turns introducing ourselves to him in between mouthfuls of food.

“They’re making you do this?” Linda Tucker asked Ben.

“No, my teacher told us about it as a volunteer activity. No one had to be here,” said Ben.

“Wait, the schools are still running here?” asked Mrs. Tucker.

“Of course. Summer break doesn’t start until May,” said Ben. Sergeant and Mrs. Tucker exchanged glances.

“Have things changed around here in the last few years, you know, with the war and all?” asked Mrs. Tucker.

“Yeah, my Dad’s away on the front line near Redding. I haven’t seen him in almost a year.” Ben looked sad.

“That’s it?” asked Mrs. Tucker.

“Uh, I guess so. Mom and my siblings and I are doing fine,” said Ben.

Sergeant and Mrs. Tucker exchanged some more glances. No one said anything, but it looked like they were having a whole private conversation with their eyes.

Sergeant Tucker looked away and made some awkward eye contact with Lieutenant Dan just as Mrs. Tucker said, “We’re not going to Reno.”

Lieutenant Dan looked exasperated. “Linda, you goddamn hippy! You know everything’s gonna be fine when we get back to the Free States, right?”

“We’re not going to Reno,” Mrs. Tucker repeated. Sergeant Tucker nodded. Lieutenant Dan rolled his eyes and let out a disgusted grunt.

While this was going on, I overheard a conversation behind me between a Californian and a Free States soldier’s wife who had apparently overheard Mrs. Tucker’s exchange with Ben, and asked, “Is school mandatory? I wouldn’t want to send my child to a public school.”

“No Ma’am, lots of people homeschool their kids,” said the Californian.

“But people who homeschool their kids still have to pay taxes for other people to go to public schools, right?”

“Well yes, they do pay taxes, Ma’am. Although, actually a fairly small amount of that has been going to schools lately.” The lady seemed reassured by this somehow, even though it was really just a diplomatic way of saying that funds had been diverted from schools to the war effort. I wasn’t a big fan of taxpayer-funded public education myself, but I had trouble imagining why anyone would think that was any better.

I heard Ashley’s voice, “Hey, there’s Cole!” I turned my head and saw Kyle and Ashley running towards me. I left the gaggle I was in, ran towards them, and hugged both.

“So, you defected?” asked Kyle, sounding surprisingly not that disappointed.

“Yeah.”

“We were thinking of doing the same, honestly,” said Ashley, “Just don’t tell the brass over there.”

“Actually the Tuckers are also defecting,” I said.

“You’re shitting me!” said Kyle.

“No, they’re really doing it.”

“I guess that would explain the tension you can see between the Tuckers and the Dans right now,” said Ashley.

Word about the Tuckers defecting went around pretty fast, and seemed to start a sort of domino effect. When the bus continued on its way to Reno, there were maybe a handful of people still on it. Not including the Dans, amazingly enough.

Soon after, another bus pulled up from the other direction. Private Jones and a few other soldiers disembarked. I saw Jones look through the crowd until he found Private Johnson, who was turned away and hadn’t seen. Jones ran towards him and called out to him. They hugged each other. Kyle, Ashley, and I wandered over to see what was going on.

“I thought you were going to Reno,” said Johnson.

“The bus pulled over in South Lake Tahoe next to another green bus, and they told us that since they were both only half full, they’d be consolidating into just one bus for the rest of the trip. After I got out of the bus to board the other one, I asked if it was too late to change my mind, and ended up getting back on the same bus, turning around, and heading back here,” said Jones.

“Wait, I thought they said the bus would be staying in California-controlled territory all the way until Reno. Don’t we control South Lake Tahoe?” asked Johnson. “We” might not have been the best pronoun to refer to the Free States by, now that we’d all defected to California, but no one pointed this out.

“Not anymore, we don’t,” said Jones, “There were Californian soldiers all over the place. No Free States soldiers or signs of fighting to be seen.”

“Jesus. I wonder why they went that far before consolidating into fewer buses. They could have done that here in Placerville,” Johnson pointed out.

“I don’t know, but my guess is they just wanted to flex on us by parking us in front of a California garrison in South Lake Tahoe,” said Jones, “One other thing. Get this: Just before we pulled in here, we passed another station just like this one. I saw a green bus pulling away from it in the other direction towards Reno. Then I looked at the people still milling around there on the ground, and there was Mrs. Fitch with her kids.”

“The Fitches defected?!” Johnson asked incredulously.

Jones shook his head, “Not Colonel Fitch. I only saw Mrs. Fitch and their kids.”

“Yeah, but you might have just not seen him. I mean, if his wife and kids were there,” said Johnson.

“Yeah, sure. I can’t prove beyond all doubt that Colonel Fitch was on the bus. But if you seriously think that crazy son-of-a-bitch would stay with his wife and kids instead the Free States of America, then I’ve got a bridge to sell you.”

Exact 2-cycles are degenerate isomorphisms

The situation in which you have vector spaces V and W, and linear maps f:V\rightarrow W and g:W\rightarrow V such that \ker\left(f\right)=\text{im}\left(g\right) and \ker\left(g\right)=\text{im}\left(f\right) often arises in the situation in which you would have an isomorphism between V and W if you knew how to divide by 0. Specifically, this happens when you’d need to divide by 0 exactly once; in similar situations in which you’d need to know how to divide by 0 multiple times in order to get an isomorphism, you get f:V\rightarrow W and g:W\rightarrow V such that f\circ g=0 and g\circ f=0 but whose kernels and images are not necessarily equal.

I’ll call such a pair \left(f,g\right) with \ker\left(f\right)=\text{im}\left(g\right) and \ker\left(g\right)=\text{im}\left(f\right) an exact 2-cycle of vector spaces. Note that the two vector spaces V and W in an exact 2-cycle are in fact isomorphic, as \dim\left(V\right)=\dim\left(\ker\left(f\right)\right)+\dim\left(\text{im}\left(f\right)\right)=\dim\left(\text{im}\left(g\right)\right)+\dim\left(\ker\left(g\right)\right)=\dim\left(W\right).

Adjugates

Given a finite-dimensional vector space V and an invertible linear map f:V\rightarrow V, its adjugate is almost its inverse; you just have to divide by \det\left(f\right). If f:V\rightarrow V is not invertible, then of course, \det\left(f\right)=0, so dividing by \det\left(f\right) doesn’t work. But if f has nullity 1, then \ker\left(f\right)=\text{im}\left(\text{adj}\left(f\right)\right) and \ker\left(\text{adj}\left(f\right)\right)=\text{im}\left(f\right). That is, \left(f,\text{adj}\left(f\right)\right) is an exact 2-cycle. If f has nullity N\left(f\right)\geq2, then \det\left(f\right)=0^{N\left(f\right)}, and hence inverting f requires dividing by 0 more than once, and \text{adj}\left(f\right)=0.

Homogeneous polynomials and multilinear forms

Given a vector space V over a field k, let k\left[V\right]_{2} denote the space of quadratic forms on V (that is, homogeneous quadratic polynomial maps V\rightarrow k), and let Sym^{2}V^{*} denote the space of symmetric bilinear forms on V.

Given a symmetric bilinear form B on V, we can construct a quadratic form Q on V by Q\left(\vec{x}\right):=B\left(\vec{x},\vec{x}\right). This gives us a map f:Sym^{2}V^{*}\rightarrow k\left[V\right]_{2} by f\left(B\right)\left(\vec{x}\right)=B\left(\vec{x},\vec{x}\right).

2B\left(\vec{x},\vec{y}\right)=B\left(\vec{x}+\vec{y},\vec{x}+\vec{y}\right)-B\left(\vec{x},\vec{x}\right)-B\left(\vec{y},\vec{y}\right), so we can recover B from f\left(B\right) by B\left(\vec{x},\vec{y}\right)=\frac{1}{2}\left(f\left(B\right)\left(\vec{x}+\vec{y}\right)-f\left(B\right)\left(\vec{x}\right)-f\left(B\right)\left(\vec{y}\right)\right). That is, the map g:k\left[V\right]_{2}\rightarrow Sym^{2}V^{*} given by g\left(Q\right)\left(\vec{x},\vec{y}\right)=Q\left(\vec{x}+\vec{y}\right)-Q\left(\vec{x}\right)-Q\left(\vec{y}\right) is twice the inverse of f.

This doesn’t quite work if \text{char}\left(k\right)=2, since we can’t do the part where we divide by 2. In fact, f is not invertible in this case. But g is still a well-defined map k\left[V\right]_{2}\rightarrow Sym^{2}V^{*}, and it’s still true that g\circ f=2 id_{Sym^{2}V^{*}} and f\circ g=2 id_{k\left[V\right]_{2}}; it’s just that now that means g\circ f=0 and f\circ g=0. In fact, \ker\left(f\right)=\text{im}\left(g\right) and \ker\left(g\right)=\text{im}\left(f\right). \ker\left(g\right) and \text{im}\left(f\right) are the \dim\left(V\right)-dimensional space of diagonal quadratic forms (polynomials that are linear combinations of squares of linear functions V\rightarrow k), and \ker\left(f\right) and \text{im}\left(g\right) are the {\dim\left(V\right) \choose 2}-dimensional space of alternating symmetric bilinear forms. Thus Sym^{d}V^{*} and k\left[V\right]_{2} are both \dim\left(V\right)+{\dim\left(V\right) \choose 2}-dimensional.

Similar things happen with higher degree homogeneous polynomials and symmetric multilinear forms. Let k\left[V\right]_{d} be the space of homogeneous degree-d polynomials on V and Sym^{d}V^{*} the space of symmetric d-linear forms on V. We have functions f:Sym^{d}V^{*}\rightarrow k\left[V\right]_{d} given by f\left(\Phi\right)\left(\vec{x}\right):=\Phi\left(\vec{x},...,\vec{x}\right) and g:k\left[V\right]_{d}\rightarrow Sym^{d}V^{*} given by g\left(\phi\right)\left(\vec{x}^{1},...,\vec{x}^{d}\right)=\sum_{I\subseteq\left[d\right]}\left(-1\right)^{d-\left|I\right|}\phi\left(\sum_{i\in I}\vec{x}^{i}\right). g\left(f\left(\Phi\right)\right)=d!\Phi and f\left(g\left(\phi\right)\right)=d!\phi, so if \text{char}\left(k\right)=0 or \text{char}\left(k\right)>d, then f and g are bijections, and d! times each others’ inverse. Otherwise, g\circ f=0 and f\circ g=0. If \frac{d}{2}<\text{char}\left(k\right)\leq d, then \text{char}\left(k\right) divides d! with multiplicity 1, and \ker\left(f\right)=\text{im}\left(g\right) and \ker\left(g\right)=\text{im}\left(f\right). If 1<\text{char}\left(k\right)\leq\frac{d}{2}, then \text{char}\left(k\right) divides d! with multiplicity \geq2, and all bets are off. Though \dim\left(k\left[V\right]_{d}\right)=\dim\left(Sym^{d}V^{*}\right)={\dim\left(V\right)+d-1 \choose d}, no matter what \text{char}\left(k\right) is.

Newtonian spacetime

In special relativity, we work with a 4-dimensional (3 for space and 1 for time) real vector space T, with a symmetric bilinear form \left\langle \cdot,\cdot\right\rangle, called the Minkowski inner product, of signature \left(-+++\right); that is, the associated quadratic form can be given, in coordinates, by -t^{2}+x^{2}+y^{2}+z^{2} (t is the time coordinate and x,y,z are spatial coordinates for some reference frame). If \left\langle \vec{v},\vec{v}\right\rangle >0, then \vec{v} is spacelike, and \sqrt{\left\langle \vec{v},\vec{v}\right\rangle } measures its distance (in the reference frame in which its temporal coordinate is 0). If \left\langle \vec{v},\vec{v}\right\rangle <0, then \vec{v} is timelike, and \sqrt{-\left\langle \vec{v},\vec{v}\right\rangle } measures its duration (in the reference frame in which it is at rest). By currying, the Minkowski inner product can be seen as a linear map T\rightarrow T^{*}, where T^{*} is the vector space of linear maps T\rightarrow\mathbb{R}. Since the Minkowski inner product is nondegenerate, this linear map T\rightarrow T^{*} is an isomorphism.

In Newtonian physics, things are a little different. We can still work in 4-dimensional spacetime, but we don’t have a single Minkowski inner product measuring both distance and duration. We do have a global notion of time; that is, there’s a linear map t:T\rightarrow\mathbb{R} that tells you what time it is at each point in spacetime. \ker\left(t\right) is space in the present moment, so it should be Euclidean space; that is, it should be equipped with an ordinary inner product.

The time function t induces a degenerate inner product on T by \left\langle \vec{v},\vec{w}\right\rangle :=t\left(\vec{v}\right)t\left(\vec{w}\right). As before, this can be seen as a linear map T\rightarrow T^{*} (it sends \vec{v} to t\left(\vec{v}\right)t), with 1-dimensional image \text{span}\left(t\right) and 3-dimensional kernel \ker\left(t\right).

The ordinary inner product on \ker\left(t\right) gives us a degenerate inner product on T^{*}: since our inner product on \ker\left(t\right) is non-degenerate, it induces an isomorphism between \ker\left(t\right) and its dual, and hence induces an inner product on \ker\left(t\right)^{*}. There’s a canonical map T^{*}\rightarrow\ker\left(t\right)^{*} given by restriction: \varphi\mapsto\varphi\restriction_{\ker\left(t\right)}. So given \varphi,\psi\in T^{*}, we can define their inner product to be the spatial inner product of their restrictions to \ker\left(t\right). This can be seen as a linear map T^{*}\rightarrow T (given \varphi:T\rightarrow\mathbb{R}, restrict it to \ker\left(t\right), and then find the element of \ker\left(t\right)\subseteq T that corresponds to it via the spatial inner product) with image \ker\left(t\right) and kernel \text{span}\left(t\right). We have thus found canonical maps T\rightarrow T^{*} and T^{*}\rightarrow T such that the kernel of each is the image of the other.

Why?

In the spacetime example, it is conventional in special relativity to normalize the speed of light to 1. But another thing we can do is let the speed of light be the variable c. So \left\langle \left[\begin{array}{c} t_{1}\\ x_{1}\\ y_{1}\\ z_{1} \end{array}\right],\left[\begin{array}{c} t_{2}\\ x_{2}\\ y_{2}\\ z_{2} \end{array}\right]\right\rangle =-c^{2}t_{1}t_{2}+x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{1}. As a map T\rightarrow T^{*}, this is \left[\begin{array}{c} t\\ x\\ y\\ z \end{array}\right]\mapsto\left[\begin{array}{cccc} -c^{2}t & x & y & z\end{array}\right]. The inverse map T^{*}\rightarrow T is \left[\begin{array}{cccc} \tau & \alpha & \beta & \gamma\end{array}\right]\mapsto\left[\begin{array}{c} -c^{-2}\tau\\ \alpha\\ \beta\\ \gamma \end{array}\right], or, as an inner product on T^{*}, \left\langle \left[\begin{array}{cccc} \tau_{1} & \alpha_{1} & \beta_{1} & \gamma_{1}\end{array}\right],\left[\begin{array}{cccc} \tau_{2} & \alpha_{2} & \beta_{2} & \gamma_{2}\end{array}\right]\right\rangle =-c^{-2}\tau_{1}\tau_{2}+\alpha_{1}\alpha_{2}+\beta_{1}\beta_{2}+\gamma_{1}\gamma_{2}. We’re going to want to take a limit as c\rightarrow\infty and get something finite, so we’ll have to scale our inner product on T down by a factor of c^{2}, giving us \left\langle \left[\begin{array}{c} t_{1}\\ x_{1}\\ y_{1}\\ z_{1} \end{array}\right],\left[\begin{array}{c} t_{2}\\ x_{2}\\ y_{2}\\ z_{2} \end{array}\right]\right\rangle =-t_{1}t_{2}+c^{-2}x_{1}x_{2}+c^{-2}y_{1}y_{2}+c^{-2}z_{1}z_{1}, or, as a map T\rightarrow T^{*}, \left[\begin{array}{c} t\\ x\\ y\\ z \end{array}\right]\mapsto\left[\begin{array}{cccc} -t & c^{-2}x & c^{-2}y & c^{-2}z\end{array}\right]. The limit c\rightarrow\infty gives us our temporal inner product on Newtonian spacetime, \left\langle \left[\begin{array}{c} t_{1}\\ x_{1}\\ y_{1}\\ z_{1} \end{array}\right],\left[\begin{array}{c} t_{2}\\ x_{2}\\ y_{2}\\ z_{2} \end{array}\right]\right\rangle =-t_{1}t_{2}, and our spatial inner product on the dual space \left\langle \left[\begin{array}{cccc} \tau_{1} & \alpha_{1} & \beta_{1} & \gamma_{1}\end{array}\right],\left[\begin{array}{cccc} \tau_{2} & \alpha_{2} & \beta_{2} & \gamma_{2}\end{array}\right]\right\rangle =\alpha_{1}\alpha_{2}+\beta_{1}\beta_{2}+\gamma_{1}\gamma_{2}, giving us our exact 2-cycle of maps between T and T^{*}, \left[\begin{array}{c} t\\ x\\ y\\ z \end{array}\right]\mapsto\left[\begin{array}{cccc} -t & 0 & 0 & 0\end{array}\right] and \left[\begin{array}{cccc} \tau & \alpha & \beta & \gamma\end{array}\right]\mapsto\left[\begin{array}{c} 0\\ \alpha\\ \beta\\ \gamma \end{array}\right]. (I did say that this should only work if we have to divide by 0 once, not if we must do so twice, and this involved c^{2}, but we never used c on its own anywhere, so we can just say c=\sqrt{\infty}, and it’s fine).

Let’s go back to the first example. Given f:V\rightarrow V of nullity 1, perturb f slightly to make it invertible by adding an infinitesimal \varepsilon times some map g:V\rightarrow V. The only condition we need g to satisfy is g\left(\ker\left(f\right)\right)\nsubseteq\text{im}\left(f\right). That way \det\left(f+\varepsilon g\right), which must be a multiple of \varepsilon, is not a multiple of \varepsilon^{2}. \left(f+\varepsilon g\right)\circ\text{adj}\left(f+\varepsilon g\right)=\text{adj}\left(f+\varepsilon g\right)\circ\left(f+\varepsilon g\right)=\det\left(f+\varepsilon g\right)id_{V}. Clearly f\circ\text{adj}\left(f\right)=\text{adj}\left(f\right)\circ f=\det\left(f\right)id_{V}=0. Given \vec{x}\in\ker\left(f\right), \left(f+\varepsilon g\right)\left(\vec{x}\right)=\varepsilon g\left(\vec{x}\right), so \text{adj}\left(f+\varepsilon g\right)\left(\varepsilon g\left(\vec{x}\right)\right)=\det\left(f+\varepsilon g\right)\vec{x}. Hence \text{adj}\left(f+\varepsilon g\right)\left(\frac{\varepsilon}{\det\left(f+\varepsilon g\right)}g\left(\vec{x}\right)\right)=\vec{x}. Since \det\left(f+\varepsilon g\right) has 0 constant term but nonzero coefficient of \varepsilon, \frac{\varepsilon}{\det\left(f+\varepsilon g\right)} can be evaluated at \varepsilon=0, and has a nonzero, finite value. Then \text{adj}\left(f\right)\left(\frac{\varepsilon}{\det\left(f+\varepsilon g\right)}\vert_{\varepsilon=0}g\left(\vec{x}\right)\right)=\vec{x}. So \left(f,\text{adj}\left(f\right)\right) forms an exact 2-cycle for reasons closely relating to the fact that perturbing each of them infinitesimally can make them inverses up to an infinitesimal scalar multiple.

Now, in the second example, where V is a vector space over a field k of positive characteristic, \frac{d}{2}<\text{char}\left(k\right)\leq d, and we have an exact 2-cycle f:Sym^{d}V^{*}\rightarrow k\left[V\right]_{d}, g:k\left[V\right]_{d}\rightarrow Sym^{d}V^{*}, let {\cal O} be an integral domain of characteristic 0 with a unique maximal ideal \mathfrak{m}, such that {\cal O}/\mathfrak{m}=k and \text{char}\left(k\right)\notin\mathfrak{m}^2 (for instance, if k=\mathbb{F}_{p}, we can use {\cal O}=\mathbb{Z}_{p} and \mathfrak{m}=p\mathbb{Z}_{p}). Lift V to a free {\cal O}-module \tilde{V} with \tilde{V}\otimes k=V (in coordinates, this means, instead of V=k^{n}, work with \tilde{V}={\cal O}^{n}, which carries a natural map to k^{n} by reducing each coordinate mod \mathfrak{m}). Then there are natural maps \tilde{f}:Sym^{d}\tilde{V}^{*}\rightarrow{\cal O}\left[\tilde{V}\right]_{d} and \tilde{g}:{\cal O}\left[\tilde{V}\right]_{d}\rightarrow Sym^{d}\tilde{V}^{*} such that \tilde{g}\circ\tilde{f}=d!id_{Sym^{d}\tilde{V}^{*}} and \tilde{f}\circ\tilde{g}=d!id_{{\cal O}\left[\tilde{V}\right]_{d}}, and \tilde{f} and \tilde{g} reduce mod \mathfrak{m} to f and g, respectively. Where K is the field of fractions of {\cal O} (so K=\mathbb{Q}_p in our example with k=\mathbb{F}_p and \cal{O}=\mathbb{Z}_p), \tilde{f}\otimes K:Sym^{d}\left(\tilde{V}\otimes K\right)^{*}\rightarrow K\left[\tilde{V}\otimes K\right]_{d} and \tilde{g}\otimes K:K\left[\tilde{V}\otimes K\right]_{d}\rightarrow Sym^{d}\left(\tilde{V}\otimes K\right)^{*} are bijections (in coordinates, \tilde{V}\otimes K=K^{n}, and tensoring a map with K just means the same map extended over the field of fractions), as they are inverses of each other up to a multiple of d!, which is invertible in K. Since \text{char}\left(k\right)\leq d, d!\in\mathfrak{m}, and g\circ f=0 and f\circ g=0. Given \phi\in\ker\left(g\right), if we lift \phi to \tilde{\phi}\in{\cal O}\left[\tilde{V}\right]_{d}, \tilde{g}\left(\tilde{\phi}\right)\in\mathfrak{m}Sym^{d}\tilde{V}^{*}. Since \text{char}\left(k\right)>\frac{d}{2}, d!\notin\mathfrak{m}^{2}, and hence \frac{\tilde{g}\left(\tilde{\phi}\right)}{d!}\in Sym^{d}\tilde{V}^{*}, and of course, \tilde{f}\left(\frac{\tilde{g}\left(\tilde{\phi}\right)}{d!}\right)=\tilde{\phi}. Reducing mod \mathfrak{m}, we get f\left(\frac{\tilde{g}\left(\tilde{\phi}\right)}{d!}\mod\mathfrak{m}\right)=\phi. Thus \ker\left(g\right)=\text{im}\left(f\right). Similarly, given \Phi\in\ker\left(f\right), lift \Phi to \tilde{\Phi}\in Sym^{d}\tilde{V}^{*}. \tilde{f}\left(\tilde{\Phi}\right)\in\mathfrak{m}{\cal O}\left[\tilde{V}\right]_{d}. \frac{\tilde{f}\left(\tilde{\Phi}\right)}{d!}\in{\cal O}\left[\tilde{V}\right]_{d}, and \tilde{g}\left(\frac{\tilde{f}\left(\tilde{\Phi}\right)}{d!}\right)=\tilde{\Phi}. Reducing mod \mathfrak{m}, we get g\left(\frac{\tilde{f}\left(\tilde{\Phi}\right)}{d!}\mod\mathfrak{m}\right)=\Phi. Thus \ker\left(f\right)=\text{im}\left(g\right). So \left(f,g\right) forms an exact cycle because, in K, they are inverses up to a factor of d!, which we can divide by, and which is 0 with multiplicity 1 in k, since d!\in\mathfrak{m}\setminus\mathfrak{m}^{2}.

The general story

All three arguments from the previous section took the following form: Let {\cal O} be a discrete valuation ring with residue field k, field of fractions K, and valuation \nu:K^{\times}\rightarrow\mathbb{Z}. Let V and W be free {\cal O}-modules, and let f:V\rightarrow W and g:W\rightarrow V be such that f\circ g=\varepsilon id_{W} and g\circ f=\varepsilon id_{V}, for some \varepsilon\in{\cal O} with \nu\left(\varepsilon\right)=1. Then f\otimes K:V\otimes K\rightarrow W\otimes K and g\otimes K:W\otimes K\rightarrow V\otimes K are isomorphisms, and each is \varepsilon times the inverse of the other. f\otimes k:V\otimes k\rightarrow W\otimes k and g\otimes k:W\otimes k\rightarrow V\otimes k form an exact 2-cycle: they compose to 0 because f and g compose to \varepsilon id, which goes to 0 in k, and given \vec{x}\in V\otimes k such that \left(f\otimes k\right)\left(\vec{x}\right)=0, we can lift \vec{x} to \tilde{x}\in V. f\left(\tilde{x}\right)\in\varepsilon W, so \varepsilon^{-1}f\left(\tilde{x}\right)\in W, and g\left(\varepsilon^{-1}f\left(\tilde{x}\right)\right)=\tilde{x}, so tensoring with k sends \varepsilon^{-1}f\left(\tilde{x}\right) to some \vec{y}\in W such that \left(g\otimes k\right)\left(\vec{y}\right)=\vec{x}. Thus \ker\left(f\right)=\text{im}\left(g\right). The same argument with f and g switched shows \ker\left(g\right)=\text{im}\left(f\right). The exact 2-cycle \left(f\otimes k,g\otimes k\right) is a sort of shadow of the isomorphisms f\otimes K,g\otimes K.

In the spacetime example, K=\mathbb{R}\left(\left(c^{-2}\right)\right), {\cal O}=\mathbb{R}\left[\left[c^{-2}\right]\right], k=\mathbb{R}, and \varepsilon=c^{-2}. In the adjugates example, K=k\left(\left(\varepsilon\right)\right), {\cal O}=k\left[\left[\varepsilon\right]\right], and the \varepsilon in the general story is \det\left(f+\varepsilon g\right). In the homogeneous polynomials and symmetric multilinear forms example, K is a discretely valued field of characteristic 0 with residue field k, {\cal O} is its valuation ring, and \varepsilon=d!.

All exact 2-cycles of vector spaces can be fit into this general story. Given any exact 2-cycle f:V\rightarrow W, g:W\rightarrow V (V, W vector spaces over k), we can take a discretely valued field K with residue field k, and then lift f,g to \tilde{f},\tilde{g} with \tilde{g}\circ\tilde{f}=\varepsilon id for some \varepsilon\in K with \nu\left(\varepsilon\right)=1, exactly the conditions in the above argument.

What more?

What about exact 2-cycles in abelian categories other than vector spaces? In general, the two objects in an exact 2-cycle need not be isomorphic. For instance, with abelian groups, there’s an exact 2-cycle between the 4-element cyclic group and the Klein four-group. Though two objects in an exact 2-cycle must be isomorphic in any category in which every short exact sequence splits (this is the gist of the dimension-counting argument from the beginning showing that two vector spaces in an exact 2-cycle must be isomorphic). Is there still some way of seeing exact 2-cycles as degenerate isomorphisms even in contexts in which there need not be actual isomorphisms?

Also, what about exact n-cycles? That is, a cycle of n functions such that the image of each is the kernel of the next. If an exact 2-cycle is a degenerate form of an isomorphism, and an isomorphism is an exact sequence of length 2, then perhaps an exact 3-cycle should be a degenerate form of an exact sequence of length 3 (i.e. a short exact sequence). This is hard to picture, as a short exact sequence is not symmetric between its objects. However, for reasons not understood by me, algebraic topologists care about exact 3-cycles in which two of the three objects involved are the same (these are called exact couples), and this apparently has something to do with short exact sequences in which the first two objects are isomorphic, which provides some support for the idea that exact 3-cycles should have something to do with short exact sequences. An exact sequence of length 1 just consists of the 0 object, so this suggests an exact 1-cycle (i.e. an endomorphism of an object whose kernel and image are the same) should be considered a degenerate form of the 0 object, which is also hard to picture.

It’s a big world out there

Kimi and Jerilyn’s mother continued their bedtime story, “And then Adam the bat’s friend, Jane the fish, showed up and stuck her head out of the water. Adam hastily finished chewing the beetle he was eating before exclaiming, ‘Jane! Where’ve you been? We haven’t seen each other in ages.’ ‘I’ve been exploring a marvelous new worlds. I wish I could show you,’ said Jane the fish. ‘Who says you can’t? I can’t swim, but you could carry me,’ said Adam the bat. ‘I suppose so. You’ll have to hold your breath, though,’ said Jane. So Adam took in a big breath of air, and held on to Jane’s back. ‘Hold on tight!’ said Jane, and plunged below the surface. She swam, and swam, and swam, for what seemed like eternity, especially to the air-breather on her back trying to hold his breath. Finally, just as Adam was about to run out of breath, Jane the fish surfaced again, and Adam the bat took in a big breath of fresh air. There wasn’t a rock ceiling above their heads, just empty space all the way up. And far, far, far above the ground there was an enormous intense light, so bright that neither bat nor fish could look directly into it without hurting their eyes, and it illuminated their surroundings so much that they could see far around them from light alone, without echolocation. Adam shook his wings dry, took off, flew up, and kept climbing higher into the air, with no rock ceiling above him to limit his ascent. Eventually he got spooked by how far he’d gotten from any solid object, so he started flying back down, and returned to Jane in the water. That’s all for now, dears. Sleep tight.” Their mother kissed each of them on the forehead.

“Mom,” asked Kimi, “could there actually be a light that bright?”

“I don’t know,” she answered, “but according to ancient myth, there is such a thing. Or was, at least. I suppose there’s no way of knowing whether it’s still around. It’s in a far away world with no rock ceiling too, so goes the myth. Sweet dreams.” Their mother left.

“No rock ceiling,” Kimi whispered, “That’s even wilder than the thing about the light. Like, would it just be air all the way up forever? Surely there’d have to be an end somewhere, right?”

“Maybe there is a rock ceiling there, but it’s so high up that you can’t hear the echo,” Jerilyn suggested.

“Wow, that would be so disorienting, not being able to hear the echo off the rock ceiling,” said Kimi.

“Given what Mom said about the light, maybe you could see the rock ceiling even if you couldn’t echolocate it,” said Jerilyn.

“But I guess if people thought there wasn’t a rock ceiling at all, it must be high enough that you can’t see it either,” said Kimi.

“I guess so,” Jerilyn agreed.

“Jerilyn,” said Kimi.

“What?”

“Do you think it’s real?”

“No,” said Jerilyn.

“Are you sure?”

Jerilyn hesitated. “No,” she said. She really had no way of knowing for sure, however outlandish it may sound.

“Jerilyn.”

“What?”

“I’m not actually feeling all that tired. Are you?”

“Eh, somewhat, but not especially.”

“Let’s go find the place Mom was talking about.”

Jerilyn thought about it. On the one hand, the mythical place probably didn’t exist, and even if it did, there was no way they were going to find it. On the other hand, an adventure might be fun. “Let’s do it,” she said.

They snuck off and made their way to their canoe. They avoided making sounds so as not to advertise their presence, so they had to rely on touch to find their way, but they knew the route well enough that that wasn’t a huge impediment.

They set off, and as they knew the waters immediately surrounding the dock by heart, they were able to navigate away from the island silently, but once they were a ways out, Kimi started making clicking noises with her tongue so they could echolocate their surroundings. They aimed straight for the closest point where the rock ceiling met the water. They couldn’t echolocate that far, of course, but Jerilyn remembered the way from her navigation lessons. Once they got too far from the archipelago, they had to rely on trying to keep going in a straight line, but soon after, they encountered the wall.

“What now?” asked Kimi.

“I suppose we look around for a tunnel,” said Jerilyn.

They turned right and followed where the rock ceiling met the water, keeping it on their left, their casual conversation sufficing to provide enough noise for them to track their surroundings. They never found a tunnel. Eventually they got tired, pointed their canoe back in the direction they came from, and set off for home. When they first encountered an island, they weren’t sure which one it was, and they went all the way around it in a circle so they could estimate its size and shape. It seemed unfamiliar, but Jerilyn thought back to her navigation lessons, and by the time they had completed their circle around the island, she came up with a guess as to which island it was. If she was right, they were significantly off course. She turned the canoe in the direction she thought home was, and when they passed the next island, she gained confidence that she was right, and indeed, their new path took them straight home, where they docked the canoe, dried themselves off, went straight to bed, and each fell asleep instantly.

*

Kimi and Jerilyn made several more expeditions to find tunnels to new worlds, taking off in different directions each time. On their fourth trip, they found an indentation well into the rock, which tapered out into a vein of air sticking just above the surface of the water. They got as far in as they could, until the rock ceiling got too low for them to stay under while they were sitting in the canoe. They stashed their paddles in the canoe, and carefully got out and swam farther in while towing the canoe. They soon reached a point where the canoe couldn’t go any farther even without them inside. They found a part of the rock ceiling that jutted down below the rest, and they pulled the end of their canoe downwards, pushed it under the jutting rock, and released it, so that the jutting rock extended into the canoe and would keep it from floating away.

They swam in further. But soon even the indentation they found sunk below the surface of the water. They each took a big breath of air, and kept swimming farther out underwater. They hadn’t brought sonar rods or a light, and couldn’t snap underwater, so they had no way of echolocating underwater, and had to rely on touching the rock ceiling above them to tell where it was. They didn’t get very far before Jerilyn decided that that wasn’t a great idea. She turned back, and pushed Kimi to turn back as well. Even with Jerilyn’s caution, they were both somewhat short of breath by the time they could get their noses back into the air.

On their next trip, they brought a pair of sonar rods, and aimed for the same indentation they had found on their previous trip. When they arrived at where the rock ceiling met the water, they were in unfamiliar territory. On their previous trip, they had been keeping the line where the rock ceiling met the water to their left as they’d followed it until finding the indentation, and this time, they’d tried going a bit to the right of the course they’d taken on the previous trip in an attempt to go more directly to the indentation, so they figured that they’d overcorrected, and turned left. They soon found the indentation again.

Again, they went as far as they could while keeping their heads above water, Kimi carrying the sonar rods. Then they dove down into the water, much deeper than necessary just to stay below the rock, so that they would be able to echolocate as far as possible without the nearby part of the rock getting in the way, and Kimi rang the sonar rods.

The rock ceiling’s descent flattened out not long after the last of it passed below the surface of the water, and there was a small air pocket just a bit after the rock ceiling flattened out. About twice as far in as the air pocket, the rock ceiling started to pitch up sharply.

They swam up back towards the surface for air, Kimi ringing the sonar rods between armstrokes so they could keep track of where the air was instead of bumping into the rock ceiling.

“Let’s check out that air pocket,” Kimi suggested, after they surfaced.

“Not a good idea,” said Jerilyn.

“We can totally make it there,” said Kimi.

“Air pockets sometimes have bad air in them. We could get there, of course, but I’m not so sure we could make it back after coughing out nasty air,” Jerilyn explained.

Kimi reluctantly agreed not to explore the air pocket, and they turned back.

*

On their next trip, they brought buckets. They figured if they weren’t sure they’d have enough air in their lungs for the trip to the air pocket and back, they could bring some more air outside their lungs.

When they’d gotten as far as they could while keeping their heads above water, they quickly discovered that it was just about impossible to swim underwater while carrying a bucket full of air. After a long while trying, they figured out how to get themselves positioned upside-down in the water with their feet against the rock ceiling while holding a bucket full of air pulling them up against the rock ceiling, so they could walk along it. Both of them still had trouble carrying a bucket and a pair of sonar rods underwater at the same time, so they’d put their sonar rods back in the canoe. But they were able to make enough sound to echolocate their immediate surroundings by hitting the sides of their buckets.

They both needed a breath by the time they got to the air pocket, as walking upside-down underwater was much slower than swimming. So they found flat portions of the rock ceiling to put their buckets down on, then turned around, exhaled, stuck their heads in their respective buckets, and took a breath. Then they exited the buckets, and Kimi approached the air pocket. She stuck her hand in, and made contact with the rock almost instantly; it was, evidently, a very shallow pocket. She stuck her nose in, being careful not to rise high enough to hit the rock ceiling, and, heeding Jerilyn’s warning, cautiously took a small breath of air. It was rancid. She coughed it up and recoiled out of the pocket, then scrambled for her bucket while fighting the urge to inhale. She finally got her head in the bucket, took deep breaths and kept coughing, while Jerilyn held her up so she could focus on regaining her breath instead of swimming.

By the time Kimi got her breathing under control, the air in the bucket was quite stale and she was short of breath again, so she left the bucket for her big sister to deal with while she swam back to fresh air. Jerilyn took another breath from her own bucket, dumped the remaining air out of the buckets, and swam back while carrying them, which took her a lot longer than it took Kimi because of the drag caused by the buckets.

“You were right. That was nasty,” Kimi commented, once Jerilyn surfaced.

They decided to make another trip underwater to try to explore past the ridge where the rock ceiling pitched back up again. They retrieved their sonar rods and tied them to Kimi’s wrist to make them easier to carry at the same time as the buckets, and set off in the same direction as before.

They set their buckets down near the air pocket, each took a breath, and then swam out to the ridge. Another ring of the sonar rods revealed that the rock ceiling pitched straight up into a vertical cliff, and that there was a wide expanse of air about thirty feet above them.

They retreated to their buckets, each took a breath from them, and then dumped the remaining air out and swam back with their buckets.

“I don’t understand how the water went so high up. The surface is definitely much higher on the other side than it is here,” said Jerilyn, after they surfaced again.

“Yeah, weird, isn’t it? Also, how are we supposed to get there? We canoed around the edge for miles in each direction and didn’t find any tunnels or places where it bends around or anything that could lead to that place,” said Kimi.

“There probably isn’t any route there going over the surface. If there was, it would be even harder to understand why the water level is different there than here,” said Jerilyn.

“A completely separate world! Do you think it’s the place Mom told us about?”

“I don’t know.”

*

They left for home, and on their next trip, they brought four buckets, with the intention of going all the way to the surface on the other side of the rock. Then they repeated the previous expedition’s trick of walking upside-down underwater with buckets of air, this time each carrying a bucket in each hand, which was even harder to get into position for, but eventually they figured it out. This made it not only difficult to ring the sonar rods, but also difficult to hit the buckets, and they resorted to periodically letting their buckets hit the rock ceiling to make enough noise to navigate.

They stopped briefly near the air pocket to turn rightside-up and take a breath from their buckets, and then turned back upside-down and kept going, buckets still in hand, all the way until the point where the ridge pitched back up again. They set down the buckets in stable locations, turned rightside-up, exhaled, took deep breaths from their full buckets, and swam up towards the surface, leaving four half-filled buckets on the underside of the ridge behind them, Kimi periodically ringing the sonar rods on their way up so they wouldn’t collide with the rock.

They surfaced and each began to take a deep breath, then stopped in shock, and cautiously started to breath again. Something was off about the air. It smelled… not stale, exactly, but strange, not like any air they’d ever smelled before. It smelled overly fresh, in a way, as if all the air they’d beathed until that point had been a bit stale, and they hadn’t noticed.

Jerilyn raised a hand out of the water, shook some water off of it, and snapped. For the briefest of instants, they both thought that perhaps there wasn’t a rock ceiling above them at all. But then they heard the echo, and realized that there was a rock ceiling above them at perhaps three times the height that they were accustomed to at home. And they couldn’t see any bright lights in the sky, or anything at all for that matter, so they couldn’t be in the place Mom had described in the myth. Aside from the rock on one side of them and bending into a ceiling far above them, there was nothing around them, just water for as far as they could hear.

“We gotta get the canoe in here so we can explore this place,” said Kimi.

“How in the world are we going to do that?” asked Jerilyn, realizing as she spoke that perhaps it should have been “how out of the world” rather than how in it.

“I don’t know,” said Kimi.

They swam around a bit, but didn’t find anything interesting, and decided to go home. They dove down under the ridge, retrieved their buckets and inhaled from them, surfaced on the other side, got in their canoe, and headed home.

*

Later, they did some experimenting at home, and discovered that their canoe was almost exactly the same density as water. Armed with this fortuitus fact, several buckets, and a lot of rope, they set off again for the other world.

A test run revealed that their rope wasn’t quite long enough to stretch from where they could park their canoe to the air on the other side of the rock. Finding this out resulted in Jerilyn dropping the rope on her way up after crossing the ridge so she could surface and breath, and then returning to their canoe, and they reeled the rope back in.

They set up three buckets of fresh air on the underside of the ridge, and one by the air pocket. Then Jerilyn took the sonar rods and swam out to the ridge and treaded water with her head in a bucket while Kimi filled the canoe with water, and pushed it underwater and forward, Jerilyn ringing the sonar rods in the water to help Kimi tell what she was doing as she swam under, and periodically ducking down into the water to keep herself updated on Kimi’s progress. Kimi wasn’t getting very good resolution from the sonar rods, but it helped that she remembered the path. Kimi, pushing the canoe ahead of her, reached the bucket by the air pocket and took a breath in it. Jerilyn took one last big breath from a fresh bucket and took off for the surface as Kimi continued forward pushing the canoe. When Jerilyn surfaced, she was able to help by reeling in the canoe, holding onto the rock cliff for leverage. Kimi went ahead of the canoe so she wouldn’t run out of air, and together they finished reeling in the canoe to the surface. With some difficulty, they emptied the water out of the canoe, righted it, and got back in.

Righting the canoe had been a lot of work, and they took a quick break to catch their breath. Then they set off in their canoe, keeping their old world to their left.

They heard sounds of civilization coming to them before they echolocated the island from their own snapping. They turned towards it and approached. They were noticed, and it seemed that they had caused a fair amount of consternation.

They got close, and a man was standing on the end of a peninsula near them holding a long, straight stick, facing them and snapping repeatedly. There were also boulders sticking above the water a ways to either side of them.

“Hello,” said Kimi, “Who are you? I’m Kimi.”

The man did not respond, but he did stop snapping and started clicking his tongue. The tongue-clicking wasn’t giving them good resolution on him, but they could tell he was moving in some way. Jerilyn snapped, revealing that the man had both hands on the stick, which was pointed at them, and he was leaning back as if about to throw it. Jerilyn dug her paddle into the water and swung them around, just as the man threw the stick. It narrowly missed Kimi.

“Hey, what was that for?” Kimi shouted.

“Kimi, paddle forward hard!” said Jerilyn, as she began to do so herself. They heard splashing sounds to either side of them, followed by the sounds of people swimming towards them. The man on the shore began clicking his tongue again, and seemed to be preparing for another throw. Jerilyn swung the canoe around again, and the stick just missed her. She resumed paddling forward, and the man on the shore dove into the water.

Someone grabbed the back of the canoe near Jerilyn and pulled himself up towards her. She moved her paddle between them just in time to block a thrust of a stick towards her. He grabbed her paddle with the hand that hand been on the canoe. Kimi lunged at him and hit him in the neck with her paddle with a surprising amount of force for someone her size. He dropped Jerilyn’s paddle as well as his own stick and fell back into the water. The recoil from Kimi’s lunge caused their canoe to collide with someone else as he pulled up towards the position Kimi had just left. Jerilyn hit him over the head with the edge of her paddle, and he too lost his grip on the boat. Jerilyn pushed him away from the boat with her paddle while he was too disoriented to grab it, and then Kimi and Jerilyn returned to their former positions and kept paddling hard. No one caught up to them, and they relaxed a bit once their pursuers had given up.

It took a while before they encountered the next sign of civilization. They approached much more cautiously this time, coming to rest at shouting distance. A small gaggle of people were gathered at the shore closest to them.

“Hello!” one of them shouted. They sounded funny.

“Hello!” Kimi shouted back.

“What is that thing?” asked the person on the shore. Their words were tricky to understand.

“What thing?” asked Kimi.

“The thing you’re sitting on floating in the water,” the stranger clarified.

“The canoe?” asked Kimi.

“The what?”

“This is called a ‘canoe’,” said Kimi, slapping the side of the canoe.

“Okay, so, what is it?”

“You use it to cross the water,” said Kimi. She wasn’t sure what else to say about the concept of canoes.

“What are you doing?” asked the stranger, giving up on getting more information about the canoes.

“We’re exploring,” said Kimi. “The last people we encountered weren’t very nice,” she added.

“Uh, were they the <unrecognizable word>?”

“The what?” asked Kimi.

“Did you encounter them over there?” asked the stranger, gesturing in the direction Kimi and Jerilyn had just come from, and snapping to give them good enough resolution to tell where he was pointing.

“Yes,” said Kimi.

“What the <unrecognizable> were you doing over there?”

“Uh, we didn’t know not to go there.”

“Uh, well now you know. Good thing you survived. Where are you from?” asked the stranger.

“Elsewhere,” said Kimi, knowing the name of their island wouldn’t mean anything to them.

“Uh-huh. Hey, do you guys need any supplies, like food or anything? We’d be happy to help out if you show us how the canoe works,” said the stranger.

“That would be gr-” Kimi started.

“Kimi, no,” Jerilyn interrupted, “They want to steal our canoe.”

They were both getting hungry, but they’d have trouble getting back home without their canoe. It wasn’t worth the risk. They kept going. They were not pursued.

*

It was a long time before they found land again. When they did find land, it wasn’t an island separated from the old world by water like the others had been, but instead, the rock wall separating them from the old world flattened out to become navigable by foot. They were ravenous, having serious regrets about having ventured so far without food, and on the verge of turning back. So they were quite gratified when they smelled vents. They pulled their canoe onto the shore, located the vents, and gorged themselves on ventmoss. Their hunger sated, they noticed they were getting quite tired, and they went to sleep.

When they awoke, they decided to explore the new land they’d found. They walked inland for quite some time without finding another shore; they’d never imagined a land so vast before. Eventually they became tired again, gave up on finding water on the other side, and turned back. They lost track of the exact route they had taken, and when they reached the shore again, it wasn’t familiar territory. A gust of wind carried a faint smell of vents towards them, and, guessing that it was from the same vents they had found earlier, they followed the shore in the direction the wind had come from. This guess turned out to be correct, and they found their canoe right where they’d left it. They ate some more ventmoss, drank from the water, and rested for a while.

Then they decided to venture uphill, in the direction of the old world; perhaps they would be able to walk on top of the rock ceiling of the old world. The ground gradually steepened, and they kept going long past the point where they had to crawl on all fours, and each step brought them more up than forward. At times, they had to rely on their voices for echolocating footholds when their hands were occupied clinging to the rock and they couldn’t snap. When they turned back, it was due to some combination of the steepness spooking them, and them getting quite tired. They downclimbed facing backwards until the ground had flattened out enough that they could walk upright without falling over, and then they walked their way back to their canoe and the vents, had another meal, and went to sleep.

When they woke up again, they decided to return home. They followed the route they had taken last time, but steered clear of any signs of civilization. When they neared the place where they’d met the people who’d attacked them, they stayed very close to the rock wall separating them from the old world, paddled slowly, and instead of snapping, frequently gently tapped the rock next to them for guidance, in hopes of minimizing noise and not advertising their presence.

When they reached approximately the place where they had first surfaced into the new world, they had some trouble figuring out exactly the right place. Kimi periodically dove into the water with the sonar rods, and in most places, it was easy to tell that they couldn’t be in the right place because the rock extended down too far vertically into the water. But eventually they found a point below them where the rock didn’t extend as far down, and theorized that that might be their route home.

Jerilyn dove below the edge of the rock, rang the sonar rods, and sure enough, there were their buckets of air on the underside of the ridge. She went back to the surface, and they tied their rope to their canoe, filled the canoe with water, and pushed it under while Jerilyn held the rope. They surfaced again after pushing the canoe down a ways underwater, took deep breaths, dove all the way under the ridge until they got their heads in air buckets, and pulled the canoe further down by reeling in the rope until the canoe was below the ridge. Then they dumped the air out of their buckets and carried buckets and rope back to the other side, with a quick stop at the bucket they’d placed midway to take breaths and pack up that bucket too. They were desperate for air by the time they finally surfaced on the other side.

After they finished panting for breath, they reeled in their canoe, and laboriously emptied the water out of it, righted it, and went home. Their parents were delighted to see them, cross at the prolonged absence, and skeptical of their tales of the new worlds they’d discovered.

*

Some time later, Kimi and Jerilyn decided to make another expedition to the new world and try to climb further up the steep cliffs they’d found. Realizing that it would take a long time, and they’d want water and food other than ventmoss, they packed some dried fish and plenty of buckets, and fashioned some seals for their buckets so that water could be stored in them without spilling when jostled around.

They set out along the same path as in their previous expeditions, although it took them some time to find again the indentation in the rock where they’d crossed over into the new world. Once they did, they repeated their usual procedure to get to the other side, after tying their extra buckets (two containing dried fish sealed inside) to the canoe, since carrying the extra buckets underwater themselves would have been too unwieldy.

Once they reached the air on the other side, reeled in their canoe, righted it, and emptied the water out, they took a break to catch their breath. They then continued roughly in the same direction as their previous journey, with a detour to steer clear of signs of civilization before they rejoined their original route, which they successfully stayed on from then on, making for a lengthy but uneventful trip to the place they had landed at on their previous trip.

Unlike on their previous trip, they were not hungry when they reached the land, as they had been snacking on dried fish the whole time. But they were quite tired, so they went to sleep before going any further.

*

When they awoke, they filled the remaining space in their buckets of dried fish with ventmoss, filled two other buckets with water, and took off uphill, each carrying a food bucket over one shoulder and a water bucket over the other. They kept going past where they had turned back the previous time, and not long after, had to backtrack a bit because the route seemed too precariously steep. But after a little exploring, they were able to find a more navigable route up.

After a long ascent and many quick breaks, they decided they needed some sleep. Unfortunately, they were on very steep ground. However, after a bit of exploring, they managed to find a crevice of flat ground big enough for both of them to lie down in, and they went to sleep.

They continued their ascent when they awoke. At one point, Jerilyn, who was in the lead, slipped and fell on a steep stretch. Fortunately, she did not hit Kimi on the way down, and was not far above some flatter terrain on which she managed to stop her fall. Miraculously, the seals on both of her buckets had held.

Kimi downclimbed to join Jerilyn, and asked if she was alright. Jerilyn reported that while she would probably develop some bruises from the fall, she was otherwise undamaged. They looked around for a safer way up, eventually found one, and continued on.

The hill eventually flattened out considerably, and they were able to consistently walk upright without their hands on the ground, though still uphill. The rock ceiling got progressively lower, to the point where it wasn’t far above their heads. In places, they even had to duck under it, though there were also places where the rock ceiling was much higher. At one such point where they rock ceiling was anomalously high, they saw a few small points of light above them at an angle, and in that particular direction, the rock ceiling was further away than they could echolocate, if it was there at all.

Eventually they grew tired, and went to sleep again. When they awoke, they noticed that the ground quite a ways behind them was glowing brightly. The air in a line connecting the rock ceiling to that patch of ground was also glowing faintly. They walked towards it, but the glowing patch narrowed and disappeared before they reached it. They turned back uphill and pressed on.

Later, they saw another glowing patch of ground, again with accompanying faintly glowing ray of air shooting up to the rock ceiling, well to their right. They headed towards it, but it too narrowed and disappeared before they reached it, and they turned back uphill.

The rock ceiling narrowed further, and they had to crawl to keep going. On multiple occasions, the rock ceiling come so close to the ground that they could not go further, or even merged with the ground, becoming a wall in front of them, and in such cases, they had to backtrack and find a different route up. At one point, the only route forward was so narrow between ground and ceiling that, in order to get through them, they had to take their buckets off their shoulders and push them ahead, and advance while lying flat. Kimi, being smaller, had an easier time of this, and at one point, Jerilyn got stuck, but Kimi was able to turn around in a slightly wider spot just ahead and give Jerilyn a hand, helping her get through.

The ceiling rose further above them again, eventually to the point where they could walk upright without ducking. They saw a patch of little points of light ahead of them, and they went in that direction, which required a steep climb. As they drew close, it became apparent that the points of light were coming from a hole in the rock wall, as echoes bounced off rock to every side of the patch of points of light, but not from the patch itself.

They passed through the hole. Though the ground continued to stretch out before them in all directions, there was no longer any wall to either side or in front of them, nor a ceiling above them, as far as they could tell from the echoes of their snaps. There was an almost-vertical wall behind them surrounding the hole, but rather than bending above them into a ceiling as it rose, it bent back in the other direction, as if to form high ground after flattening out further beyond their hearing range. There were many little points of light in every direction above them. There was one big source of bright light, almost a disk, but with one side blunted slightly inwards. There was faint light pervading through the air, so that they could see things in their immediate vicinity, including each other, clearly, despite the bright lights being far above them, and they could even see geological features much farther away than they could hear.

“We found it!” said Kimi, “The place from the legend! Look, there’s the bright light Mom told us about!” She pointed to the big almost-disk of bright light above them.

“Yeah,” said Jerilyn, “It doesn’t hurt to look at, though. And Mom didn’t mention all the other lights. Still, considering it was an ancient myth, it did turn out to be remarkably accurate. That sure is a lot of light.”

They explored the new wide open land, snapping as they went to echolocate the ground, even though they could see it just fine, since they were not accustomed to using light to find their footing. They quickly discovered that it was far larger even than it had first appeared. For instance, they set off in the direction of what appeared to be a patch of vegetation low to the ground, which they could see but not echolocate, but the vegetation seemed to grow larger but draw further away as they approached, not coming within echolocating range until well after they expected it to.

On their way, they heard a burbling sound, and investigating, they found a trail of fast-moving liquid flowing across the ground. Kimi tapped the surface of the liquid hesitantly, then cupped her hands, plunged them under the surface, and brought some of the liquid back up in her hands. It felt like water. She sipped it. It tasted like water. She reported her findings, and Jerilyn followed suit, and concurred. They had never come across such a wide stretch of such fast-flowing, shallow water before. It was a fortunate find, as they had been running low on water, and would have had a hard time on their way back if they hadn’t found more water. The water was fresher than the water in their buckets, so they refilled their buckets with it.

By the time they finally reached the patch of vegetation they’d been headed towards, it became apparent that the vegetation, which they had initially thought to be low to the ground, was actually enormous, with thick stalks extending far over their heads, high enough to extend well past the rock ceiling from home, and branching out, with vegetation covering the branches far above them.

A similar phenomenon occurred when they headed for some small hills in the distance. Again, the hills seems to draw further away as they approached. But unlike the vegetation, the hills did not also seem to grow as they approached. They pursued the hills longer than they had pursued the vegetation, but the hills still seemed no closer, and their size hadn’t changed. They speculated that perhaps the hills were simply illusions, or perhaps they were vastly further away than the vegetation had been. They were tired. They found a good spot to lie down, and went to sleep.

*

Something was wrong. Kimi opened her eyes and screamed, waking Jerilyn, who also screamed. There was light everywhere. So much light, as if an anglerfish’s lure was right in front of their eyeballs, except that it was coming from all directions.

They quickly identified the source of the light: an inconceivably bright light coming from the ground in the distance, which, true to the legend, it hurt to look at. They turned away from the light, held each others’ hands, and took deep breaths to calm themselves down while they got used to the incredible quantity of light all around them. Jerilyn speculated that, since this light was so bright it hurt to look at, and was located far away on the ground, and the light they’d seen before was merely bright and located far up above them, that perhaps the light that their Mom had spoken of in the myth, which was supposed to be painfully bright and high up above them, was a conflation of the two lights that they’d seen.

Once they’d calmed down a bit, they kept exploring. The bright light slowly climbed above the ground and into the air, which Jerilyn noted meant she was probably wrong in her earlier speculations. At the same time, the light kept gradually getting even brighter, to the point where it hurt to look in any direction at all, and, counterintuitively, it actually got harder to see as the intensity of light increased. The novelty of so much light flooding their surroundings wore off quickly, so they ended up spending a lot of time with their eyes closed, but their ability to see farther than they could echolocate was useful for navigating, so sometimes they would squint or partially cover their eyes instead.

Eventually, Kimi noticed that her skin hurt. She remarked on this, and Jerilyn noticed that her skin hurt as well. There was no obvious cause to their ailments. Jerilyn speculated that, since they’d been fine before the light got so bright, and the skin under their clothing didn’t hurt, that perhaps the light was hurting their skin. They decided to try getting out of the light.

They found some more of the tall vegetation, which was dense enough to block much of the light from coming under it. They took a break under it. It was generally more pleasant there, as it was cooler (it had been warm earlier), and the reduced level of light didn’t hurt their eyes as much.

Their skin kept getting worse, though. This gave them some doubt over whether it was the light that was hurting their skin, but it still seemed possible that it was because of the light, and their skin was continuing to hurt because of damage already done. And they didn’t have any better ideas than staying there; the hole in the rock that they had emerged from was far away, and they didn’t feel like making their way back to it in all the light, in case it was the light that was hurting their skin. They had no guarantee that the light would go away, but since it had been much dimmer earlier, that gave them some hope that it would dim again.

Kimi began to cry out of some combination of fear and the pain of her skin. Jerilyn tried to comfort her, though her skin also hurt, and she was also concerned. They waited there a long time without the light going away. They were exhausted, as they had been woken up by the light well before they would have woken up on their own, but they also couldn’t get to sleep because of the light, stress, and pain in their skin. Their skins were growing blisters, and they were losing hope that the light would go away any time soon, so they were considering making their way back to the hole, when they noticed that the source of the light was slowly making its way back towards the ground. They decided to wait for it to get there to see what would happen.

The light slowly dimmed as the bright light drew close to the ground, and Kimi and Jerilyn took off for the hole they’d emerged from. They’d gotten used to the way that their surroundings would seem to grow and draw away as they approached, and they were able to use landmarks they recognized by sight to navigate back to the hole. They refilled their water buckets again when they reached the fast-flowing vein of water. There was plenty of vegetation and wildlife around them, and they speculated that some of it might be edible, and they had gone through well over half their food, so it was tempting to attempt to restock on food for the return trip, but they didn’t know how to determine what was edible, as they didn’t recognize any of it. Jerilyn was concerned that, since light seemed to be toxic to their skin in high doses, perhaps consuming vegetation that had been exposed to that much light might also be toxic to them (she realized later that this could also be an issue with the water that they’d found, but it wasn’t like they could just not drink water, so it was a risk they’d have to take). They had to make do with the food that they’d already packed.

The bright light in the sky was long gone, and, following its departure, the ambient light continued to dim. By the time they reached the cliff, the ambient light had returned to the level it had been at when they’d emerged, and they could see the little points of light, and the one big light in the sky that had so impressed them when they’d first seen it, but no longer seemed so grand, in comparison to the much brighter light that had replaced it for a time.

They found the hole that they’d emerged from, walked in, and retreated inwards quite a ways from the hole before they collapsed on the ground, exhausted, and slept.

*

Their skins were still painful and sensitive when they awoke, and the hole they’d traveled through was glowing intensely.

They continued on their way back home, but when they got to approximately the point where they thought the narrow spot they’d crawled up through was, it took them a long time before they found it. Crawling back through it was quite painful, as it was impossible to climb through without scraping their sensitive skin. But after some painful struggle, they made it through.

Their progress down was much slower than their progress up had been, both because of their skin sensitivity slowing down their crawling, and because it was difficult to retrace their steps. Recognizing this, they rationed their food and water so that it would last long enough. During the phase of their journey where they had to crawl under a low ceiling, they seemed hopelessly lost for a long time before they finally made their way to an area where they had enough room to stand up, and in that more open area, they were eventually able to find what seemed to be their previous path. Satisfied that they were no longer lost, they went to sleep before continuing.

They had an easier time following their route up from then on. Despite their skin pain and weariness slowing them down, they actually exceeded their pace from the way up on the flatter portions of the trip, but they lost that extra time on the portions where they had to climb. Despite their efforts to conserve food, they ran out by the next time they stopped to sleep.

After descending further for quite a long time, they ran out of water, but they realized that they were getting close to the water, the vents, and their canoe. They desperately needed more sleep, but they needed food and water more, so they pressed on. They were quite relieved when they finally reached the bottom. They drank from the water, sated their hunger with ventmoss, and went to sleep. When they woke up, they got in their canoe and set off for home.

The Knot

George and I were afraid we might be late for our meeting with the wizard, and not wishing to keep them waiting for us, we rushed there. Just before we arrived, I checked my phone and saw that we were two minutes early. I apprehensively prepared myself to knock on the door, but it swung open before I did so, revealing an impressively cluttered office. There was no one inside. George and I looked at each other.

“Do you suppose we should go in?” George asked.

“I don’t think the door would have opened if we weren’t supposed to,” I said. After some hesitation, I stepped inside, and George followed. The door closed behind us, causing us both to reflexively turn back towards the door. I tried the door handle, and found that the door offered no resistance to being opened again. Reassured that we weren’t trapped, I closed the door again, to return it to the condition that I presumed the wizard preferred it in.

I noticed a loop of thin red rope hanging over the doorknob. There were no ends tied together in a knot. I picked it up to look for where the ends had been fused together, but could not find any joint; the rope appeared to have been constructed in a perfectly homogeneous circle.

I placed the loop of rope back around the doorknob, and turned my attention to the other objects filling the room. There was a perfectly spherical orb sitting on the wizard’s desk. The orb had a cloudy appearance, and the clouds drifted aimlessly on the surface of the orb, despite the orb otherwise appearing to be solid. There was a shelf on a wall, holding an old oscilloscope, a set of the five platonic solids, each made out of smooth black material, and a beaker that held a liquid which was dancing around violently, but never spilling out of the beaker despite appearing to come close very frequently. There was a fireplace in the corner with a fire, but the only material in the fireplace was a bird sitting in the middle of the fire, but the bird wasn’t burning, and it looked like it was sleeping. The bird raised its head to look at us quizzically, and then went back to sleep. I heard a faint popping sound, which I soon figured out had come from the liquid in the beaker. There was a bookshelf, completely packed with books, covering an entire wall, and there were also a few open books and many loose sheets of paper covering the wizard’s desk, as well as a few sheets of paper that had fallen to the floor. Very few of the papers I saw were in English, and most weren’t in any script I recognized. Some didn’t appear to have any writing at all on them, consisting only of cryptic diagrams.

I noticed a strand of rope sticking out from under some papers on the wizard’s desk. It appeared to be made out of very similar material to the loop of rope on the doorknob, except that it was green instead of red. I carefully moved the papers that were on top of it out of the way so I could see the rest of the rope. Like the rope hanging on the doorknob, it formed a closed loop. There were three points where the rope crossed over another part of the rope. The crossings alternated, in the sense that if you started at any crossing, and followed the strand on top around the loop, it would lead to the bottom strand of the next crossing it encounters, and then the top strand of the third crossing, and then the strand going under the point where you started, and so on. Only part of the rope was the green I had initially seen, another stretch of rope was red, matching the loop of rope on the doorknob, and part of it was blue. The rope was arranged so that the three points where the colors changed were hidden under the crossings.
I moved the portion of red rope that crossed over the boundary between green and blue, so that I’d be able to see the point where the color of the rope changed from green to blue. To my surprise, the piece of rope that I had just uncovered was solid blue all the way up to the new point that the red strand crossed over it. George asked me how it had done that, but I didn’t know, and I ignored the question. I wiggled the red strand some more, but the portion of the rope it was moving over kept changing between blue and green so that the color switch always occurred exactly under the red strand. I tried holding the red strand in place and pulling the green strand under it, but again blue rope turned green just as it emerged out from under the crossing. I lifted the red strand into the air, and moved my head around to look under it from both directions. The color of the lower strand shifted in unison with my head, so that I never caught a glimpse of the boundary between the colors. I wiggled the strands going over the other two crossings to see if they would exhibit the same phenomenon, and they did. I paused for a moment to stare at the rope in confusion, and then picked up a piece of green rope and moved it over the blue portion of the rope, forming two additional crossings. Blue rope turned red as the green strand passed over it, forming an additional stretch of red rope in the middle of the blue part of the rope, again with the color change happening precisely under the crossings. Next I tried moving the green strand over the point where the blue strand crossed over the boundary between red and green. As I had anticipated, the stretch of rope going over the crossing turned from blue to red as the green strand passed over it, and an additional short stretch of blue rope had formed out of the red rope coming out from under the crossing, with all color boundaries being hidden behind other stretches of rope. I returned the loop of rope to its original configuration, and then tried twisting part of the blue portion of the rope, so that it crossed over itself. This did not cause any color changes, and I undid the twist.

“Hey George, I want to try something. Can you go around to the other side of the desk for a minute?” I said.

“Are you sure the wizard will be okay with us messing with his stuff like this?” George asked.

“I’m sure it’ll be fine. Come on,” I said, pushing George in the intended direction. I actually had no idea whether or not the wizard would mind, but my curiosity had won out over my fear of offending the wizard. George walked around to the other side of the desk as I had requested.

“Okay, now look closely at this crossing,” I instructed, pointing to where the green stretch of rope passed over the boundary between the red and blue strands, which we were looking at from opposite sides. I crouched so that I was looking at the knot from a shallower angle, and George followed my example. I lifted the green strand going over the crossing up in the air. I was looking at the crossing from the side that the red strand was coming out from, and the blue stretch of rope coming out the other side appeared to turn red as the green rope passed in front of it in my field of vision.

“What’s it look like?” I asked.

“The rope under the green strand is now blue up until the point where it crosses behind the strand,” he said. I put my finger on the red rope directly under the green part I had lifted.

“So this looks blue?” I asked.

“Yeah,” he said.

“So you can see my finger touching a blue stretch of rope?” I asked.

“Yeah, that’s what I said,” George confirmed. I stood up and bent over to look at the rope from above, and pressed the green strand I was holding into my face running vertically between my eyes, so that I could see the piece of rope crossing under it from opposite sides of the green strand with each eye. It was a purple blur that could have been the result of red light reflecting off the rope into my right eye and blue light reflecting off the rope into my left eye. I unfocused my eyes so that the stretch of rope I was looking at would appear in different places in my field of vision in each eye, and indeed, it appeared as separate red and blue strands.

Suddenly remembering the loop of rope on the doorknob, I dropped the rope I was holding and went to go get it. George walked back around the desk to the side facing the door. I returned with the red loop of rope and held it over the rope on the table. The green and blue portions of the rope that I could see through the red loop had switched colors, while the red portion of the rope on the table was not changed in appearance by viewing it through the red loop. I lifted part of the rope on the table, and slid the loop of red rope under it. The loop was no longer red all the way around, with color changes whenever it passed under a strand of rope of a different color. I grabbed the formerly red loop of rope by a blue stretch in the center of the loop of rope on the table, and pulled it out. I was holding a solid blue loop of rope. I put the blue loop of rope aside, took out my phone from my pocket, and opened the camera. I lifted the green strand and put my phone under it to take a picture of the spot where the rope crossing under it switched from red to blue. The camera image on the screen showed the strand changing from red to blue right under the spot where the green strand crossed over the phone, so that the boundary between red and blue wasn’t visible on the screen. I took a picture, and then moved the rope out of the way so that I could see the spot where the color changed. But the picture I saw on the phone screen was of a completely red strand of rope. I moved the phone back under the green strand, and saw that the still image of a strand of rope in my camera was changing from red to blue as I moved the green strand over it. I pulled the phone back out the other side of the green strand, and it bore an image of a completely blue strand of rope. I closed the picture so I could take another one. The image of the knot in the phone screen looked the same as the actual knot, except that the colors red and blue were switched. I put down the phone, and pulled a pen and small notebook out of my pocket. I tore off a page of the notebook, and wrote on it the current color of the loop of rope I had taken from the doorknob (blue). I folded up the piece of paper, slipped it under the multicolored loop of rope with the crossings, and pulled it out through the center. I unfolded it, and found the word “green” written on it, in my handwriting, instead of the “blue” that I had written. I picked up my phone and called a friend.

She picked up, and before she said anything, I said, “Hi Kelly. Pick a color. Red, green, or blue?”

“Blue. Why do you ask?” she said.

“I’ll explain later. Thanks. Bye,” I said, and hung up. I wrote “blue” under the word “green” on the piece of paper, folded it back up, and slipped it under the knot and pulled it out through the center, as I had done before. I unfolded it, and saw that the word “green” that had been near the top of the paper had turned into “red”, while the word “blue” that I had written when Kelly picked it had remained unchanged. I also noticed that the pen I was using had blue ink, and the color of the ink on the page had never changed. There were a couple more things I wanted to try. I thought through what I was going to do, and then called Kelly back.

“Can you pick a color again? Same options,” I asked.

“Red,” said Kelly.

“Thanks,” I said, and hung up. I lifted part of the knot into the air and stuck my right hand under it, so that my hand was sticking out through the center part of the knot. The plan was to hand the phone from my left hand to my right hand, and then pull it with my right hand back from under the knot, except that if Kelly had named the current color of the loop of rope that had been on the doorknob, I would only go through the motions of this without actually holding the phone. The loop of rope from the doorknob was blue, and Kelly had said red, so I kept the phone in my left hand as I moved my left hand towards my right, and I attempted to grasp the phone with my right hand. But while I saw my right hand grab the phone, I felt my fingers pass through thin air where I saw the phone. I withdrew my right hand out from under the knot, and while the phone was definitely pulled out of my left hand, and I saw my right hand holding the phone as it receded, I felt my right hand in a fist closed around nothing. As my hand passed out from under the knot, the fist became visible and the phone seemed to disappear. George gasped, as this was the first sign visible to him that anything was amiss.

“Where’s your phone go?” he asked.

“I don’t know. In retrospect, I probably shouldn’t have used my phone for that. At least we’ve still got your phone if we want to try taking more pictures,” I said. I felt rather foolish, as I had actually identified this outcome in advance as consistent with previous observations, but somehow hadn’t seriously considered the possibility that it would actually happen.

“You just managed to lose your phone in the magic rope. I’m not letting you touch mine,” said George. He had a point. I thought about how I might get the phone back, but couldn’t think of anything, and besides, there was another experiment I’d been going to try. I reached for the red strand of rope (chosen because it was the color that Kelly had picked), but before I touched it, it started receding under the green strand, as if the blue strand on the other side was being pulled, but the blue strand itself was motionless, and rather than turning blue as it came out from under the green strand, the red rope would simply vanish as it passed under the green strand, leaving a significantly shortened stretch of red rope by the time this stopped. The point where the red strand disappeared under the green was no longer aligned with the point that the blue strand came out from under the green on the other side. I grabbed the red rope near where it crossed under the blue strand and pulled. More red rope came out of nowhere so that the red strand still continued all the way up to where it disappeared under the blue strand, even as I pulled it away, just as if the green strand on the other side were passing under the blue strand and turning red, but the green strand itself did not move. The point where the red strand passed under the blue strand and vanished also became misaligned with the point where the green strand emerged out the other side. When I stopped pulling on the red strand, there was about the same amount of red rope visible as there had been before some of it had vanished under the green strand.

“Hello, folks. Sorry I’m late,” came a voice from behind us in a heavy accent that I didn’t recognize. George and I turned around and saw someone of unidentifiable gender in robes and a pointy hat, carrying a wooden staff with a hexagonal piece of metal attached to the side and a shiny truncated octahedron fastened to the top, and wearing a ring on each of their ten fingers, each in a different style. The door was closed behind the wizard. I hadn’t heard it open or close. The wizard’s eye caught the knot of rope on their desk.

“Oy, the bloody thing’s out of sync again,” they said, and walked over to the desk, put the staff down leaning against the desk, pulled a wand out of their robes, and jabbed their wand at the knot. They put their wand back in their robes, picked up the knot of rope, and threw it up in the air. When it landed back on the desk, the strands were perfectly aligned with each other again.

“There we go,” said the wizard. They picked up their staff and gestured with it towards a wall, out of which lept two folding chairs, which positioned themselves in front of the wizard’s desk and unfolded into chairs that did not look the least bit like folding chairs.

“Have a seat,” said the wizard, indicating the chairs. I put my phone back in my pocket, and sat down.