Hedonistic Learning

Introduction

Classical First-Order Logic (Classical FOL) has an absolutely central place in traditional logic, model theory, and set theory. It is the foundation upon which ZF(C), which is itself often taken as the foundation of mathematics, is built. When classical FOL was being established there was a lot of study and debate around alternative options. There are a variety of philosophical and metatheoretic reasons supporting classical FOL as The Right Choice.

This all happened, however, well before category theory was even a twinkle in Mac Lane’s and Eilenberg’s eyes, and when type theory was taking its first stumbling steps.

My focus in this article is on what classical FOL looks like to a modern categorical logician. This can be neatly summarized as “classical FOL is the internal logic of a Boolean First-Order Hyperdoctrine.” Each of the three words in this term, “Boolean”, “First-Order”, and “Hyperdoctrine”, suggest a distinct axis in which to vary the (class of categorical models of the) logic. All of them have compelling categorical motivations to be varied.

Read more...

Introduction

In 1983, Mark Overmars described global rebuilding in The Design of Dynamic Data Structures. The problem it was aimed at solving was turning the amortized time complexity bounds of batched rebuilding into worst-case bounds. In batched rebuilding we perform a series of updates to a data structure which may cause the performance of operations to degrade, but occasionally we expensively rebuild the data structure back into an optimal arrangement. If the updates don’t degrade performance too much before we rebuild, then we can achieve our target time complexity bounds in an amortized sense. An update that doesn’t degrade performance too much is called a weak update.

Taking an example from Okasaki’s Purely Functional Data Structures, we can consider a binary search tree where deletions occur by simply marking the deleted nodes as deleted. Then, once about half the tree is marked as deleted, we rebuild the tree into a balanced binary search tree and clean out the nodes marked as deleted at that time. In this case, the deletions count as weak updates because leaving the deleted nodes in the tree even when it corresponds to up to half the tree can only mildly impact the time complexity of other operations. Specifically, assuming the tree was balanced at the start, then deleting half the nodes could only reduce the tree’s depth by about 1. On the other hand, naive inserts are not weak updates as they can quickly increase the tree’s depth.

The idea of global rebuilding is relatively straightforward, though how you would actually realize it in any particular example is not. The overall idea is simply that instead of waiting until the last moment and then rebuilding the data structure all at once, we’ll start the rebuild sooner and work at it incrementally as we perform other operations. If we update the new version faster than we update the original version, we’ll finish it by the time we would have wanted to perform a batched rebuild, and we can just switch to this new version.

More concretely, though still quite vaguely, global rebuilding involves, when a threshold is reached, rebuilding by creating a new “empty” version of the data structure called the shadow copy. The original version is the working copy. Work on rebuilding happens incrementally as operations are performed on the data structure. During this period, we service queries from the working copy and continue to update it as usual. Each update needs to make more progress on building the shadow copy than it worsens the working copy. For example, an insert should insert more nodes into the shadow copy than the working copy. Once the shadow copy is built, we may still have more work to do to incorporate changes that occurred after we started the rebuild. To this end, we can maintain a queue of update operations performed on the working copy since the start of a rebuild, and then apply these updates, also incrementally, to the shadow copy. Again, we need to apply the updates from the queue at a fast enough rate so that we will eventually catch up. Of course, all of this needs to happen fast enough so that 1) the working copy doesn’t get too degraded before the shadow copy is ready, and 2) we don’t end up needing to rebuild the shadow copy before it’s ready to do any work.

Read more...

Introduction

Morleyization is a fairly important operation in categorical logic for which it is hard to find readily accessible references to a statement and proof. Most refer to D1.5.13 of “Sketches of an Elephant” which is not an accessible text. 3.2.8 of “Accessible Categories” by Makkai and Paré is another reference, and “Accessible Categories” is more accessible but still a big ask for just a single theorem.

Here I reproduce the statement and proof from “Accessible Categories” albeit with some notational and conceptual adaptations as well as some commentary. This assumes some basic familiarity with the ideas and notions of traditional model theory, e.g. what structures, models, and $$ are.

Read more...

Introduction

Andrej Bauer has a paper titled The pullback lemma in gory detail that goes over the proof of the pullback lemma in full detail. This is a basic result of category theory and most introductions leave it as an exercise. It is a good exercise, and you should prove it yourself before reading this article or Andrej Bauer’s.

Andrej Bauer’s proof is what most introductions are expecting you to produce. I very much like the representability perspective on category theory and like to see what proofs look like using this perspective.

So this is a proof of the pullback lemma from the perspective of representability.

Preliminaries

The key thing we need here is a characterization of pullbacks in terms of representability. To just jump to the end, we have for $$ and $$, $$ is the pullback of $$ and $$ if and only if it represents the functor $$

That is to say we have the natural isomorphism $$

We’ll write the left to right direction of the isomorphism as $$ where $$ and $$ and they satisfy $$. Applying the isomorphism right to left on the identity arrow gives us two arrows $$ and $$ satisfying $$ and $$. (Exercise: Show that this follows from being a natural isomorphism.)

One nice thing about representability is that it reduces categorical reasoning to set-theoretic reasoning that you are probably already used to, as we’ll see. You can connect this definition to a typical universal property based definition used in Andrej Bauer’s article. Here we’re taking it as the definition of the pullback.

Proof

The claim to be proven is if the right square in the below diagram is a pullback square, then the left square is a pullback square if and only if the whole rectangle is a pullback square. $$

Rewriting the diagram as equations, we have:

Theorem: If $$, $$, and $$ is a pullback of $$ and $$, then $$ is a pullback of $$ and $$ if and only if $$ is a pullback of $$ and $$.

Proof: If $$ was a pullback of $$ and $$ then we’d have the following.

The second isomorphism is $$ being a pullback and $$ is an arrow into $$ so it’s necessarily of the form $$. The first equality is just $$ mentioned earlier. The second equality merely eliminates the use of $$ using the equation $$.

This overall natural isomorphism, however, is exactly what it means for $$ to be a pullback of $$ and $$. We verify the projections are what we expect by pushing $$ through the isomorphism. By assumption, $$ and $$ will be $$ and $$ respectively in the first isomorphism. We see that $$.

We simply run the isomorphism backwards to get the other direction of the if and only if. $$

The simplicity and compactness of this proof demonstrates why I like representability.

Introduction

It is not uncommon for universal quantification to be described as (potentially) infinite conjunction¹. Quoting Wikipedia’s Quantifier_(logic) page (my emphasis):

For a finite domain of discourse $$, the universal quantifier is equivalent to a logical conjunction of propositions with singular terms $$ (having the form $$ for monadic predicates).

The existential quantifier is equivalent to a logical disjunction of propositions having the same structure as before. For infinite domains of discourse, the equivalences are similar.

While there’s a small grain of truth to this, I think it is wrong and/or misleading far more often than it’s useful or correct. Indeed, it takes a bit of effort to even get a statement that makes sense at all. There’s a bit of conflation between syntax and semantics that’s required to have it naively make sense, unless you’re working (quite unusually) in an infinitary logic where it is typically outright false.

What harm does this confusion do? The most obvious harm is that this view does not generalize to non-classical logics. I’ll focus on constructive logics, in particular. Besides causing problems in these contexts, which maybe you think you don’t care about, it betrays a significant gap in understanding of what universal quantification actually is. Even in purely classical contexts, this confusion often manifests, e.g., in confusion about $$-inconsistency.

So what is the difference between universal quantification and infinite conjunction? Well, the most obvious difference is that infinite conjunction is indexed by some (meta-theoretic) set that doesn’t have anything to do with the domain the universal quantifier quantifies over. However, even if these sets happened to coincide² there are still differences between universal quantification and infinite conjunction. The key is that universal quantification requires the predicate being quantified over to hold uniformly, while infinite conjunction does not. It just so happens that for the standard set-theoretic semantics of classical first-order logic this “uniformity” constraint is degenerate. However, even for classical first-order logic, this notion of uniformity will be relevant.

Read more...

Introduction

The purpose of this article is to answer the question: what is the coproduct of two groups? The approach, however, will be somewhat absurd. Instead of simply presenting a construction and proving that it satisfies the appropriate universal property, I want to find the general answer and simply instantiate it for the case of groups.

Specifically, this will be a path through the theory of Lawvere theories and their models with the goal of motivating some of the theory around it in pursuit of the answer to this relatively simple question.

If you really just want to know the answer to the title question, then the construction is usually called the free product and is described on the linked Wikipedia page.

Read more...

Introduction

This is a brief article about the notions of preserving, reflecting, and creating limits and, by duality, colimits. Preservation is relatively intuitive, but the distinction between reflection and creation is subtle.

Preservation of Limits

A functor, $$, preserves limits when it takes limiting cones to limiting cones. As often happens in category theory texts, the notation focuses on the objects. You’ll often see things like $$, but implied is that one direction of this isomorphism is the canonical morphism $$. To put it yet another way, in this example we require $$ to satisfy the universal property of a product with the projections $$ and $$.

Other than that subtlety, preservation is fairly intuitive.

Reflection of Limits versus Creation of Limits

A functor, $$, reflects limits when whenever the image of a cone is a limiting cone, then the original cone was a limiting cone. For products this would mean that if we had a wedge $$, and $$ was the product of $$ and $$ with projections $$ and $$, then $$ was the product of $$ and $$ with projections $$ and $$.

A functor, $$, creates limits when whenever the image of a diagram has a limit, then the diagram itself has a limit and $$ preserves the limiting cones. For products this would mean if $$ and $$ had a product, $$, then $$ and $$ have a product and $$ via the canonical morphism.

Creation of limits implies reflection of limits since we can just ignore the apex of the cone. While creation is more powerful, often reflection is enough in practice as we usually have a candidate limit, i.e. a cone. Again, this is often not made too explicit.

Example

Consider the posets:

Failure of reflection

Let $$ with $$ and $$ mapping to $$ where $$. Reflection fails because $$ maps to a meet but is not itself a meet.

Failure of creation

If we change the source to just $$, then creation fails because $$ and $$ have a meet in the image but not in the source. Reflection succeeds, though, because there are no non-trivial cones in the source, so every cone (trivially) gets mapped to a limit cone. It’s just that we don’t have any cones with both $$ and $$ in them.

In general, recasting reflection and creation of limits for posets gives us: Let $$ be a monotonic function. $$ reflects limits if every lower bound that $$ maps to a meet is already a meet. $$ creates limits if whenever $$ has a meet for $$, then $$ already had a meet and $$ sends the meet of $$ to the meet of $$.

tl;dr The notion of two sets overlapping is very common. Often it is expressed via $$. Constructively, this is not the best definition as it does not imply $$. Even classically, this second-class treatment of overlapping obscures important and useful connections. In particular, writing $$ for “$$ overlaps $$”, we have a De Morgan-like duality situation with $$ being dual to $$. Recognizing and exploiting this duality, in part by using more appropriate notation for “overlaps”, can lead to new concepts and connections.

Introduction

The most common way I’ve seen the statement “$$ overlaps $$” formalized is $$. To a constructivist, this definition isn’t very satisfying. In particular, this definition of overlaps does not allow us to constructively conclude that there exists an element contained in both $$ and $$. That is, $$ does not imply $$ constructively.

As is usually the case, even if you are not philosophically a constructivist, taking a constructivist perspective can often lead to better definitions and easier to see connections. In this case, constructivism suggests the more positive statement $$ be the definition of “overlaps”. However, given that we now have two (constructively) non-equivalent definitions, it is better to introduce notation to abstract from the particular definition. In many cases, it makes sense to have a primitive notion of “overlaps”. Here I will use the notation $$ which is the most common option I’ve seen.

Properties

We can more compactly write the quantifier-based definition as $$ using a common set-theoretic abbreviation. This presentation suggests a perhaps surprising connection. If we swap the quantifier, we get $$ which is commonly abbreviated $$. This leads to a duality between $$ and $$, particularly in topological contexts. In particular, if we pick a containing set $$, then $$ where the complement is relative to $$, and $$ is assumed to be a subset of $$. This is a De Morgan-like duality.

If we want to characterize these operations via an adjunction, or, more precisely, a Galois connection, we have a slight awkwardness arising from $$ and $$ being binary predicates on sets. So, as a first step we’ll identify sets with predicates via, for a set $$, $$. In terms of predicates, the adjunctions we want are just a special case of the adjunctions characterizing the quantifiers.

What we actually want is a formula of the form $$. To do this, we need an operation that will allow us to produce a set from a predicate. This is exactly what set comprehension does. For reasons that will become increasingly clear, we’ll assume that $$ and $$ are subsets of a set $$. We will then consider quantification relative to $$. The result we get is:

The first and last equivalences require additionally assuming $$. The last equivalence requires classical reasoning. You can already see motivation to limit to subsets of $$ here. First, set complementation, the $$, only makes sense relative to some containing set. Next, if we choose $$, then the latter formulas state that no matter what $$ is it should be a subset of the expression that follows it. Without constraining to subsets of $$, this would require a universal set which doesn’t exist in typical set theories.

Choosing $$ as $$, $$ as $$, and $$ as $$ leads to the familiar $$, i.e. $$ is a subset of $$ if and only if it doesn’t overlap $$’s complement.

Incidentally, characterizing $$ and $$ in terms of Galois connections, i.e. adjunctions, immediately gives us some properties for free via continuity. We have $$ and $$. This is relative to a containing set $$, so $$, and $$ and each $$ are assumed to be subsets of $$.

Categorical Perspective

Below I’ll perform a categorical analysis of the situation. I’ll mostly be using categorical notation and perspectives to manipulate normal sets. That said, almost all of what I say will be able to be generalized immediately just by reinterpreting the symbols.

To make things a bit cleaner in the future, and to make it easier to apply these ideas beyond sets, I’ll introduce the concept of a Heyting algebra. A Heyting algebra is a partially ordered set $$ satisfying the following:

1. $$ has two elements called $$ and $$ satisfying for all $$ in $$, $$.
2. We have operations $$ and $$ satisfying for all $$, $$, $$ in $$, $$ if and only $$ and $$, and similarly for $$, $$ if and only $$ and $$.
3. We have an operation $$ satisfying for all $$, $$, and $$ in $$, $$ if and only if $$.

For those familiar with category theory, you might recognize this as simply the decategorification of the notion of a bicartesian closed category. We can define the pseudo-complement, $$.

Any Boolean algebra is an example of a Heyting algebra where we can define $$ via $$ where here $$ is taken as primitive. In particular, subsets of a given set ordered by inclusion form a Boolean algebra, and thus a Heyting algebra. The $$ operation can also be characterized by $$. This lets us immediately see that for subsets of $$, $$. All this can be generalized to the subobjects in any Heyting category.

As the notation suggests, intuitionistic logic (and thus classical logic) is another example of a Heyting algebra.

We’ll write $$ for the partially ordered set of subsets of $$ ordered by inclusion. As mentioned above, this is (classically) a Boolean algebra and thus a Heyting algebra. Any function $$ gives a monotonic function $$. Note the swap. $$. (Alternatively, if we think of subsets in terms of characteristic functions, $$.) Earlier, we needed a way to turn predicates into sets. In this case, we’ll go the other way and identify truth values with subsets of $$ where $$ stands for an arbitrary singleton set. That is, $$ is the poset of truth values. $$ being the terminal object of $$ induces the (unique) function $$ for any set $$. This leads to the important monotonic function $$. This can be described as $$. Note, $$ cannot contain $$ as a free variable. In particular $$ and $$. This monotonic function has left and right adjoints:

$$ for monotonic functions $$ and $$ means $$.

$$ and $$. It’s easily verified that each of these functions are monotonic.¹

It seems like we should be done. These formulas are the formulas I originally gave for $$ and $$ in terms of quantifiers. The problem here is that these functions are only defined for subsets of $$. This is especially bad for interpreting $$ as $$ as it excludes most of the interesting cases where $$ partially overlaps $$. What we need is a way to extend $$ / $$ beyond subsets of $$. That is, we need a suitable monotonic function $$.

Assume $$ and that we have an inclusion $$. Then $$ and $$. This will indeed allow us to define $$ and $$ as $$ and $$. We have:

Here, $$ is the direct image of $$. This doesn’t really do anything in this case except witness that if $$ then $$ because $$.²

We can recover the earlier adjunctions by simply using these two pairs of adjunctions. $$

Here the $$ is crucial so that we use the $$ of $$ and not $$.

In this case, the $$ is truly doing nothing because $$ is the same as $$.

While we have $$, we see that the inclusion of $$ is what breaks the direct connection between $$ and $$.

Examples

As a first example, write $$ for the interior of $$ and $$ for the closure of $$ each with respect to some topology on a containing set $$. One way to define $$ is $$ if and only if there exists an open set containing $$ that’s a subset of $$. Writing $$ for the set of open sets, we can express this definition in symbols: $$ We have a “dual” notion: $$ That is, $$ is in the closure of $$ if and only if every open set containing $$ overlaps $$.

As another example, here is a fairly unusual way of characterizing a compact subset $$. $$ is compact if and only if $$ is open in $$ equipped with the Scott topology³. As before, this suggests a “dual” notion characterized by $$ being an open subset. A set $$ satisfying this is called overt. This concept is never mentioned in traditional presentations of point-set topology because every subset is overt. However, if we don’t require that arbitrary unions of open sets are open (and only require finite unions to be open) as happens in synthetic topology or if we aren’t working in a classical context then overtness becomes a meaningful concept.

One benefit of the intersection-based definition of overlaps is that it is straightforward to generalize to many sets overlapping, namely $$. This is also readily expressible using quantifiers as: $$. As before, having an explicit “universe” set also clarifies this. So, $$ with $$ would be better. The connection of $$ to $$ suggests instead of this fully symmetric presentation, it may still be worthwhile to single out a set producing $$ where $$. This can be read as “there is a point in $$ that touches/meets/overlaps every $$”. If desired we could notate this as $$. Negating and complementing the $$ leads to the dual notion $$ which is equivalent to $$. This dual notion could be read as “the $$ (jointly) cover $$” which is another common and important concept in mathematics.

Conclusion

Ultimately, the concept of two (or more) sets overlapping comes up quite often. The usual circumlocution, $$, is both notationally and conceptually clumsy. Treating overlapping as a first-class notion via notation and formulating definitions in terms of it can reveal some common and important patterns.

Introduction

Complex-step differentiation is a simple and effective technique for numerically differentiating a(n analytic) function. Discussing it is a neat combination of complex analysis, numerical analysis, and ring theory. We’ll see that it is very closely connected to forward-mode automatic differentiation (FAD). For better or worse, while widely applicable, the scenarios where complex-step differentiation is the best solution are a bit rare. To apply complex-step differentiation, you need a version of your desired function that operates on complex numbers. If you have that, then you can apply complex-step differentiation immediately. Otherwise, you need to adapt the function to complex arguments. This can be done essentially automatically using the same techniques as automatic differentiation, but at that point you might as well use automatic differentiation. Adapting the code to complex numbers or AD takes about the same amount of effort, however, the AD version will be more efficient, more accurate, and easier to use.

Nevertheless, this serves as a simple example to illustrate several theoretical and practical ideas.

Read more...

Introduction

This is part 3 in a series. See the previous part about internal languages for indexed monoidal categories upon which this part heavily depends.

In category theory, the hom-sets between two objects can often be equipped with some extra structure which is respected by identities and composition. For example, the set of group homomorphisms between two abelian groups is itself an abelian group by defining the operations pointwise. Similarly, the set of monotonic functions between two partially ordered sets (posets) is a poset again by defining the ordering pointwise. Linear functions between vector spaces form a vector space. The set of functors between small categories is a small category. Of course, the structure on the hom-sets can be different than the objects. Trivially, with the earlier examples a vector space is an abelian group, so we could say that linear functions form an abelian group instead of a vector space. Likewise groups are monoids. Less trivially, the set of relations between two sets is a partially ordered set via inclusion. There are many cases where instead of hom-sets we have hom-objects that aren’t naturally thought of as sets. For example, we can have hom-objects be non-negative (extended) real numbers from which the category laws become the laws of a generalized metric space. We can identify posets with categories who hom-objects are elements of a two element set or, even better, a two element poset with one element less than or equal to the other.

This general process is called enriching a category in some other category which is almost always called $$ in the generic case. We then talk about having $$-categories and $$-functors, etc. In a specific case, it will be something like $$-categories for an $$-enriched category, where $$ is the category of abelian groups. Unsurprisingly, not just any category will do for $$. However, it turns out very little structure is needed to define a notion of $$-category, $$-functor, $$-natural transformation, and $$-profunctor. The usual “baseline” is that $$ is a monoidal category. As mentioned in the previous post, paraphrasing Bénabou, notions of “families of objects/arrows” are ubiquitous and fundamental in category theory. It is useful for our purposes to make this structure explicit. For very little cost, this will also provide a vastly more general notion that will readily capture enriched categories, indexed categories, and categories that are simultaneously indexed and enriched, of which internal categories are an example. The tool for this is a (Grothendieck) fibration aka a fibered category or the mostly equivalent concept of an indexed category.¹

To that end, instead of just a monoidal category, we’ll be using indexed monoidal categories. Typically, to get an experience as much like ordinary category theory as possible, additional structure is assumed on $$. In particular, it is assumed to be an (indexed) cosmos which means that it is an indexed symmetric monoidally closed category with indexed coproducts preserved by $$ and indexed products and fiberwise finite limits and colimits (preserved by the indexed structure). This is quite a lot more structure which I’ll introduce in later parts. In this part, I’ll make no assumptions beyond having an indexed monoidal category.

Read more...