User tom leinster - MathOverflow

An ultrafilter is a set of subsets containing exactly one element of each finite partition: reference request

2011-07-04T13:42:40Z

There are probably dozens of ways of defining "ultrafilter". The definition I've seen most often involves first defining "filter", then declaring an ultrafilter to be a maximal filter.

But there's another, shorter way to state the definition:

Let $X$ be a set. An ultrafilter on $X$ is a set $\mathcal{U}$ of subsets such that for all partitions $$ X = X_1 \amalg \cdots \amalg X_n $$ of $X$ into a finite number $n \geq 0$ of subsets, there is exactly one $i$ for which $X_i \in \mathcal{U}$.

I'd be amazed if this wasn't in the literature somewhere, but I haven't been able to track it down. Can anyone help?

Actually, there's an even more economical definition: instead of allowing $n$ to be any natural number, you take it to be 3. Thus, the condition is that whenever $X = A \amalg B \amalg C$, exactly one of $A$, $B$ and $C$ is in $\mathcal{U}$. (The same thing works with 4, or 5, etc., though not with 2.) I'm mostly interested in the version with arbitrary $n$, which seems more natural, but if you've seen the $n = 3$ version in the literature then I'd like to hear about that, too.

Edit To be clear, when I use the word "partition" I don't mean to imply that the sets $X_i$ are nonempty. I just mean a family of pairwise disjoint sets $X_i$ whose union is $X$. They can be empty.

Answer by Tom Leinster for Surface area of a convex set

2013-04-20T12:13:00Z

A good reference is Klain and Rota's little book Introduction to Geometric Probability, especially Section 5.5.

Here's the formula. The surface area of a compact convex subset $K$ of $\mathbb{R}^n$ is

$$ \frac{1}{\omega_{n - 1}} \int_{S^{n-1}} Vol_{n-1}(\pi_{\theta^{\bot}} K) d\theta. $$

Here $\omega_{n - 1}$ is the volume of the unit Euclidean $(n - 1)$-ball, $\theta^\bot$ is the linear subspace of $\mathbb{R}^n$ orthogonal to the point $\theta$ of $S^{n - 1}$, and $\pi_{\theta^{\bot}}$ is orthogonal projection onto that subspace; also, $Vol_{n - 1}$ is Lebesgue measure on $\mathbb{R}^{n - 1}$.

As you may know, this is a special case of the more general "Crofton formula" for the intrinsic volumes. In the surface area formula, we're effectively integrating over the space of all $(n - 1)$-dimensional linear subspaces of $\mathbb{R}^n$; for the general Crofton formula, we integrate over the space of all $k$-dimensional linear subspaces of $\mathbb{R}^n$, for some fixed $k$. This gives the formula for the $k$-dimensional intrinsic volume. All this is nicely explained in Klain and Rota.

Understanding Gibbs's inequality

2013-02-25T13:21:45Z

Short version

Gibbs's inequality is a simple inequality for real numbers, usually understood information-theoretically. In the jargon, it states that for two probability measures on a finite set, the relative entropy is always nonnegative.

I'd like to hear about non-information-theoretic ways of understanding it. I'd be particularly pleased if there were some nice geometric interpretation.

Statement and proof of Gibbs's inequality

For natural numbers $n$, let $\mathbf{P}_n$ denote the set of probability measures on an $n$-element set: that is, $$ \mathbf{P}_n = \{ p \in \mathbb{R}^n : p_1, \ldots, p_n \geq 0, \sum p_i = 1 \}. $$ Theorem (Gibbs) Let $p \in \mathbf{P}_n$. Then, for $q$ varying in $\mathbf{P}_n$, the quantity $\prod q_i^{p_i}$ is maximized by $q = p$.

Usually this is stated in logarithmic form: $-\sum p_i \log q_i \geq -\sum p_i \log p_i$ for all $p, q \in \mathbf{P}_n$. But I'd like to reach a direct understanding of the product form.

There are at least two extremely easy proofs. Ignoring zero probabilities, they run as follows. The first: since $\log$ is concave, $\sum p_i \log (q_i/p_i) \leq \log \sum p_i (q_i/p_i) = 0$. The second: since $\log x \leq x - 1$ for all $x$, we have $\sum p_i \log (q_i/p_i) \leq \sum p_i (q_i/p_i - 1) = 0$.

The question

Can Gibbs's inequality, in the product form stated above, be understood geometrically? Or if not geometrically, is there an intuitive interpretation other than the information-theoretic one? (I have nothing against information theory — it's just that I'd like to have multiple ways of thinking about it.)

There is a hint that Gibbs's inequality can be interpreted as some kind of isoperimetric inequality. Take $p$ to be the uniform distribution. Then the inequality states that for $q \in \mathbf{P}_n$, the quantity $(q_1 q_2 \cdots q_n)^{1/n}$ is maximized by taking $q$ to be uniform. We might as well remove the power $1/n$, and then the result is: among all $n$-dimensional boxes of prescribed total edge-length, the cube has the greatest volume.

But I see no way of extending the isoperimetric interpretation to non-uniform $p$. For example, take $p = (2/3, 1/3)$. Then Gibbs states that among all $q \in \mathbf{P}_2$, the maximum value of $q_1^2 q_2$ is attained by $q = (2/3, 1/3)$. This doesn't seem geometrically obvious to me in the way that the uniform case does.

Answer by Tom Leinster for "Philosophical" meaning of the Yoneda Lemma

2009-10-29T04:03:02Z

Lazily, I'll just point to some notes on this question: What's the Yoneda Lemma all about?

Do the elementary properties of mixed volume characterize it uniquely?

2011-08-03T01:58:03Z

Background

Take 2 convex sets in $\mathbb{R}^2$, or 3 convex sets in $\mathbb{R}^3$, or generally, $n$ convex sets in $\mathbb{R}^n$. "Mixed volume" assigns to such a family $A_1, \ldots, A_n$ a real number $V(A_1, \ldots, A_n)$ , measured in $\mathrm{metres}^n$.

As I understand it, mixed volume is a kind of cousin of the determinant. I'll give the definition in a moment, but first here are some examples.

$V(A, \ldots, A) = \mathrm{Vol}(A)$, for any convex set $A$.
More generally, suppose that $A_1, \ldots, A_n$ are all scalings of a single convex set (so that $A = r_i B$ for some convex $B$ and $r_i \geq 0$). Then $V(A_1, \ldots, A_n)$ is the geometric mean of $\mathrm{Vol}(A_1), \ldots, \mathrm{Vol}(A_n)$ .
The previous examples don't show how mixed volume typically depends on the interplay between the sets. So, taking $n = 2$, let $A_1$ be an $a \times b$ rectangle and $A_2$ a $c \times d$ rectangle in $\mathbb{R}^2$, with their edges parallel to the coordinate axes. Then $$ V(A_1, A_2) = \frac{1}{2}(ad + bc). $$ (Compare and contrast the determinant formula $ad - bc$.)
More generally, take axis-parallel parallelepipeds $A_1, \ldots, A_n$ in $\mathbb{R}^n$. Write $m_{i1}, \ldots, m_{in}$ for the edge-lengths of $A_i$. Then $$ V(A_1, \ldots, A_n) = \frac{1}{n!} \sum_{\sigma \in S_n} m_{1, \sigma(1)} \cdots m_{n, \sigma(n)}. $$ (Again, compare and contrast the determinant formula.)

The definition of mixed volume depends on a theorem of Minkowski: for any compact convex sets $A_1, \ldots, A_m$ in $\mathbb{R}^n$, the function $$ (\lambda_1, \ldots, \lambda_m) \mapsto \mathrm{Vol}(\lambda_1 A_1 + \cdots + \lambda_m A_m) $$ (where $\lambda_i \geq 0$ and $+$ means Minkowski sum) is a polynomial, homogeneous of degree $n$. For $m = n$, the mixed volume $V(A_1, \ldots, A_n)$ is defined as the coefficient of $\lambda_1 \lambda_2 \cdots \lambda_n$ in this polynomial, divided by $n!$.

Why pick out this particular coefficient? Because it turns out to tell you everything, in the following sense: for any convex sets $A_1, \ldots, A_m$ in $\mathbb{R}^n$, $$ \mathrm{Vol}(\lambda_1 A_1 + \cdots + \lambda_m A_m) = \sum_{i_1, \ldots, i_n = 1}^m V(A_{i_1}, \ldots, A_{i_n}) \lambda_{i_1} \cdots \lambda_{i_n}. $$

Properties of mixed volume

Formally, let $\mathscr{K}_n$ be the set of nonempty compact convex subsets of $\mathbb{R}^n$. Then mixed volume is a function $$ V: (\mathscr{K}_n)^n \to [0, \infty), $$ and has the following properties:

Volume: $V(A, \ldots, A) = \mathrm{Vol}(A)$. (Here and below, the letters $A$, $A_i$ etc. will be understood to range over $\mathscr{K}_n$, and $\lambda$, $\lambda_i$ etc. will be nonnegative reals.)
Symmetry: $V$ is symmetric in its arguments.
Multilinearity: $$ V(\lambda A_1 + \lambda' A'_1, A_2, \ldots, A_n) = \lambda V(A_1, A_2, \ldots, A_n) + \lambda' V(A'_1, A_2, \ldots, A_n). $$ (These first three properties closely resemble a standard characterization of determinants.)
Continuity: $V$ is continuous with respect to the Hausdorff metric on $\mathscr{K}_n$.
Invariance: $V(gA_1, \ldots, gA_n) = V(A_1, \ldots, A_n)$ for any isometry $g$ of Euclidean space $\mathbb{R}^n$ onto itself.
Multivaluation: $$ V(A_1 \cup A'_1, A_2, \ldots, A_n) = V(A_1, A_2, \ldots) + V(A'_1, A_2, \ldots) - V(A_1 \cap A'_1, A_2, \ldots) $$ whenever $A_1, A'_1, A_1 \cup A'_1 \in \mathscr{K}_n$ .
Monotonicity: $V(A_1, A_2, \ldots, A_n) \leq V(A'_1, A_2, \ldots, A_n)$ whenever $A_1 \subseteq A'_1$ .

There are other basic properties, but I'll stop there.

Questions

Is $V$ the unique function $(\mathscr{K}_n)^n \to [0, \infty)$ satisfying properties 1--7?

If so, does some subset of these properties suffice? In particular, do properties 1--3 suffice?

If not, is there a similar characterization involving different properties?

(Partway through writing this question, I found a recent paper of Vitali Milman and Rolf Schneider: Characterizing the mixed volume. I don't think it answers my question, though it does give me the impression that the answer might be unknown.)

Why are abelian groups amenable?

2010-01-18T03:02:28Z

A (discrete) group is amenable if it admits a finitely additive probability measure (on all its subsets), invariant under left translation. It is a basic fact that every abelian group is amenable. But the proof I know is surprisingly convoluted. I'd like to know if there's a more direct proof.

The proof I know runs as follows.

Every finite group is amenable (in a unique way). This is trivial.
$\mathbb{Z}$ is amenable. This is not trivial as far as I know; the proof I know involves choosing a non-principal ultrafilter on $\mathbb{N}$. This means that $\mathbb{Z}$ is amenable in many different ways, i.e. there are many measures on it, but apparently you can't write down any measure 'explicitly' (without using the Axiom of Choice).
The direct product of two amenable groups is amenable. This isn't exactly trivial, but the measure on the product is at least constructed canonically from the two given measures.
Every finitely generated abelian group is amenable. This follows from 1--3 and the classification theorem.
The class of amenable groups is closed under direct limits (=colimits over a directed poset). This is like step 2: it seems that there's no canonical way of constructing a measure on the direct limit, given measures on each of the groups that you start with; and the proof involves choosing a non-principal ultrafilter on the poset.
Every abelian group is amenable. This follows from 4 and 5, since every abelian group is the direct limit of its finitely generated subgroups.

Is there a more direct proof? Is there even a one-step proof?

Update Yemon Choi suggests an immediate simplification: replace 1 and 4 by

1'. Every quotient of an amenable group is amenable. This is simple: just push the measure forward.

4'. Every f.g. abelian group is amenable, by 1', 2 and 3.

This avoids using the classification theorem for f.g. abelian groups.

Tom Church mentions the possibility of skipping steps 1--3 and going straight to 4. If I understand correctly, this doesn't use the classification theorem either. The argument is similar to the one for $\mathbb{Z}$: one still has to choose an ultrafilter on $\mathbb{N}$. (One also constructs a Følner sequence on the group, a part of the argument which I didn't mention previously but was there all along).

Yemon, Tom and Mariano Suárez-Alvarez all suggest using one or other alternative formulations of amenability. I'm definitely interested in answers like that, but it also reminds me of the old joke:

Tourist: Excuse me, how do I get to Edinburgh Castle from here?

Local: I wouldn't start from here if I were you.

In other words, if a proof of the amenability of abelian groups uses a different definition of amenability than the one I gave, then I want to take the proof of equivalence into account when assessing the simplicity of the overall proof.

Jim Borger points out that if, as seems to be the case, even the proof that $\mathbb{Z}$ is amenable makes essential use of the Axiom of Choice, then life is bound to be hard. I take his point. However, one simplification to the 6-step proof that I'd like to see is a merging of steps 2 and 5. These are the two really substantial steps, but they're intriguingly similar. None of the answers so far seem to make this economy. That is, every proof suggested seems to involve two separate Følner-type arguments.

Answer by Tom Leinster for The symmetric monoidal category of finite sets

2013-01-03T10:27:27Z

Re Question 1, one place where this appears is in Example (d) on p.23 of my paper Homotopy algebras for operads (arXiv:math.QA/0002180). There I used $\mathrm{CMon}$ to denote the terminal symmetric operad (whose algebras are commutative monoids) and $\widehat{\mathrm{CMon}}$ to denote the free symmetric monoidal category containing a $\mathrm{CMon}$-algebra (a commutative monoid). The statement made there is that $\widehat{\mathrm{CMon}}$ is a skeleton of the category of finite sets.

I'm absolutely sure that this wasn't original to me, but I don't know what the correct reference is.

Answer by Tom Leinster for Not-so-symmetric monoidal categories

2013-01-01T18:39:15Z

(This is really a comment, not an answer; but it's too long to fit in a comment.)

Carl, I'm unsure what you're asking. The first paragraph seems to be about monoidal categories such that $X \otimes Y \cong Y \otimes X$ for all objects $X$ and $Y$, but not naturally in $X$ and $Y$. The remaining paragraphs seem to be about something else entirely.

Perhaps the kind of example you had in mind in the first paragraph is the following. The category of finite totally ordered sets is monoidal: given two finite totally ordered sets $X$ and $Y$, the tensor product $X \oplus Y$ is the disjoint union of $X$ and $Y$ ordered by putting everything in $X$ before everything in $Y$. It has the property that $X \oplus Y \cong Y \oplus X$ for all $X$ and $Y$. On the other hand, there's no natural isomorphism between the functors $$ (X, Y) \mapsto X \oplus Y, \qquad (X, Y) \mapsto Y \oplus X, $$ so it's not a symmetric monoidal category.

But maybe that this is irrelevant to what you're thinking about. I'm afraid I just can't tell what you're after. Can you clarify?

Answer by Tom Leinster for The origin of sets?

2012-12-22T22:51:03Z

This isn't meant entirely seriously as an answer to your question, but: on page 344 of Practical Foundations of Mathematics, Paul Taylor writes:

Adam of Balsham (1132) observed that the difference between finite and infinite sets is that the latter admit proper self-inclusions, such as $n \mapsto 2n$.

Obviously this is staggeringly early and it would be astonishing if this dude Adam had anything like our present-day conception of set. Paul doesn't appear to give a reference, but perhaps he (Paul, not Adam) will see this and tell us more.

Answer by Tom Leinster for Subadditivity for Renyi entropies

2012-12-21T00:01:41Z

Suvrit has answered it completely, but let me suggest how you might go about finding counterexamples.

It's often useful to work with not the Rényi entropies but their exponentials, $$ D_\alpha(X) = \exp(H_\alpha(X)) = \Bigl( \sum_{i=1}^n p_i^\alpha \Bigr)^{1/(1-\alpha)} $$ (where, as in your question, $X$ is a random variable with distribution $p_1, \ldots, p_n$). One advantage of working with $D$ rather than $H$ is that there's a useful limit as $\alpha \to \infty$, namely $$ D_\infty(X) = 1/\max_i p_i. $$ Since this is such a simple formula, $\alpha = \infty$ is a good case to try when testing conjectures.

In terms of $D$, subadditivity becomes $D_\alpha(A, B) \leq D_\alpha(A) D_\alpha(B)$. It's easy to find counterexamples when $\alpha = \infty$: for instance, $$ \begin{pmatrix} 1/2 &1/4 \\ 1/4 &0 \end{pmatrix} $$ is a counterexample since $$ \frac{1}{\max\{1/2, 1/4, 1/4, 0\}} = 2 > \frac{16}{9} = \frac{1}{\max\{3/4,1/4\}}\frac{1}{\max\{3/4,1/4\}}. $$ It follows that this is a counterexample for all sufficiently large finite $\alpha$. If you graph it, you see that it is in fact a counterexample for all $\alpha$ greater than about $1.6$. Tweaking it gives you counterexamples for all $\alpha > 1$.

Answer by Tom Leinster for Maps between operads of different arities

2012-12-20T16:56:39Z

I'm not certain I understand the intent of the question, but perhaps the following is the kind of thing Poisson is looking for.

A non-symmetric operad is a sequence $(P_n)_{n \geq 0}$ of sets together with an identity element and maps defining composition, all satisfying some axioms.

A symmetric operad is the same, but also comes with a map $\theta_*\colon P_n \to P_n$ for each bijection $\theta\colon \mathbf{n} \to \mathbf{n}$, again satisfying axioms. (Here I use $\mathbf{n}$ to denote a fixed $n$-element set, say $\{1, \ldots, n\}$.)

A finitary algebraic theory is the same, but also comes with a map $\theta_* \colon P_n \to P_m$ for each function $\theta\colon \mathbf{n} \to \mathbf{m}$, again satisfying axioms.

The three types of structure have successively greater expressive power. For example, there is no non-symmetric operad encoding the theory of commutative monoids (because expressing the equation $xy = yx$ requires the nontrivial bijection $\mathbf{2} \to \mathbf{2}$). There is a symmetric operad encoding the theory of commutative monoids, but there is none encoding the theory of commutative monoids in which every element is idempotent (because expressing the term $x^2$ requires the surjection $\mathbf{2} \to \mathbf{1}$).

This doesn't mean that finitary algebraic theories are 'better' than operads, because there's a trade-off: the contexts in which it's possible to talk about algebras are successively narrower. That is, given an operad $P$, you can talk about algebras for $P$ in an arbitrary monoidal category $\mathcal{E}$; but if $P$ has the structure of a symmetric operad, you need $\mathcal{E}$ to be symmetric monoidal in order to talk about $P$-algebras in $\mathcal{E}$; and if $P$ is a finitary algebraic theory, you need the monoidal structure on $\mathcal{E}$ to be actual categorical product $\times$.

There are many well-known equivalent definitions of "finitary algebraic theory": clone, Lawvere theory, finitary monad on $\mathbf{Set}$, etc, or the classical definition from universal algebra (modulo choice of presentation). The definition I'm implicitly referring to above is perhaps not so well-known, though it's simple enough. You can find the details in Definitions 2.3.1 and 2.3.2 of Miles Gould's thesis, and the equivalence to the other definitions is Theorem 2.3.12.

Finite order arithmetic and ETCS

2012-12-02T21:31:43Z

I'm looking for a reference to the statement that Lawvere's Elementary Theory of the Category of Sets (ETCS) is equal in proof-theoretic strength to finite order arithmetic. The person who informed me of this said it was well-known in certain circles, but he couldn't think of a reference.

Actually, all I need is a reference to one half of the equivalence: that anything provable in finite order arithmetic is provable in ETCS. The story: I've been looking at Colin McLarty's paper A finite order arithemetic foundation for cohomology, which shows that nothing stronger than finite order arithmetic is needed anywhere in EGA or SGA. I want to state that nothing stronger than ETCS is needed anywhere in EGA or SGA. To back that up with references, I therefore need something that relates ETCS to finite order arithmetic.

Edit This question has generated lots of discussion about McLarty's paper. I'm genuinely interested in that discussion, but I'd also like to emphasize that it's peripheral to my question, which is simply a reference request: where can I find it stated/proved that ETCS is equal in strength to finite order arithmetic?

Further edit Maybe I can make this question more transparent to experts in non-categorical set theory. ETCS is well-known to have the same strength as the membership-based theory known as "bounded Zermelo with choice" or "restricted Zermelo with choice". (One reference: Mac Lane and Moerdijk, Sheaves in Geometry and Logic, Section VI.10.) The axioms are extensionality, empty set, pairing, union, power set, foundation, restricted comprehension, infinity, and choice. Here "restricted comprehension" means that we only consider formulas that are restricted in the sense that all quantifiers are of the form "$\forall x \in y$" or "$\exists x \in y$".

Answer by Tom Leinster for expository papers related to quantum groups

2012-12-03T02:49:01Z

You might enjoy the short book by Ross Street: Quantum groups: a path to current algebra (Cambridge University Press, 2007).

Answer by Tom Leinster for When do Kan extensions preserve limits/colimits?

2012-11-12T02:42:15Z

$F$ preserving colimits doesn't imply that $\text{Lan}_Y(F)$ preserves colimits, even if all the categories are cocomplete.

Consider, for example, the case $C = D$ and $F = 1_C$. Then the left Kan extension $\text{Lan}_Y(1_C)$ exists if and only if $Y$ has a right adjoint, and if it does exist, it is the right adjoint of $Y$. (This is Theorem X.7.2 of Categories for the Working Mathematician.) Of course, $1_C$ preserves colimits, but right adjoints usually don't.

(From your notation, I guess you're generalizing from the case where $P$ is the category of Presheaves on $C$ and $Y$ is the Yoneda embedding. In that case, as I bet you know, $\text{Lan}_Y(F) = - \otimes F$ not only preserves colimits but has a right adjoint.)

Answer by Tom Leinster for Topics for an Undergraduate Expository Paper in Number Theory

2012-09-25T21:05:19Z

Several times, I've supervised a project on perfect numbers. For a start, the students can prove the classification theorem for even perfect numbers. They can also look up and state the known results on odd perfect numbers, and/or do stuff on multiplicative functions.

I don't know whether this is at the right level for the students you have. Maybe it's too elementary. But for the students I had, I thought it worked well.

Square roots of the Laplace operator

2012-05-07T22:07:22Z

In several places in the literature (e.g. this paper of Caffarelli and Silvestre), I've seen an integral formula for fractional Laplacians. I'd like to understand it. In this question, I'll stick to the case of the square root.

The formula I've seen is this: $$((-\triangle)^{1/2}f)(x)= C_n \int_{\mathbb{R}^n}\frac{f(x) - f(y)}{\|x - y\|^{n + 1}}\ dy. $$ Here $x \in \mathbb{R}^n$ and $C_n$ is a constant. Also, $f$ is a function $\mathbb{R}^n \to \mathbb{R}$, but I'm not sure what regularity assumptions it's supposed to satisfy.

For this notation to be justified, it must surely be the case that $$ (-\triangle)^{1/2} \bigl((-\triangle)^{1/2} f\bigr) = -\triangle f $$ for all nice enough $f$. My question is: why? I haven't been able to prove this identity even in the case $n = 1$.

Comments

It's clearly the case that the Laplace operator has a square root defined by $$ \widehat{((-\triangle)^{1/2}f)}(\xi) = \|\xi\| \hat{f}(\xi). $$ The paper linked to says that this operator $(-\triangle)^{1/2}$ is the same as the operator $E$ defined by the integral formula. If I'm understanding correctly, proving this is equivalent to proving (i) that $E$ really is a square root of the Laplacian, and (ii) that $E$ is a positive operator on functions of compact support.
I've seen a couple of references to Landkof's 1972 book Foundations of Modern Potential Theory. Unfortunately, those citing Landkof's book don't say which part of the book they're referring to, and I've been unable to find the relevant part myself. I'd be happy for someone to simply tell me where in that book to look.
I can see that the integral formula has something to do with Laplacians. Switching to spherical coordinates, the formula is $$ ((-\triangle)^{1/2}f)(x) = \text{const}\cdot\int_0^\infty \frac{\int_{S^{n-1}} f(x + ru)\ du - f(x)}{r^2}\ dr $$ where $du$ is surface area measure on $S^{n-1}$ normalized to a probability measure. The integrand converges to $(\triangle f)(x)$ as $r \to 0$ (up to a constant factor). Also, the integrand is identically zero if $f$ is harmonic, which is promising.

Answer by Tom Leinster for What do we call a set that has one or fewer elements?

2012-09-20T10:50:52Z

In category theory, subobjects of the terminal object are sometimes called subterminal. An equivalent definition: an object $A$ is subterminal if and only if for all objects $B$, there is at most one map $B \to A$. (Note that in the case where the category is $\mathbf{Set}$ and $B = 1$, this says exactly that $A$ has at most one element.) The sets you mention are the subterminal sets.

(But still, if I was writing a paper in which I only mentioned such sets a handful of times, I'd probably just say "sets with at most one element".)

Answer by Tom Leinster for A characterisation of Boolean algebras

2012-08-30T00:28:35Z

Edit: Patricia Hersh points out in the comments that I didn't prove it was a Boolean algebra: I only showed that it was a complemented lattice. But maybe this fragment is useful, so I'll leave it here.

Write $M^{\mathrm{op}}$ for $M$ with the reverse ordering. Since the negation map $a \mapsto -a$ is an order-reversing involution, it defines an isomorphism $M^\mathrm{op} \to M$. But $M$ is a meet-semilattice with least element, so $M$ is also a join-semilattice with greatest element. Hence $M$ is a lattice (bounded, if that's not already in your definition of "lattice"). Moreover, the isomorphism $a \mapsto -a$ interchanges joins and meets, i.e. the de Morgan laws hold.

Taking $b = -a$ in your condition, we have $a \wedge (-a) = 0$ for all $a$. But by the de Morgan laws, we also have the dual of your condition: $a \vee b = 1$ if and only if $-b \leq a$. Taking $a = -b$ in this dual condition gives $(-b) \vee b = 1$ for all $b$, as required.

There are two slightly different notions of ultraproduct. Why is one said to be better than the other?

2012-08-24T17:01:39Z

Let $I$ be a set and $\mathcal{U}$ an ultrafilter on $I$. Let $(X_i)_{i \in I}$ be an $I$-indexed family of sets. The ultraproduct of the family $(X_i)$ with respect to $\mathcal{U}$ is, everyone agrees, another set. But which set is it? There are two different definitions, and they sometimes give different results.

For the sake of discussion, I'll call them "Type 1" and "Type 2" ultraproducts.

Type 1 $\ $ The type 1 ultraproduct of $(X_i)_{i \in I}$ with respect to $\mathcal{U}$ is $$ \Bigl( \prod_{i \in I} X_i \Bigr) \Bigl/ \sim $$ where $$ (x_i)_{i \in I} \sim (x'_i)_{i \in I} \iff \{ i \in I: x_i = x'_i \} \in \mathcal{U}. $$

Type 2 $\ $ View the poset $(\mathcal{U}, \subseteq)$ as a category. The type 2 ultraproduct of $(X_i)_{i \in I}$ with respect to $\mathcal{U}$ is the colimit of the functor $(\mathcal{U}, \subseteq)^{\text{op}} \to \mathbf{Set}$ defined on objects by $$ J \mapsto \prod_{j \in J} X_j $$ and on maps by projection. Explicitly, then, the Type 2 ultraproduct is $$ \Bigl( \coprod_{J \in \mathcal{U}} \prod_{j \in J} X_j \Bigr) \Bigl/ \approx $$ where $$ (x_j)_{j \in J} \approx (x'_k)_{k \in K} \iff \{ i \in J \cap K: x_i = x'_i \} \in \mathcal{U}. $$

The difference $\ $ The two types of ultraproduct are the same if either none of the sets $X_i$ are empty or almost all of them are empty. But in the remaining case, where at least one $X_i$ is empty but the set of such $i$ is not large enough to belong to $\mathcal{U}$, they're different: the Type 1 ultraproduct is empty but the Type 2 ultraproduct is not.

The question $\ $ I've read in a couple of texts (both coming from the point of view of categorical logic) that the Type 2 ultraproduct is really the right one. But why? On what criteria is Type 2 judged to be better than Type 1?

A vague guess at an answer $\ $ I think I can guess very roughly what's going on. There's been a tradition in logic — maybe dying out now? — of taking all structures to be nonempty by definition. But when you move to the more general setting of categorical logic, that's no longer a satisfactory approach. Although in the category of sets, there's just a single object with no elements, in many other categories, there are lots of interesting objects with no (global) elements: e.g. there are lots of interesting sheaves with no global sections.

So categorical logic sometimes involves a recasting of classical, set-based logic, in order to handle empty sets/types satisfactorily. I imagine that something of the sort is going on here. (I only defined ultraproducts of sets, but you could of course define ultraproducts of objects of any other sufficiently complete category.) But still, I don't see clearly why Type 2 is the right choice.

See also This question of Joel David Hamkins, and its responses.

Answer by Tom Leinster for There are two slightly different notions of ultraproduct. Why is one said to be better than the other?

2012-08-25T13:02:24Z

Michael Barr pointed out one thing that goes wrong if you try to use the type 1 definition when some of the sets involved are empty. Now that I understand this issue better, I'll point out a couple of other things that go wrong. They're both of the form "this theorem holds cleanly for type 2 ultraproducts, but for type 1 you have to make exceptions".

I'll use the standard notation for the ultraproduct of $(X_i)_{i \in I}$ with respect to an ultrafilter $\mathcal{U}$ on $I$: $$ \Bigl( \prod_{i \in I} X_i \Bigr) \bigl/ \mathcal{U} $$ (for either of the two definitions). The notation makes more sense for type 1 than type 2, but never mind.

(1) Ultraproduct with respect to a principal ultrafilter is projection. That is, if $k \in I$ and $\mathcal{U}$ is the principal ultrafilter on $k$ then $(\prod X_i)/\mathcal{U} = X_k$. This is true without exception for type 2 ultraproducts. It is almost true for type 1, but fails if $X_k \neq \emptyset$ and $X_i = \emptyset$ for some $i \neq k$.

(2) Ultraproducts preserve finite coproducts. That is, writing $+$ for the coproduct (disjoint union) of sets, $$ \Bigl( \prod_{i \in I} (X_i + Y_i) \Bigr) \bigl/ \mathcal{U} \cong \Bigl( \prod_{i \in I} X_i \Bigr) \bigl/ \mathcal{U} + \Bigl( \prod_{i \in I} Y_i \Bigr) \bigl/ \mathcal{U} $$ for any families of sets $(X_i)$ and $(Y_i)$. This is true without exception for type 2 ultraproducts (using the fact that these are ultra$\mbox{}$filters). But again, it isn't quite true for type 1: it can fail when some of the sets are empty. For example, let $I$ be a set, choose any nonempty proper subset $J$ of $I$, and put $$ X_i = \begin{cases} 1 &\text{if } i \in J\\ \emptyset &\text{otherwise} \end{cases} \qquad\ \qquad Y_i = \begin{cases} \emptyset &\text{if } i \in J\\ 1 &\text{otherwise,} \end{cases} $$ where $1$ denotes a one-element set. Then according to the type 1 definition, $(\prod(X_i + Y_i))/\mathcal{U} = 1$ but $(\prod X_i)/\mathcal{U} + (\prod Y_i)/\mathcal{U} = \emptyset$.

I guess all of these things that go wrong are intimately related to Łoś's theorem, which Michael alluded to.

Where is number theory used in the rest of mathematics?

2012-03-09T14:50:53Z

Where is number theory used in the rest of mathematics?

To put it another way: what interesting questions are there that don't appear to be about number theory, but need number theory in order to answer them?

To put it another way still: imagine a mathematician with no interest in number theory for its own sake. What are some plausible situations where they might, nevertheless, need to learn or use some number theory?

Edit It was swiftly pointed out by Vladimir Dotsenko that the borders between number theory and algebraic geometry, and between number theory and algebra, are long and interesting. One could answer the question in many ways by naming features on that part of the mathematical landscape. But I'd be most interested in hearing about uses for number theory that aren't so obviously near the borders of the subject.

Background In my own work, I often find myself needing to learn bits and pieces of other parts of mathematics. For instance, I've recently needed to learn new bits of analysis, algebra, topology, dynamical systems, geometry, and combinatorics. But I've never found myself needing to learn any number theory.

This might very well just be a consequence of the work I do. I realized, though, that (independently of my own work) I knew of no good answer to the general question in the title. Number theory has such a long and glorious history, with so many spectacular achievements and famous results, that I thought answers should be easy to come by. So I was surprised that I couldn't think of much, and I look forward to other people's answers.

Answer by Tom Leinster for functors unique up to self-equivalence of the source category

2012-08-18T16:24:04Z

In short, this is equivalence of objects in the weak slice 2-category $\mathbf{CAT}/T$.

First recall the classical notion of slice category: given any category $\mathcal{C}$ and object $C$, there's a category $\mathcal{C}/C$ (called $\mathcal{C}$ sliced over $C$) whose objects are the maps in $\mathcal{C}$ with codomain $C$ and whose maps are commutative triangles.

When $\mathcal{C}$ is a 2-category, you can make the same sort of definition (so that any object $C$ of $\mathcal{C}$ gives rise to a slice 2-category $\mathcal{C}/C$), but you now have a choice to make. The objects of $\mathcal{C}/C$ are defined as before, but you could ask for the 1-cells in $\mathcal{C}/C$ to be strictly commutative triangles, or triangles that commute up to a specified invertible 2-cell, or triangles that commute up to a specified not-necessarily-invertible 2-cell (and then you have to decided which way it points). In all cases, there's an obvious way to define the 2-cells of $\mathcal{C}/C$.

Let's take the "weak" or "pseudo" version of $\mathcal{C}/C$, in which the 1-cells are triangles that commute up to a specified invertible 2-cell. Take two objects of $\mathcal{C}/C$, say $h\colon D \to C$ and $h'\colon D' \to C$. In any 2-category, there's a notion of equivalence of objects. In this case, $h$ and $h'$ are equivalent in $\mathcal{C}/C$ if and only if there's an equivalence $s\colon D \to D'$ in $\mathcal{C}$ such that $h' \circ s \cong h$.

Applied to $\mathcal{C} = \mathbf{CAT}$, this gives the notion of "weak equivalence" you mention. (It just so happens that in your setting, the domains of $H$ and $H'$ are equal.)

What are the algebras for the double dualization monad?

2012-08-15T17:03:07Z

Let $k$ be a field, and let $\mathbf{Vect}$ denote the category of vector spaces (possibly infinite-dimensional) over $k$. Taking duals gives a functor $(\ )^*\colon \mathbf{Vect}^{\mathrm{op}} \to \mathbf{Vect}$.

This contravariant functor is self-adjoint on the right, since a linear map $X \to Y^*$ amounts to a bilinear map $X \times Y \to k$, which is essentially the same thing as a bilinear map $Y \times X \to k$, which amounts to a linear map $Y \to X^*$ . It therefore induces a monad $(\ )^{**}$ on $\mathbf{Vect}$.

What are the algebras for this monad?

Remarks

I assume this is known (probably since a long time ago).
The first paper I came across when searching for the answer was Anders Kock, On double dualization monads, Math. Scand. 27 (1970), 151-165. I'm pretty sure it doesn't contain the answer explicitly, but it's possible that it contains some results that would help.
The monad isn't idempotent (that is, the multiplication part of the monad isn't an isomorphism). Indeed, take any infinite-dimensional vector space $X$. Write our monad as $(T, \eta, \mu)$. If $\mu_X$ were an isomorphism then $\eta_{TX}$ would be an isomorphism, since $\mu_X \circ \eta_{TX} = 1$. But $\eta_{TX}$ is the canonical embedding $TX \to (TX)^{**}$, and this is not surjective since $TX$ is not finite-dimensional.
There's another way in which the answer might be somewhat trivial, and that's if $(\ )^*$ is monadic. But it doesn't seem obvious to me that $(\ )^*$ even reflects isomorphisms (which it would have to if it were monadic).
There's a sense in which answering this question amounts to completing the analogy:

sets are to compact Hausdorff spaces as vector spaces are to ?????

Indeed, the codensity monad of the inclusion functor (finite sets) $\hookrightarrow$ (sets) is the ultrafilter monad, whose algebras are the compact Hausdorff spaces. The codensity monad of the inclusion functor (finite-dimensional vector spaces) $\hookrightarrow$ (vector spaces) is the double dualization monad, whose algebras are... what? (Maybe this will help someone to guess what the answer is.)

Answer by Tom Leinster for Is every functor a composition of adjoint functors?

2012-08-16T14:55:25Z

Here's a really trivial way to see that the answer is "no": a functor from the empty category to a nonempty category is never a composite of adjoints (since a functor from the empty category to a nonempty category is never an adjoint).

How is the Julia set of $fg$ related to the Julia set of $gf$?

2012-01-02T12:58:21Z

Let $f$ and $g$ be complex rational functions (of degree $\geq 2$ if that helps). What can be said about the relationship between $J(fg)$ and $J(gf)$, the Julia sets of the composite functions $f \circ g$ and $g \circ f$?

If I'm not mistaken, $f$ restricts to a map $J(gf) \to J(fg)$, and $g$ restricts to a map $J(fg) \to J(gf)$. So $J(fg)$ and $J(gf)$ surject onto each other in a particular way (and, indeed, in a way that commutes with the actions of $fg$ on $J(fg)$ and $gf$ on $J(gf)$). Since Julia sets are completely invariant, the restricted map $f: J(gf) \to J(fg)$ is $deg(f)$-to-one, and similarly the other way round.

So there's some kind of relationship between the two sets.

If $f$ or $g$ has degree one then $J(fg)$ and $J(gf)$ are "isomorphic", in the sense that there's a Möbius transformation carrying one onto the other. Thus, the simplest nontrivial example would be to take $f$ and $g$ to be of degree 2. I don't know a way of computing, say, the example $f(z) = z^2$ and $g(z) = z^2 + 1$. That would mean computing the Julia sets of $gf(z) = z^4 + 1$ and $fg(z) = z^4 + 2z^2 + 1$.

My question isn't completely precise, I'm afraid. But here are some of the things that I would value in an answer: theorems on what $J(fg)$ and $J(gf)$ have in common, examples showing how different they can be, pictures of $J(fg)$ and $J(gf)$ for particular functions $f$ and $g$, and references to where I can find out more (especially those accessible to a non-specialist). Thanks.

Answer by Tom Leinster for Do you use the Mathematics Subject Classification (MSC) when searching for literature?

2012-05-11T15:43:14Z

No. It never occurs to me to use the MSC when searching, and I don't know why I'd want to use it rather than search for specific terms.

When I have to list MSC codes for my own publications, I often find that they don't seem to fit very well. I'm sure I couldn't design a better classification, but as a search tool it seems to me to have outlived its usefulness. Maybe there are other uses.

(For comparison, which is better: a system where you type "guacamole recipe" into a search engine, or a system where you first learn that 381798.45 is the Thing Subject Code for "Mexican food", then browse the list of all web pages with code 381798.45?)

Answer by Tom Leinster for What are the benefits of viewing a sheaf from the "espace étalé" persepctive?

2012-05-07T21:26:54Z

Let me expand on Yosemite Sam's comment. Pullbacks are indeed easier to define if you view a sheaf as a local homeomorphism. On the other hand, pushforwards are easier to define if you view a sheaf as a set-valued functor.

Suppose we have a continuous map $f: X \to Y$ of topological spaces.

Given a sheaf $F$ on $Y$, viewed as a local homeomorphism $\pi: F \to Y$, we can simply pull $\pi$ back along $f$ to obtain a map into $X$; it is easily shown to be a local homeomorphism too. This is the pullback sheaf $f^* F$.

On the other hand, given a sheaf $E$ on $X$, viewed as a functor $\mathrm{Open}(X)^{op} \to \mathbf{Set}$ (where $\mathrm{Open}(X)$ is the poset of open subsets of $X$), we can simply compose $E$ with the functor $\mathrm{Open}(Y) \to \mathrm{Open}(X)$ that takes inverse images along $f$. This gives a set-valued functor on $\mathrm{Open}(Y)$; it is easily shown to be a sheaf too. This is the pushforward sheaf $f_* F$.

So, there are advantages to proving the equivalence between the two definitions early on.

Answer by Tom Leinster for Sheafification - Why does twice suffice?

2012-05-01T21:37:12Z

"Why" questions can often be answered in multiple ways; I'll give an answer that's different from the other good comments and answers that you've already had.

Sheaves are the first rung on an infinite ladder of concepts. The next rung is "stack". A stack is something like a "sheaf of categories", but there are added complications. A typical example of a stack on a topological space $X$ is the assignment $U \mapsto Sh(U)$, sending each open subset $U \subseteq X$ to the category $Sh(U)$ of sheaves on $U$. Sheaves on subsets of $X$ can be patched together, not quite uniquely, but uniquely up to canonical isomorphism. From this, you can work out what the definition of stack must be. This appears as an exercise somewhere in Mac Lane and Moerdijk.

After stacks, there are 2-stacks (something like sheaves of 2-categories), 3-stacks, and so on. (According to this terminological scheme, stacks are 1-stacks and sheaves are 0-stacks.) And just as sheaves are presheaves satisfying certain conditions, $n$-stacks are "$n$-prestacks" satisfying certain conditions.

The point now is that "twice suffices" fits into a larger pattern. For stacks, you need to apply (a version of) the plus construction three times. For 2-stacks, you need to apply it four times. In general, for $n$-stacks, you need to apply it $n+2$ times.

(I confess that this is something I've only heard in conversation, I believe from Andrew Kresch. I don't know the details.)

Answer by Tom Leinster for The deep significance of the question of the Mandelbrot set's local connectedness?

2012-05-01T22:43:38Z

I don't know enough to give a detailed answer, but I can at least give a reference: Milnor's book Dynamics in One Complex Variable (Vieweg). You can find an early draft here. Appendix F mentions a couple of conjectures that would follow from MLC: see the footnote on page F-2 in the linked pdf file.

While I'm at it, I can't resist repeating one of my favourite mathematical stories ever, which concerns the connectedness of the Mandelbrot set. It is connected, as you'd guess from the picture, but because of the thin filaments involved, this is not obvious if your image is too low-resolution. So there was some confusion in the early days. I'll let Milnor (Appendix F) take up the story:

Mandelbrot made quite good computer pictures, which seemed to show a number of isolated "islands". Therefore, he conjectured that [the Mandelbrot set] has many distinct connected components. (The editors of the journal thought that his islands were specks of dirt, and carefully removed them from the pictures.)

Answer by Tom Leinster for Essential reads in the philosophy of mathematics and set theory

2012-04-18T09:53:48Z

David Corfield's Towards a Philosophy of Real Mathematics is an excellent read, and also likely to stretch you mathematically. It takes up the theme mentioned in Andrej's answer: mathematics is a great deal more than set theory, so philosophy of mathematics should be a great deal more than philosophy of set theory. (But I understand that you're specifically interested in philosophy of set theory, and of course there's nothing wrong with that.)

Comment by Tom Leinster

2013-05-09T13:37:21Z

Another apposite phrase: If it walks like a duck and quacks like a duck, it probably is a duck. What the proof of the Yoneda lemma reveals is that the best judge of whether something's a duck is a duck.

Comment by Tom Leinster

2013-05-08T17:01:28Z

SuperDave, your questions aren't appropriate for this site and are likely to be closed soon. The FAQ has suggestions for other sites that might suit your purposes.

Comment by Tom Leinster

2013-05-07T19:32:34Z

PS to Butch: I'll acknowledge you when I update the paper for which I needed this, arxiv.org/abs/1209.3606. Forgive the impertinence, but is Butch Malahide your real name? Feel free to contact me by email. (I'd contact you myself, but there's no address on your profile.)

Comment by Tom Leinster

2013-05-07T19:29:06Z

Excellent. Thanks very much. For the sake of precision, let me add that they don't quite do the case $n=3$ in the sense described in my question. They do show that if a set $\mathcal{U}$ of subsets of $X$ satisfies the partition condition for all $n\leq 3$, then $\mathcal{U}$ is an ultrafilter. But they seem not to observe that it suffices to require it for $n=3$ (which implies it for $n=0,1,2$). Quite possibly they knew it but just didn't think it was worth mentioning.

Comment by Tom Leinster

2013-02-25T23:01:38Z

Nice! Thanks. Nevertheless, the "trick" aspect of it means that it doesn't entirely satisfy me: what I want is to get an intuitive picture in my head which makes the result seem obvious (just as for the isoperimetric inequality). @Noah: I suspect the uniqueness part can't be extended to arbitrary real weights too easily. Indeed, in the introduction to their book Inequalities, Hardy, Littlewood and Pólya comment on this limitation of such rational-approximation arguments.

Comment by Tom Leinster

2013-02-25T13:07:19Z

Thanks. Fixed.

Comment by Tom Leinster

2013-01-29T02:22:27Z

This article comes from the excellent Princeton Companion to Mathematics. If you (profiles117...) can get hold of a copy, you might enjoy browsing it. Certainly it's pitched at a level significantly higher than you're likely to be used to. Nevertheless, you might find that it gives you an impression of what the wide world of mathematics looks like.

Comment by Tom Leinster

2013-01-25T17:17:02Z

Hello Mehrpooya. At the moment, your question isn't suitable for this site. Please have a look at some other questions here, and you'll see what the problem is: you need to make it much more specific. Please also read the FAQ. You can edit your question to improve it.

Comment by Tom Leinster

2013-01-22T17:36:49Z

Ah, maybe I can guess: an equivalence relation, viewed as a groupoid?

Comment by Tom Leinster

2013-01-22T17:18:59Z

Nice answer, but what is a "setoid"?

Comment by Tom Leinster

2013-01-21T00:26:48Z

@François: re whether mathematicians act as if functions come equipped with codomains, I think this varies from subject to subject. One subject where codomains are crucial is algebraic topology. For example, suppose we construe the circle $S^1$ as a subset of the plane $\mathbb{R}^2$. The identity $S^1 \to S^1$ definitely has to be distinguished from the inclusion $S^1 \to \mathbb{R}^2$, since when you pass to first homology, the former gives an isomorphism but the latter gives $\mathbb{Z} \to 0$, which isn't even injective.

Comment by Tom Leinster

2013-01-17T01:48:43Z

Thanks for the explanation, Yemon. I agree, it does seem to be a very open-ended question, maybe too much so.

Comment by Tom Leinster

2013-01-16T23:35:20Z

English fixed (correctly, I hope: I hadn't even heard of AW*-algebra).

Comment by Tom Leinster

2013-01-15T23:54:46Z

Kind of off topic, but: why do people so often say "unique minimal element" when "least element" is shorter and (I would say) more vivid? They're the same, at least under the axiom of choice. But undeniably, the definition of local ring is phrased in terms of a "unique maximal (proper) ideal" waaay more often than "largest (proper) ideal". Why?

Comment by Tom Leinster

2013-01-15T00:38:43Z

Anyone who's ever been single knows the phenomenon whereby everyone else in the room is a couple. But I've never heard anyone say they liked that.