Introduction I’ll start by rationalizing an example of “old” umbral calculus from Wikipedia . |\newcommand{pair}[2]{\langle{#1}\mid{#2}\rangle}| |\newcommand{bigpair}[2]{\left\langle{#1}\ \middle|\ {#2}\right\rangle}| |\newcommand{pseq}[2]{\{#1\}_{#2 \in \mathbb N}}| |\newcommand{ucomp}[2]{#1_n(\underline #2(x))}| We know |(x+y)^n = \sum_{k=0}^n {n \choose k} x^{n-k} y^k|. We then “infer” that…
Introduction I want to talk about one of the many pretty areas of number theory. This involves the notion of an arithmetic function and related concepts. A few relatively simple concepts will allow us to produce a variety of useful functions and theorems. This provides only a glimpse of the start of the field of analytic number theory, though many of these techniques are used in other places as…
Introduction Purely functional list concatenation, xs ++ ys in Haskell syntax, is well known to be linear time in the length of the first input and constant time in the length of the second, i.e. xs ++ ys is O(length xs). This leads to quadratic complexity if we have a bunch of left associated uses of concatenation. The ancient trick to resolve this is to, instead of producing lists, produce…
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…
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…
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…
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…
Introduction It is not uncommon for universal quantification to be described as (potentially) infinite conjunction 1 . Quoting Wikipedia’s Quantifier_(logic) page (my emphasis): For a finite domain of discourse |D = \{a_1,\dots,a_n\}|, the universal quantifier is equivalent to a logical conjunction of propositions with singular terms |a_i| (having the form |Pa_i| for monadic predicates). The…
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…
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, |F|, preserves limits when it takes limiting cones to limiting cones. As often happens in category theory texts, the notation focuses on…