User todd trimble - MathOverflow

Answer by Todd Trimble for Proof by contradiction in a topos

2013-05-02T18:17:08Z

It depends on what examples you have in mind when you say "proof by contradiction". This topic has come up a number of times recently at MO, but I recommend to your attention the useful blog post by Andrej Bauer, which explains that there is a subtle distinction to be made between "proof of negation" and "proof by contradiction".

If the proposition to be proved is already of the form $\neg p$, then it may help to recall that $\neg p$ is (by definition) the weakest assumption one could make such its conjunction with $p$ entails falsity (in symbols, $x \leq \neg p$ iff $x \wedge p \leq 0$). This is true in intuitionistic logic as well as in classical logic. So a proof of a negated proposition $\neg p$ would quite properly begin, "suppose $p$, then ... contradiction". Many people call this a proof by contradiction, because the structure of the argument-phrasing looks just like any old proof by contradiction.

An example of this is Cantor's theorem (that there is no surjection from a set to its power set, or $\neg$ "there exists a surjection..."). This can be formulated in any topos and is true in any topos, Boolean or not.

(If this helps, notice that in intuitionistic logic, we have that $\neg p$ is equivalent to $\neg \neg \neg p$: a negated proposition is always equivalent to its double negation.)

But contrast this with for example the Hahn-Banach theorem: every locally convex topological vector space admits a continuous functional to the ground field. This proposition, which is not in negated form, is a prime example of something which has no constructive proof. A typical method of proof would be something like "by Zorn's lemma, there is a maximal closed subspace that admits such a continuous functional, and suppose this were not the whole space" and eventually derive a contradiction. This type of reasoning is not valid in a general topos.

For another example, consider "$\sqrt{2}$ is irrational". This is a negative proposition: "$\neg (\exists p, q \in \mathbb{Z}_+ \; p^2 = 2 q^2)$". The usual arithmetic proofs are valid in any topos.

Answer by Todd Trimble for For a monoid with zero $M$, how many additive operations on $M$ can there be making $M$ a ring?

2013-05-01T01:00:41Z

As for question 3, if the question is whether it's true that there are always countably many nonisomorphic additive group structures that extend a structure of infinite monoid with zero to a ring structure, the answer is no. In fact, there need not be any such extensions.

For example, consider a monoid given by a meet-semilattice with a top and bottom element; the multiplication is defined to be the meet. Every element is idempotent and so any ring extension would have to be a Boolean ring. There is in fact at most one way that a poset can be a Boolean algebra (so the number of ring extensions is either zero or one), but most posets are not Boolean algebras. For example, for $n \geq 2$ the poset of linear subspaces of $\mathbb{R}^n$ cannot be a Boolean algebra, because the distributive law fails.

Answer by Todd Trimble for Elementary proof for identity involving sums of binomials

2013-04-19T14:40:31Z

After canceling $1$'s and clearing denominators, the identity can be rearranged to this one:

$$n^{n+1} = \sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k+1} + \sum_{k=1}^n \binom{n}{k} n^{n-k} k!$$

and now we proceed to give a bijective proof. The left side counts data of the form

Endofunction $f: S \to S$ on an $n$-element set $S$, plus a distinguished point $s$ of $S$.

Draw the endofunction as a directed graph, where an edge is drawn from $x$ to $y$ if $f(x) = y$. This graph can be decomposed into connected components, and there are two disjoint possibilities:

Case 1: either $s$ belongs to a cycle (this includes the case where $f(s) = s$), or
Case 2: removal of the edge from $s$ to $f(s)$ produces a disconnection of the connected component of $s$.

Let us count the possibilities for the first case. The cycle to which $s$ belongs defines a $k$-element set, say, and gives a structure of linear order on this set, namely the ordering $s, f(s), \ldots, f^{k-1}(s)$. There are $k!$ ways of giving such a linear order, and this order describes the restriction of $f$ to the cycle containing $s$. The remainder of $f$ is just given by some function $S \backslash \mathrm{cycle}(s) \to S$ on the complement, of which there are $n^{n-k}$ many. Thus the second sum of the asserted identity counts the possibilities for case 1.

For case 2, consider the set of elements $x$ such that $f^{(j)}(x) = s$ for some $j \geq 0$. This defines some $k$-element subset, and the graph of the restriction of $f$ to this subset is described as a rooted tree with root at $s$. The number of such rooted tree structures on a $k$-element set is $k^{k-1}$, by Cayley's theorem. Then, the rest of $f$ is given by its restriction to the complement of this $k$-element set (notice it takes the complement to itself) -- there are $(n-k)^{n-k}$ possibilities here -- plus knowledge of the element $f(s)$ which belongs to this $(n-k)$-element set. Thus the first sum on the right side of the identity counts the number of possibilities for case 2, and we are done.

Answer by Todd Trimble for Is there any nontrivial monad on the category of graphs?

2013-04-18T12:17:55Z

I take it morphisms $f: X \to Y$ are by definition functions that preserve the relation: if $x, x'$ are related in $X$, then $f(x), f(x')$ are related in $Y$.

It's easy to manufacture some silly examples of nontrivial monads, by finding suitable monoidal products on the category of graphs and then finding monoids with respect to that monoidal product. One such monoidal product takes the disjoint sum of two graphs. Then an example of a monoid therein is the one-point graph $1$, which carries a unique monoid structure.

The associated monad $M$ takes a graph and adjoins an isolated point to the graph, which one could regard as basepoint. If $f: X \to Y$ is a graph morphism, then $M(f)$ is the obvious basepoint preserving extension. To be precise, $M(X) = 1 + X$; the unit of the monad is the inclusion of $X$ in $1 + X$, and the multiplication $1 + 1 + X \to 1 + X$ is the identity on $X$ but identifies the two copies of $1$ as one.

Answer by Todd Trimble for What is "Data" involved in a mathematical construction?

2013-04-15T05:07:03Z

The word "data" (singular datum) comes from the Latin and means "thing(s) given". In mathematics, a notion is typically introduced by saying something like, "an operad consists of the following data... subject to the following axioms". It's the stuff that has to be given in the first place before you can begin putting conditions on them in the form of axioms.

In logic, data is described by a signature (which specifies what sorts of operations and relations one is dealing with); once the signature is given, then you can specify the axioms in terms of logical formulas which are written in terms of the function and relation symbols of the signature.

Answer by Todd Trimble for Does "induction" for a functor algebra imply it is initial?

2013-04-14T17:04:33Z

It looks as though you might have already observed this yourself, but suppose $F: C \to C$ is an endofunctor and $C$ has equalizers. Then if $F$ has a weakly initial algebra $X$ (meaning that for every $F$-algebra $Y$ there exists an $F$-algebra map $X \to Y$), then $X$ is initial if and only if every $F$-subalgebra of $X$ is all of $X$. For, if $f, g: X \to Y$ are two $F$-algebra maps, then their equalizer is an $F$-subalgebra of $X$, and its being equal to $X$ would force $f = g$.

This is not a completely idle observation however, because one sometimes has formal ways to construct weakly initial $F$-algebras. Suppose for instance that $C$ is finitely complete and cartesian closed and $F$ carries a structure of $C$-enriched functor. Then, if the end

$$\int_{c \in C} c^{c^{F(c)}}$$

exists (meaning an object universal with respect to dinatural maps to the functor $G: C^{op} \times C \to C$ defined by $G(d, c) = c^{d^{F(c)}}$), it is a weakly initial $F$-algebra. For instance, when $C = Set$ and $F(c) = 1 + c$, we have

$$\int_{c} c^{c^{1 + c}} \cong \int_c c^{c^c \times c} \cong \int_c (c^c)^{(c^c)}$$

which is the set of dinatural transformations $c^c \to c^c$. This is isomorphic to $\mathbb{N}$ conceived as the set of Church numbers $\lambda f: f^{(n)}$ where $f$ is of variable type $c^c$.

If you are interested specifically in natural numbers objects, then there is a remarkable theorem due to Peter Freyd:

Theorem: In a topos $E$, the following are equivalent for a structure $(N, o: 1 \to N, s: N \to N)$:

$(N, o, s)$ is a natural numbers object;
The maps $o: 1 \to N, s: N \to N$ are coproduct injections (that witness $N$ as a coproduct $1 + N$) and $N \to 1$ is the coequalizer of the pair $(1_N, s): N \to N$;
$s$ is monic, the subobjects $s: N \to N$ and $o: 1 \to N$ are disjoint (have the initial object as their pullback), and any subalgebra of the algebra structure $(o, s): 1 + N \to N$ on $N$ is all of $N$.

The proof is not at all easy, but you can find it in Johnstone's Sketches of an Elephant, section D.5.

Answer by Todd Trimble for Fixed point theorems

2013-04-10T20:07:09Z

One of the most awesome fixed-point theorems I know of is due to Pataraia:

If $L$ is a poset with a bottom element and with joins of directed subsets, then every monotone function $f: L \to L$ has a (least) fixed point.

It is a strengthening of the Knaster-Tarski theorem, and is somewhat reminiscent of the Bourbaki-Witt theorem, but is entirely constructive. Related discussion at the n-Category Café here.

Answer by Todd Trimble for How to refer to a theorem that you have shown to be wrong

2013-04-05T12:27:52Z

In my opinion, it would be a bad idea to label statements known to be false as theorems. If you really want to do this, maybe you could put inverted commas around the word "theorem", to indicate you explicitly cast doubt on its following from axioms by applying rules of deduction. Or you could call it an Assertion, followed by a bold declaration that the assertion is false and the demonstration of such.

Answer by Todd Trimble for Which compositions have these sum-like and product-like properties on the positive reals?

2013-04-01T18:41:06Z

As remarked in comments under the question, an example would be $x \star y = \sqrt{x^2 + y^2}$. Indeed, if $f$ is any strictly monotonic bijection on $\mathbb{R}_{>0}$ (either monotone increasing or monotone decreasing), then $x \star y = f^{-1}(f(x) + f(y))$ or $x \star y = f^{-1}(f(x)f(y))$ furnish examples which address the question.

This is the usual "transport of structure" trick in mathematics: if we have e.g. a linearly ordered abelian group $(G, \cdot, \leq)$ and a linearly ordered set $(X, \leq)$ and an order-preserving isomorphism $f: X \to G$, then we can transport the group structure on $G$ along $f$ to get an ordered abelian group structure on $X$ which is isomorphic (by construction) to the ordered abelian group structure on $G$. That's all that was done here.

However, such examples raise an obvious further question: is every example isomorphic (as an ordered semigroup) either to $(\mathbb{R}_{> 0}, +, \leq)$ or to $(\mathbb{R}_{> 0}, \cdot, \leq)$? The division between these standard examples is that the additive case has no identity, whereas the multiplicative case does. This observation will to some extent guide the analysis (which I will leave somewhat sketchy at the end).

Each element $x$ of such a structure $(\mathbb{R}_{> 0}, \star, \leq)$ satisfies either

$x = x \star x$,
$x < x \star x$,
$x > x \star x$.

In the first case, we claim $x$ is an identity. Indeed, if $x \star y \neq y$ for some $y$, then $x \star y = (x \star x) \star y = x \star (x \star y)$, which contradicts the assumption that $x \star -$ is injective (since it is strictly monotone = strictly increasing).

We will say that $x$ is inflationary if $x < x \star x$, and deflationary if $x \star x < x$.

Lemma 1: If $x$ is inflationary, then $y < x \star y$ for every $y$. If $x$ is deflationary, then $x \star y < y$ for every $y$.

Proof: If $x < x \star x$, then $x \star y < (x \star x) \star y$ since $- \star y$ is strictly increasing. Thus $x \star y < x \star (x \star y)$. Therefore $y < x \star y$ since $x \star -$ is strictly increasing. Similar argument if $x \star x < x$.

Lemma 2: If there exists an inflationary element and a deflationary element, then there exists an identity.

Proof: The collection of inflationary elements is upward closed (if $x$ is inflationary and $x \leq y$, then $y$ is inflationary since by lemma 1 we have $y < x \star y \leq y \star y$). Similarly the collection of deflationary elements is downward closed. These facts imply $y < x$ if $y$ is deflationary and $x$ is inflationary. Put $e = \inf\{x: x < x \star x\} = \sup\{y: y \star y < y\}$. We claim $e$ is an identity. For if $e < e \star e$, then for every $y < e$ we have $y \star e < e < e \star e$ (since $y$ is deflationary). Letting $y$ approach $e$ from the left, this contradicts continuity of $- \star e$. Similarly $e \star e < e$ is impossible.

If $e$ is an identity, we have $y < e < x$ iff $y$ is deflationary and $x$ is inflationary.

Lemma 3: If $x$ is inflationary, then $x^n \star z = z \star x^n$ is unbounded above for any $z$ (where $x^n := x^{\star n}$). If $y$ is deflationary, then $y^n z = z \star y^n$ is unbounded below.

Proof: Otherwise, if $w$ is the least upper bound of $x \star z, x^2 \star z, x^3 \star z, \ldots$, then $w$ is an upper bound of $x \star w$ by continuity. But this contradicts $w < x \star w$ from lemma 1. Similarly for the second statement.

Lemma 4: If there exists an identity $e$, then $(\mathbb{R}_{> 0}, \star, \leq)$ is a group.

Proof: Suppose $y < e < x$. Then the set $y^m x^n$ is unbounded above and below by lemma 3. It follows that the images of the functions $y \star -$ and $x \star - = - \star x$ are unbounded both above and below. Since these images are intervals (by strict monotonicity), they must be all of $\mathbb{R}_{> 0}$. Thus $y \star -$ and $x \star -$ are bijections, so that there exists $z$, $w$ with $y \star z = e$ and $x \star w = e$, as was to be shown.

At this point, we have that if there exists an identity, then the structure is a linearly ordered abelian group whose underlying order is isomorphic to $\mathbb{R}_{> 0}$ or to $\mathbb{R}$. Sketching here: it is standard that such a structure is isomorphic to $(\mathbb{R}, +, \leq)$ (or to $(\mathbb{R}_{> 0}, \cdot, \leq)$). For such a group is divisible, contains a copy of $\mathbb{Q}$ as a dense subgroup, and then one finishes using completeness and continuity. Notice this is true even without assuming the Surjectivity property of the OP (that comes for free if there's an identity).

Now suppose there is no identity. Then either every element is inflationary, or every element is deflationary, by lemma 2. WLOG, we may assume every element is inflationary. Let me sketch an argument why such a structure should be isomorphic to $(\mathbb{R}_{> 0}, +, \leq)$ .

The trick is to extend $(\mathbb{R}_{> 0}, \star, \leq)$ to a linearly ordered commutative topological monoid $(\mathbb{R}_{\geq 0}, \star, \leq)$ (the topology is the order topology) by treating $0$ as the identity. Here the continuity of the operation $\star: \mathbb{R}_{\geq 0}^2 \to \mathbb{R}_{\geq 0}$ at $(0, 0)$ is secured by the Surjectivity property.

Now we have a cancellative linearly ordered commutative monoid, to which we may formally adjoin negatives to get a linearly ordered abelian group whose underlying order is isomorphic to $\mathbb{R}$, and the argument sketched above (using divisibility, completeness, etc.) should get the job done.

Answer by Todd Trimble for Sums of Squares and Totally Positive Numbers

2013-03-28T05:08:57Z

The product $ab$ of sums of squares $a$, $b$ is clearly a sum of squares. It follows that a quotient $a/b$ is also a sum of squares, since $a/b = ab(b^{-1})^2$.

Answer by Todd Trimble for How to show a certain determinant is non-zero

2013-03-27T20:36:15Z

Just in case it helps: to see that the OP's matrix $M$ has nonzero determinant using the argument in Noam Elkies' argument above, consider

$$\begin{equation*} \mathrm{det}\; \begin{pmatrix} e^{\lambda_1 x_1} & e^{\lambda_2 x_1} & \cdots & e^{\lambda_n x_1}\\\\ e^{\lambda_1 x_2} & e^{\lambda_2 x_2} & \cdots & e^{\lambda_n x_2}\\\\ \vdots & \vdots & & \vdots\\\\ e^{\lambda_1 x} & e^{\lambda_2 x} & \cdots & e^{\lambda_n x} \end{pmatrix} \end{equation*} $$

as an exponential polynomial $f(x) = \sum_{k=1}^n a_k e^{\lambda_k x}$. This has roots at $x = x_1, x_2, \ldots, x_{n-1}$. On the other hand, Elkies argued (see mathoverflow.net/questions/83999) that an exponential polynomial with $n$ terms has at most $n-1$ real roots. (We actually need only the weaker claim that $f(x)$ has at most $n-1$ distinct real roots. This follows by induction, where the inductive step involves Rolle's theorem applied to the derivative of the exponential polynomial $e^{-\lambda_n x}f(x)$, which has $n-1$ terms.) Thus $f(x)$ must be nonzero at $x = x_n$, as desired.

Answer by Todd Trimble for On the category of virtual species

2013-03-19T00:24:34Z

I had tried to do something like this around 1994, and then again a little later as I will explain in a moment. The first time around, I had tried formalizing this in the context of species valued in a category of "virtual sets" (finite sets, to avoid an Eilenberg swindle), guided by Joyal's pretty observation that the implication "$A + C \cong B + C$ implies $A \cong B$" definitely has computational meaning as you say: starting with a given bijection $f: A + C \to B + C$, feed back the outputs of $f$ that land in $C$ as inputs, and iterate to obtain a bijection $g: A \to B$. This operation is natural in the sense fully explained in Joyal-Street-Verity's paper, Traced Monoidal Categories. (Essentially the same observation appears in Conway and Doyle's paper, Division by Three, if I remember correctly.)

One can categorify the taking of formal differences, starting with the category of finite sets and bijections and applying the tortile category construction in Traced Monoidal Categories. It's pretty simple in this case and one winds up with the compact closed category of oriented 1-cobordisms (so objects are oriented compact 0-manifolds, i.e., multisets of +'s and -'s, and morphisms are diffeomorphisms of oriented compact 1-manifolds with boundary). I tried developing a calculus of virtual species as functors from $\mathbb{B}$ to this category, but at some point the project petered out. Unfortunately I cannot recall exactly where it petered out at this remove in time, but I suspect it had to do with the fact that to get the full richness of the usual theory of species uses good properties of $\mathrm{Set}$ such as cartesian closure, and that some of these properties don't translate well to the category of virtual sets (the category of oriented 1-cobordisms). For example, taking the negative of a set should be a duality functor (a contravariant equivalence), but cartesian closed categories that are self-dual collapse to posets.

A few years later I had another crack at it (while I was hanging out as a visitor at U. Chicago, around 1996), but this time I was more interested in formalizing virtual linear species (i.e., differences of $\mathrm{Vect}$-valued species), since the primary application in the Joyal paper centered on linear species and particularly the structure of the Lie species. The basic idea was to use differential $\mathbb{Z}_2$-graded spaces modulo quasi-isomorphism as the receiving category, thinking of $(V_0, V_1, d)$ as representing a formal difference $V_0 - V_1$. This approach seemed much more promising, and is implicit in my Notes on the Lie Operad, which you can find here if you are interested. However, I was never satisfied with those notes and never tried to publish them -- I should return to this, and particularly the model category of $\mathbb{Z}_2$-graded chain complexes as an environment for virtual linear species. (Perhaps someone else has fleshed it all out in the meantime?)

Answer by Todd Trimble for Bases of open sets with connected intersections

2013-03-08T13:33:25Z

I reckon you consider the empty subspace to be connected (since for a Hausdorff space, at least one such intersection must be empty). In that case, for a Riemannian manifold, you can get not just connectedness, but contractibility for all (nonempty) finite intersections of basis elements, by taking a neighborhood basis to consist of geodesically convex neighborhoods. (An open set $U$ is geodesically convex if any two points in $U$ are connected by a unique geodesic in $U$, one whose length is the distance between the points). For it is immediate that any (nonempty) intersection of geodesically convex neighborhoods is also geodesically convex, hence contractible. Details are spelled out in this nLab article.

Of course, a (paracompact Hausdorff) smooth manifold admits a Riemannian metric, so you have the result for smooth manifolds.

I believe CW complexes have the same property (a proof of the existence of a good open cover is sketched in the same nLab article), but I haven't checked that carefully.

Answer by Todd Trimble for Is there a constructive proof of Cantor–Bernstein–Schroeder theorem ?

2013-03-03T19:14:08Z

If you accept that toposes are models of constructive set theory, then another way to answer the question is to give a (non-Boolean) topos where the CBS theorem fails; that would show that this theorem can't possibly have a constructive proof.

A simple example of such a topos is the arrow category $Set^\to$, whose objects are functions $X_0 \to X_1$ between sets and whose morphisms are commutative squares. Let $X$ be the object $f: \mathbb{N} \to \mathbb{N}$ that takes $n \in \mathbb{N}$ to $\mathrm{int}(n/2)$, where $\mathrm{int}(x)$ is the greatest integer less than or equal to $x$; let $Y$ be the object $g: \mathbb{N} \to \mathbb{N}$ that takes $n$ to $\mathrm{Int}((n+1)/2)$, where $\mathrm{Int}(x)$ is the least integer greater than or equal to $x$. It is pretty clear that $X$ and $Y$ are non-isomorphic, because $g^{-1}(0)$ has cardinality $1$ where all fibers of $f$ have cardinality $2$. But, just by drawing pictures of these objects, it is easy to construct monomophisms $i: X \to Y$ and $j: Y \to X$ (e.g., define $i_0(n) = n+1$ and $i_1(n) = n+1$ for all $n$, and define $j_0(n) = n+1$ for $n \gt 0$, $j_0(0) = 0$, and $j_1(n) = n$ for all $n$).

For people who are not used to thinking of topos theory as "constructive set theory", there is another way of considering the example above in terms of "$H$-valued sets", where $H$ is the Heyting algebra with three elements, $H = \{0 < 1/2 < 1\}$. The law of the excluded middle does not hold; one can easily calculate $\neg \neg (1/2) = 1$.

An $H$-valued set is a set $X$ together with a function $e_X: X \times X \to H$ which measures the extent to which elements of $X$ are considered "equal", subject to transitivity and symmetry axioms:

$$e_X(x, y) \wedge e_X(y, z) \leq e_X(x, z), \qquad e_X(x, y) = e_X(y, x).$$

We can think of $e_X(x, x)$ as measuring the extent to which $x$ "exists". An $H$-valued relation is a function $r: X \times Y \to H$ such that

$$e_X(x', x) \wedge r(x, y) \leq r(x', y), \qquad r(x, y) \wedge e_Y(y, y') \leq r(x, y'), \qquad r(x, y) \leq e_X(x, x) \wedge e_Y(y, y).$$

An $H$-valued function $f: X \to Y$ is an $H$-valued relation such that

$$f(x, y) \wedge f(x, y') \leq e_Y(y, y'), \qquad e_X(x, x) \leq \bigvee_{y \in Y} f(x, y)$$

where the first condition is an analogue of well-definedness and the second roughly says that $f(x)$ is defined to the extent $x$ exists. It turns out that the category of $H$-valued sets is equivalent to the topos $Set^\to$.

Under this equivalence, $X$ in the example above is identified with the pair $(\mathbb{N}, e_X: \mathbb{N} \times \mathbb{N} \to H)$ where $e_X(n, n) = 1$, where $e_X(m, n) = 1/2$ if $m \neq n$ but $f(m) = f(n)$, and otherwise $e_X(m, n) = 0$. There is a similar description of $Y$ in terms of $H$-valued sets. For such $H$-valued sets where $e_X(x, x') = 1$ for all precisely when $x = x'$, functional $H$-relations between them can be described as actual functions $f: X \to Y$ subject to the condition $e_X(x, x') \leq e_Y(f(x), f(x'))$ for all $x, x'$ in $X$.

The monomorphic functional relations $i: (\mathbb{N}, e_X) \to (\mathbb{N}, e_Y)$ and $j: (\mathbb{N}, e_Y) \to (\mathbb{N}, e_X)$ turn out to be given by $i(n) = n+1$ and $j(0) = 0$, $j(n) = n+1$ for $n > 0$ (i.e., the functions $i_0$ and $j_0$ in the example above). The monomorphicity amounts to the condition that $e_Y(i(x), i(x')) = e_X(x, x')$ for all $x, x'$ in $X$ (and similarly for $j$). This is easily checked.

Now one can try to run through the König proof to see what goes kaflooey. Following the Wikipedia description, every element of the disjoint union $X \sqcup Y$ unambiguously belongs to an "$X$-stopper" or to a "$Y$-stopper":

$$1_X \stackrel{i}{\mapsto} 2_Y \stackrel{j}{\mapsto} 3_X \stackrel{i}{\mapsto} \ldots$$

$$0_Y \stackrel{j}{\mapsto} 0_X \stackrel{i}{\mapsto} 1_Y \stackrel{j}{\mapsto} \ldots$$

But: when one attempts to define an isomorphism $\phi: X \to Y$ out of this by following the prescription, it immediately goes wrong. Look at what this putative function $\phi$ does to the "half-equal" elements $0_X$ and $1_X$. It sends them respectively to the not-at-all-equal elements $0_Y$ and $2_Y$. Thus it fails to respect

$$e_X(0_X, 1_X) \leq e_Y(\phi(0_X), \phi(1_X))$$

as required by law.

Answer by Todd Trimble for Are exponentials in categorical models of linear logic harmful?

2013-03-01T15:53:03Z

Michal already answered the question where we consider intuitionistic multiplicative linear logic, without an involutive linear negation; there are many such models where we can have a symmetric monoidal closed structure concurrent with a cartesian closed structure on a category. Another easy example (in fact a special case of one of his constructions) is the topos of $G$-sets where $G$ is an abelian group, made into a symmetric monoidal closed category by using the Day convolution.

I'd like to supplement his answer by mentioning that if you do demand an involutive negation as well (i.e., work with classical multiplicative linear logic), which we categorically model using $\ast$-autonomous categories, then we do get a collapse: every such model is posetal. More is true: a cartesian closed category $C$ that is self-dual must be a poset; notice that a classical linear negation gives a self-duality, i.e., an equivalence

$$\neg: C^{op} \stackrel{\cong}{\to} C.$$

This is because the initial object in a cartesian closed category is strict, i.e., for any object $X$, if there is a morphism $X \to 0$, then $X \cong 0$. Given that fact, consider morphisms $1 \to (A \Rightarrow B)$. Then, letting $(-)^\ast$ be the self-duality functor, these are in bijective correspondence with morphisms

$$(A \Rightarrow B)^\ast \to 0$$

and if such a morphism exists, then $(A \Rightarrow B)^\ast \cong 0$ by strictness. In particular, there is at most one morphism $(A \Rightarrow B)^\ast \to 0$, and therefore at most one morphism $1 \to A \Rightarrow B$, and hence at most one morphism $A \to B$ for any two objects $A$, $B$.

Answer by Todd Trimble for Gödel, Escher, Bach: b is a power of 10.

2013-03-01T03:57:41Z

You should probably read this very nice blog post by David Speyer, which concerns exactly this problem (and more importantly, the technical parts of the Gödel incompleteness theorem).

Answer by Todd Trimble for Products of Boolean algebras and probability measures thereon

2013-02-24T17:05:24Z

Since the opposite of the category of Stone spaces is equivalent to the category of Boolean algebras, the product of Stone spaces would have to correspond to the coproduct of Boolean algebras. Thus what you want is to construct the coproduct of a family of Boolean algebras directly, but without invoking Stone duality.

This is just general (categorical) universal algebra. The theory of Boolean algebras is a finitary algebraic theory, so on general grounds you can construct the coproduct of a family $\{B_i\}_{i \in I}$ by taking a filtered colimit over the system of finite coproducts. Usually (and more generally for commutative rings) this is called an (infinite) tensor product:

$$\bigotimes_{i \in I} B_i = \mathrm{colim}_{\mathrm{finite}\; F \subset I} \otimes_{i \in F} B_i$$

More concretely, this colimit is simply a set-theoretic union of finite tensor products of Boolean algebras, construed as commutative algebras over the ring $\mathbb{Z}/(2)$. This description matches that in Nik's answer.

For the moment I'll stop here, although I might come back to address the second query on probability measures.

Answer by Todd Trimble for Reference for my monads?

2013-02-20T20:41:14Z

What you are describing is an example of Max Kelly's notion of club, closely connected with the concept of operad. The original references date back to the 70's; one reference is

G.M.Kelly. On clubs and doctrines. In Category Seminar, Sydney 1972/1973. Springer LNM 420, pp. 181-257 (1974).

Actually, a club is defined to be a monoid in a monoidal category $M$ whose objects are pairs $(C, F: C \to Cat)$ where $C$ is a small category, and where a morphism $(C, F) \to (D, G)$ consists of a functor $H: C \to D$ and a natural transformation $G H \to F$; the monoidal product is a kind of wreath product. There is an "actegory" structure (an action of the monoidal category $M$) on $Cat$,

$$\wr: M \times Cat \to Cat,$$

so that each club = monoid in $M$ induces a monad on $Cat$. You can also find a succinct description of this material here.

As a reality check, here is a more direct description of the (underlying functor of the) monad on $Cat$, associated with the club structure on the inclusion $i: \mathrm{FCat} \hookrightarrow Cat$, which can be extracted by applying the construction given in Borisov's paper, pp. 3-4. The monad takes a category $D$ to a category which I will denote $\mathrm{FCat} \wr D$ (Borisov uses a semi-direct product symbol). The objects of $\mathrm{FCat} \wr C$ are pairs $(C, l: i(C) \to D)$ where $C \in \mathrm{FCat}$ is a finite category and $l: i(C) \to D$ is a functor. Morphisms $(C, l) \to (C', l')$ of $\mathrm{FCat} \wr D$ are pairs $(F: C \to C', \phi: l \to l' \circ i(F))$ where $\phi$ is a natural transformation.

Unless I have misunderstood something, this gives one of the monads described in the OP. I think the other monad is obtained by a process of dualization (apply $(-)^{op}$, then apply the first monad, then apply $(-)^{op}$ again), so we really only need to worry about the first. As I said, all the laborious technical details were covered long ago in the "Australian school".

Other familiar examples of clubs are where we take the inclusion $i: Set \to Cat$, mapping each set $S$ to the discrete category on $S$; the corresponding monad is the free coproduct completion monad. Another is the composite inclusion $\mathbb{P} \hookrightarrow Set \hookrightarrow Cat$ of the groupoid of finite permutations; here the corresponding monad is the free symmetric (strict) monoidal category construction.

Answer by Todd Trimble for Flatness of projective bundles

2013-02-19T12:32:02Z

Isn't any fiber bundle $p: E \to B$ projection an open map? If $e \in E$ belongs to an open $U$, then there is a trivializing neighborhood $V_e$ of $p(e)$ so that $p^{-1}(V_e) \to V_e$ is isomorphic to a projection map $V_e \times F \to V_e$, which is certainly open. Hence $p(U \cap p^{-1}(V_e))$ is open. Since direct images preserve unions, we see that

$$p(U) = p(\bigcup_{e \in U} U \cap p^{-1}(V_e)) = \bigcup_{e \in U} p(U \cap p^{-1}(V_e))$$

is open.

Answer by Todd Trimble for Unitalization internal to monoidal categories

2013-02-18T17:47:33Z

Edit: an earlier version of this answer muddled a distinction between lax limit and 2-limit. I've decided to undelete it in case someone sees how to complete the argument at the end.

If $C$ is locally presentable and $S$ is a semi-monad whose underlying functor is accessible, then there exists a unitalization of $S$. Here is a proof modeled after an idea discussed at the nLab at the page free monad.

Define an algebra of a semi-monad $S: C \to C$ in the expected way, as an object $X$ of $C$ equipped with a morphism (an "action") $SX \to X$ satisfying the usual associativity law for an action. Morphisms between algebras are also defined in the expected way, so that there is a full embedding $S$-$\mathrm{Alg}_\mathrm{smd} \hookrightarrow S \downarrow C$ into the comma category. (I use the subscripts "smd" and "mnd" to indicate algebras qua semi-monads and monads.)

The main thing to check is that the forgetful functor $S$- $\mathrm{Alg}_\mathrm{smd} \to C$ is monadic in the "evil" sense, so that there is an isomorphism $F$-$\mathrm{Alg}_\mathrm{mnd} \simeq S$-$\mathrm{Alg}_\mathrm{smd}$ in $Cat/C$ for some monad $F$. The claim is that then $F$ is the free monad on the semi-monad $S$. For in that case, given a monad $M$ on $C$ we have natural bijections between

Semi-monad morphisms $S \to M$,
$S$-algebra structures $S U_M \to U_M$ where $U_M:$ $M$-$\mathrm{Alg}_\mathrm{mnd} \to C$ is the forgetful functor,
Morphisms $M$- $\mathrm{Alg}_\mathrm{mnd} \to S$ - $\mathrm{Alg}_\mathrm{smd}$ in $Cat/C$,
Morphisms $M$- $\mathrm{Alg}_\mathrm{mnd} \to F$ - $\mathrm{Alg}_\mathrm{mnd}$ in $Cat/C$,
$F$-algebra structures (qua algebras over a monad) $F U_M \to U_M$,
Monad morphisms $F \to M$

so that $F$ is evidently the free monad on the semi-monad $S$.

So now we check monadicity, using the precise monadicity theorem. It is straightforward that the forgetful functor $U: S$-$\mathrm{Alg}_{\mathrm{smd}} \to C$ creates (not just reflects!) $U$-split coequalizers, so we just have to check that $U$ has a left adjoint. However, since the 2-category of locally presentable categories and accessible functors inherits 2-limits from $Cat$, and since $S$- $\mathrm{Alg}_\mathrm{smd}$ is a ~~2-limit~~ (edit: lax limit) in $Cat$ (for essentially the same reason that Eilenberg-Moore categories for monads are ~~2-limits~~ lax limits), ~~we see that $U: S$- $\mathrm{Alg}_\mathrm{smd} \to C$ is an accessible functor between locally presentable categories~~. In this situation, existence of a left adjoint to $U$ is equivalent to preservation of limits by $U$. But limit-preservation is clear. So the conditions of the precise monadicity theorem are satisfied.

Edit: The last paragraph would need to be fixed to make the argument complete, either by somehow showing $U$ lives in the 2-category of accessible categories and accessible functors (note that $S$- $\mathrm{Alg}_{\mathrm{smd}}$ is complete, and so would then be locally presentable), or e.g. by showing that the full inclusion $S$- $\mathrm{Alg}_{\mathrm{smd}} \hookrightarrow S \downarrow C$ is reflective, or by some other means.

Answer by Todd Trimble for What is a good example of a hyperspace where the base space is non-Hausdorff?

2013-02-14T11:57:03Z

A source of examples that comes to mind is Alexandroff topologies. For example, take the natural numbers $\mathbb{N}$, and declare a set $U \subseteq \mathbb{N}$ to be open if it is downward closed in the usual order. The closure of a point $n$ is then $\{m \in \mathbb{N}: m \geq n\}$. The poset of closed sets under reverse inclusion looks like the ordinal $\omega + 1$, and if you give this the Alexandroff topology as well (open sets = down-sets), then this will give a hypertopology.

Answer by Todd Trimble for Adjoint of Pushout as Modal Operators in Internal Logic

2013-02-11T17:02:55Z

Probably you should get a hold of a textbook on categorical logic for some of these questions. Of the references given in the Wikipedia article, the one by Lambek & Scott and the two with Lawvere as an author might be a good start. A study of these would probably help make the table in the nLab seem less "peculiar".

I see that Wouter Stekelenburg has posted an answer just as I started this, but it wouldn't hurt to amplify. The propositional connectives (on predicates of a given type $A$) are interpreted as operations on the poset of subobjects $Sub(A)$ (e.g., the pullback of two subobjects of $A$ is another subobject of $A$ which corresponds to the meet). Next, each morphism $f: B \to A$ in the category induces an inverse image operation $f^{-1}: Sub(A) \to Sub(B)$, formally defined by taking a pullback: if $i: U \to A$ is a monomorphism, then the pullback of the cospan $(f, i)$ is given by a pair of maps $(g: V \to U, j: V \to B)$ where one may show easily from general properties of pullbacks that $j$ is a monomorphism, thus giving a subobject of $B$. In the classical case where $f$ is a projection map $\pi: X \times A \to A$, you can think of the inverse image $\pi^{-1}: Sub(A) \to Sub(X \times A)$ as interpreting the operation which takes a predicate $\phi$ of type $A$ and forming a predicate of type $X \times A$ by harmlessly adjoining a variable of type $X$, e.g., by taking $\phi \wedge [x = x]$.

Then quantifiers $\exists_f$, $\forall_f$ are operations $Sub(B) \to Sub(A)$ that are left and right adjoint (respectively) to $f^{-1}: Sub(A) \to Sub(B)$. It might help to consider the classical case where $f$ is the projection $\pi: X \times A \to A$. Here the left adjoint $\exists_f$ takes a subobject of $X \times A$ (that interprets a predicate $\phi(x, a)$ of type $X \times A$) to one of type $A$, interpreting the predicate that is usually denoted $\exists_x \phi(x, a)$. (In other words, classical quantification has to do with adjoints to puling back along projection maps $\pi$.) The adjunction between $\exists_{\pi}$ and $\pi^{-1}$ corresponds to the inference rule

$$\exists_x \phi(x, a) \vdash \psi(a) \qquad \mathrm{iff} \qquad \phi(x, a) \vdash \psi(a) \wedge [x = x]$$

where the entailment symbols are interpreted as subobject inclusions in the appropriate posets $Sub(A)$, $Sub(X \times A)$. (Normally one isn't so fussy as to write $\psi(a) \wedge [x = x]$; one usually writes simply $\psi(a)$, but keeping in mind that $\psi$ is here being considered a predicate of type $X \times A$, so that the types match.)

Your guesses about the modalities are a little off. There are lots of places to read about categorical semantics of modal logic; one nice place (for S4 necessity) is in the paper by Awodey and Kishida. It might help first to be familiar with the topological semantics of "necessity" as a topological interior operation on power sets $\Box = \mathrm{int}: P(A) \to P(A)$, due originally to Tarski.

Answer by Todd Trimble for Where in ordinary math do we need unbounded separation and replacement?

2013-02-10T19:51:04Z

I asked the same question about the replacement axiom not long ago at the $n$-Category Café, and the answer I got back from Mike Shulman is that it's used for example in the transfinite construction of free algebras, which really refers to a body of connected results in category theory as described here. The essential use made of replacement is in the transfinite compositions; this also occurs in the small object argument.

Having said that, a part of me still wonders whether there aren't workarounds. In many cases an initial algebra of a functor is situated inside a terminal coalgebra of the same functor, and the construction of the latter often doesn't require transfinite compositions (this is the case, e.g., for polynomial endofunctors). Paul Taylor in his book Practical Foundations of Mathematics has a section on general recursion using a theory of well-founded coalgebras, which is manifestly meaningful in contexts where one does without replacement, such as ETCS, and I wonder to what extent this could be put to use to construct free algebras without resorting to replacement.

Answer by Todd Trimble for Trichotomies in mathematics

2013-02-06T18:39:29Z

Here is a cluster of examples with a common theme, based partly on comments here and in an MO thread on whether an empty space should be considered connected, and partly on an article in the nLab, "too simple to be simple".

One should note that some of these trichotomies were once-upon-a-time considered dichotomies; for example, for many people in the past, 1 was a prime number. Also one should notice that there are a number of cross-connections (homomorphisms, if you will) between these examples, and that list is by no means complete (this is CW, so feel free to add more!).

A module can be reducible, irreducible, or zero.
A filter in a Boolean algebra can be "submaximal" (faute de mieux!), a maximal filter = ultrafilter, or an improper filter.
An element in a p.i.d. is composite, prime, or a unit.
A topological space (or a graph) can be disconnected, connected, or "unconnected" (empty).
As for elements satisfying a predicate, one can have a multiplicity, unique existence, or nonexistence.

The last trichotomy is often considered a dichotomy: nonuniqueness vs. uniqueness. (I.e., nonexistence falls under the scope of uniqueness = "at most one".) But experience in mathematics, e.g. in category theory and its focus on universal properties, shows that unique-existence deserves to be considered in a category of its own.

Theories can be incomplete but consistent, complete, or inconsistent.

Answer by Todd Trimble for Is the empty graph a tree?

2013-02-02T08:46:15Z

The whole discussion seems to devolve on whether the empty graph (or empty space) should be considered "connected". Angelo and I are of the school that it should not, but this should be explained since some of the traditional definitions of "connected" apparently allow the empty space to be connected.

A general abstract context is as follows. Let $C$ be a category with finite coproducts with the property that for any two objects $a$, $b$ (whose coproduct is denoted $a+b$), the canonical functor

$$C/a \times C/b \to C/(a+b): (x \to a, y \to b) \mapsto (x + y \to a + b)$$

is an equivalence. Such a category is said to be extensive. The category of topological spaces is extensive, the category of graphs is extensive, any topos is extensive, and there are many, many other examples.

Now, say an object $a$ in an extensive category is connected if the functor

$$\hom(a, -): C \to Set$$

preserves binary coproducts (whence it can be shown to preserve finite coproducts). This is a fundamental definition; see the nLab for an extended discussion. Under this definition, the empty space (the empty graph, etc.), i.e., the initial object, is not connected.

An equivalent definition is to say $c$ is connected if, whenever $c \cong a + b$, exactly one of $a, b$ is inhabited. If one insists that the empty space should be connected, then change the word "exactly" to "at most", and instead of saying the canonical map $\hom(c, x) + \hom(c, y) \to \hom(c, x + y)$ is an isomorphism, say it is merely surjective. However, most results come out more cleanly by working with the definition above, which disqualifies the empty set.

Compare the notion of prime ideal: working in the lattice of ideals of a p.i.d. $R$ where $\leq$ is given by reverse inclusion, the coproduct or join of ideals $a, b$ is $ab$, the initial ideal is $R$, and we say an ideal $p$ is prime if $p \neq R$ and $p \leq ab$ implies $p \leq a$ or $p \leq b$. The condition $p \neq R$ is considered fundamental to the definition of prime. Without it, we no longer have e.g. unique decomposition of integers into prime factors (compare the fact that every graph is uniquely a coproduct of connected graphs under our definition, but this is not so if the empty graph is considered to be connected). See also the numerous examples in the nLab discussion "too simple to be simple"; for example, $1$ is too simple to be a prime, and the zero module is considered too simple to be a simple module.

Every acyclic graph (a forest) is uniquely a coproduct of acyclic connected graphs (i.e., trees) under our definition of connectedness. This includes the empty forest. So a forest can be empty, but a tree cannot.

Answer by Todd Trimble for Noncontractible connected topological rings ?

2013-01-26T20:24:15Z

Here is a method for manufacturing such topological rings.

The main technical ingredient is a product-preserving functor

$$\Theta: \mathrm{Set}^{\Delta^{op}} \to \mathrm{CGHaus}$$

from the category of simplicial sets to the category of compactly generated Hausdorff spaces that is not, however, the usual geometric realization functor. This will almost undoubtedly be unfamiliar, and so will require some preface. The basic idea though is that while the usual geometric realization uses for its topological input the usual interval $I = [0, 1]$, the formal properties of the realization functor, particularly the fact it preserves finite products, still hold upon replacing $I$ by any compact topological interval $L$ and replacing ordinary affine simplices by $L$-valued simplices. This $L$-based realization $\Theta$, being product-preserving, takes simplicial rings to ring objects in $\mathrm{CGHaus}$. By choosing an appropriate $L$ that is connected but not path-connected, we can construct a topological ring that is connected but not path-connected, hence not contractible.

We define an interval to be a linearly ordered set with distinct top and bottom elements, and an interval map as an order-preserving map that preserves the top and bottom. Observe that the usual affine simplex $\sigma_{n-1}$ of dimension $n-1$ can be described as the space of $(n-1)$-tuples $0 \leq x_1 \leq \ldots \leq x_{n-1} \leq 1$ (topologized as a subspace of $I^n$), or in other words as the space of interval maps $[n+1] \to I$ from the finite interval with $n+1$ points to $I$. Meanwhile, the category $\mathrm{FinInt}$ of finite intervals $[n+1]$ is equivalent to $\Delta^{op}$ (where $\Delta$ is the category of finite nonempty ordinals); indeed we have a functor $\hom(-, [2]): \Delta^{op} \to \mathrm{FinInt}$, where the set of order-preserving maps $\hom([n], [2])$ from the $n$-element ordinal $[n]$ to $[2]$ is given the pointwise order, thus inheriting an interval structure from the interval structure on $[2]$, where we have $[n+1] \cong \hom_{\Delta}([n], [2])$ as intervals).

The usual geometric realization $R(X)$ of a simplicial set $X$, from a categorical point of view, is a tensor product $X \otimes_\Delta \sigma$ of a "right $\Delta$-module" $X: \Delta^{op} \to \mathrm{Set}$ with a left $\Delta$-module $\sigma: \Delta \to \mathrm{CGHaus}$ (the affine simplex functor):

$$\sigma: \Delta \simeq \mathrm{FinInt}^{op} \stackrel{\hom(-, I)}{\to} \mathrm{CGHaus}$$

$$[n] \mapsto [n+1] \mapsto \hom_{\mathrm{Int}}([n+1], I).$$

This tensor product is often described by a coend formula

$$R(X) = X \otimes_\Delta \sigma = \int^{[n] \in \Delta} X([n]) \cdot \hom_{\mathrm{Int}}([n+1], I).$$

As is well-known, $R$ is product-preserving. What is perhaps less well-known is that the only thing we need from $I$ to prove this fact is that it's compact Hausdorff and the interval order $\leq$ is a closed subset of $I \times I$. Complete details may be found in the nLab here. Therefore, if we replace $I$ with another compact Hausdorff topological interval $L$ (so that $\leq_L$ is a closed subset of $L \times L$), we get the same result, that the functor $\Theta = R_L$ defined by the formula

$$R_L(X) = \int^{[n] \in \Delta} X([n]) \cdot \hom_{\mathrm{Int}}([n+1], L)$$

is also product-preserving.

Let us take our compact topological interval $L$ to be the end-compactification of the long line (so, adjoin points $-\infty$ and $\infty$ to the ends of the long line). This is connected, but not path-connected because for example there is no path from $\infty$ to any other point. Now we just turn a crank: start with any denumerable non-trivial ring $R$ in $\mathrm{Set}$ -- I'll take $R = \mathbb{Z}/(2)$ -- and apply a sequence of product-preserving functors,

$$\mathrm{Set} \stackrel{K}{\to} \mathrm{Cat} \stackrel{N}{\to} \mathrm{Set}^{\Delta^{op}} \stackrel{R_L}{\to} \mathrm{CGHaus}.$$

(Here $K$ is the functor that takes a set $S$ to the category such that $\hom(x, y)$ is a singleton for any $x, y \in S$; this is right adjoint to the forgetful functor $\mathrm{Cat} \to \mathrm{Set}$ that remembers only the set of objects, and being a right adjoint, $K$ preserves products. The nerve functor $N$ also preserves products.) Since ring objects can be defined in any category with finite products, we have that product-preserving functors transport ring objects to ring objects. One should draw a picture of the category $K(\mathbb{Z}/(2))$; it's pretty clearly connected, and its nerve will be a connected simplicial set, or indeed a connected simplicial ring. The $L$-based realization of that will thus be a connected colimit of (connected) $L$-based simplices $\sigma_L(n) = \hom([n+1], L)$ (see the nLab here for connected colimits of connected spaces), and so it too will be a connected ring object in $\mathrm{CGHaus}$.

At this point, the overall idea should be pretty clear, and the rest is just some technical mopping-up.

One technical point is that products in $\mathrm{CGHaus}$ need not be usual topological products (as shown by a famous example of Dowker), so one might object that we could end up not with a topological ring, but some kind of funny ring object in $\mathrm{CGHaus}$. However, in many cases of interest, topological products do coincide with $\mathrm{CGHaus}$ products. This is particularly the case for colimits of countable increasing sequences of compact Hausdorff spaces: their product in $\mathrm{CGHaus}$ is the usual topological product. (The same proof as given by Allen Hatcher for Theorem A.6 here will do.) Thus, what counts here is that $N(K(\mathbb{Z}/(2)))$ is a simplicial set with finitely many cells in each dimension, and $R_L$ applied to this involves taking a countable union of compact Hausdorff spaces, so we are okay here.
A second technical point involves showing that $X = (R_L \circ N \circ K)(\mathbb{Z}/(2))$ is not path-connected, which is intuitively clear, but an idea of proof would be nice. $X$ can be described as a union of nondegenerate simplices, where there are two such simplices in each dimension $n$ (corresponding to paths of length $n$ of the form $0 \to 1 \to 0 \to \ldots$ and $1 \to 0 \to 1 \to \ldots$), and a point in the interior of each such simplex has coordinates given by an increasing chain of length $n$ in a dictionary order, say $(j_1, t_1) < (j_2, t_2) < \ldots < (j_n, t_n)$ where the $j_k$ belong to the order type $-\omega_1 \cup \omega_1$ ($\omega_1$ being the first uncountable ordinal, and $-\omega_1$ is of opposite order type, extending in the "negative" direction), and the $t_k$ belong to $[0, 1)$. Every point of $X$ is an interior point of some unique $n$-simplex. Now if $\alpha: I \to X$ is a path connecting a point in the interior of an $n$-simplex, $n > 0$, to a 0-simplex, then let $(a, b) \subset I$ be a connected component of the open set of $t \in I$ such that $\alpha(t)$ is interior to an $n$-simplex with $n > 0$. Since $(a, b)$ has countable cofinality, there is a countable ordinal $\kappa$ such that for every $t \in (a, b)$, the maximum ordinal $|j_k|$ occurring in the coordinate description of $\alpha(t)$ is bounded above by $\kappa$. But $\alpha(a)$, being a 0-cell, has a neighborhood $U$ where every point $p \in U$, $p \neq \alpha(a)$, has a maximum $|j_k|$ (in its coordinate description) greater than $\kappa$, and we have reached a contradiction.

Answer by Todd Trimble for Free cocommutative commutative Hopf monoids

2013-01-15T17:31:56Z

As for question (1): assuming cocomplete cartesian monoidal category means that cartesian products distribute over colimits (and I know from past experience that you do mean this, Martin), then it's true that the monad $T$ preserves reflexive coequalizers. The main thing you need is that finitary power functors $c \mapsto c^n$ preserve reflexive coequalizers. This is a corollary of a result that you can find on the first page of chapter 0 of Johnstone's Topos Theory, which is a $3 \times 3$ lemma stating that if the rows and columns are reflexive coequalizer diagrams, then so is the diagonal. It easily follows from this lemma that for example the squaring functor $c \mapsto c \times c$ preserves reflexive coequalizers, and a similar inductive argument allows you to extend this to any finite power $c \mapsto c^n$.

To derive the fact that monads $T: C \to C$ based on a Lawvere algebraic theory $\theta$ preserve reflexive coequalizers, write

$$T(c) = \int^{n \in \mathrm{FinSet}^{op}} \hom_\theta(i(n), i(1)) \cdot c^n$$

where the tensor $S \cdot c$ of a set $S$ with an object $c$ is the coproduct of copies of $c$ indexed over $S$. (Here $i: \mathrm{FinSet}^{op} \to \theta$ denotes the unique (up to isomorphism) map of Lawvere algebraic theories, viewing $\mathrm{FinSet}^{op}$ as the "initial" Lawvere algebraic theory.) Since coend functors and tensor functors $S \cdot -$ preserve reflexive coequalizers, as does $c \mapsto c^{n}$, we see that $T$ does as well.

I can't think of a more direct nice description of the composite left adjoint $F$, nor do I think one is needed because I think the description you gave is plenty nice.

As for (2): the underlying functor is definitely not monadic. It's not even a right adjoint, because for example for $C = \mathrm{Vect}_k$, it fails to preserve the terminal object (which in $\mathrm{AbHopf}(\mathrm{Vect})_k$ is the monoidal unit $k$, as is the case just in $\mathrm{CoMon}(\mathrm{Vect})_k$).

Edit: Since this came up in comments, let me provide an alternative proof of the fact that finite power functors on a cocomplete cartesian monoidal category preserve reflexive coequalizers. Recall that a category $J$ is sifted if the diagonal functor $J \to J \times J$ is final (result due to Gabriel and Ulmer). A prototypical example is where $J$ is the generic parallel pair equipped with a section in common. Then follow Steve Lack's soft proof here, which uses just the assumption that $C$ is cocomplete cartesian monoidal and the finality of the diagonal on $J$, to show the binary product $C^2 \to C$ preserves reflexive coequalizers. Similarly, the $n$-fold product $C^n \to C$ preserves reflexive coequalizers. The $n$-fold power on $C$ is a composite of the diagonal $\Delta: C \to C^n$ (which is a left adjoint, thus colimit-preserving) with the $n$-fold product, so it too preserves reflexive coequalizers.

Answer by Todd Trimble for Unit sphere in R^\infty is contractible?

2013-01-19T22:21:56Z

The question doesn't seem to be very well expressed, but the intended question might be as follows. Take $\mathbb{R}^\infty$ to mean the vector space consisting of real tuples $(v_1, v_2, v_3, \ldots)$ such that all but finitely many $v_i$ are zero, equipped with the coherent topology (so that $U \subseteq \mathbb{R}^\infty$ is open iff $U \cap \mathbb{R}^n \subseteq \mathbb{R}^n$ is open in the standard Euclidean topology on $\mathbb{R}^n$, here identifying $\mathbb{R}^n$ with the subset of tuples $(v_1, v_2, v_3, \ldots)$ such that $v_i = 0$ for $i > n$). Let $S^\infty \subseteq \mathbb{R}^\infty$ be the subset consisting of tuples such that $\sum_i |v_i|^2 = 1$, equipped with the subspace topology. Then $S^\infty$ is contractible.

The idea is easy enough: define a map $f: S^\infty \to S^\infty$ by $f(v_1, v_2, \ldots) = (0, v_1, v_2, \ldots)$, and define a homotopy $H_1$ from the identity on $S^\infty$ to $f$ by

$$H_1(t, v) = N((1-t)v + tf(v))$$

where $N: \mathbb{R}^\infty \backslash \{0\} \to S^\infty$ is the map $v \mapsto \frac{v}{\|v\|}$. Then define a second homotopy $H_2$ from $f$ to the constant function on $S^\infty$ valued at $p = (1, 0, 0, 0, \ldots)$ by

$$H_2(t, v) = (1-t)^{1/2}f(v) + t^{1/2}p.$$

Gluing these two homotopies together, we have a homotopy which contracts $S^\infty$ to a point.

Edit: The question arose in a comment as to why $H_1$ is continuous. It might help to bear in mind two facts: (1) that the coherent topology on an increasing union of spaces $X = \bigcup_i X_i$ is the colimit topology, i.e., the topology of the colimit in $\mathrm{Top}$ of the diagram $X_1 \subset X_2 \subset \ldots$, and (2) the functor $[0, 1] \times -: \mathrm{Top} \to \mathrm{Top}$ preserves colimits because $[0, 1]$ is locally compact Hausdorff (i.e., if $I$ is locally compact Hausdorff, then $I \times -$ is left adjoint to exponentiation $(-)^I$, and left adjoints preserve colimits). For example, to check that the map

$$\mathrm{colim}_n I \times S^n \cong I \times \mathrm{colim}_n S^n \to \mathbb{R}^\infty \backslash \{0\}$$

defined by $v \mapsto (1-t)v + tf(v)$ is continuous, it suffices to check that its restriction to each $I \times S^n$ is continuous (by definition of colimit). But this restriction is a composite of manifestly continuous maps, $I \times S^n \to \mathbb{R}^{n+1} \backslash \{0\} \hookrightarrow \mathbb{R}^\infty \backslash \{0\}$, where the first map is defined again by $v \mapsto (1-t)v + tf(v)$. Similarly, to check that the normalization map $N: \mathbb{R}^\infty \backslash \{0\} \to S^\infty$ is continuous, it suffices to check that its restriction to each $\mathbb{R}^n \backslash \{0\}$ is continuous, but this restriction is a composite of continuous maps $\mathbb{R}^n \backslash \{0\} \to S^n \hookrightarrow S^\infty$.

Answer by Todd Trimble for Vertical and Horizontal Isomorphisms in 2-categories

2013-01-16T18:44:16Z

Before answering, let me remark that it's generally considered a little weird (some would say, with tongue partly in cheek, "evil") to posit categorical axioms which enforce equalities between objects, since models of such axioms will not be invariant with respect to categorical equivalences. Such axioms ought to be replaced by enforcing corresponding isomorphisms between objects, satisfying suitable coherence axioms.

With that in mind, let's start by putting the question a little differently: suppose that for each object $X$ we have units $\eta_X: I \to \bar{X} \otimes X$, $\eta_X': I \to X \otimes \bar{X}$, and counits $\epsilon_X: X \otimes \bar{X} \to I$, $\epsilon_X': \bar{X} \otimes X \to I$ such that the triangular equations for adjunctions $X \dashv \bar{X}$, $\bar{X} \dashv X$ hold and

$$\eta_X' \circ \epsilon_X = 1_{X \otimes \bar{X}}, \qquad \eta_X \circ \epsilon_X' = 1_{\bar{X} \otimes X}$$

$$\epsilon_X \circ \eta_X' = 1_I = \epsilon_X' \circ \eta_X$$

(Edit: As noted by Chris and myself below, given an object $\bar{X}$ and invertible maps $\eta_X: I \to \bar{X} \otimes X$, $\phi: I \to X \otimes \bar{X}$, one can always construct an invertible map $\eta_X': I \to X \otimes \bar{X}$ such that $\epsilon_X := (\eta_X')^{-1}$ and $\epsilon_X' := (\eta_X)^{-1}$ are counits that fit into appropriate triangular equations. Details (for the more general case of 2-categories or bicategories in place of monoidal categories) are given in the nLab article mentioned in my comment.)

Then, as you surmise, $f$ is invertible with respect to $\circ$ iff it is "invertible with respect to $\otimes$". Essentially we follow your definition of $\bar{f}$ given $f^{-1}$, defining

$$\bar{f} = (\epsilon_X' \otimes 1_{\bar{Y}}) \circ (1_{\bar{X}} \otimes f^{-1} \otimes 1_{\bar{Y}}) \circ (1_{\bar{X}} \otimes \eta_Y)$$

and what we really mean by "invertible with respect to $\otimes$" is that we have equations

$$\epsilon_Y \circ (f \otimes \bar{f}) \circ \eta_X' = 1_I = \epsilon_Y' \circ (\bar{f} \otimes f) \circ \eta_X.$$

The most perspicuous way to show these equations hold is by using string diagram calculus. Since I am not too handy with graphics, I'll just briefly sketch how to derive the first equation, leaving it to you to believe or verify that the second equation works similarly. The main steps are that

$$\begin{array} \epsilon_Y \circ (f \otimes \bar{f}) \circ \eta_X' & = & \epsilon_Y \circ (f \otimes 1_{\bar{Y}}) \circ (1_X \otimes \epsilon_X' \otimes 1_X \otimes 1_{\bar{Y}}) \circ (\eta_X' \otimes 1_X \otimes 1_{\bar{Y}}) \circ (f^{-1} \otimes 1_{\bar{Y}}) \circ \eta_Y' \\ & = & \epsilon_Y \circ (f \otimes 1_{\bar{Y}}) \circ (f^{-1} \otimes 1_{\bar{Y}}) \circ \eta_Y' \\ & = & \epsilon_Y \circ \eta_Y' \\ & = & 1_I \end{array} $$

where the first equation uses the definition of $\bar{f}$ and axioms of a monoidal category, the second uses a triangular equation, and the fourth uses one of the invertibility axioms for $Y$. Remaining details are similarly routine.

Answer by Todd Trimble for What, precisely, does Klein's Erlangen Program state?

2013-01-15T22:01:50Z

(Rewritten in response to David Corfield's comment below.)

A somewhat more modern take on the Erlanger Programm was given in Tarski's 1966 talk What Are Logical Notions? (published 1986), as described in the Wikipedia article on Tarski, which proposes a distinction between what is logical and what is non-logical. The idea that as one loosens the theory (say from Euclidean geometry to affine geometry to topology to...), the relevant automorphism group becomes larger and larger, so that maximal automorphism groups (symmetric groups) correspond to theories of maximal looseness, where one is left with purely logical notions.

However, it should be said that Tarski's idea was clearly anticipated by F.I. Mautner, writing in 1946; see here. For some commentary on this, see this post by David Corfield at the $n$-Category Café.

As shameless self-promotion, I'll mention that James Dolan and I dabbled a little in this as well; some results were described at the $n$-Category Café, here and here. There we give describe a Galois correspondence between subgroups of symmetric groups and complete theories, in categorical terms.

Comment by Todd Trimble

2013-05-18T07:30:40Z

Yes, it has that kind of flavor. That still doesn't prevent me from finding it amazing.

Comment by Todd Trimble

2013-05-18T01:30:30Z

That's really quite a remarkable result...

Comment by Todd Trimble

2013-05-17T13:05:05Z

Although Matthew has bowed out, I just want to say what a pleasure it is to read his comments generally, not only for their erudition but for their wonderful civility. Too bad not all comments under this question in particular are so civil...

Comment by Todd Trimble

2013-05-14T15:30:51Z

As in party-pooper, I suppose (for those who don't know the English expression: someone who acts in a way to dampen enthusiasm).

Comment by Todd Trimble

2013-05-13T00:38:03Z

I wouldn't worry about it -- let it stand. It seems like an interesting remark. Since some like me might not be too familiar with the Banach-Dieudonne theorem and its consequences, you might also consider fleshing this out a bit (I quickly googled and the statement I found applied to Banach spaces, which $\mathbb{R}^\infty$ is not, so it would help me personally to have a little more explanation).

Comment by Todd Trimble

2013-05-09T16:57:29Z

@Gerard: such a pro tem explanation is good enough for me. It would be ridiculous to hold every MO question to the same standard (explain to me why I should care), and in my view many other questions that appear on MO are of even less intrinsic interest. I expect the problem is indeed challenging. People should work on it only if they feel like it.

Comment by Todd Trimble

2013-05-09T00:35:50Z

I don't know, guys. The linked Wikipedia article seems to give a clear enough indication of what the (symmetric) Pythagorean tree is; just click on it if you want to know. If the question were slightly edited to "what is known about the area?" (beyond what is contained in the Wikipedia article or articles linked therein), then it wouldn't disqualify itself on the grounds of being an open problem, and probably about as acceptable as many other MO questions, although I agree with Deane that the response to Anton was really uncalled for (and could warrant a flag). If you don't like it, skip it.

Comment by Todd Trimble

2013-05-08T23:07:25Z

Thank you for this tremendous answer, Andrej! It practically made my day.

Comment by Todd Trimble

2013-05-08T00:05:43Z

@Amir: I am utterly confused about what actually happened at that discussion. I don't think anyone who wasn't there can really comment on that discussion, and certainly not on the basis of such a skeletal report. It might help if the discussion were videotaped and made public, so that you could point to specific moments of the discussion that trouble you, although it's my opinion that MathOverflow (and its particular functionalities) are in fact poorly adapted for such a discussion about a discussion. I have just entered a vote to close.

Comment by Todd Trimble

2013-05-07T06:09:18Z

I am aware of what was said in the OP. However, in view of the update, it's not clear to me that anyone's feelings were accurately recounted. We could have a real discussion if we could see something expressed in print, instead of getting information second-hand whose accuracy has been called into question.

Comment by Todd Trimble

2013-05-06T14:31:56Z

What on earth is this about?

Comment by Todd Trimble

2013-05-04T11:12:12Z

Thanks for clarifying your comment, trb456. I largely agree, but I thought the general discussion here was to be about mathematicians (e.g., the author of Theorems For a Price). I didn't mean to sound insulting by using the word 'academic', and I'm sorry if I did.

Comment by Todd Trimble

2013-05-04T10:45:00Z

You should try googling. The Wikipedia article can help.

Comment by Todd Trimble

2013-05-03T13:47:36Z

Thanks to John Stillwell for providing a fuller quotation -- the final words are something that most mathematicians would agree with. And while he exaggerates when he says "all physicists", he's right that many (most?) physicists have such attitudes, perhaps even moreso in his day.

Comment by Todd Trimble

2013-05-03T13:21:39Z

Yes, a proof that certifies 99.999% likelihood of validity should itself be impeccable. I think Terry Tao was driving at something slightly different, about arguments being both correct but perhaps more crucially for the advancement of understanding, letting the high-level ideas shine through without being cluttered with details at a routine and professionally trivial level. But I agree that everyone, and I would include prodigies, has to go through these stages. That said, I feel as though some of this discussion is academic: which mathematicians nowadays publicly wish to get rid of rigor?