This paper proposes appropriate sound and complete proof systems for algebraic structures over metric spaces by combining the development of Quantitative Equational Theories (QET) with the Enriched Lawvere Theories. We extend QETs to Metric Equational Theories (METs) where operations no longer have finite sets as arities (as in QETs and the general theory of universal algebras), but arities are now drawn from countable metric spaces. This extension is inspired by the theory of Enriched Lawvere Theories, which suggests that the arities of operations should be the lambda-presentable objects of the underlying lambda-accessible category. In this setting, the validity of terms in METs can no longer be guaranteed independently of the validity of equations, as is the case with QET. We solve this problem, and adapt the sound and complete proof system for QETs to these more general METs, taking advantage of the specific structure of metric spaces.

Markov categories are a recent categorical approach to the mathematical foundations of probability and statistics. Here, this approach is advanced by stating and proving equivalent conditions for second-order stochastic dominance, a widely used way of comparing probability distributions by their spread. Furthermore, we lay the foundation for the theory of comparing statistical experiments within Markov categories by stating and proving the classical Blackwell-Sherman-Stein Theorem. Our version not only offers new insight into the proof, but its abstract nature also makes the result more general, automatically specializing to the standard Blackwell-Sherman-Stein Theorem in measure-theoretic probability as well as a Bayesian version that involves prior-dependent garbling. Along the way, we define and characterize representable Markov categories, within which one can talk about Markov kernels to or from spaces of distributions. We do so by exploring the relation between Markov categories and Kleisli categories of probability monads.

We propose a categorical framework for processes which interact bidirectionally with both an environment and a “controller”. Examples include open learners, in which the controller is an optimiser such as gradient descent, and an approach to compositional game theory closely related to open games, in which the controller is a composite of game-theoretic agents. We believe that “cybernetic” is an appropriate name for the processes that can be described in this framework.

Lenses, optics and dependent lenses (or equivalently morphisms of containers, or equivalently natural transformations of polynomial functors) are all widely used in applied category theory as models of bidirectional processes. From the definition of lenses over a finite product category, optics weaken the required structure to actions of monoidal categories, and dependent lenses make use of the additional property of finite completeness (or, in case of polynomials, even local cartesian closure). This has caused a split in the applied category theory literature between those using optics and those using dependent lenses. The goal of this paper is to unify optics with dependent lenses, by finding a definition of fibre optics admitting both as special cases.

Interventional causal models describe several joint distributions over some variables used to describe a system, one for each intervention setting. They provide a formal recipe for how to move between the different joint distributions and make predictions about the variables upon intervening on the system. Yet, it is difficult to formalise how we may change the underlying variables used to describe the system, say moving from fine-grained to coarse-grained variables. Here, we argue that compositionality is a desideratum for such model transformations and the associated errors: When abstracting a reference model M iteratively, first obtaining M' and then further simplifying that to obtain M'', we expect the composite transformation from M to M'' to exist and its error to be bounded by the errors incurred by each individual transformation step. Category theory, the study of mathematical objects via compositional transformations between them, offers a natural language to develop our framework for model transformations and abstractions. We introduce a category of finite interventional causal models and, leveraging theory of enriched categories, prove the desired compositionality properties for our framework.

We state and prove the zero-one laws of Kolmogorov and Hewitt-Savage within the setting of Markov categories, a category-theoretic approach to the foundations of probability and statistics. This gives general versions of these results which can be instantiated not only in measure-theoretic probability, where they specialize to the standard ones in the setting of standard Borel spaces, but also in other contexts. For example, applying the Kolmogorov law to the Kleisli category of the hyperspace monad on topological spaces gives criteria for when maps out of an infinite product of topological spaces into a Hausdorff space are constant.

Let \Omega _1 \leftarrow \Omega _2 \leftarrow \dots be a sequence of probability spaces, for example \Omega _i = (\Omega , \mathcal {F}_i, P) for some filtration of sigma-algebras. A martingale on this object is a sequence of random variables defined on \Omega _i so that E[X_{i+1} \mid \Omega _i] = X_i. Let \Omega _\infty denote the limit of this diagram in probability spaces. Then every martingale of L^2-random variables defines a sequence of random variables on \Omega _\infty . This sequence converges in L^2, say to X_\infty , and X_n = E[X_\infty \mid \Omega _n]

Manifold (to their credit!) publishes their calibration plots. These are generally pretty good. Some people seem take this as strong evidence that Manifold makes good predictions.

We can try to think about perfect calibration in market terms. If some method could improve on Manifold's predictions, then that method could be turned into a profitable trading strategy. So we can think about statements that Manifold makes "good" predictions in terms of the classes of strategy they rule out. In the extreme case, if the market was perfectly efficient, no strategy could make a profit - meaning there's no way to improve the predictions.

Perfect calibration means that, (for example) of the markets currently trading at 10% YES, 10% will resolve YES. This means that no trading strategy of the type "whenever a market is valued at 10% YES, buy some of it" can make a profit in expectation. This is obviously an *incredibly weak* notion of market efficiency. We expect this to hold, but this doesn't mean the predictions are well-priced at all.

Imagine two people forecasting the same set of 100 potential natural disasters. The first forecaster (call him A) assigns probability 1% to them all. The second forecaster (B) assigns probability 80% to two of them, and 2% to the rest. In the end, exactly one of the disasters happen, and it's one of the two that the second forecaster assigned 80% probability to.

A has perfect calibration. B, by contrast, has pretty bad calibration (his 80% "should" have been 50%, and his 2% should have been 0%).

But: - B has a better Brier score (A has (0.0099 + 0.99^2)/100, B has approximately (0.8^2 + 0.2^2 + 0.0004 \cdot 98) /100, and remember lower is better). - More to the point, B's forecast is *clearly more useful* - having some reasonable ideas *which* of the 100 potential disasters will happen is clearly more important than getting the overall rate right - We could make this point even more stark by letting B assign 90% probability to the disaster that ended up happening, and 1% probability to the ones that don't.

People often say things like "X has good calibration, meaning when they say there's a 10% chance of something happening, it happens 10% of the time. So when they say there's a 10% chance of nuclear war (or whatever), we should take it seriously".

The first sentence is of course a correct explanation of calibration. But think of our disaster forecasters from before. A had perfect calibration, meaning when A says that disasters overall happen only one time in a hundred, he's right. But if he says that some *specific* disaster has a very low, 1%, probability of happening, we shouldn't necessarily take that forecast very seriously. Perhaps it's actually easy to know which 1% of disasters happen. A's ability to get the base rate right does say something about his forecasting, but the fact that he can't do better than the base rate doesn't prove that we can't, and should therefore adopt his forecast.

[^2]: Another is log scoring, where if you say X will happen with probability p and it happens, you score is -\log p instead of (1-p)^2. For our purposes the difference doesn't really matter (both have this property of being a "proper scoring rule", so if you have to assign the same probability to some set of questions, you optimize your score by assigning the fraction of them that comes out true).

The category of bimorphic lenses and its many generalizations has been widely studied and utilized in applied category theory. We will not give a review of the literature here, but see e.g. Riley's paper on "optics" (one of the many generalizations) Reference [riley-optics], which includes a decent overview.

Dispensing with a point of notation, we will denote objects of the category of lenses \binom {A}{X}, and morphisms \varphi : \binom {A}{X} \to \binom {B}{Y} as (\varphi ^+: X \to Y,\varphi ^- : X \times B \to A). Note that we write the *forwards* pass on the bottom of the tuple, breaking with the convention used by Riley and many others.

The category \mathsf {Lens}= \mathsf {Lens}(\mathsf {Set}) of lenses embeds into the category of polynomial functors \mathsf {Poly} and natural transformations as the full subcategory of functors of the form X \times (-)^A. Since \mathsf {Poly} admits all coproducts, and these are computed pointwise, one immediate consequence is that we have the coproducts \binom {A}{X} + \binom {A}{Y} = \binom {A}{X + Y} in \mathsf {Lens}. These seem to have been studied first by Hedges (Reference [hedges-morphisms-open-games]). (For a reference on \mathsf {Poly}, including this inclusion, see eg Spivak Reference [spivak-poly-abundant]. \mathsf {Poly} is another branch on the tree of generalizations of \mathsf {Lens}, studied extensively by Spivak and others).

Given the above, one might expect these to be all the coproducts of \mathsf {Lens} (up to isomorphism) - they are certainly the only ones preserved by this inclusion¹1 There is a quibble here, since \binom {A}{0} \cong \binom {B}{0} for any sets A,B, these being the initial objects of \mathsf {Lens}. This is of course the natural "nullary" version of the binary formula, but it also means that \binom {A}{0}+\binom {B}{X} = \binom {B}{X}, and that this coproduct is preserved by the inclusion into \mathsf {Poly}, even if A \not \cong B. . But this turns out not to be the case.

Let's begin with a worked example of the "exotic" coproducts. Note that I simply denote by n \in \mathbb {N} the set \{1, \dots n\} with n elements. In particular 0 is the empty set.

Having seen the above, we may begin to lose hope of understanding the coproducts in \mathsf {Lens} at all. Fortunately the situation is not completely chaotic - in some sense, the preceding example is the *only* problem - all the coproducts in \mathsf {Lens} are either of the form \binom {A}{\coprod _i X_i} (up to isomorphism), or they are of the same form as the example.

The following result, characterizing the "good" coproducts, was already essentially proven by Hedges in Reference [hedges-morphisms-open-games]²2 Hedges states it only for \mathcal {C} = \mathsf {Set}, but his proof goes through unaltered for our case. He also only constructs a particular family of coproduct diagrams, but the ones considered here are just his composed with isomorphisms in \mathsf {Lens}, so there is really nothing serious going on , but I'll state it here and sketch a proof for completeness.

We can now return to the main theorem. The following argument is somewhat clunky and ad hoc. The main point is that we can characterize the cases where \mathsf {Set}(U,V) is empty, namely only when V is empty and U is not. In a general category, this can be much more complicated, and there does not seem to be any completely general method. This means we don't know which possible C we need to deal with when understanding when the backwards pass is a bijection, which makes it seemingly impossible to give a general classification of the coproducts by this method.

(The second point is that it's easy to understand when the maps between hom-spaces are bijections in \mathsf {Set} - we have a somewhat clunky argument but it's pretty straightforward and it can probably be done in a more conceptual way, if one took the time to find it).

We can replace Y with the coproduct \coprod _i X_i, and each forwards pass \varphi _i^+ with the inclusion, without loss of generality (if we are not in this situation up to isomorphism, we don't have a coproduct by the above)

It's clear that the first condition of the theorem implies that \mathsf {Set}(X_i \times C, B) \to \mathsf {Set}(X_i \times C, A_i) is a bijection always, and so we have a coproduct. As for the second condition, suppose X_i is nonempty and A_i is empty. Then for nonempty C, the set \mathsf {Set}(X_i \times C, A_i) is clearly empty, fulfilling the second condition of the lemma, whereas for empty C, the map \mathsf {Set}(X_i \times C, B) \to \mathsf {Set}(X_i \times C, A_i) is a map between two singletons (since X_i \times C is empty), and hence a bijection.

This proves that if one of the two conditions hold, we have a coproduct. To see the other direction, suppose neither condition holds. If the second condition doesn't hold, then there is always a map X_i \to A_i, and hence the set \mathsf {Set}(X_i \times C, A_i) is never empty, so according to the lemma, it suffices to show that for some i and some C, the map (\varphi _i^-)^*: \mathsf {Set}(X_i \times C, B) \to \mathsf {Set}(X_i \times C, A_i) is not a bijection.

Since the first condition doesn't hold, let j, x' \in X_j be such that the map \varphi ^-_j(x',-): B \to A_j is not a bijection. Suppose first it's not surjective and let a' be something not in the image.

Take C = *. Then the constant function - \mapsto a' : X_j \times * \to A_j is clearly not in the image of (\varphi _j^-)^*, since that would require, for some \psi , \varphi _j^-(x,\psi (x,*)) = a' for all x, and in particular for x = x', but that's a contradiction.

On the other hand suppose it's not injective, and that \varphi _j^-(x',b_0) = \varphi _j^-(x',b_1) for some b_0,b_1 \in B. Now take C = B and consider a function \psi : X_j \times B \to B, defined by \psi (x',b_0) = b_1, and \psi (x,b) = b for all other pairs (x,b). Now \varphi _j^-(x',\psi (x',b_0)) = \varphi _j^-(x',b_1) = \varphi _j^-(x',b_0). And for all other x or b, clearly \varphi _j^-(x,\psi (x,b)) = \varphi _j^-(x,b). Hence (\varphi _j^-)^*\psi = (\varphi _j^-)*(\pi _B: X_j \times B \to B) (\pi _B being the projection). But \psi \neq \pi _B, so (\varphi _j^-)^* is not injective in this case. This concludes the proof.

The idea of a _coarse space_ is to formalize a sense in which the inclusion of metric spaces \mathbb {Z} \hookrightarrow \mathbb {R} is an equivalence. These two spaces have the same "large-scale structure", in the sense that any function into \mathbb {R} can be approximated up to uniformly bounded error by one into \mathbb {Z}. Say two functions f,f': X \to Y into a metric space are _close_ if there exists a constant C with d_Y(f(x),f'(x)) \leq C for all x. Say a function between metric spaces is _controlled_ if postcomposition with it preserves closeness (it turns out there is a simpler equivalent statement of that, but it doesn't really matter). Then we can consider equivalence classes of controlled functions between metric spaces, under the equivalence relation of closeness. This is "coarse geometry".

It turns out there is a way to abstract away from the metric and describe a "coarse structure" on a set, which remembers enough information to tell which pairs of functions are close and which are controlled, but nothing else - and that there then exist coarse structures that aren't induced by metrics. I personally think of this as kind of complementary to the way topologies remember what's necessary to talk about continuity - if continuous functions between metric spaces are about preserving the "small-scale structure", the notion of convergence, then coarse geometry is the opposite of that.

The category of coarse spaces admits finite products, so we can talk about "coarse group theory", which is explored in An Invitation to Coarse Groups by Leitner and Vigolo, which I've been reading a bit recently. It's full of interesting stuff - maybe my favorite bit is the story about geometric group theory. If you have a group G with a generating set S, you can define a metric by setting d(a,b) to be the length of the shortest way of writing a^{-1}b as a word in generators - this amounts to taking the graph distance on the Cayley graph. Studying this metric structure on the group G can tell you a lot of interesting stuff about the group - but the metric is highly dependent on the choice of generating set S! So it's somehow very surprising that all these different metric come back and give us the same group-theoretic information (since the group G is fixed). Leitner and Vigolo shows that for all finite S, the metrics give the same coarse structure on G, and much of geometric group theory "sees" only coarse structure!

I find all this really cool and I highly recommend the paper. I want to talk about a subtlety that comes up in the category of coarse groups.

Consider two possible coarse structures on the set \mathbb {Z} - the trivial structure and the one induced by the normal metric, which we can write \mathbb {Z}_{|\cdot |}. The identity map \mathbb {Z}_{\mathrm {triv}} \to \mathbb {Z}_{|\cdot |} is obviously a coarse group homomorphism. It's also an epimorphism. In normal group theory we have the very convenient isomorphism theorem saying that the image of a group homomorphism is, up to isomorphism, the quotient of the domain by the kernel. But there is no coarse subgroup of \mathbb {Z}_{\mathrm {triv}} that can play this role.

Let's think about how to remedy this. The universal property of the kernel dictates that maps into it must be precisely those maps into \mathbb {Z}_{\mathrm {triv}} that are close to zero in \mathbb {Z}_{|\cdot |}. The first condition boils down to taking each coarsely connected component to the same point, and the second condition means that the image must be a bounded subset (in the metric). Of course, there is no coarse set like this - it would have to consist of "the bounded subsets of \mathbb {Z}", but of course every point is contained in one of these subsets.

The answer is to relax the notion of coarse space, by removing the condition that \Delta _X is among the controlled sets. This leads to the notion of _fragmentary coarse space_:

- A fragmentary coarse space is a set X equipped with a family \mathcal {E}_X of subsets of X \times X, stable under finite unions, subsets, and so that if E_1,E_2 \in \mathcal {E}_X, then E_1 \circ E_2 \in \mathcal {E}_X. - A subset A \subset X is called a _fragment_ if \Delta _A is in \mathcal {E}_X. - Two functions f,f': X \to Y between fragmentary coarse spaces are _fragmentary close_ if, for each fragment A of X, f(A) \times f'(A) \in \mathcal {E}_Y. - A function f: X \to Y is _fragmentary controlled_ if, for each A \in \mathcal {E}_X, (f\times f)(A) \in \mathcal {E}_Y. - The category of fragmentary coarse spaces and equivalence classes of fragmentary controlled functions up to fragmentary closeness is denoted \mathbf {FragCrs}

Leitner and Vigolo show that \mathbf {FragCrs} is complete and cocomplete, and in fact even Cartesian closed (these convenient properties are the reason they introduce the notion of frag-coarse space). I now claim that it is furthermore _regular_.

Observe that this property passes to the category of group objects in \mathbf {FragCrs}. Hence given any quotient homomorphism f: G \to H between (fragmentary) coarse groups, there exists a kernel \mathrm {ker}(f) so that H = G/\mathrm {ker}(f), although the kernel may have to be a fragmentary-coarse group even if G and H are coarse. Thus, passing to fragmentary-coarse groups provides us with a nice group theory.

Since \mathbf {FragCrs} is complete and cocomplete, it suffices to show that pullbacks of regular epimorphisms are again regular. We first claim that every epimorphism f: X \to Y is in fact regular. Note that Leitner-Vigolo show that f is an epimorphism if and only if, for each fragment Y' of Y, there exists a fragment X' of X and a controlled set F \in \mathcal {E}_Y, so that Y' \subset F(f(X')) (i.e for every y \in Y', there exists x \in X' so that (f(x),y) \in F). Given this, we see that Y is frag-coarse-equivalent to X equipped with the frag-coarse structure f^{-1}(\mathcal {E}_Y) - clearly f is a frag-coarse surjection from this space to Y, and also a frag-coarse embedding, hence an equivalence. So every epimorphism is, up to isomorphism, given by a map which is set-theoretically the identity. One also sees that the codomain necessarily has the same fragments as the domain. Now, inspecting the construction of coequalizers for frag-coarse spaces, it's not too hard to see that the frag-coarse structure on X that gives the coequalizer of the kernel pair of f must coincide with the one on the codomain on f. Hence every epimorphism is regular.

Now, if i: X \to \bar {X} is an epi (assumed to be set-theoretically the identity), and f: Y \to \bar {X} is any map, we must show that again Y \times _{\bar {X}} X \to Y is an epimorphism. The construction of limits makes it clear that the fragments of the pullback are each contained in a set of the form A \times B where A,B are fragments of Y and X respectively and f(A) \times B is controlled in \bar {X}. Since for each fragment A of Y, f(A) is a fragment of \bar {X}, it's clear that we can find a matching fragment B for each A. Then the projection from this fragment is surjective on the nose, and hence the projection is epimorphic.

Now let's consider the example of \mathbb {Z}_{\mathrm {triv}} \to \mathbb {Z}_{|\cdot |}. In fact since the forgetful functor from group objects preserves all limits, we can compute the kernel of this map just in \mathbf {FragCrs}. It is given by the frag-coarse structure on \mathbb {Z} where a set is U controlled if it's bounded (namely if the identity is close to zero on it) - not if the distance d(x,y) is bounded as (x,y) ranges over U, but if the whole thing is a bounded subset of \mathbb {Z} in the 1-norm. This means that the fragments are exactly the bounded subsets of \mathbb {Z} (and that there is no nontrivial frag-coarse structure beyond that - a set is controlled if and only if it's contained in the product A \times A for a fragment A).

It's not too hard in this case to verify that the quotient of \mathbb {Z}_{\mathrm {triv}} by this subgroup is in fact \mathbb {Z}_{|\cdot |}. Namely, a coarse map out of \mathbb {Z}_{\mathrm {triv}} restricts to zero on the subgroup if and only if it carries the bounded subsets of \mathbb {Z} to sets that are bounded-close to zero in the codomain, i.e sets so that A \times \{0\} is controlled. But for a coarse group homomorphism, this is enough to be controlled as a morphism on \mathbb {Z}_{|\cdot |}.

Let K(x) be the kolmogorov complexity of a binary string (finite). Say x is c-incompressible if K(x) \geq |x| - c. An infinite string is Martin-löf random if there exists c so that all its finite prefixes are c-incompressible.

Given a finite string w, C_w is the open set of strings with that prefix. A constructive open is an open given as the union of an enumerable sequence of such things. A constructive nullcover is a computable sequence U_i \supset U_{i+1} of constructive opens so that \mu (U_i) \leq 2^i (\mu being the obvious "lebesgue" measure on Cantor space). A sequence x is Martin-Löf random if, for any constructive nullcover, x \neq \cup ^\infty U_i.

A _Martingale_ is a function \{0,1\}^* \to [ 0,\infty ), interpreted as the profit of a betting strategy (betting on coinflips) on the given sequence of coinflip outcomes. It's _fair_ if m(x) = (m(x .0) + m(x.1))/2 - in other words, the amount you win on a zero must equal the amount you lose on a one. Ie "you're betting at fair odds".

A martingale _succeeds_ on a Martin-löf random sequence if its limsup on the prefixes is infinite - i.e if it wins unbounded amounts of money at fair odds without ever risking any more than its finite starting pot (since it cannot go negative).

A martingale is _constructive_ if it is "lower computable", and a sequence is Martin-Löf random if there is no constructive martingale that succeeds on it.

Ie if there is no computable gambling strategy to extract unbounded money from the assumption "this sequence produces fair coinflips".

In other words, as long as the world is computable, you can comfortably treat any Martin-löf sequence as random. Of course, if the world is computable, you cannot store one in any way, and any black box that outputs a Martin-Löf sequence is in some sense "either random or uncomputable".

So in some sense there's _no way_ of telling the difference between a deterministic, computable world that contains some black boxes that output Martin-Löf sequences, and a computable world that contains some black boxes that output "actually random" sequences. This provides some justification for the philosophical position that "randomness" is always about quantifying the limitations (of information, or in this case, of which functions they can compute) of the observer, advanced eg here.

Suppose x belongs to some constructive nullcover, (U_n) Then we can construct a constructive martingale which essentially makes the bet "x will be in U_n", continuously making a profit. Basically, assume we have already defined m(w) for all the strings up to length k, Consider a string w of that length. Either both of w.0 and w.1 belong to U_k, or neither, or exactly one of them. If neither do, then we know we're not looking at x, so it doesn't matter. If both do, then we make no bet at this point, but use U_k again to compure w.00, w.01 and so on. If only one of them do, then we bet all our money on that one. This martingale succeeds on x, and is constructive because the U_ns are.

On the other hand, suppose a constructive martingale m succeeds on x. Without loss of generality, assume m(\epsilon ) = 1, where \epsilon is the empty string. Let U_n be the set of strings where m(w) > 2^n for some prefix. Clearly no fair betting strategy can get positive expected value, so the measure of U_n is at most 2^{-n}. On the other hand U_n is computable because m is. This proves equivalence of the martingale and constructive nullcover definitions.

Now suppose x is compressible, i.e the value n - K(x_n) is unbounded. Then there exists a program which receives and infinite bitstring as input and produces output one bit at a time, and an input y, so that when run with input y it produces x as output, and so that the difference between the number of input bits consumed and the number of output bits produced grows without bound (the input is just a suitable sequence of very effective compressions of x. The program simulates these, then outputs the extra bits from the end). Note that given n, we can compute k so that, after consuming k bits of input, the program produces n+k bits of output. Then we can define U_n to be the set of infinite strings that have a length n+k prefix which is a possible output of the program on an input of length k. There are at most 2^k such outputs, each of which determines a set of measure 2^{-n-k}, so this has measure 2^{-n}. But clearly n is in there.

On the other hand, suppose x is in some nullcover U_n. Then we can try to compress the prefixes of x as follows:

- Compute the gödel number of the program enumerating the prefixes defining U_n, for some n - Find the kth output of this program, for some k, which is necessarily a prefix of x. We may assume wlog that this program produces its output in ascending order of length.

The length of this program is a constant c, to store the program computing (U_n) and for gluing code, plus \log n + \log k bits to store n and k. Let l_i be the length of the ith prefix defining U_n Then \sum _i 2^{-l_i} \leq 2^{-n}. This implies that the l_i is at least n + \log i. Hence this is a length c + \log n + \log k program that produces a prefix of x of length at least n + \log k - hence for n large enough, this is an arbitrarily good compression.

The very first thing I do is to send the paper to my [reMarkable]. I read the paper on the reMarkable, and keep a piece of paper next to me for scratches, and my laptop open for googling and for notes.

I go over the beginning of the paper, taking some loose notes. I jot the following down on a piece of paper: **Terms**

- Reeb graphs - The thesis of curry - Cellular sheaves? How do they work? - (Unwritten thought: I remember that I've read about "cellular sheaves" before. They're some sort of system for encoding a sheaf on a cellular complex of some soty, in a way that's "analogous" to sheaves on the geometric realization on the complex.) - Hodge Laplacian for vector spaces? - (Unwritten thought: the paper is about a laplacian for lattices - this seems to be a different version of the same concept? What's that like?) - Graph signal processing? - (Unwritten thought: the paper described this as signal processing where the signals live on graphs instead of in real numbers?)

I also make notes when something makes me think of an idea related to one of my projects. At this point I'm at page 7, and I've made two such notes thus far.

At this point I have a vague idea of where the paper is situated - what's going on. There's a lot of references in this introduction to ideas I don't really know about, or only half remember. But nothing has made me think I should go look it up before I proceed.

At page 7 or so is where I get impatient with the paper just dumping a bunch of definitions around lattices on me, and start skimming forward a bit. On page 8, I notice the important point that we're dealing with categories of lattices where the morphisms are _connections_. Here I remember that I already know about galois connections - a connection being the same thing but here they don't reverse the order.

On page 9 we get to "cellular sheaf theory". Here the authors luckily recall the definition of cellular sheaf I was missing before. I make a note in the margin at the top of page 10: "Ie F(\bullet ) \to F(\bullet - \bullet ) - **not** the other way". This is the important point of a cellular sheaf

- It assigns an object (vector space,set,etc) to each _cell_ in a cell complex - The restriction maps go the opposite way from what you expect, from points to segments (and in general to higher-dimensional cells), not the other way around - There is no sheaf condition.

I briefly try to connect this picture with something I half-remember about the connection between a space and the geometric realization of the nerve of a cover (while reading the paper, I didn't remember the term Cech nerve, but just had a picture in my head which upon reflection seems to be captured by that term). I fail to make any actual progress with this but mentally note that this idea smells right. I skim the description of global sections and so on, but note the definition of the cellular cochain complex.

In the section on Cellular Hodge theory, I make the following note in the margin: "every de Rham class has a unique harmonic rep", summarizing what they're saying about the kernel of the Laplacian for Riemannian manifolds (/what I half-remember about this stuff). "Harmonic" here means exactly "in the kernel of the Laplacian". I make a note of the "hodge laplacian".

At this point I am skimming forwards a lot. I stare at the Tarski Laplacian on page 12 for a bit. I write "how does this 'diffusion' work?" in the margin. Then I think a bit about how to view this stuff as "diffusion". I think something like the following:

- The expanding part is the completion associated to the connection

F(v) \to F(e) whenever e is an edge adjacent to v, then the "intersection" of all those completions for every edge. The the mixing part is kinda this same thing, but for every _neighbor_ vertex, i.e for every edge from a different vertex w, you "extend" from w to the edge, then restrict to v. "Mixing".

I read some of the stuff about how diffusion lets a cochain "flow" to a global section, and made a note of the similar property of the Tarski laplacian - that the fixpoints of 1 \wedge L are exactly the global sections. Here I also thought to myself that it was interesting that this is just a _zero-dimensional_ theory, no higher homology objects.

Now I skim forward a bit more to page 15 at the bottom, "Tarski Cohomology", where the authors get to the question I just raised (this sort of "author mindreading" is always pleasing). They note here essentially that the definition for dimension zero also works in higher dimensions.

Then they pass to the comparison with more "ordinary" chain complex based cohomology. Here I initially skim forward and try to get the gist of things. I see they introduce something called the "Grandis cohomology", which I note is cohomology of a chain complex in lattices (which is in fact a preadditive category, so this makes sense kinda). You can compare this with usual cohomology by considering the "Grassmannian functor" associating to a vector space its lattice of subspaces. Here I got a bit confused about the relationship between the various types of cohomology, so I had to go back and forth a bit to make sense

- The Tarski cohomology is the fixpoints of a certain endomorphism on the k-chains (defined in a natural way) - Given a chain complex, the Grandis cohomology is the cohomology in the usual sense - We can compare these in the case of a sheaf of vector spaces, by either - Constructing the usual chain complex of vector spaces, usign the Grasmannian functor and taking grandis cohomology - Or taking the associated Grassmannian sheaf and then taking its Tarski cohomology.

These are not in general the same. The reason you can't just build a chain complex out of a sheaf of lattices is that, while you can define a coboundary map, it doesn't form a chain complex, in the sense that \delta ^2 \neq 0. We can however do still do something with this fake chain complex, apparently involving mimicking the definition of the Hodge laplacian. This gives another type of cohomology, which is also not equivalent to Taski cohomology.

At this point there are still a lot of details I don't understand. I have the big picture, though. The next step would probably be to pick up some of the references to understand why this is useful - but I decide not to do that.

I also consider making flashcards or notes about this paper. This blog post is already a file in my notes, so I have that. I decide that these concepts _probably_ aren't worth comitting to memory, except "cellular sheaves", which I've come across a few times. I also decide to make notes on some of the concepts.

If you want to look at the sparse margin notes I took while reading this paper, it's here.

[^fn:1]: In this case, it was recommended to me by <https://arxivist.com>

This paper came out in 2020, so it's practically ancient history. But it's really cool! It's about

- The problem of finding a path between two vertices on a graph - An algebraic generalization of this where you replace "graph" by more exotic things (the "algebraic path problem") - An _open_ generalization of this where you build your (generalized) graph by gluing together smaller examples.

The basic algebraic structure is a _quantale_ - an ordered set equipped with a binary operation (compatible with the order), which has all joins. Some basic examples:

- \{0 \leq 1\} with the operation \vee (OR). Here the algebraic path problem detects the existence of a path from one vertex to another. - [0,\infty ] equipped with + and given the _reverse_ order (so join = infimum). In this case the algebraic path problem finds the length of the _shortest_ path (\infty if there is no path).

The first observation is that this boils down to computing the pointwise join \bigvee _i M^i of all the powers of the adjacency matrix corresponding to a graph - where we simply _define_ a "graph over a quantale" to be such an adjacency matrix. If the quantale is \{0,1\}, this is a graph in the usual sense, each edge is either there or not. If the quantale is [0,\infty ], each edge has a certain length (which may be infinite to denote "no edge"). Thus we have "the algebraic path problem".

The second observation is that you can "glue graphs together" by taking pushouts in a certain category of matrices, and this respects the computation of the paths above. There is a lot of very nice category theory in this.

This is an even older paper, which spawned a lively field of research (see eg here and here). This is about associating an invariant called _magnitude_ to metric spaces, which measures their "size" in a kind of hard-to-understand way:

- The magnitude of a finite set of points, all at distance \infty , is the number of points - As the distances go to zero, the magnitude converges to one (in the above case of finitely many points) - The magnitude of the interval [0,t] is 1 + t/2.

I don't think I really understand this stuff deeply, but it's very interesting!

Galois theory is one of the cornerstones of algebra. It studies the relationship between _field extensions_ - that is, inclusions F \subseteq K of one field in another - and subgroups of the group Aut(K/F), of those automorphisms \phi of K with \phi (f) = f for all f \in F. It's somewhat clunky to treat this topic using category theory, for the simple reason that a lot of constructions aren't functorial, involving some choices that can't be made canonically.

Tom Leinster explains a neat proof of one of the fundamental theorems, namely that all fields admit an algebraic closure. The trick here is to work with _rings_ for as long as possible, and then right at the end quotient by a maximal ideal to pass back to fields.

The post ends with a remarkable idea. The algebraic closure is not functorial, in the sense that there is no endofunctor \bar {-}: \mathsf {Field} \to \mathsf {Field} and natural transformation 1 \to \bar {-} so that X \to \bar {X} is always the inclusion of X in its algebraic closure. However, Leinster conjectures that this can be remedied as follows: Consider a pair (\mathcal {E},k), where \mathcal {E} is a topos and k is a field in \mathcal {E} - meaning a ring satisfying the formula \forall x. x = 0 \vee \exists y. xy = 1. Then we can consider the collection of morphisms to pairs (\mathcal {E}',k'), where k' is algebraically closed. Then for \mathcal {E} = \mathsf {Set}, k a normal field, there is an initial such map, given by the topos Gal(k)-\mathsf {Set} of sets with an action of the absolute Galois group of k, and \bar {k} equipped with its natural action.

Unfortunately, this doesn't hold. To see why, first recall why the map of ordinary fields i: k \to \bar {k} is not initial among maps from k to algebraically closed fields. The reason is simply that Gal(\bar {k}/k) is not trivial, so there are multiple maps \bar {k} \to \bar {k} from i to i.

Now let \phi be an element of the absolute Galois group, and consider the functor \phi _*: Gal(k)-\mathsf {Set} \to Gal(k)-\mathsf {Set} that carries a set X to itself with the &phi;-conjugate Gal(k)-action, with (g,x) \mapsto \phi g \phi ^{-1} . x (here g.x is the original action). This is an equivalence of categories, so certainly a geometric morphism (even "in both directions"). Now \phi is a map \bar {k} \to \bar {k} "over" the inclusion i: k \to \bar {k}. It's obviously not Gal(k)-equivariant - but it _is_ equivariant from \bar {k} \to \phi _*\bar {k}. Namely, \phi g \phi ^{-1} . \phi . x = \phi . g.x, which is exactly what should hold. Thus, both the identity and (\phi _*,\phi ) form maps

over (\mathsf {Set},k) (To verify commutativity of the geomtric morphisms, the functor \mathsf {Set} \to Gal(k)-\mathsf {Set} equips a set with the trivial action, and obviously conjugating the trivial action you still get the trivial action). Just as in the normal case, this contradicts initiality.

In categorical approaches to probability, we usually study categories of stochastic maps given as Kleisli categories of "probability monads" - the ur-example being the Giry monad G: \mathsf {Meas} \to \mathsf {Meas} which carries a measurable space to the space of probability measures on it. This is quite distinct from how something like a stochastic process is usually treated in probability theory. There one would usually consider a function f: X \times \Omega \to Y, where \Omega is some "background space of samples", equipped with a probability measure. This formulation is strictly more expressive, since it allows you to express correlations between f(x) and f(x'), but since this is exactly expressive power that you usually _don't_ want in the usual categorical setups, in some sense the Giry formulation may be more appropriate. In any case, Dan Shiebler develops this alternative approach in this paper. He also considers how the paradigm of _maximum likelyhood_ statistics fits into the categorical learning framework as developed eg by Fong-Spivak-Tuyeras in Backprop as Functor and further by Crutwell-Gavranovic-Ghani-Wilson-Zanasi, Categorical Foundations of Gradient-Based Learning

A blog post from the AlgebraicJulia project, about implementing certain ideas from ACT in actual software. Here, they're discussing a notion of "composing dynamical systems". There are different ways of doing this:

- If you have a _parameterized_ dynamical system - one which depends on certain inputs - you can let another dynamical system control those inputs - If you have two dynamical systems, both with a distinguished variable of the same type, you might be able to have them _share_ that variable. This requires that you can somehow "add up" the changes prescribed by each of the dynamical systems. For example, for ODEs you can add the derivatives, and for "difference equations" like y_{n+1} - y_n = F(y_n), you can add the differences. But of course given a fully general "discrete dynamical system" like y_{n+1} = s(y_n), you can't do this.

The blog posts discusses the implementation of this idea in the `AlgebraicDynamics.jl` package.

You probably know that _intuitionistic_ logic is where you don't assume the Law of Excluded middle, P \vee \neg P for all formulas P. You may have heard this described also as _constructive_ logic, and heard something along the lines of "to prove an existence statement constructively, you have to provide an explicit algorithm for constructing an example". Since there are many interesting models of intuitionstic logic that refute LEM, which have nothing to do with algorithms (like toposes), this statement is obviously a bit odd. The right way to interpret it is _realizability logic_, which formalizes the idea of "there is a computable procedure verifying this statement". Then we find that

- In order for \exists a: P(a) to hold, there must be an algorithm that produces a such that P(a) (in a suitable sense) - The logic obeys the rules of intuitionistic logic (but not in general LEM, because this would require that for any statement, there was an algorithm which figured out whether P(x) or \neg P(x) holds, which is not true).

I don't regret skimming. The book spends a lot of time on concepts which didn't really seem interesting to me - but of course that's highly personal, and I guess it's trying to be somewhat comprehensive, so that's the price you pay. I might have strongly preferred to read a summary of the interesting ideas (like this one), but it's hard to say how much I would have absorbed - somehow you usually learn more from being a bit immersed in things.

(of the book). Reproduced here so you can see if anything strikes your fancy:

1. Judgment and rules 2. Statics and dynamics 3. Total functions 4. Finite data types 5. Types and propositions 6. Infinite data types 7. Variable types 8. Partiality and recursive types 9. Dynamic types 10. Subtyping 11. Dynamic dispatch 12. Control flow 13. Symbolic data 14. Mutable state 15. Parallelism 16. Concurrency and distribution 17. Modularity 18. Equational reasoning 19. Appendices.

My notes won't be following this structure.

This is probably the biggest thing I got out of this book. A lot of this is just my existing learning on this stuff finally crystallizing - so what I've written here may reflect me a lot more than the book.

Given a functor F: \mathcal {C} \to \mathcal {C}, we can try to solve the equation F(X) \cong X in at least two ways: We can take an _initial algebra_ of F, or a _terminal coalgebra_ of F. Recall that an algebra is an object X with a map FX \to X. There's an obvious category of algebras, and it's a theorem that for the initial object I, if it exists, the map FI \to I is an isomorphism. Dually, a coalgebra is an object with a map X \to FX, there's a category of coalgebras, and if there is a terminal object T, T \to FT is an isomorphism. These correspond in some sense to "minimal" and "maximal" solutions of the equation F(X) \cong X.

Example: Let \mathcal {C} = \mathsf {Set}, F(X) = 1 + X. The initial algbra is the set of naturals, with \xi : 1 + \mathbb {N} \to \mathbb {N} taking * \in 1 to 0 and n \in \mathbb {N} to n+1. The terminal coalgebra is the set of _conaturals_, \mathbb {N} \cup \{\infty \}, with \xi taking 0 to *, and every other conatural n to n-1 (with \infty - 1 = \infty ).

Let's say you want to construct a map \mathbb {N} \to X. You can do so by _induction_: specify an F-algebra structure on X, and there'll automatically be a unique homomorphism \mathbb {N} \to X. This algebra structure corresponds to a map f: 1 + X \to X. This map tells you:

1. f(* \in 1) is where 0 should go 2. f(x \in X) is where n+1 should go, if n goes to x.

In other words, and inductive definition.

Moreover, you can prove properties of such maps using initiality. Let f: \mathbb {N} \to X be an algebra homomorphism, and let's suppose I want to show that f(n) \in U \subset X for some subset. Then it suffices to prove that there is an algebra homomorphism p: Y \to X with image contained in U. The obvious way to construct this homomorphism is to let Y be some subset of X, contained in U. For Y to be an algebra, we must have, if s: 1 + X \to X, s(*)\in Y and s(y) \in Y for y \in Y. In other words, Y must be stable under successor and contain the initial element.

We can in particular do ordinary induction by applying this to the identity map. Let U \subset \mathbb {N} be the subset of elements satisfying some property. I want to show that the identity has image contained in U, i.e that U is the whole thing. It suffices to show that it contains 0 and is closed under taking successor, i.e to perform induction in the usual sense.

Coinduction is dual to this. It lets you construct maps into the terminal algebra, and prove equality between such maps. Now maybe let F(X) = A \times X for some set A. The terminal coalgebra is the set A^\omega of _streams_, functions \mathbb {N} \to A, with the structure map A^\omega \to A \times A^\omega slicing off the first element.

Given a map X \to A \times X, we get a map f: X \to A^\omega by terminality. Moreover, we can use _coinduction_ to show that f(x) = f(y) for some x,y \in X. Namely, if we can find any coalgebra homomorphism g: X \to \bar {X} so that g(x) = g(y), then we must have f(x) = f(y), since we automatically have f = f'g, with f': \bar {X} \to A^\omega the unique map. How do we construct such a map? The obvious way is to let \bar {X} the quotient of X by some equivalence relation \sim . For X/\sim to still be an algebra - in other words, for the map X \to A \times X to descend to a map X/\sim \to A \times X/\sim , we must have that

1. x \sim y entails s_1(x) = s_1(y) 2. x \sim y entails s_2(x) \sim s_2(y)

where s_1: X \to A, s_2: X \to X are the two components of s: X \to A \times X.

The general slogan is that induction lets us understand _maps out of the structure_ - which includes

The simplest explanation of this is that type safety is a property of a type system and a "operational semantics", i.e of a model of program execution. In turn the simplest notion of execution is to give:

- A subset of expressions in the language called "values", which are "done", i.e they represent the results of computation - A relation e \mapsto e' on expressions saying "e can evaluate to e' in one execution step".

Then type safety means, if e is well-typed of type \tau , either e \mapsto e' for some e' : \tau , or e is a value. You _don't_ want to say something like "any well-typed program evaluated to a value of that type", because your type system probably doesn't guarantee termination (if it does, you language is not Turing complete). Obviously you need more sophisticated versions of this to account for more complicated models of program evaluation, programs with side effects, etc, but this is the idea.

Given a type T with a free type variable t (like t \times \mathrm {int}), we can form the type \forall t. T. An element of this type should be something that can "play the role" of T no matter what t is. For example \lambda x^A.x: A \to A gives an element of \forall A. A \to A.

The behaviour of elements of this type is basically:

- you can "cast" an element of \forall t. T to T[A/t], i.e you can "specialize" the value. - To produce an element of \forall t. T, i have to produce an element that typechecks as T, no matter what the value of t is (the type variable t can't appear in the context).

Similarly you can make sense of "existential types" \exist t. T.

Once you have these, you can define _recursive_ types, too. Take something like a list of integers: `Data Intlist = Nil | Cons Int Intlist`. In other words, `Intlist = () + (Int,Intlist)`.

We can type this using universally quantified types as \forall t. ((() + \mathrm {Int} \times A) \to A) \to A. This basically means: you give me an a : A and a map m: \mathrm {Int} \times A \to A, and I give you an A, for any type A. The `Nil` constructor is the map which simply returns the given a. The `Cons n l` constructor, for `n` an integer, returns an intlist which, given (a,m), feeds it to `l` (returning a'), then computes m(n,a') and returns it.

If you unpack this in your head, you'll see that this is exactly folding. A list is something you can fold over - the a provided is the initial accumulator and the m: \mathrm {Int} \times A \to A is the combination map.

The general formulation of the above is \forall a. (T(a) \to a) \to a. Essentially, we are picking out the _initial algebra_ of T, by saying that this is the universal thing with a map to a for each T-algebra structure on a [^fn:1].

We could also pick out the _terminal coalgebra_, by writing \exists (a \to T(a), a). This has the dual meaning - given any T-coalgbra structure, and a point in the carrier, we obtain a point of the terminal coalgebra. The terminal coalgebra of T(x) = () + x \times \mathrm {Int} is the type of "colists" - possibly infinite lists (of integers). We see above that to produce a colist, we have to provide an element a : A of some type, as well as a map s: A \to () + A \times \mathrm {Int}. s(a) = () means the list is empty, s(a) = (a',n) means n is the head and the rest of the list corresponds to the pair (s,a'). This is "iteration", or maybe "cofolding".

This is about how to evaluate programs. Simple "pure functional" languages can "just" be evaluated by successively applying reduction rules. But this is pretty limited - both in performance terms, but also prevents you from doing a few cool things, like _continuations_.

A _call stack_ is basically a list of functions - in the sense of "expressions with a hole in them" - that are waiting for the result of computation, along with a value that's being evaluated, and a "pointer" which tells us whether the next step is to reduce the active value some more, or to return it, i.e plug it into the next function

So eg the stack `a;b;c > e` means "we're in the process of evaluating `e`. Once that's done, evaluate `c e`, then `b (c e)` and so on". On the other hand `a;b;c < e` means "`e` is a value that's done evaluating, pass it to `c`, then `b`, then `a`.

Then you need to make up some rules for how to handle these things - which order to evaluate expressions and so on.

To augment this language with continuations, you can add expressions like `callcc : (Cont(a) -> a) -> a` and `throw : a -> Cont(a) -> b`, where the meaning of `callcc` is "run this function with a "continuation" pointing the current state - if the continuation is ever "used" by `throw`, just immediately return the value `a` that was supplied". Then the dynamics of this stuff is:

- `s > callcc f` evaluates to `s > f [s]`, where `[s] : Cont a` is a representation of the current stack, and - `s' > throw a [s]` evaluates to `s > a`, i.e throwing restores the stack from the time the continuation was created.

You might have heard about "free theorems", from Wadler's paper Theorems for Free!. Parametricity is the technical term for those things. The basic idea is that a term of polymorphic type has certain properties _purely by virtue of its type_. This is the so-called "free theorem" associated to that type.

The basic idea behind parametricity is to associate a relation to every type:

- Elements of "primitive" types like \mathrm {Int} and such are equivalent if they're equal (this is just a relation on the type itself) - Elements of the product type A \times B are equivalent if they have equivalent coordinates (according to the relations associated to A and B) - Elements of function types A \to B are equivalent if they map equivalent terms to equivalent terms, i.e f \sim f' if a \sim a' implies f(a) \sim f'(a'). - Let A \mapsto T(A) be a "type operator" - we can interpret it as an operation on _relations_ - in particular, it can act on relations A \leftrightarrow A' which are not defined on a single set. The relation \forall . A T(A) is the relation on the set \prod _A T(A) defined by g \sim g' if g_A \sim _T(\alpha ) g_A' for all relations \alpha : A \leftrightarrow A'.

The statement of parametricity is then that x \sim x for all (well-typed) terms x of closed type.

For example, parametricity for id: \forall A. A \to A means that for any relation \sim : A \leftrightarrow B, we have id_A(a) \sim id_B(b) if a \sim b. Specializing eg to a \sim b if and only if a = a_0 for some fixed element (taking maybe B=()), we see that id must be the identity. The precise version of this is more complicated, because you need to deal with the possibility that there may be free type variables around, and also the fact that a type is not really a set (so you need to work with relations on _terms_ - this is what the book does - or use domain theory - this is what Wadler does).

[^fn:1]: Although the quantified definition is more general, because it works even when T is not a functor in a, but just some type that depends on a

Consider the ring of complex polynomials in n variables, \mathbb {C}[x_1,x_2,\dots x_n]. The elements of thing ring can be viewed as _functions_ \mathbb {C}^n \to \mathbb {C}. Given a polynomial f, we can think of it as an _equation_ in n variables - a solution to the equation is a tuple (a_1, \dots a_n) \in \mathbb {C}^n so that f(a_1,\dots ,a_n) = 0. Let V(f) \subseteq \mathbb {C}^n be the set of solutions.

Given a _set_ of polynomials S \subset \mathbb {C}[x_1,\dots x_n], let V(S) = \{(a_1, \dots a_n) \in \mathbb {C}^n \mid f(a_1,\dots a_n) = 0,\ \forall f \in S\} be the set of solutions to the _system_ of equations given by S.

This gives a mapping from subsets S \subset \mathbb {C}[x_1, \dots x_n] to subsets U \subset \mathbb {C}^n. We can also go the other way - given such an U, let I(U) be the set of f such that f(a) = 0 for all a \in U. (We are now writing a := (a_1,\dots a_n) for brevity).

Now V and I enjoy the following very special properties:

- They are both _order-reversing_ - if U \subseteq U' then I(U') \subseteq I(U), and the same for V. - S \subseteq I(V(S)) and U \subseteq V(I(U)).

This means that I and V forms a _Galois connection_ (nlab) - a dual adjunction between two posets. This implies a bunch of interesting things. One of the most important is that the mapping S \mapsto I(V(S)) is a _closure operator_, meaning that in addition to the above inequality, I(V(I(V(S)))) = I(V(S)). In fact for anything of the form I(U), we have I(V(I(U))) = I(U).

This Galois connection is _the_ key to algebraic geometry. It allows us to analyse algebraic things (subsets of a ring) in geometric terms (subsets of a space). So it would be really good if we could understand this thing. In particular, what is the closure operator S \mapsto I(V(S))?

It's pretty clear that I(V(S)) must be an _ideal_ - if f(a) = 0 for all a \in V(S), then f(a)g(a) = 0 too (and if f(a) = g(a) = 0, then f(a) + g(a) = 0). So an obvious guess would be that I(V(S)) = (S), the ideal generated by S.

But this turns out not to be true - there's one more thing we need to close off S under to make this work. Namely, if (f^2)(a) = f(a)^2 = 0, then also f(a) = 0. So if f^2 \in I(V(S)), then f \in S (and similarly for f^n). I(V(S)) is a _radical ideal_ - specifically, it is the radical \sqrt {(S)} of the ideal generated by S. This statement is _Hilbert's Nullstellensatz_ ("zero locus theorem", see wikipedia, nlab)

Let \mathcal {L} be a first-order language, i.e a collection of _function symbols_ f_1,f_2,\dots , each with a specified arity, and /relation symbols R_1,R_2,\dots , also each with a specified arity[^fn:1].

An \mathcal {L}-structure is a set M equipped with a function [f_i]_M : M^n \to M for each f_i, where n is the arity of f_i, and a subset [R_i]_M \subset M^n for each R_i, where n is again the arity.

A _first-order formula in \mathcal {L}_ is a formula built up out of the function symbols, variables, and the connectives \forall , \exists , \vee , \wedge , \neg , =. A model M satisfies the formula if the formula is true when interpreted in the usual way for the model.

A _theory_ is a set of formulas. Given a theory T, let Sat(T) be the set of models that satisfy each formula in T. Given a set of models \mathcal {M}, let Tru(\mathcal {M}) be the set of formulas that are satisfied by each model.

Then it's not hard to see that Sat and Tru form a Galois connection between sets of formulas (theories), and sets of models. What is the closure operator on theories induced by this Galois connection? In other words: Start with a set of formulas. These formulas pin down a set of models, namely the models that satisfy all those formulas. Now almost certainly some more formulas are going to happen to be true for all these models. For example, if \phi \wedge \psi is a formula in T, then also \phi is going to be true for every model - so \phi \in Tru(Sat(T)). In general, any formula which is _provable_ using the normal rules of logic from formulas in T is going to be in Tru(Sat(T)). This is because the normal rules of logic are _sound_ - if you can prove something from true premises, it's true. And in fact, this suffices! To be precise, Tru(Sat(T)) consists _exactly_ of those formulas that are provable using the normal deduction rules of first-order logic from T. This is a celebrated theorem of Gödel (nlab, wikipedia). Since it has the same formal structure as Hilbert's Nullstellensatz - characterizing the closure operator induced by a Galois connection - we might call it _Gödel's Nullstellensatz_. (It is usually called the completeness theorem).

Fix a category \mathcal {C}. Let f: X \to Y, g: A \to B be morphisms. We say that _f has the left lifting property with respect to g_, and that g has the right lifting property with respect to f, if, for each diagram of this form, if the outer square commutes, there exists a dashed arrow making the triangles commute as well:

Given a class S of morphisms in \mathcal {C}, let LLP(S) be the class of morphism with the left lifting property with respect to _all_ morphisms f \in S, analogously RLP(S).

It is again not hard to see that RLP and LLP form a Galois connection from the collection of subclasses of morphisms in \mathcal {C} to itself. What is the closure operator LLP(RLP(-))? This is probably a bit harder to motivate than the previous examples, but understanding it is important in model category theory.

As before, we can try to find some constructions that LLP(RLP(-)) is certainly closed under:

- Pushouts, in the sense that if f: X \to Y is in LLP(RLP(-)), and g: X \to Z is any morphism, the induced Z \to X+_Y Z is also in there. - Retracts: given a commutative diagram

where the horizontal composites are identities, if f is in the class, so is g

- Transfinite composition: given a sequence X_0 \to X_1 \to \dots with each map in the class, the maps to the colimit \operatorname {colim}_i X_i are also in the class (here this diagram can be indexed by any ordinal).

Each of these proofs is essentially by a diagram chase.

A class closed under all these constructions is called _saturated_. Then we have _Quillen's Nullstellensatz_ (which is confusingly usually called the _Small object argument_): If \mathcal {C} is locally presentable, and S is a small set, then LLP(RLP(S)) is the smallest saturated class containing S.

I guess you can actually dispense with the function symbols if you want

Let X be the set of states of some physical system. Here I will assume that there is a finite number of states and time advances in discrete steps - there is some function T: X \to X which steps time forward one step. We assume that these dynamics are time-reversible in the weak sense that T is a bijection - every state is the future of exactly one "past" state. Let S: X \to \mathbb {R} be some function. Assume S(x) \leq S(Tx) - in other words, S can never decrease. Then S is constant, i.e S(x) = S(Tx).

Proof: Assume for contradiction S(x) < S(Tx) for some x. Since X is finite, let \sum _x S(x) be the sum of S over all states. Then clearly \sum _x S(x) = \sum _x S(Tx), since Tx just ranges over all the xs. But on the other hand, we have S(x) \leq S(Tx) for all x, and S(x) < S(Tx) in at least one case. So we must have \sum _x S(x) < \sum _x S(Tx) - contradiction.

This proof can be generalized to the continuous time and space case without too much trouble, for the types of dynamics that actually show up in physics (using Liouville's Theorem). The proof above still requires a _bounded_ phase volume (corresponding to the finiteness of X). To generalize to other situations we need some more assumptions - the easiest thing is to assume that the dynamics are time-reversible in a stronger sense, and that this is compatible with the entropy in some way.

(You can find easy counterexamples in general, e.g. if X=\mathbb {Z} and the dynamics are T(x) = x+1, then obviously we really do have that S(x) =x is increasing. Nothing to do about that.)

Anyways the bounded/finite versions of the theorems do hold for a toy thermodynamic system like particles in a (finite) box - here the phase volume really is bounded.

Okay, so what the hell is going on? Did your high school physics textbook lie to you about this? Well, yes. But you're probably never going to observe entropy going down in your life, so you can maybe rest easy.

Let X be the physical system under consideration again. But suppose now that we can't observe x \in X, but only some "high-level description p(x) \in Y. Maybe x is the total microscopic state of every particle in a cloud of gas - their position and momentum - while p(x) is just the average energy of the particles (roughly corresponding to the temperature). x is called a _microstate_ and y = p(x) is called a _macrostate_. Then the _entropy_ of y \in Y is S(y) = \ln (p^{-1}(\{y\})) - the logarithm of the number of microstates x where p(x) = y. We say these are the microstates that _realize_ the macrostate y.

The connection with Shannon entropy is now that this is exactly the Shannon entropy of the uniform distribution over p^{-1}(y). This is the distribution you should have over microstates if you know nothing except the microstate. In other words, the entropy measures your uncertainty about the microstate given that you know nothing except the macrostate.

There are more sophisticated versions of this definition in general, to account for the fact that

- In general, your microstates are probably sets of real numbers, and there are probably infinitely many compatible with the macrostate, so we need a notion of "continuous entropy" (usually called differential entropy, I think) - Your measurement of the macrostate is probably not that certain (but this turns out to matter surprisingly little for thermodynamic systems),

but this is the basic gist.

Okay, so why does entropy go up? _Because there are more high-entropy states than low-entropy states_. That's what entropy _means_. If you don't know anything about what's gonna happen to x (in reality, you usually understand the dynamics T themselves, but have absolutely no information about x except the macrostate), it's more likely that it will transfer to a macrostate with a higher number of representatives than to one with a low number of representatives.

This also lets us defuse our paradox from above. In reality, entropy doesn't go down for literally every microstate x. It's not true that S(p(Tx)) > S(p(x)) for all x - I proved that impossible above. What _can_ be true is this: given a certain macrostate, it's more probable that entropy increases than that it decreases.

We can consider an extreme example where we have two macrostates L and H, corresponding to low and high entropy. Clearly the number of low-entropy states that go to a high-entropy state is exactly the same as the number of high-entropy states that go to a low-entropy state. That's combinatorics. But the _fraction_ of low-entropy states that go to high-entropy is then necessarily larger than the fraction of high-entropy states that go to low-entropy states.

In other words, P(H(x_{t+1})|L(x_t)) > P(L(x_{t+1})|H(x_t))

Okay, but that's a lot weaker than "entropy always increases"! How do we get from here to there? I could say some handwavy stuff here about how the properties of thermodynamic systems mean that the differences in the number of representatives between high-entropy and low-entropy states are massive - and that means the right-hand probability above can't possibly be non-neglible. And that in general this works out so that entropy is almost guaranteed to increase.

But that's very unsatisfying. It just happened to work out that way? I have a much more satisfying answer: entropy almost always increases because matter is stable at large scales.

Wait, what? What does that mean?

By "matter is stable at large scales", I mean that the macroscopic behaviour of matter is predictable only from macroscopic observations. When a bricklayer builds a house, they don't first go over them with a microscope to make sure the microstate of the brick isn't going to surprise us later. And as long as we know the temperature and pressure of a gas, we can pretty much predict what will happen if we compress it with a piston.

What this means is that, if p(x) = p(x'), then _with extremely high probability_, p(Tx) = p(Tx'). It might not be literally certain, but it's sure enough.

Now, let's say we're in the macrostate y. Then there is some macrostate y' which is _extremely likely_ to be the next one. For very nearly all x so that p(x) = y, we have p(Tx) = y'. But this means that y' must have at least that many microstates representing it, since T is a bijection. So the entropy of y' can at most be a _tiny_ bit smaller than the entropy of y - this difference would be as tiny as the fraction of x with p(Tx) \neq y', so we can ignore it.

So unless something super unlikely happens and p(Tx) \neq y', entropy goes up.

By the way, this also explains what goes wrong with time-reversibility, and why in reality, you can easily tell that a video is going backwards. The "highly probably dynamics" Y \to Y, which takes each macrostate the the most probable next state, don't have to be time-reversible. For instance, let's return to the two-macrostate system above. Suppose that with 100% certainty, low-entropy states become high-entropy. Let there be N_L low-entropy states and N_H high-entropy states. Then, just because T is a bijection, there must be N_L high-entropy states that become low-entropy. Now if N_H \gg N_L, then practically all high-entropy states go to other high-entropy states. So L \mapsto H but H \mapsto H.

Of course in reality, if you start with a low-entropy state and watch this unfold for a _really_ long time, you'll eventually see it become a low-entropy state again. It's just extremely unlikely to happen in a short amount of time.

The entropy of a given macrostate is the uncertainty about the microstate _of an observer who knows only the macrostate_. In general, you have more information than this. For example, if the system starts in a low-entropy state, and you let it evolve into a high-entropy state, you know that the system is in one of the very small number of high-entropy states which come from low-entropy states! But since you can only interact with the system on macroscales, this information won't be useful.

There's the following very classical paradox in probability theory: Suppose you toss a dart at a dartboard. For each point p on the dartboard, we can ask for the probability that the dart hits that exact point p. Suppose we have no relevant information about the tossing process, so that each point seems equally likely. What is the probability P(p)? Well, it can't be more than zero, because then the total probability, the probability that the dart hits any point, would be, not just greater than 1, but infinite! This is because there are infinitely many points on the dartboard, and any positive number added to itself infinitely many times is infinite. But hold on, it also can't be 0, because that means by a similar argument that the probability that the dart hits any point on the dartboard is also 0 - but it must hit _some_ point.

First I'll note that this problem actually is _not_ entirely resolved by measure theory. Measure theory allows for a uniform probability measure on continuous spaces like the interval [0,1] (by, essentially, not allowing us to add probabilities up in every case. More on this later). But if we just suppose a countable dartboard, we're left with the same problem.

But, hang on, does a dartboard really have an infinite number of points? And what does it mean for the dart to hit a point? Certainly the point of the dart _itself_ has a non-infinitesimal area, so that if we partition the dartboard into "points" of that size, there will be a finite number, each of which we can assign some positive probability without issue. In general, any area on the dartboard, no matter how small, has a positive probability of being struck by the dart, and this remains true no matter how small we make the dart, as well.

In other words, this paradox hinges on an infinitesimal dart, as well as an infinitesimally accurate measuring tape with which to measure the coordinates, which presumably has infinitely long numerals on it (presumably the person assigning these credences has an infinitely large brain as well, to be able to hold in their minds the coordinates pointing out a specific point on the dartboard to infinite precision).

Any mathematician knows that you have to handle a situation like this _very carefully_. You cannot expect to apply your intuition directly and get consistent results. I am actually kind of surprised to find serious philosophers making this kind of argument in 2020. This is on par with saying that Zeno's paradox proves you can't use numbers to measure space (or time).

To be fair to Maudlin here, I do think he has a point: there do seem to be situations where you should be indifferent between a (countably) infinite number of outcomes, and probability theory won't let you do that. Dartboards is just a bad example.

Maudlin's shaky relationship with infinity shows up again in his discussion of the classical Kolmogorov approach to probability. He cites the definition of a _finitely additive_ probability measure, and not the \sigma -additive (or countably additive) version used by every probability theorist and statistician in the world. Then he criticizes it for only being finitely additive!

He also critizises the use of a \sigma -algebra, arguing that it seems irrational to exclude certain sets from consideration. I think Maudlin needs to spend a small amount of time understanding non-measurable sets before arguing they're stupid. For one thing, a nonmeasurable subset of \mathbb {R}^2 (such as we might ask "will the dart hit a point in this subset or not" of), is _extremely weird_. It's consistent with ZF minus Choice that there exist no such sets. Certainly such sets always contain regions of "infinite complexity", in the sense that there are (non-infinitesimal) regions of the dartboard so that, if the dart hits there, no finite amount of measurement will suffice to determine whether it is in the set or out of it. Indeed, it's not too far off the mark to think of the \sigma -algebra as denoting the "determinable" events.

The fact that a probability measure is only _countably_ additive is still a bit weird. You can make philosophical arguments for this choice: To check whether a \in \cup _n A_n, we can check whether a \in A_n for each a - and this is guaranteed to give you an answer in a finite amount of time, but only if you're taking a finite union. There are reasonable counterarguments to this, but Maudlin doesn't engage with this topic at all - it really seems as if he doesn't realize that mathematicians have been taking infinite disjunctions of events all this time[^fn:1].

Maudlin's proposed replacement for numbers is essentially the following idea: it's not required that a person's credences be represented by some definite "thing" - a number or another mathematical object. Instead we should ask about the _structure_ on the system of credences, and what rules this should follow for any "rational" person.

This is actually a very good idea! Structuralism! Defining things extrinsically rather than intrinsically! I like this approach.

Let's go over the basic principles that Maudlin comes up with. The paper is short on rigor, but since it's a philosophy paper and not a math paper, I won't hold that against it.

- The set of "credences" should have a partial order[^fn:2]. - The map \operatorname {Cr} which assigns an event its credence should be order-preserving - in other words, if event P entails the event Q, then \operatorname {Cr}(P) \leq \operatorname {Cr}(Q). - There should be a least credence \bot and a greatest credence \top , corresponding respectively to the credence in an event which is certain not to happen or certain to happen (say, a contradiction and a tautology). - The map \mathrm {Cr} should have the following property: if P \Rightarrow Q, \operatorname {Cr}(P) = \operatorname {Cr}(Q),

then \operatorname {Cr}(Q \wedge \neg P) = \bot . This is the so-called "Euclidean property" that Maudlin cannot stop going on about: "the whole is greater than the part", or in this case, if P entails Q, and it's possible that Q but not P (i.e. Q does not entail P), then our credence in Q must be _strictly greater_ than our credence in P.

We can define a partial addition operation on credences, denoted \oplus in the paper, by setting \operatorname {Cr}(P) \oplus \operatorname {Cr}(Q) = \operatorname {Cr}(P \vee Q) whenever \Cr (P \wedge Q) = \bot . It's not exactly clear in the paper whether we extend this using the equality on credences - for example, whether we can assign a value to \operatorname {Cr}(P) \oplus \operatorname {Cr}(P) by finding some other event Q so that \operatorname {Cr}(P) = \operatorname {Cr}(Q), \operatorname {Cr}(P \wedge Q) = \bot , and setting \operatorname {Cr}(P) \oplus \operatorname {Cr}(P) = \operatorname {Cr}(P \vee Q). This seems a harmless enough extension (if we really regard credences as _equal_, and not just equivalent in some sense, it seems inevitable), but Maudlin doesn't really spell it out. Nevertheless the addition is still _partial_, since, for example, when rolling a fair dice, we can't add our credence in the event "The result will be one of 1,2,3,4" to itself, since there is no mutually exclusive event which is equally likely. This is not really a bug - indeed, while you can add probabilities and get a number greater than 1, you can't really treat that number _as a probability_.

So far, Maudlin's approach differs from the Kolmogorovian approach chiefly in that he lets the poset of credences be any ordered set, not just numbers, and that he doesn't require the order on credences to be _total_ - we can have no opinion about the relative plausibility of two events without declaring them _equally_ plausible. This is reasonable enough. Probably the weirdest thing here is that the "Euclidean property" is _also satisfied by Kolmogorov probability!_ The reason that adding a point to a set doesn't change the probability that the dart will land there is simply that it's impossible that the dart will land at that precise point. This is obviously counterintuitive (and there are ways of defending it, and counterarguments to those, and so on - but Maudlin does not engage with this at all), but that is the classical approach. It does not seem to violate the Euclidean property at all.

Having the addition in hand, we can actually reformulate the Euclidean property simply as "\oplus is cancellative", i.e if C \oplus D= C \oplus D' then D = D'. This means that \operatorname {Cr}(Q) = \operatorname {Cr}(P) \oplus \operatorname {Cr}(Q \wedge \neg P), and if this equals \operatorname {Cr}(Q) then \operatorname {Cr}(Q \wedge \neg P) = \bot , since \bot is the unit of addition.

Now Maudlin wants to talk about _relations_ between credences. First of all I have to go on a rant about his whole discussion about ratios. Mathematics has come a long way since Euclid, and citing him like you actually believe his axioms provide a sound formal basis of geometry is not gonna convince anyone that you know what you're talking about. Maudlin goes oddly pedantic and says that the ratio of a circle's circumference to its diameter is not \pi , but rather, the ratio of the number \pi to the number 1, and this is in general what people mean when they identify a ratio with a number. I'm glad to hear that Maudlin has found a solution to the long-standing problem of the identity of mathematical objects (presumably resolving it in favor of a _very_ strong form of Platonism?), but I couldn't find this in the bibliography of the paper or any of his other work. Until I do, I have to insist that "loose talk" is when you insist that two mathematical objects identified under isomorphism cannot possibly be called equal, not the other way around.

Okay, rant done. We can define the ratios between credences by addition. For example, we can say that credence C is twice as big as credence D if C = D \oplus D. Maudlin, quoting Euclid: "Magnitudes are said to have a ratio to one another which can, when multiplied, exceed one another". There is however a serious problem with this: the partiality of addition means that you can't _compare_ these ratios, and many pairs of credences have no ratio to one another, even though Maudlin insists that they do.

Let's pull back here a bit. Suppose I have an ordered (commutative) monoid (M,\leq ,+). Then I can say that m,m' have a ratio to each other if there exist n,n' \in \mathbb {N} so that n.m \geq m', and n'.n' \geq m. If this is true, we can actually obtain a unique real-numbered ratio "m/m'" as the supremum of all n/n' \in \mathbb {Q} so that n.m' \leq n'.m.[^fn:3] Here I'm using n.m to denote the n-fold sum m + m + \cdots + m.

Now, this _doesn't_ work for credences - even in situations where it feels like it should[^fn:4]. The increasingly accurate rational approximations to the "true" real ratio requires longer and longer chains of addition, but this is generally impossible to define for credences. We can define what it means for C/C' to be an integer - namely that n.C' = C. We can also _sometimes_ define what it means for C/C' to be a rational number - for example if 2.C = 3.C', we can say C/C' = 2/3. But if e.g. C = \top , there's no way to make this work. And, crucially, we can't usually compare ratios with each other either - otherwise, we might have argued that expecting number representations for each ratio is too much.

As it stands, by Maudlin's (or rather, Euclid's) definition of ratio, there is no ratio between \top and any event with "probability greater than 1/2" (speaking informally - of course credences aren't probabilities and so on), in contrast with how Maudlin uses it.

This is an area where the paper could really have benefited from some rigor. It's not clear whether Maudlin means to tack on "ratios" as a primitive notion - so that, in addition to having a "more likely than" relation on credences, we have ratios between certain pairs of credences, which can be compared.

All these issues could be solved _very easily_, by imposing some extra structure on the model. For instance we could add "formal sums" of credences which don't have a sum, and say that the statement 2.P \geq Q makes sense even when 2.P is not defined as a credence.

As I mentioned above, I actually, genuinely think it's a good idea to think about replacements for classical probability theory. In some sense my own work on Markov categories is a version of this, a sort of "synthetic probability theory". Much like Maudlin, Markov categories start by asking "what structure do we actually need to do the job of probabilities?". They go in a very different direction, not least because we actually care about the job that probabilities do for people in the real world, but the spirit is actually similar.

But stress-testing your theory by applying it to situations involving infinity - without working rigorously with infinity _at all_ - is bound to get you into trouble. Frankly, if the only problem your theory solves is that it makes sense of infinite conjunctions, it's basically useless. Infinite conjunctions only come up in abstrac mathematical models, and trust me, those guys aren't really looking for a new theory. In the real world, it's very hard to write down infinitely many statements and think about your credence in the statement "one of these is true".

The mathematical idea in this paper - which, again, I actually don't think is a stupid idea - could have fit in a couple of pagers, including a fair amount of exposition and the easy fixes to the problem mentioned above. The philosophical work here seems mainly to be a takedown of traditional probability, which falls woefully flat.

[^fn:1]: A less elegant reason for asking for countable composition but not general infinitary composition is that it leads to a useful, theoretically convenient theory, but still allows for measures like the uniform measure on the interval. This is just an argument from practicality - we take these axioms instead of some others because they make the calculations work out - so I won't hold it against Maudlin if he doesn't take this argument very seriously [^fn:2]: Maudlin seems to not know this term, which probably could have cut several pages from his exposition [^fn:3]: Ironically, in the usual construction of real numbers, they are limits of ratios (between integers), so one could make a convincing argument that a real number really is literally a ratio. [^fn:4]: Credences can be "infintesimal, in the sense that we might have n.C \leq C' for ALL n. That's not what I'm talking about."

- It's very very good and I'm happy I bought one. If your relationship with working "on things" is like mine, I recommend it. - It's expensive and you can get an iPad + accessories + Apple Pencil for the same price, which may be better - There are some annoyances

Would I buy the reMarkable again? That is, if it was struck by a meteor tomorrow, would I buy a new one? Yes (but see my notes on other options). In my opinion, these devices are now good enough that it's worth paying a premium to get the "paper experience". I would not recommend saving up for the reMarkable - that is, if your disposable income is small and you'd need to make an effort over a time period to find the money, it's probably not worth it. If you own a laptop and are considering buying a tablet, which you anticipate using largely for reading and writing, the reMarkable is recommendable. If you're in the market for a tablet to use also for laptop tasks, it's not up to the job.

My fiancé is one of those stationery nerds. She own several different fountain pens and a metric boatload of ballpoint pens, gel pens, highlighters, markers, and what have you. She buys a specific brand of Japanese calendar (Hobonichi) each year. She has had the same color-coding system for her notes since we started university&nbsp;[^fn:1]. She meticulously pagemarks and sorts all her notes into plastic sleeves and binders.

I am not like my fiancé. My workflow for most of my first five years at university consisted of the following:

- Keep a stack of papers and ballpoint pens in my backpack (along with the books I'm using and my laptop and so on). - When you sit down to work somewhere, get laptop, stack of papers, and a ballpoint pen out. - When you need to think, locate a blank spot on a piece of paper in front of you and write there. - If there's no space, go through the papers until you find some space. - When you stop working, gather all the papers into your backpack. - Periodically go through your papers and throw out any that have writing all over them - Periodically add a fresh dump of blank papers to your backpack.

The two points I want to make here is:

- I am a very disorganized person - I fucking love paper

Paper is awesome. I am long paper. Whoever you are, you should be using more paper. There's absolutely no reason to strain your head to the breaking point, keeping a bunch of things inside it, instead of putting them on paper. Actually, if you take one recommendation from this review, just make sure to keep paper and pen wherever you work and use it all the time. Go to these links to buy some _right now_, they're cheap (but you probably have this stuff already - use it!). See also Paper Trauma. I also invite you to consider buying a big notebook, but I haven't tried that yet myself.

But paper has some limitations:

- You sometimes run out - If you want to write your notes about something you're reading on paper, the best place is the thing you're reading - but this requires that it be on paper (instead of a computer). This means you have to buy a book (these have a tendency to pile up rapidly, if it even is a book you can buy) or print it out (this tends to be messy, and you might not have a printer. Back at the university of Copenhagen, I used to print out a lot of stuff and spiral-back it, but I can't do this any more). - Sometimes you lose your old paper where you wrote something important (usually, because you didn't know at the time it would be important). - It's easy to make a mess by creating a huge stack of paper. If you're like me, "clean up your big pile of papers" can sometimes become a bit of an "ugh" task that you can't get around to and which sucks up a lot of energy.

Enter the reMarkable 2. A "next-generation paper tablet", it promises you that you can "Replace your notebooks and printed documents with the only tablet that feels like paper". Naturally, I was intrigued.

The writing experience is _very very good_. It doesn't quite feel like paper - it's not _that_ close - but apart from actually writing on paper it's the best I've tried (having, admittedly, not tried that many). It's leagues ahead of writing on a "normal" tablet using a stylus.

Drawing on the reMarkable has the following advantages over paper:

- You can erase things, perfectly - You can undo/redo strokes - You can zoom - You can select and move things - There's layers, like in image editing software.

The surface feels a bit too smooth - it doesn't have the same friction as dragging a pen over paper. It's still better than a normal screen (like a iPad) though. You can tell they added some texture to make this more lifelike, but it's not the same.

Not surprisingly, it's a bit awkward to hold the tablet with one hand and write with the other. The holding hand doesn't provide quite enough support. You really need to support it with a table or your knees or something.

Probably the biggest thing I would like is a bigger screen.

Notes about the OS

• November 10, 2020
• Eigil Fjeldgren Rischel

The "OS", as it is, is basically just a folder structure where you can arrange pdfs, EPUBs (I haven't tried this), and "notebooks", which are basically collections of pages of your drawing/writing/scribbling. You can also add things to "favorites" and sort by "type" (notebook/pdf/EPUB). It's not amazing, especially since it's a bit sluggish to use, but it does the job.

You can get stuff out of and into the reMarkable in a few ways:

- If you create an account in their server and connect it, it automatically syncs to their cloud, and you can get at this data from a desktop app and a mobile app. These are also how you get stuff into it. The syncing here is pretty slow, so I don't use this a lot. - You can send a mail from the tablet with a collection of pages - either annotated pdf/epub or raw notebook. This is what I do, and it works great! - There's also a browser extension which turns a website into an EPUB and sends it to the tablet. It works okay, about the same as something like Pocket or Instapaper. - You can also have the reMarkable convert you handwriting into text and send it as an email. This is actually surprisingly (to me) good, but probably not quite good enough to send a mail without proofreading (you can check and edit the message on the tablet before sending). The first line in the following picture was converted without error, while the second became "The Quick brown tote jumps over the lazy chef".

I haven't tested this extensively, and I expect it to do worse on other languages than English (you can switch the language used in the setting menu).

The basic things I've done with the reMarkable so far breaks down into roughly three categories:

- During video meetings, I've scratched notes on the tablet - I've put things on the tablet to read, and scribbled in the margins while I did so - I've used the blank pages (notebooks) to work on.

The reMarkable 2 device itself costs 400 EUR (473 USD at current rates, but prices may differ by region). This price point is severely misleading, since it's more or less useless unless you buy a pen (you can read on it, of course, but if that's all you want to do I would definitely consider it overpriced).

The basic "Marker" costs 60 EUR, and the "Marker plus" costs 100 EUR. The only difference is that the plus weighs slightly more and that you can use the rear end to erase. It's probably best to just consider the base price of the device 460 EUR and ask whether you want to pay 40 EUR for the eraser.

Lastly, you can purchase a cover, or "folio". Here your options are the basic folio for 80 EUR, which is simply a sleeve that you can slide the reMarkable into, and the "Book Folio", which is essentially a folder, which magnetically attaches to the back of the reMarkable and wraps around it. This costs 100 EUR for the basic "polymer weave", and 150 EUR for the black or brown "Premium Leather" version. These are "overpriced" in the sense that, if there was a market for reMarkable accessories, you would certainly be able to buy much better protective covers for much less. But there isn't, so you're stuck with these, and the question is whether they're worth the money.

You can also buy a reMarkable 1 with basic Folio and (non-eraser) Marker for 349 EUR.

When I bought my reMarkable, I paid a reduced price because I was buying it early. I bought the Marker Pro and the Polymer Weave Book Folio, and ended up paying 460 EUR.

So how much does the reMarkable 2 cost? Based on my experience so far, the built-in eraser is super convenient and well worth the money. You probably want _some_ sort of protective cover, to prevent the screen from getting dings and scratches, but I have to stress that the Folios really seem to be nothing special. If I was buying it again I would probably buy the Book Folio again, just because 20 EUR isn't a lot and it seems a bit incovenient to be taking it in and out of the sleeve all the time. On that basis, it costs 600 EUR, or ~710 USD.

That's a lot. For that money you could buy an iPad (329 USD), Apple Pencil ($129), and a smart cover ($50), and still have money left over. You could use that money to buy extra memory for the iPad, cellular web access (not a killer app for me, but the reMarkable lacks it). You could even buy an iPad Air, if you maybe skimped out on the cover. I didn't look into the Android options, but presumably those are even cheaper. So if you're looking for a "general work tablet", you should probably skip the reMarkable. If you're looking for the paper feeling, you could consider Paperlike, for just 40 USD (which I have not tried and cannot opine on).

reMarkable really has nothing in the way of tablet features. You can't install any apps (actually, there's a small community of hackers, but nobody is seriously developing third-party software). You wouldn't want to install any of the apps you have on other devices even if you could, because the refresh speed is too low for most "normal" software to really be usable. You can't browse the internet.

What you can do is basically:

- Write and draw with a stylus like you were drawing on blank paper - Read pdfs and ebooks, and write on them.

If stuff like that is such an important part of your workflow that getting a significantly better experience than you would doing the same thing on an iPad is worth giving up _all of the iPad's other features_, you should consider the reMarkable. Personally, this is basically the only reason I would really want to own a tablet anyway. In fact, the fact that I can't browse the internet on it is probably a strong feature in its favor, since it makes it harder to distract yourself with twitter.

Another comparison is with the line of products from Boox. The most direct comparison is with the Note Air, which has a similar form factor and price point. There is also Supernote. I have no experience with any of these. It seems that the Boox Note Air is generally more feature-rich than the reMarkable - it actually runs Android, and is thus closer to a "proper" tablet. This review may provide some information, and recommends the Note Air.

I have to say these products are really tempting me, especially the ones with larger screens. If I was buying a new "paper tablet" today, I would seriously consider them.

[^fn:1]: for the record, her opinion of my reMarkable was that it seemed awesome, but it was a nonstarter for her, because it didn't do colors

A _continuous open dynamical system_ consists of the following data:

- An input set \mathbb {R}^I - An output set \mathbb {R}^O - A state set \mathbb {R}^S - A "dynamics" D: \mathbb {R}^{I+S} \to \mathbb {R}^S. - A "readout" r: \mathbb {R}^{S} \to \mathbb {R}^O.

This is a continous open dynamical system I \to O. Here I,O,S are natural numbers. Note that we are constraining our spaces to being \mathbb {R}^n. Of course we could have made sense of the above definition for any smooth manifold, asking instead for a map I \times S \to TS so that for each i the map S \to TS is a section of the tangent bundle. The reason we're looking only at Euclidean spaces is because, to actually use Euler's method, we need a way of "stepping along the derivative". In our case this is given by simply adding the derivative - in general, we need a map TS \to S.

A trajectory of this dynamical system is a pair of functions i(t),s(t) so that s'(t) = D(i(t),s(t)).

Given systems I \to X, X \to O, we can compose them to obtain a system I \to O. Suppose the state, dynamics and readout of the two systems are respectively S_1,D_1,r_1,S_2,D_2,r_2. Then the state of the composed system is S_1 + S_2, the readout is simply (s_1,s_2) \mapsto r_2(s_2), and the dynamics are D(i,s_1,s_2) = (D_1(i,s_1),D_2(r_1(s_1),s_2)). This corresponds to plugging the output of the first system into the input of the second.

Note that this does not form a category, because there are no identities - there is no way to simply feed the input into the output.

Now for the discrete systems: A discrete open dynamical system consists of the following data:

- An input set I - An output set O - A state set S - An update function U: I \times S \to S. - A readout function r: S \to O.

Now the composition is pretty much analogous: given systems (S_1,U_1,r_1): I \to X, (S_2,U_2,r_2) : X \to O, the composite has input I, output O, state space S_1 \times S_2, readout (s_1,s_2) \mapsto r_2(s_2), and update U_2(i,s_1,s_2) = (U_1(i,s_1),U_2(r_1(s_1),s_2)).

Again, there are no identities.

Recall that _Euler's method_ is a way of solving a differential equation y' = F(y). Given a starting condition y(0) = y_0, we fix some step size h and move forward one step at a time, approximating y(t + h) \approx y(t) + hy'(t) = y(t) + hF(y(t)).

This is essentially replacing a continuous dynamic system with a discrete dynamical system. The state space is the same, and the update function steps forward h by the above method. Formally, if (I,O,S,D,r) is a continuous dynamical system, define Eu_h(I,O,S,D,r) to have

- State space \mathbb {R}^S - the same state space, essentially. - Input space \mathbb {R}^I - Output space \mathbb {R}^O - Update function U(i,s) = s + hD(i,s) - Readout simply given by r

Then, we have that Eu_h is _compositional_ - in other words, if X,Y are continuous systems and X;Y their composite, then Eu_h(X;Y) = Eu_h(X);Eu_h(Y). The proof is essentially just by writing out the definitions.

- The desired identity for in/output, state sets and readout is clear. - For the update, on the left-hand side the update is given by U(i,s_1,s_2) = (s_1,s_2) + h(D_1(i,s_1),D_2(r_1(s_1),s_2)). On the left-hand side, the update is given by U(i,s_1,s_2) = (s_1 + hD_1(i,s_1), s_2 + hD_2(r_1(s_1),s_2)) - these are of course equal.

In ODE solving, a "higher-order method" is one that tries to incorporate information about higher derivatives to make a better estimate. We can view Euler's method as, essentially, calculating y(t+h) by replacing y with its first-order Taylor approximation T_1y(t+h) = y(t) + hy'(t), which we can calculate from the differential equation. We can often get a better estimate by incorporating higher derivatives - by trying to compute y(t) + hy'(t) + \frac {h^2}{2}y^{(2)}(t), for example. Essentially, we are incorporating information about how the derivative will change (or how we think it will change) over the interval [t,t+h]. If it's going up, then we'll get a higher value than we expected just from looking at the derivative now. If it's going down, we'll get a lower value.

The issue here, of course, is that we can't compute the second derivative directly - the differential equation doesn't tell us what it should be. That leaves us with two options

- Derive both sides of y'(t) = F(y(t)) to get y''(t) = F'(y(t))y'(t) = F'(y(t))F(y(t)).

Of course, this requires that the function F in the equation is actually differentiable, and that you have access to a symbolic representation so that you can compute the derivative explicitly. This falls in the general class of methods called _multiderivative methods_. It's easy to see how the above also gives a mapping from continuous systems to discrete ones, although I have not checked the details of compositionality.

- Estimate y''(t) \approx \frac {y'(t)- y'(t-h)}{h} = \frac {F(y(t)) - F(y(t-h))}{h}. This can then be calculated from the past two steps.

It's not immediately obvious how to make this into a discrete dynamical system. After all, the next state depends not only on the current state, but also on the previous one. The idea will be to make a state of the discrete system consist of _two_ points in the space - the transition replaces the first with the second, and computes a new second point by the method. Explicitly, given as above a continuous dynamical system:

- The input and output are as Euler's method - The state is \mathbb {R}^S \times \mathbb {R}^S. - The readout is r(s_1,s_2) = r(s_2) (the readout of the "present") state. - The update is U(i,s_1,s_2) = (s_2, s_2 + hD(i,s_2) + \frac {h}{2}(D(i,s_2) - D(i,s_1)))

Note that in this method, we are updating under the assumption of constant input - it may be more appropriate to remember the last input as well, and use that. In any case, I have not verified compositionality of this method either.

The dual of a chu space is simply given by swapping the two sets, i.e (X,U,e)^\bot := (U,X,(u,x) \mapsto e(x,u)). This defines a self-duality on the category of Chu spaces, Chu(Set,S) \cong Chu(Set,S)^{op}

The additive connectives \& and \oplus are simply given by the product and coproduct in the category of Chu spaces. Let's describe this explicitly:

- Given Chu spaces A= (X,U,e), B=(Y,V,e'), their product A \& B is given by (X \times Y, U + V, e \& e'), where e\& e'(x,y,u \in U) = e(x,u), and e\ampe '(x,y,v\in V) = e'(y,v).

This corresponds to a game where the other player chooses one of the games to play, and a choice in that game. You have to choose a strategy for both games, not knowing which will be played. - The terminal object is (*,\emptyset ,0), where 0 denotes the empty function. Interpreting this as a game is slightly weird - it is a game that cannot be played, as the opponent has no moves to make. (Hence if given a choice between this and another game, the opponent must move in the other game, so that this is a unit for the product, as it should be). - Given A and B as above, their coproduct A \oplus B is given by (X + Y, U \times B, e \oplus e'), which is exactly dual to the product. In other words, here the player chooses a game and a move in it, while the opponent must choose a move in both games. - The initial object is (\emptyset ,*,0) - the player cannot move in this game.

The additive connectives, in other words, are much as you would expect from the "game" interpretation. The multiplicative connectives are more weird.

The tensor A \otimes B of two Chu spaces as above is defined by (X \times Y, [X,V] \times _{[X\times Y,S]} [Y,U], e\otimes e'), where e \otimes e'((x,y),(f,g)) = e'(y,f(x)) = e(x,g(y)). (Here the last equality is exactly the condition that (f,g) lies in the pullback). In other words, to play A \otimes B, the player simply chooses a strategy in each game. The opponent must choose a strategy in A which depends on the player's strategy in B - a map Y \to U, and vice versa. These conditional strategies must satisfy the condition that, whether we play A using the strategy matching the player's strategy from B, or vice versa, we get the same result.

If you squint a bit, this is somewhat like the tensor product of games from before - the opponent can adjust their strategy based on the player's moves in the other game. But it's also very different. For example if the two images e(X \times U) and e'(Y \times V) are disjoint subsets of S, the opponent has no moves in this game.

The tensorial unit is I = (*,S,1_S) - in this game, the opponent simply chooses the outcome. Indeed, we have A \otimes I \cong A - the player's choice amounts to choosing a \in X, while the opponent must choose a map * \to U - a point in U, and a map X \to S, which has to equal the map x \mapsto e(x,u) corresponding to their chosen U, so this is no choice at all.

There is a canonical map A \otimes A^\bot \to I^\bot = (S,*,1_S). In A \otimes A^\bot , the player must choose a strategy and a counter-strategy. The opponent must choose a map X \to X and Y \to Y - of course the canonical choice is the identity. The outcome of this game is exactly the result of playing the player's two chosen strategies against each other - this is the element s \in S that the player's strategy is taken to.

In general, we can identify maps A \to I^\bot with choices of strategy for the opponent - the point is sent to that strategy, while the map X \to S is constrained to being exactly the outcome corresponding to that strategy.

Dually, we can identify maps I \to A with strategies for the player. This of course means that a linear logic proof of the sequent \vdash A identifies a strategy for the player in the game defined by A.

Category theory is an amazingly successful tool for pure mathematics. Since its introduction by Eilenberg and MacLane in Generalized Theory of Natural Equivalences, it has completely transformed algebraic topology and algebraic geometry.

Let's study some examples of this:

Idempotent monads, aka localizations

• October 14, 2020
• Eigil Fjeldgren Rischel

It's very common in algebraic topology that you have some class of morphisms W in your category \mathcal {C} that you want to treat as isomorphisms. First of all, category theory tells us that there is essentially a unique way to make sense of this: The desired category \mathcal {C}[W^{-1}] should have the following universal property: given a functor \mathcal {C} \to \mathcal {D} which sends every f \in W to an isomorphism, there should be a unique extension over \mathcal {C}[W^-1], as in this diagram:

This formalizes the intuition that \mathcal {C}[W^{-1}] is \mathcal {C}, with the maps W turned isomorphisms, and nothing else changed. Category theory (the Yoneda lemma), applied to the category of categories, tells us that this determines \mathcal {C}[W{-1}] up to equivalence of categories. Under quite weak assumptions, this category can be constructed.

But understanding the category \mathcal {C}[W^{-1}] is usually very difficult. However, in good cases, something miraculous happens, and \mathcal {C}[W^{-1}] appears as a subcategory of \mathcal {C} itself!

As a very simple example, we can consider the category \mathrm {Ab} of abelian groups. Call a homomorphism a "rational equivalence" if

- If f(x) = 0, then nx = 0 for some n \in \mathbb {Z} - For each y in the image, there exists x,n so that f(x) = ny.

Call the category of rational equivalences W. Then \mathrm {Ab}[W^{-1}] is equivalent to the subcategory consisting of \mathbb {Q}-modules - those abelian groups A where each multiplication by n map (n \cdot -): A \to A is a bijection.

The way to construct this in general is to consider the subcategory of _W-local objects_ - those objects A where, for every f: X \to Y in W, the map \mathcal {C}(A,X) \to \mathcal {C}(A,Y) is a bijection. If every object admits a map \lambda : A \to \tilde {A} with \lambda \in W and \tilde {A} W-local, then the construction A \mapsto \tilde {A} assembles into a functor, which exhibits the subcategory of W-local objects as \mathcal {C}[W^{-1}].

In this case, part of the utility of category theory is it lets us ask this question in the first place. But beyond that, it gives us access to the idea of, to put it technically, asking for objects that represent functors with certain properties (for example, those that invert certain morphisms) - in general terms, to describe objects in terms of their relations to other objects.

(The really powerful uses of this technique involve doing something more complicated to model categories, or, equivalently, applying it to \infty -categories. But I won't get into that here - see e.g. my undergraduate thesis or section 5.2.7 of Higher Topos Theory.)

The phrase "universal property"[^fn:2] appears neither in the original ZX calculus paper, nor in Graphical Structures for Design and Verification of Quantum Error Correction, which is one of the more successful applications (both of the ZX calculus and of category theory in general, outside pure math). Clearly they are not that interested in characterizing objects by their mapping properties - indeed, since the objects in this case are just finite-dimensional Hilbert spaces, hence direct sums of \mathbb {C}, characterizing such a thing is not that interesting. The point is that in the classical domains of category theory, the primary thing is the objects, and how they map to one another. When we think about maps, we are usually just looking for an abstract machine that will guarantee the existence of a map with such-and-such properties, not in looking "inside" the map, so to speak, to see what it does. This in contrast with the ZX calculus, where the chief point is that we want a method for writing down maps between Hilbert spaces and understanding how they work. So also open Petri nets - the interesting structure here is (obviously) the _Petri net_, not the finite sets which serve as objects.

In this domain, the chief interest is in the _functors_ - we want to know, for example, that a certain "black-boxing" construction from the category of Petri nets to the category of (say) linear relations preserves the composition.

As remarked by Jules Hedges here, the "compositionality" above is really just about operation-preserving maps between algebras of some operad - the fact that the operad (or a suboperad) is the operad for categories[^fn:3] is not really important. So we can consider the operad where

- The types (or colors) are pairs (I,O) of finite sets - The operations are generated by a composition operation (A,B),(B,C) \to (A,C), an identity operation () \to (A,A), and optionally a "tensor" operation (A,B),(X,Y) \to (A+X,B+Y) and some more operations for the unitors and associators in the monoidal structure. - Quotiented by the axioms of a monoidal category.

Then the _set_ of open petri nets is an algebra for this operad, and we're essentially looking for an algebra homomorphism into a different algebra.

This perspective has a number of advantages:

- When mapping into a situation where a slightly different structure exist, we can describe this by adding an operad homomorphism to the mix. - We can take algebras in _categories_ to get categories where the _objects_ are the systems we're interested in.

This can give us some interesting universal properties - for example, the initial Petri net (with given input-output sets I,O) would seem to be the net with exactly I+O as places, and no transitions.

We can go even further and consider morphisms between systems with different interfaces. Presently the best framework for this seems to be double categories, which means we're going back to the operad for categories[^fn:4], but that's fine. For example, in Morphisms of Open Games, Jules Hedges constructs a double category of open games, and describes limits and colimits in the "vertical category of morphisms" - i.e. in the category where objects are open games and maps are morphisms _between_ them.

In fact, various technologies for describing "open systems", like the Structured Cospans of Baez and Courser, already output a double category. And in fact the composition in these systems already involves some sort of universal property, being described as a pushout.

Above we have thought about many different situations where we're interested in studying the "behaviour", in some sense, of complex systems, and we try to understand this behaviour as a functor in a category of such systems. Perhaps the most famous example of this is the notion of _functorial semantics_ from logic (indeed the term "functorial semantics" seems to describe the black-boxing functor quite well). The general pattern is that we have a _syntactical category_ where the morphisms are terms in some syntax, subject to some equivalence relation (often generated by some set of syntactical rewriting rules), and this is mapped into some sort of "semantics" category. Here it very often happens that the necessary structure to interpret the syntax corresponds to some more or less natural categorical structure, and the syntactical category is the initial such category (so that there is a well-defined interpretation of the syntax in each suitable category).

An example of this is simply typed lambda calculus, or STLC. I guess it's well-known that the simply typed lambda-calculus can be interpreted in any cartesian closed category. Each type A is mapped to an object [ [A ] ], with [ [ A \to B ] ] = [ [ B ] ]^{[ [ A ] ]}. Then a judgment \Gamma \vdash e : A, where \Gamma = x_1 : X_1, x_2 : X_1, \dots x_n : X_n, is mapped to a morphism \prod _i [ [ X_i ] ] \to [ [ A ] ], by inducting on the proof of the judgment using the projections and the hom-product adjunction.

One can show that the _initial_ Cartesian closed category with a certain set of objects and points - we might say the CCC _generated_ by that data - can be described as having objects the contexts, and morphisms the judgments, in STLC with those constants. But this is somewhat interesting - the syntax of lambda calculus is "about writing down functions", just as the ZX calculus. Yet there are also universal properties in the mix - the fact that the functor A \times - has a right adjoint for all A. Across many areas of categorical logic, similar things happen.

[^fn:1]: It actually holds for D^n for all n, but let's keep things simple [^fn:2]: A lot of things are described as _universal_, but this refers to the important property that any quantum computation can be described in ZX-calculus [^fn:3]: There isn't really an operad for categories - what I describe here is for "categories with a specific set of objects" - but that's not so important [^fn:4]: There are ways to generalize this - David Jaz Myers has studied monoidal double functors into a double category of categories, which seems to be a version of this (in some sense, this uses the fact that any operad can be upgraded to a symmetric monoidal category). See eg this talk.

If you've taken a course on group theory, you've probably learned about _presentations_ of a group. Here are some examples:

- \langle s,r | r^4, s^2 srsr \rangle - \langle a, b | \rangle - \langle a, b | aba^{-1}b^{-1} \rangle .

On the left of the pipe, we have a set S of _generators_. On the right of the pipe, we have a different set R of _relations_ - these are "group words" in the generators, i.e words involving both the generators and their inverses. The meaning of such a "presentation" is that it describes a group, namely the quotient of the free group on S by the relations.

Every group G has a presentation (in fact, many), for example given by taking S = G and R given by all words which evaluate to 1 in G. This leads to the idea that one could _define_ group theory out of presentations. This seems to work out well - in fact, given G,H groups, if we take their "canonical" presentations as above, a group homomorphism G \to H is exactly the same thing as a function G \to H which takes those words in G which evaluate to 1 to words in H which evaluate to 1.

However, this doesn't work in general - most group presentations don't have "enough generators" to represent all group homomorphisms into the presented group. And there are many maps which "should" be group isomorphisms which don't have an inverse on the level of presentations.

The basic things you can do in a model category are:

- Invert certain maps that "should" be isomorphisms (or "equivalences") - Replace an object with a "better behaved" one which is "equivalent" in that sense.

Let's take a more classical example from "real" homotopy theory: Simplicial sets. In this context, we think of a simplicial set X as a "model" for a topological space, its geometric realization |X|. A map X \to Y is a simplicial homotopy equivalence if the map of spaces |X| \to |Y| is a homotopy equivalence of spaces. However, in many cases, such an equivalence can't be inverted, even up to (simplicial) homotopy. Similarly, there are often maps between geometric realizations which can't be represented by maps between the simplicial sets, even up to homotopy.

The basic solution to this is to work with certain nice simplicial sets called _Kan complexes_. A Kan complex has "enough simplexes" so that all the maps between them that "should" exist, do. Now we _could_ simply work with the category of Kan complexes - but this is an inconvenient category. Its main deficiency is probably that it does not have all colimits. This is compared to the full category of simplicial sets, which is as nice as they come.

So we use a powerful piece of technology called a _model structure_, making simplicial sets into a model category. (This is usually called the Kan model structure, or the Kan-Quillen model structure).

The upshot of this is that every simplicial set is homotopy equivalent to a Kan complex, in a very structured way which lets you use the technically convenient structure of the whole category of simplicial sets to describe "the homotopy theory of Kan complexes".

Now we are going to try to adapt the above to groups.

The way to do this is to describe the _trivial cofibrations_ - essentially, these will be those maps which are "morally group isomorphisms".

Using the machinery of model categories, we can get away with specifying only a small "generating family". These are on page 2 of the paper.

Now here's a fun fact: this small list pins down exactly the "proper" presentations of groups, in this sense:

**Theorem**: The following two are equivalent for a presentation \langle S \mid R \rangle

- The map S \to F(S)/R is bijective, and R contains every word which is zero in F(S)/R. - For every diagram

if f is in the generating list, there exists an extension like the dashed arrow making the triangle commute.

**Proof**: First, it's easy to check for each type of generating arrow that this holds:

- a and b must be sent to the same element (by injectivity), so we can simply send c there as well. - We can extend the map by sending a to whatever element w^{-1} evaluates to. - The remaining three maps simply add relations which are derivable from the existing ones - hence their images must already be in R.

Now for the other direction, suppose a,b \in S go to the same element in F(S)/R. Then the map \langle a,b \mid ab^{-1} \rangle \to \langle S \mid R \rangle does not have an extension over the first generating map. Hence that map is injective. Suppose w \in F(S)/R is not in S. Then the map \langle S \mid \emptyset \rangle \to \langle S \mid R \rangle does not extend over \langle S \sqcup \{a\} \mid a w^{-1} \rangle - there is nowhere to send a (since it must be sent to something that goes to w, for the property to hold). The statement that R contains every word that goes to zero means that R is stable under certain operations, which can similarly be proved from the morphisms.

It follows from the general theory of model categories that there always exists a map \langle S \mid R \rangle \to P into a "nice" (in technical terms, fibrant) presentation, which is itself a trivial cofibration. Understanding what the trivial cofibrations are in technical terms is more complicated - an argument going in the other direction from the one above will show that they are exactly those which correspond to group isomorphisms, but this might be a bit tricky.

Given a program p: A \to B, we can define \bar {p}: A \to A as follows: to compute \bar {p}(n), run p(n) until completion, then return n no matter what.

Certainly any universal Turing machine admits this construction. Does this define a restriction category? Recall the axioms of a restriction category:

1. f\bar {f} = f 2. \bar {f}\bar {g} = \bar {g}\bar {f} 3. \overline {g\bar {f}} = \bar {g}\bar {f} 4. \bar {g}f = f\overline {gf}

(If these compositions are well-defined).

1. Clearly f\bar {f} has the same values as f. It runs in almost exactly twice the runtime of f, plus whatever the overhead of composition and the \bar {(-)} construction is. It is not actually completely obvious that this is small enough for _every_ universal Turing machine. Nevertheless, the assumption that T(\bar {p},n) \leq T(p,n) + C for some constant C seems rather harmless, which suffices here. 2. \bar {f}\bar {g} and \bar {g}\bar {f}, again, clearly have the same values. With the assumption from above, the runtime is also asymptotically the same. 3. Once again it's easy to see that the two maps have the same values. The first one runs in T(g,n) + T(f,n) + 2C, and so does the second one, hence they have the same (asymptotically) runtime. 4. Here the claim about equivalent runtimes is a bit more subtle. The first one takes T(f,n) + T(g,f(n)) time (up to asymptotic equivalence). The second one takes T(f,n) + T(g,f(n)) + T(f,n). But these two are equivalent - the second is at most twice the first.

Hence \mathsf {Comp} is a restriction category.

Do "restriction products" exist in \mathsf {Comp}. This would seem to rely on a _constant-time_ bijection \mathbb {N} \cong \mathbb {N} \times \mathbb {N}. I am fairly sure this doesn't exist - since the encoding size of a natural number grows as the logarithm, it would seem that such a bijection must have unbounded runtime.

This may be remedied by passing to a less restrictive form of equivalence. For example, suppose we can find a logarithmic-time implementation of the above bijection. Then we can alter the definition of \lesssim so that p \lesssim p' as long as there exists C so that T(p',n) \leq CT(p,n)\log (n) (and they have the same values). There are other reasons to prefer this equivalence relation. It is not in general true that universal Turing machines can simulate each other with _constant_ overhead. This means that the choice of UTM made at the beginning of this post is actually significant. But it _is_ true that they can simulate each other with _logarithmic_ overhead.&nbsp;[^fn:1] This means the choice of machine is unimportant, making for a much nicer theory.

The construction of this correspondence does seem to be the only obstruction to equipping \mathsf {Comp} with a Cartesian restriction structure, in the "obvious" way (where A \times B is the subset of \mathbb {N} which corresponds under this bijection to a pair (a\in A, b \in B).)

Can we define a trace operation on \mathsf {Comp}? This would be an operation Tr^X_{A,B}: Hom(A \times X \to B \times X) \to Hom(A,B). The idea would be that to evaluate Tr^X_{A,B}(f) on a \in A, you run f(a,0) to obtain b_1, x_1, then run f(a,x_1) to obtain b_2,x_2 and you keep doing this until you find a fixpoint where x_n = x_{n+1} then the resulting b_{n+1} is your output. (If this never terminates, you simply don't halt on that input).

The obvious problem is that the choice of 0 is non-canonical. We might want to let Tr^X_{A,B} only be defined when this input doesn't matter - but this property is not obviously computable! (We would have to check every possible n). This probably precludes Tr^X_{A,B} from satisfying the axioms of a trace. I'm not sure, but I think the issue will appear in the axiom Tr^X_{A,B}Tr^Y_{A\otimes X, B \otimes X}(f) = Tr^{X\otimes Y}_{A,B}(f). The right-hand side corresponds to applying f(a,0,0), then f(a,x_1,y_1), then proceeding like that until we find a fixpoint (x_n,y_n). In the second, we first define a function f(a,x) by applying f(a,x,0) to find y_1, then going until we find a fixpoint y_n. Then we apply _the function to defined_, call it f', with f'(a,0) to find x_1, and so on. In other words, we first find a fixpoint y for f(a,0,y), and use that fixpoint to produce x_1. Then we find a fixpoint for f(a,x_1,y) and so produce y_2, and so on. This does eventually produce a pair (x,y) which form a fixpoint for f(a,x,y), but not necessarily the same one as the "simultaneous" procedure. This problem is exactly fixed if we only allow those as where the starting input doesn't matter - then there is a unique fixpoint, and we are happy.

The second problem, of course, is that the two procedures defined above have _very different runtimes_. This problem does seem to be baked into the axioms of a traced monoidal category. This is perhaps not surprising - these axioms are not saying that both sides are equally fast ways of computing the result, just that the results are equal. So perhaps we should look for some alternative "complexity-sensitive" version of these axioms that make sense in our context.

On the other hand, the temptation to regard a string diagram with loops as describing a meaningful program is very strong. This would suggest that we need a different version of \mathsf {Comp}, or perhaps a different traced structure, that makes the two sides of the equation equal.

Comp is, first of all, not a Turing category, because undecidable subsets of the natural numbers won't be retracts of them. If we fiddle with the definition to fix this issue (we can remove all other objects than \mathbb {N} and \{1\}, for example), it might actually be a Turing category - because of the fact that universal Turing machines can simulate each other with logarithmic overhead.

- What is the general definition of which \mathsf {Comp} is an example? - Does this actually help at all? - Is there a (family of) model(s) of computation which allows us to A: make a category with useful internal structure, B: without fiddling with various notions of asymptotic performance.

[^fn:1]: See eg Wikipedia

A discrete dynamical system (S,T) consists of a set S and a time-step function T: S \to S. It's clear that this is exactly the same thing as a \mathbb {N}-set, i.e a set with an action of the monoid (\mathbb {N},+,0)[^fn:1]. A "morphism of discrete dynamical systems" is just the obvious thing, namely a map which preserves the action - an equivariant map.

For now, we will restrict ourselves to those dynamical systems with "time-reversible dynamics" - that is, those where the action T: S \to S is a bijection. The subcategory of such things inside \mathbb {N}-\mathsf {Set} is equivalent to \mathbb {Z}-\mathsf {Set} - a dynamical system is time-reversible if and only if the action of \mathbb {N} extends to an action of \mathbb {Z}.

Now, we will be interested in _localizations_ of the category \mathbb {Z}-\mathsf {Set}. One important family of such localizations comes from the group homomorphisms \mathbb {Z} \to \mathbb {Z}/n.

This homomorphism gives a functor \mathbb {Z}/n-\mathsf {Set} \hookrightarrow \mathbb {Z}-\mathsf {Set}. In fact, this functor is fully faithful, and its image is exactly the subcategory of n-periodic dynamical systems - i.e those for which T^n(x) = x for all x \in S. Moreover, this functor admits a left adjoint L_n. It takes a dynamical system (S,T) to (S/\sim , \bar {T}), where \sim is the equivalence relation generated by x \sim T^nx and \bar {T} is the induced map.

The order structure of this family of localizations is exactly the division order. By which I simply mean, if n | m, then an n-periodic dynamical system is also m-periodic, and if every n-periodic dynamical system is m-periodic, then n|m (proof of the second implication: consider the dynamical systen (\mathbb {Z}/m, +1)).

Using these, we can form a sort of "p-adic completion" of any dynamical system, as the limit \lim _n L_{p^n} S =: S^{\wedge }_p. The functor (-)^\wedge _p is a localization. The p-adic completion of the integers with translation action is exactly the p-adic integers (with translation action). Since each system S/p^n acquires a canonical action of \mathbb {Z}/p, it would seem that probably S^\wedge _p acquires an action of the p-adics \mathbb {Z}^\wedge _p.

However, to make sense of this, it's probably best to work in a category of topological spaces with continuous group actions. I would guess that the \mathbb {Z}/p actions assemble to a unique _continuous_ \mathbb {Z}_p^\wedge action, although I have not checked it.

The family of localizations (-)^\wedge _p is jointly conservative on _finite_ dynamical systems (since each orbit is an n-period for some n). However this fails in a predictable way in the infinite case, where we can't distinguish between (\mathbb {Z},+) and (\hat {\mathbb {Z}},+). To remedy this, one would need some sort of "rationalization" of dynamical systems. However, there we run into the issue that the functor \mathbb {Q}-\mathsf {Set} \to \mathbb {Z}\mathsf {Set} is not fully faithful - a \mathbb {Q} set has a chosen "half action", the action of 1/2 on S, but this action is not necessarily uniquely determined by the action of 1.

We take a somewhat unorthodox approach and let a _smooth dynamical system_ be a smooth manifold M with an action of the Lie group \mathbb {R}. (Again, we are looking at time-reversible systems). Given a discrete subgroup of \mathbb {R}, the quotient \mathbb {R}/H is again a Lie group, and we obtain a fully faithful inclusion \mathbb {R}/H-\mathsf {Mdf} \hookrightarrow \mathbb {R}-\mathsf {Mdf}.

The discrete subgroups of \mathbb {R} all have the form \lambda \mathbb {Z} for some \lambda , and the quotient is always diffeomorphic to S^1. As above, passing to this quotient corresponds to considering &lambda;-periodic systems.

In this situation, there no longer exists a left adjoint, for annoying reasons. The universal property of the left adjoint, if written out, tells us it should take a manifold M to the quotient M/(\lambda \mathbb {Z}) of the action by \lambda \mathbb {Z}. Consider the normal additive action of \mathbb {R} on S^1 = \mathbb {R}/\mathbb {Z}. If we take \lambda to be an irrational number, the orbits of the action are dense in S^1, and the quotient is not even a topological manifold.

One would hope this problem can be solved by something like "derived manifolds", but I haven't looked into that yet.

[^fn:1]: My natural numbers include 0

In "normal" nonstandard analysis, we consruct the "nonstandard reals" \mathbb {R}^* as an ultrapowwer of the ordinary reals with regards to some nonprincipial ultrafilter \mathfrak {u}. This means that a nonstandard real is a sequence (x_n) of reals, quotiented by the equivalence relation which identifies two sequences if the set of naturals where they agree is in the ultrafilter - in symbols, \{n | x_n = y_n\} \in \mathfrak {u}

This set inherits all the structure of the reals - where addition and multiplication is pointwise, and (x_n) \leq (y_n) if \{n | x_n \leq y_n\} \in \mathfrak {u}. In fact, it is even a totally ordered field, since first-order properties pass to ultrapowers by Łoś's Theorem. It also contains a copy of the real numbers, where x \in \mathbb {R} is identified with a constant sequence. We call these the _standard reals_.

(\mathbb {R}^* is not complete, since this is a second-order property.)

\mathbb {R} contains "infinitesimals", like the sequence (1/n) - this is a positive nonstandard real number, but less than every positive standard real number. Call this number \epsilon .

It also contains "infinite numbers", like the sequence (n) - this is a nonstandard real wich is larger than every standard real.

Given a function f: \mathbb {R}^* \to \mathbb {R}^*, we can ask for the value \frac {f(x + \epsilon ) - f(x)}{\epsilon }. This is a well-defined nonstandard real, since \epsilon is not zero. In fact, it is the nonstandard real \left (\frac {f(x + 1/n) - f(x)}{1/n}\right ). If f comes from a function \mathbb {R} \to \mathbb {R} which is differentiable, this sequence converges to f'(x). This means that the difference between the nonstandard derivative and the normal derivative is an infinitesimal, in the sense that it is smaller than every positive and larger than every negative standard real. One can show that f'(x) is the only standard real with this property - so this gives a definition of the derivative (which does not depend on the choice of \epsilon ).

Nonstandard analysis takes this idea and runs with it to develop various parts of analysis using these infinitesimals.

There are a few problems with this:

- The existence of a non-principal ultrafilter on \mathbb {N} requires some "unfortunate" axiom like the axiom of choice or somesuch. (The existence of non-principal ultrafilters on all infinite sets is called the ultrafilter theorem, and is strictly weaker than the axiom of choice, but still considered a bit suspicious - for instance it implies the existence of nonmeasurable sets). - According to Tao, it's sometimes difficult to extract a quantitative bound from an asymptotic theorem proved with nonstandard analysis - he links this to the first point.

However, these difficulties disappear if we instead use the Frechet filter, consisting of all cofinite sets, on \mathbb {N}. In other words, a cheap nonstandard real is a sequence (x_n) of reals, quotiented by the equivalence relation that (x_n) = (y_n) if x_n = y_n for n sufficiently big. Note that the Frechet filter is not an ultrafilter! Hence Łós' theorem does not hold, so the cheap nonstandard reals fail to inherit all the good properties of the ordinary reals.

The easiest example of this is that they are not a field. To see this, consider the cheap nonstandard real (0,1,0,1,0,1,\dots ). This is not equal to zero, because there are infinitely many ones. On the other hand, it is also not invertible: if we multiply it with the cheap nonstandard real (x_n), we get (x_1, 0, x_2, 0, \dots ). This is not equal to one, because there are infinitely many zeroes.

The way this would work for an ultrafilter is that either the set of even numbers or odd numbers would be in the ultrafilter. So either (0,1,0,1,\dots ) is zero or one - in either case, it's clearly invertible.

It turns out the parts of Łós' theorem that specifically fails for non-ultra filters are about statements \phi \vee \psi - disjunction, and \neg \phi - negation. Hence the statement x = 0 \vee (\exists y : xy=1) doesn't hold for the quotiented product, even though it holds for the ultraproduct.

However, this shouldn't concern us _too much_, because we can basically view this as a faily of LEM (in a way that I will explain), and LEM is another one of those slightly suspicious axioms.

In what sense does LEM fail for cheap nonstandard reals? As mentioned, the nonstandard reals are a model of the language of ordered fields. The way this works is that any formula \phi (x) in that language can be interpreted for a nonstandard real by asking if \phi (x_n) holds for a set in the ultrafilter - for short, whether \{n \mid \phi (x_n)\} \in \mathfrak {u}. A priori, this gives two ways of intepreting a formula like x=0 \vee x=1. We can ask whether \{n \mid x_n = 0 \vee x_n = 1\} \in \mathfrak {u}, or we can ask whether \{n \mid x_n = 0\} \in \mathfrak {u} \vee \{n \mid x_n=0\} \in \mathfrak {u}. The second is the "correct" semantics for first-order logic, but the first is usually more convenient. Luckily, for ultrafilters they are the same.

We can try to use this approach with a non-ultrafilter, like the Frechet filter \mathcal {F}. But now there's a difference! If we let (x_n) = (0,1,0,1,\dots ), it's true that \{n \mid x_n = 0 \vee x_n = 1\} \in \mathcal {F}, but not true that \{n \mid x_n = 0\} \in \mathcal {F} \vee \{n \mid x_n = 1\} \in \mathcal {F}. A similar problem crops up for negation.

In this way, LEM fails in some sense, because we can have \phi ,x so that \{n \mid \phi (x_n)\} \notin \mathcal {F} and \{n \mid \neg \phi (x_n)\} \notin \mathcal {F}.

Do observe however that here the "or" is being interpreted _externally_, but the "not" is being interpreted _internally_.

We will use the following characterization of \operatorname {JSD}(p,q): Let B be a "fair coinflip", i.e a random variable which is 0 with probability 1/2 and 1 otherwise. Let X be a random variable which is distributed according to p if B=0 and q if B=1. Then the mutual information of X and B is exactly the Jensen-Shannon divergence of p and q

We want to show that d(fg_0,fg_1) \leq d(g_0,g_1). Clearly we may as well square both sides, so that we're trying to show that

It suffices to show that this inequality holds for each x, so let an x be given. Then \operatorname {JSD}(g_0(x),g_1(x)) is the mutual information between a fair coin B and a variable Y distributed according to g_B(x). and \operatorname {JSD}(fg_1(x),fg_2(x)) is the mutual information between B and a variable distributed as f(Y). But "postprocessing" by f can't possible put more information about B into the random variable, since it depends on Z only through B. Hence we have the desired inequality.

We want to show d(g_0f,g_1f) \leq d(g_0,g_1) Again it suffices to show

It's enough to show this for each specific x, so let's assume wlog that X=\ast and f is simply a distribution, and we're showing

To see this, let Y be distributed according to f, let B be an unbiased coin, and let Z be distributed according to g_B(Y). Then \operatorname {JSD}(g_0f,g_1f) is I(Z;B), and \operatorname {JSD}(g_0(y),g_1(y)) is I(Z;B | Y = y).

Our claim is that I(Z;B) \leq I(Z;B | Y=y) for at least one y. We insert the entropy formula for mutual information:

Since B,Y independent, H(B|Y=y) = H(B) (equals one bit), so we may rearrange this as H(B|Z,Y=y) \leq H(B|Z) Now that the expected value E_y[H(B|Z,Y=y)] is precisely H(B|Z,Y) by definition. By a standard inequality H(B|Z,Y) \leq H(B|Z). Hence we also have the inequality H(B|Z,Y=y) for at least one y, as desired.

1. Is there a way to build something like this "canonically" - the way entropy is characterized by a set of axioms in A characterization of Entropy in Terms of Information Loss? 2. How does this relate to other metrics on probability, i.e the description from A probability monad as the colimit of spaces of finite samples

Recall that a point of a topos \mathcal {E} is a geometric morphism from the topos Set. My preferred way to think about this is to consider the sheaf topos Sh(X) on some (sober) topological space X. Then given x \in X and a sheaf S, we can form the stalk at x

S_x := \operatorname {colim}_{x \in U \subseteq X \text { open}} S(U)

1. This determines the point uniquely, i.e if (-)_x \simeq (-)_y then x = y 2. This is a left exact left adjoint Sh(X) \to Set - i.e part of a geometric morphism Set \to Sh(X). 3. All left exact left adjoints Sh(X) \to Set have this form.

Hence it makes sense to identify literal points of X with points of Sh(X) in the above sense.

We can think of a probability measure on a space X as a sort of "generalized point", which has been "smeared out". How can we lift this intuition to the level of Sh(X)? It seems sort of obvious that we shouldn't expect this to work on the level of sets - they are somehow too "discrete" to capture quantitative information about probabilities. It's actually worth mentioning here that any point of Sh(X) is determined by its action on sheaves represented by open sets, which must each be sent to either \emptyset or * (this follows from the "left exact left adjoint" assumptions). The fact that it's a left exact left adjoint furthermore implies that it must be a sort of infinitely-additive \{0,1\}-valued probability measure defined on the open sets, and it follows from this that it's a "dirac measure". This is how to prove that all points are really represented by a point. It seems that one way of considering "random points" would be to let the functor take values in a category with objects that can reasonably represent more complicated probability measures. It also seems unlikely that we can rely completely on universal properties to carry the day here. If U, V \subset X are open sets, then U \cap V is their product, both in O(X) and in Sh(X). So if a functor P: Sh(X) \to C preserves products, P(U \cap V) depends only on P(U) and P(V) - so this clearly can't capture all possible probability measures.

I haven't solved this problem completely (I'm not convinced a good general solution exists). One approach is to think about _integration of metric spaces over a measure_, which I will now explain. A _sheaf of metric spaces_ is a functor O(X)^{op} \to Met, where Met is the category of metric spaces and _short_, i.e distance-nonincreasing, maps, which satisfies the sheaf axiom. We denote the category of such sheaves by Sh(X,Met). By "the sheaf axiom", I mean it preserves limits. Since Met does not have all limits, this is a bit subtler than it may appear. However, since Met does have finite limits, this difficulty disappears if we assume X is compact.

Let M be a sheaf of metric spaces and let P be a Radon probability measure on X. Then we define M_X to be the product \prod _{x \in X}M_x of all the stalks (just considered as a set). Equip M_X with a pseudometric d by setting d(a,b) = \int d(a_x,b_x)P(dx). In other words, we _integrate_ the distances according to the given probability measure. If we quotient out with the relation a \sim b if d(a,b) = 0, this gives a proper metric space, M_X/\sim .

Now for each U \subset X with P(U) = 1, we consider the map M(U) \to M_X/\sim given by taking all the germs. We let M_P be the metric space consisting of the images of all these maps.

This defines a functor Sh(X,Met) \to Met. We can recover the probability measure on an open set A by considering a sheaf M given by two points at distance 1 if U \subset A and the singleton otherwise. Then M_P consists of two points at distance P(A). At least in the case of compact Hausdorff spaces, this determines the underlying measure uniquely. (In general, the "measure defined on open sets" that we recover in this way is called a valuation, and you can argue that we shouldn't expect to tell the difference between different measures with the same valuation).

- What useful properties characterize functors of the above form? - Is there a good way of doing this for \sigma -algebras instead of topologies? - Is there a good way of doing this for a general topos?

Let M be any metric space. Then we can form a sheaf of metric spaces where M(U) is the set of continuous functions U \to M in the sup metric. Then the metric space M_P is the set of M-valued random variables, metrized by letting d(A,B) := \mathbb {E}_P(d(A,B)) - i.e metrized by _expected_ distance.

Recall that first-order logic works with statements built up out of the logical connectives \wedge , \vee , \neg , \Rightarrow \bot , \top , \forall , \exists , =. The language of _fields_ augments these symbols with +, -, \cdot , 1, 0 (it's really just the language of commutative rings - being a field just means that additional axioms hold).

A statement in the first-order language of fields could be something like this:

\forall a,b: \neg (a = 0) \Rightarrow \exists x: a\cdot x + b = 0

This statement says that all nonconstant linear polynomials have a solution, which is true.

We could also write down a statement like \forall a, b, c, d, e: \neg (a = 0) \Rightarrow \exists x: a x^4 + bx^3 + cx^2 + dx + e = 0

This says that all fourth-order polynomials have a root, which is not always true, but true sometimes, like in \mathbb {C}.

Similarly, we can form a statement R_n for all n \in \mathbb {N}, saying that all nth order polynomials have a root. Note that the conjunction of all these statements is _not_ a first-order statement in itself - we can't take conjuctions of infinitely many statements, and there's no way to quantify over all polynomials in the theory of fields.

Similarly, we can form statements like 1+1 \neq 0. This is also true in \mathbb {C}, but fails in fields of characteristic 2. We can form statements C_n for all n, saying that n \neq 0 - that the field does not have characteristic n.

The _theory of algebraically closed fields of characteristic zero_ is the theory consisting of the axioms of a field augmented with the statements C_n and R_n for all n. A model of this theory is precisely an algebraically closed field of characteristic zero (hence the name).

Now here is a highly nontrivial fact about this theory: it is _complete_. This means that _any statement expressible in the first-order language of fields is either provable or disprovable in it_. This means that, from the perspective of first-order logic, there are really no differences between fields of this type - even though there are of course many different such fields, they have the same first-order properties.

We want to phrase the Ax-Grothendieck theorem as a first-order statement. It turns out this isn't quite possible, because we can't quantify over "all degree d polynomials" or "all n \in \mathbb {N}". Therefore we instead formulate the statement P(n,d): "Any polynomial function f : \mathbb {C}^n \to \mathbb {C}^n of degree at most d is surjective if it's injective". Then the Ax-Grothendieck statement says that P(n,d) holds for all n \geq 1, d \geq 0 (By the way: by "polynomial \mathbb {C}^n \to \mathbb {C}^n", I mean a function where each coordinate is an n-variable polynomial)

How does P(n,d) look as a first-order formula? It's quite complicated - mostly because a degree d polynomial like f involves a large number of coefficients. The main point is that there is a _definite_ number of coefficients, once n and d is fixed, and so we can write "for all choices of coefficients for f..." in first-order logic. For instance, if d = 2, n=1, this looks like \forall a_{11},a_{12},a_{21},a_{22},b_1,b_2 \dots Here a_{12} is the coefficient for x_1 in the second coordinate polynomial of f, and so on.

Now of course we can also make sense of injectivity: it's just the statement f(x_1,\dots x_n) = f(x'_1, \dots x'_n) \Rightarrow x_1=x'_1 \wedge \dots \wedge x_n = x'_n - where the equality on the left of the implication is shorthand for a complicated expression involving the coefficients of f.

And we can make sense of surjectivity: it just means \forall y_1 \dots y_n, \exists x_1, \dots x_n: f(x_1, \dots x_n) = (y_1, \dots y_n) Hence we have all the ingredients to make sense of P(n,d).

We now have most of the ingredients to fill out the proof above. Since Ax-grothendieck is a (family of) first-order statements, if it fails, there is a disproof in the first-order theory of algebraically closed characteristic zero fields. To be specific, if Ax-Grothendieck is false, then P(n,d) is false for some specific n,d, and hence there is a disproof of that statement, i.e a proof of \neg P(n,d).

Observe that such a proof is finite. Hence it can use at most finitely many of the statements C_n. Hence for p large enough (larger than any n where C_n is used in the proof), Ax-Grothendieck fails for algebraically closed fields of characteristic p - like the algebraic closure of \mathbb {F}_p. (How do we know it fails? We have a proof that it fails!) Hence there exists some polynomial function f: \overline {\mathbb {F}_p}^n \to \overline {\mathbb {F}_p}^n which is injective and not surjective. But now we can take the algebraic extension of F_p by all the coefficientsof f and the coordinates of a point y \in \overline {\mathbb {F}_p}^n which is not in the image. Call this extension L. Then f: L^n \to L^n is a well-defined injective polynomial which is not surjective. And since L is a finite extension of a finite field, it's finite. But then we clearly have a contradiction: injective fuctions between finite sets of the same cardinality are bijections, just by counting.

This concludes the proof.

Given a finite subset X of a metric space Z, which we think of as a _data set_, we consider the collection P_s(X) of subsets \sigma \subset X where d(x,y) \leq s for all x,y \in \sigma . We can order this by inclusion - it is exactly the poset of simplices in the Vietoris-Rips Complex V_s(X).

Now we want to work with this combinatorial data as if it were topological data. This is generally easiest if we're working with a simplicial set. We can make this into a simplicial set by choosing an ordering on X, but this is non-canonical. We can also consider the nerve B(P_s(X)), but this is somewhat clunky - the resulting simplicial structure is really the _subdivision_ of the complex V_s(X). (B for the nerve of a category - a simplicial set - it somewhat unusual notation, but I've stuck with Jardine's choice of notation.)

Define the Hausdorff Distance on finite subsets X,Y \subset Z of a metric space as follows: d_H(X,Y) < r if and only if for all x there exists y with d(x,y) < r, and vice versa.

Then a situation of interest is if we have two data sets with "small" Hausdorff distance - in this case, the datasets seem to reflect mostly the same underlying topology, so we'd like our methods to give mostly the same results.

What sort of relation do we have between P_s(X) and P_s(Y)? For simplicity let's work with the case where X \subset Y. Then we have an inclusion i: P_s(X) \to P_s(Y), and we can ask in what sense this is "equivalence-like". We can try to cook up an inverse by picking a nearest point \theta (y) \in X for each y \in Y. By assumption d(y,\theta (y)) < r. This means we can build a diagram

The top square commutes - in other words, i almost has a retract, except we have to add an extra error of up to 2r. The bottom square doesn't commute - after all, \theta does really move around some points. But it doesn't move around points too much - the set \sigma (t) \cup i(\theta (t)) is still in P_{s+2r}(Y), i.e: the altered points and the original points are all within 2r of each other. The pair of inclusions \sigma (t) \hookrightarrow \sigma (t) \cup i(\theta (t)) \hookleftarrow i(\theta (t)) present a _homotopy_ between i\theta and \sigma , so the bottom square commutes up to homotopy. In other words, i and \theta form a sort of "approximate deformation retract".

In this section we encounter some interesting homotopy theory-ish things. We consider the category of functors [ 0,\infty ) \to sSet (or other categories). We can equip this with the _projective model structure_, meaning a map is a weak equivalence or a fibration iff it is so sectionwise. This means the fibrant objects are exactly the functors that land in Kan complexes, and the cofibrant objects are precisely those that land in monomorphisms (this is a theorem).

Now the interesting thing we can do is consider various notions of "r-isomorphism". The basic motivation for this is that, if X \subset Y and d_H(X,Y) < r/2, we get a diagram like this

where the top triangle commutes, and the bottom commutes up to a homotopy fixing NP_s(X) - an "r-interleaving"

This tells us that the maps \pi _n(BP_s(X)) \to \pi _n(BP_{s}(Y)) is "almost an isomorphism":

- We can find a preimage for any element in \pi _n(BP_s(Y)), as long as we're willing to increase the allowed error by r. - If two elements in \pi _n(BP_s(X)) agree in \pi _n(BP_s(Y)), they also agree in \pi _n(BP_{s+r}(X))

Let's call something like this an r-isomorphism.

We can then ask in general for an r-equivalence, which gives an r-isomorphism on the (filtered) homotopy groups. These maps have various good properties

- They are stable under composition with weak equivalences - They're not quite stable under composition, rather when composing an r-equivalence and an s-equivalence, you get an r+s-equivalence. - They satisfy a similarly modified version of the 2 out of 3 condition. - A pullback of an r-equivalence which is a fibration is a 2r-equivalence (and a fibration). - If a map is an r-equivalence and a sectionwise cofibration (not the same as a cofibration in the projective model structure!), it admits a 2r-interleaving, in the sense of the diagram above.

This gives a sort of bizzarro model structure/homotopy theory for r-equivalences. In this world, an r-interleaving is a bit like a deformation retract.

Probability theory is about how to manage incomplete information. One way to interpret a statement like "the probability of event X is p" is in terms of betting odds - you think the probability of X is p if you value a lottery ticket that pays out $1 if X happens at p dollars. From this interpretation, all the laws of probability theory (except arguably those involving infinite conjunctions of events) follow, if we add the requirement that your valuation is "inexploitable" - in other words, if we require that no smart bookie can get you to make a series of bets that always loses money.

The big issue with probability theory as a model of how to reason under uncertain information is that it doesn't account for agents with _limited processing power_ (i.e all of them). A way to think about this problem is that, realistically, the best you can possible hope for is to not be outsmarted by bookies without too much more computing power than you. For example, what is the probability that among the first 10^{10^10} digits of \pi , there are more even than odd ones? If a mortal human is forced to assign this event a probability, we must choose more or less blindly - a bookie with an arbitrarily powerful computer could then win lots of money off us by calculating a lot of inaccessible digits of \pi and betting us for their parity.

This approach to "computationally bounded probability theory" is explored in the paper Logical Induction. Based on the idea about "computationally limited bookies", they build a notion of "logical inductor" - a process which assigns gradually updating probabilities to logical statements, and which is "optimal" in the sense that it can't be exploited.

In some sense, the problem solved by logical induction is that ordinary logic is _too expressive_. It can express statements which are hard to verify in a small amount of space. Interestingly, there are versions of logic that get around this limitation in various ways. Light Affine Set Theory is a version of set theory with the following interesting property: the provably total functions are precisely those with a polynomial-time algorithm. This means that the function which determines the most common parity among the first 10^{10^n} digits of \pi is _not provably total_ (assuming of course that there is no efficient algorithm for this). Of course, this sort of logic is by necessity much more restricted than normal logic. We can think about this as a sort of ultrafinitism - numbers like 10^{10^n} are "too big to exist".

What is the unifying thread here? I'm not sure. I want to say something like "you can't prove in LAST that a logical inductor is inconsistent". This is not quite meaningful - a logical inductor is a _sequence_ of probability assignments (as they have more time to calculate, they update their probabilities), and each step along the sequence will generally contain plenty of specific verifiable mistakes. But there's an idea that I'm trying to grasp at, that the inconsistency of a logical inductor "takes superpolynomial resources to detect", and hence it "is" a probability measure from the point of view of a polynomial logic. Or perhaps we should say that it "isn't not a probability measure", in the sense of constructive logic. That is, we can't verify that it's a probability measure, but we can't construct a counterexample either.

This is a post about my paper The zero-one laws of Kolmogorov and Hewitt-Savage in categorical probability, joint with Tobias Fritz. This is a "companion piece" where I try to explain those ideas in a more understandable language. There are essentially three ideas in this paper:

- "Markov categories for synthetic probability theory" - this is only treated briefly, since this is just the background that we're building on top of. Tobias has a long paper on this, A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. - "Kolmogorov products" - a take on tensor products of infinitely many objects. These are introduced into the framework to handle probabilistic systems with infinitely many variables. - "Zero-One Laws". These are theorems from probability theory of the form "If an event A satisfies ..., then P(A) \in 0,1" - i.e either it always happens or it never happens. For two classical ones, Kolmogorov's and Hewitt-Savage's, we give a way of phrasing them in the categorical language and prove them.

In this post, I'll try to give an accessible take on these ideas. I'll assume some familiarity with category theory, and a _very_ small amount of familiarity with probability theory

Most theorems in probability theory involve infinite families of variables. To make sense of that in our framework, we need to make sense of "distributions on infinite product spaces", which means we need a notion of "infinite tensor product". The definition goes like this: Let \{X_j\}_{j \in J} be a collection of objects in a markov category \mathsf {C}. For each finite subset F \subset J, we can make sense of the tensor product \bigotimes _{j \in F} X_j[^fn:3]. Since the tensor unit is terminal, we have natural maps \bigotimes _{J \in F'} X_j \to \bigotimes _{j \in F} X_j for each inclusion of finite sets F \subset F'. Then we can ask for a cofiltered limit of this system:

This is a reasonable definition of "infinite tensor product", which we can denote \bigotimes _{j \in J} X_j However, it turns out we need one more condition. The issue is that in a Markov category, having an object defined up to isomorphism is not always good enough - we want it up to _deterministic isomorphism_, so that the comonoid structure is determined as well. The natural condition to add to make sure we pick the "right" limit is that each of the projections \bigotimes _{j \in J} X_j \to \bigotimes _{j \in F} X_j, for each finite subset, is deterministic. Such an infinite tensor product, we called a _Kolmogorov product_.

With this setup, it turns out it's very easy to prove an abstract version of Kolmogorov's Zero-One Law. Informally, the content of the law is this: suppose you have a family (X_n) of independent random variables, and some event A which is determined by these variables, but is independent of any finite subset of them. Then P(A) \in \{0,1\}

Here is our abstract version: Let (X_j)_{j \in J} be objects so that the Kolmogorov product \bigotimes _{j \in K} exists. Let p: A \to \bigotimes _{j \in J} X_j be a map, and s : \bigotimes _{j \in J} X_j \to T be a deterministic map. Suppose p displays the conditional independence of the X_j given A, and that for every finite F \subset J, the joint distribution

displays the independence of X_F and T given A. (Here X_F = \bigotimes _{j \in F} X_j). Then the composite sp : A \to T is deterministic.

I will sketch the proof (see the paper for details). Essentially, we first prove that T is independent of all the X_j, not just the finite subsets. To see this, we note that the definition of independence is comparing two maps into T \otimes \bigotimes _{j\in J} X_j. This is a limit, so it's enough to show that all the component maps, which are the maps for finite F \subset J, agree - this is true by definition. Now it follows by a string diagram manipulation that sp satisfies the definition of determinism:

This concludes the proof.

To recover the classical Kolmogorov 0-1 law, we must do a little bit of technical work. We work in the Markov category \mathsf {BorelStoch} of _standard Borel spaces_. This Markov category has countable Kolmogorov products[^fn:4]. We let A = * and let our X_j be the _spaces_ that the variables X_j from the theorem take values in. We let the map p give the joint distribution of the variables. We let T = \{0,1\}, and we let s be the indicator for the event. Then the theorem says that the composite sp is deterministic. So the probability that sp is 1, which is the probability that the event happens, is either zero or one.

[^fn:1]: Euclid actually did try to define notions like lines, points, etc, but we're gonna use his name anyways [^fn:2]: Note that we're not assuming all maps, or even all isomorphisms, are homomorphic. This makes Markov categories an evil notion [^fn:3]: I am handwaving some non-issues with regards to non-strictness here [^fn:4]: It turns out that proving this is significantly harder than proving the abstract theorem, once you have the setup

I give a very short introduction to the idea of "causality" in statistics, then talk about two ways to infer causal structure for two variables - i.e, without using conditional independence statements. The ideas here are mostly taken from Peters, Janzing, and Schölkopf: Elements of causal inference: foundations and learning algorithms.

A "causal statistical model" is something like this:

Or this

Where a classical statistical model tells you what the probability of various outcomes are, (which you can then use to derive conditional probabilities, etc), a causal model gives you more information - it tells you how the distribution changes when the system is intervened on. For instance, in the first model above, intervening on X has no effect on the distribution of Z, whereas in the latter, the distribution of Z after the intervention X := x_0 is exactly the conditional distribution P(Z=z|X=x_0).

We can actually distinguish between the two causal structures above without doing interventional experiments. This is because in the first model, X and Z are independent, but don't (necessarily) remain independent after conditioning on Y. For instance, if Y = X+Z, learning that Y has a certain value tells us exactly how to compute X and Z from each other. On the other hand, in the second model, X and Z are not (necessarily) independent, but after conditioning on Y, they _are_. That's because the dependency of Z on X only "goes through" Y, so if we already know what Y is, learning about X tells us nothing about Z.

Why are X and Z independent in the first model? This is because of a basic principle of causal modeling, which we can paraphrase as "all (conditional or unconditional) dependencies between variables must be explained by causal structure". (Formally, the distribution has the _markov property_ with respect to the graph).