User owen biesel - MathOverflow

Answer by Owen Biesel for Probability and events

2012-09-29T16:12:15Z

I'll interpret "most likely" as Maximum Likelihood Estimation, that is, given some observations, what is the value of $p$ that makes the probability of those observations the largest. For example, if we observe something occurring $0$ out of $n$ times, the maximum likelihood estimate for $p$ is $0$, because that gives our observations a probability of $1$. This is only unreasonable if you have some prior information about $p$ (such as "it's probably around $0.5$, but maybe a little higher or lower" or "it's very close to either $1$ or $0$, but I don't know which").

Suppose we run $n$ trials, and find that the event occurred $n$ times, and we assume that each trial is independent with the same probability $p$ of success. Then the probability of our observation is $$P(p) = {n \choose m} p^m (1-p)^{n-m},$$ since the probability of each of the $m$ successes is $p$, the probability of the $n-m$ failures is $1-p$, and there are ${n\choose m}$ ways for $m$ of the $n$ trials to be the successful trials. Assuming $m$ and $n-m$ are both nonzero, this probability vanishes when $p=0$ or $1$, so the maximizing value of $p$ will be somewhere in between. Then we can find this maximizing value of $p$ by taking the derivative of $P$ and setting the result equal to $0$. We can take the derivative: $$P'(p) = {n\choose m} \left[mp^{m-1}(1-p)^{n-m} - (n-m)p^m(1-p)^{n-m-1}\right]$$ $$ = {n\choose m} \left[m(1-p) - (n-m)p\right]p^{m-1}(1-p)^{n-m-1}$$ This vanishes when $m(1-p)-(n-m)p=0$, i.e. when $m = np$ or $p = m/n$.

So if you have no prior information about what $p$ should be, but you observe $m$ successes in $n$ independent trials, the value of $p$ that best matches your observation is $p=m/n$.

Answer by Owen Biesel for Is the following invariant of rooted trees a complete invariant?

2012-09-22T22:22:21Z

This is not a complete answer, but there is a nice description of the information in $P_T$ which may prove useful to someone else.

First of all, I will define a slightly different polynomial $\tilde P_Z(T)$: Grafting works the same way, but if $T'$ is the leafing of $T$, then I define $\tilde P_{T'}(z)= z\tilde P_T(z)+1$. It's an easy proof by recursion that $\tilde P_T(z) = P_T(z-1)$, so this new polynomial determines $T$ just as well or poorly as yours.

By "node" of $T$, I mean a vertex of $T$ other than its root, and by "subtree" $T'$ of $T$, I mean a subgraph of $T$, such that for every node of $T$ included in $T'$, the node's parent and the edge to it are also included in $T'$. [Edit: These are non-standard uses of those words.] Then the coefficient of $z^n$ in $\tilde P_T(z)$ is the number of $n$-node subtrees of $T$. This is because, for $n>0$, choosing an $n$-node subtree of the leafing of $T$ is the same as choosing an $(n-1)$-node subtree of $T$, and for any $n$, choosing an $n$-node subtree of the grafting of $T$ and $T'$ is the same is choosing a $k$-node subtree of $T$ and an $(n-k)$-node subtree of $T'$ for some $k$ between $0$ and $n$.

Some consequences include:

If $T$ has $n$ nodes (vertices other than the root), then the highest-order term of $\tilde P_T(z)$ is $z^n$.
The coefficient of $z$ in $\tilde P_T(z)$ is the degree of the root of $T$.
If $T$ has $a$ nodes at distance $1$ from the root, and $b$ nodes at distance $2$, then the coefficient of $z^2$ in $\tilde P_T(z)$ is ${a \choose 2}+ b$.
If $T$ has a total of $n$ nodes, then the coefficient of $z^{n-1}$ is the number of leaves of $T$ (nodes with degree 1).

Hence if $\tilde P_T(z)=\tilde P_{T'}(z)$, then $T$ and $T'$ have the same numbers of vertices and leaves, their roots have the same degrees, and they have the same total number of vertices at distance $2$ from the root. It seems that more should be true, but I haven't proven any more.

Edit: I've now proved the following result: if $T$ and $T'$ are graphs whose nodes are distance at most $2$ from the root, and such that $\tilde P_T(z) = \tilde P_{T'}(z)$, then $T\cong T'$.

Proof: A rooted tree of depth at most $2$ corresponds to a sequence of natural numbers $b_1, b_2, \ldots, b_a$, where $a$ is the number of children of the root, and $b_i$ is the number of children of the $i$th child of the root. Then $$ \tilde P_{T}(z) = \prod_{i=1}^a (z(z+1)^{b_i} + 1)$$ $$ = \prod_{i=1}^a \left(1+{b_i\choose 0}z + {b_i\choose 1}z^2 + \ldots + {b_i\choose k}z^{k+1} + \ldots + {b_i\choose b_i-1}z^{b_i} + {b_i\choose b_i}z^{b_i+1}\right) $$ I show that $\tilde P_T(z)$ determines the $b_i$ up to reordering, and hence $T$ up to isomorphism.

First, note that knowing the $b_i$ up to reordering is the same as knowing the elementary symmetric polynomials in the $b_i$, because they are the solutions of $\prod_{i=1}^a(x-b_i)=0$. Or equivalently, by Newton's identities, that information is contained in the sums $\sum_{i=1}^a b_i^k$ for all $k\geq 0$. In turn, knowing the $\sum_{i=1}^a b_i^k$ for $k$ up to $n$ is the same as knowing the $\sum_{i=1}{b_i\choose k}$ for $k$ up to $n$, through simple linear identities relating the two sets of data.

Now I show that $\tilde P_T(z)$ does determine each $\sum_{i=1}^a {b_i\choose k}$ for $k \geq 0$, by induction on $k$. Suppose we know that $\tilde P_T(z)$ determines $\sum_{i=1}^a {b_i\choose k}$ for $0\leq k < n$, and now consider the coefficient of $z^{n+1}$. There is a contribution from each partition $n+1 = \lambda_1+\lambda_2+\ldots+\lambda_m$ of $n+1$, given by $$\sum_{i_1,\ldots,i_m\text{ distinct}}\left(\prod_{j=1}^m {b_i\choose \lambda_i-1}z^{\lambda_i}\right)=\left(\sum_{i_1,\ldots,i_m\text{ distinct}}\prod_{j=1}^m {b_i\choose \lambda_i-1}\right)z^{n+1}.$$ Considering the term in parentheses on the right-hand side as a polynomial in the $b_i$, note that it is symmetric in the $b_i$ and has degree $\sum_{j=1}^m(\lambda_j-1) = (n+1)-m< n$ if $m>1$. Hence such contributions are expressible in terms of the $\sum_{i=1}^a {b_i\choose k}$ for $0\leq k < n$, and so can be deduced from $\tilde P_T(z)$ by the induction hypothesis, unless the partition is simply $n+1=(n+1)$, in which case the resulting term is $\sum_{i=1}^a{b_i\choose n}z^{n+1}$. Therefore the coefficient of $z^{n+1}$ in $\tilde P_T(z)$ differs predictably from $\sum_{i=1}^a {b_i\choose n}$, so the latter is deducible from $\tilde P_T(z)$ as well.

Knowing the $\sum_{i=1}^a {b_i\choose k}$ for all $k$, we can work backwards: first we inductively deduce the $\sum_{i=1}^a b_i^k$, from which Newton's identities tell us the values of the elementary symmetric polynomials evaluated at the $b_i$. Then we recover the simplified form of $\prod_{i=1}^a (x-b_i)$, and the $b_i$ are its roots.

For example: If $\tilde P_T(z) = z^4 + 3z^3 + 3z^2 + 2z + 1$ and we know $T$ has no nodes of distance more than $2$ from the root, then we can recover $T$ as follows. The coefficient of $z$ is $a=2$, so we are trying to find $b_1$ and $b_2$ such that $$P_T(z) = (z(z+1)^{b_1} + 1)(z(z+1)^{b_2} + 1).$$ The coefficient of $z^2$ is ${a\choose 2} + (b_1+b_2) = 1 + (b_1+b_2) = 3$, so $b_1+b_2 = 2$. And the coefficient of $z^3$ is ${a\choose 3} + \sum_{i\neq j} b_i + \sum_i {b_i\choose 2} = (0) + (b_1+b_2) + \left({b_1\choose 2} + {b_2\choose 2}\right) = 2 + {b_1\choose 2} + {b_2\choose 2} = 3$, so ${b_1\choose 2} + {b_2\choose 2} = 1$. Hence $\frac{b_1^2-b_1}{2} + \frac{b_2^2-b_2}{2} = \frac{(b_1^2 + b_2^2) - (b_1 + b_2)}{2} = \frac{(b_1^2 + b_2^2) - 2}{2} = 1$, so $b_1^2 + b_2^2 = 4$. Therefore $b_1b_2 = \frac{(b_1 + b_2)^2 - (b_1^2 + b_2^2)}{2} = \frac{2^2 - 4}{2} = 0$, so $b_1$ and $b_2$ are the roots of $$x^2 - (b_1+b_2)x + (b_1b_2) = x^2 - 2x.$$ Therefore $b_1$ and $b_2$ are $0$ and $2$, up to reordering, so $T$ is the tree whose root has $a=2$ children, one of which has $0$ children, and the other of which has $2$.

When is this diagram of tensor powers an equalizer?

2012-09-01T21:41:57Z

Let $A$ be a commutative ring with $1$, and $B\subseteq A$ be a subring.

Is there a simple condition on $B$ and $A$ guaranteeing that $B\to A\rightrightarrows A\otimes_B A$ is an equalizer?
In other words, when does $a\otimes_B 1 = 1\otimes_B a$ imply that $a\in B$?

This always holds, for example, if $B=K$ is a field and $A=L$ is a finite separable extension of $K$. For then, if $\ell\otimes 1 = 1\otimes \ell$ in $L\otimes_K L$, the same clearly holds in $\bar K\otimes_K L$, where $\bar K$ is a separable closure of $K$ containing $L$. But the $\bar K$-algebra homomorphism $\bar K\otimes_K L\to \bar K^{\mathrm{Hom}_K(L,\bar K)}$ sending $\alpha\otimes\ell\mapsto (\alpha\cdot s(\ell))_{s:L\to\bar K}$ is an isomorphism, and the equation becomes $\ell = s(\ell)$ for all $s:L\to \bar K$. But this means $\ell$ is fixed by the action of the absolute Galois group of $K$ (which acts transitively on the $s$), so $\ell\in K$.

Does the result hold for general $B$ and $A$? If not, is there a simple condition describing when it does hold? Or, failing that, is there a simpler proof in the case of a separable field extension, that doesn't need Galois theory?

Answer by Owen Biesel for Is there a notion of likelihood that incorporates information content?

2012-09-01T03:10:42Z

What you are missing is normalization: your likelihood functions $L(\theta|f,g)$ and $L(\theta|f)$ shouldn't be comparable, because adding up the likelihood for all the possible $\theta$s gives different totals. If you instead define
$\displaystyle L(\phi|x) = \frac{Pr[X=x|\phi]}{\sum_{\phi'} P[X=x|\phi']}$,
then you obtain equalities:

$\displaystyle L(\theta|f,g) = \frac{Pr[F=f, G=g|\theta]}{\sum_{\theta'} P[F=f, G=g|\theta']} = \frac{Pr[G=g|F=f]Pr[F=f|\theta]}{\sum_{\theta'} P[G=g|F=f]P[F=f|\theta']}$

$\displaystyle = \frac{Pr[F=f|\theta]}{\sum_{\theta'} P[F=f|\theta']} = L(\theta|f) $

To learn more, try searching for Bayesian Networks, especially "parameter learning."

Is 2 a zerodivisor in the ring parametrizing rank-n algebras?

2012-08-29T18:01:17Z

Let $n$ be a natural number; I am studying (commutative) rings $R$ and $R$-algebras $A$ such that $A\cong R^n$ as $R$-modules. There is a universal such algebra: a ring $R_0$ and a free, rank-$n$ $R_0$-algebra $A_0$, such that if $(R, A)$ is any other such pair, there is a ring homomorphism $R_0\to R$ making $A\cong R\otimes_{R_0} A_0$.

The construction is as follows: Let $R_0$ be the quotient of the polynomial ring

$\mathbb{Z}[\eta^i,\alpha_{ij}^k:i,j,k\in\{1,\ldots,n\}]$

by the ideal generated by elements of the form

$\alpha_{ij}^k-\alpha_{ji}^k$ ,
$\displaystyle\sum_{m=1}^n \alpha_{ij}^m \alpha_{km}^\ell - \sum_{m=1}^n\alpha_{ik}^m \alpha_{jm}^\ell$ , and
$\displaystyle\sum_{m=1}^n\alpha_{im}^j\eta^m - \delta_i^j$ , as $i,j,k,$ and $\ell$ range from $1$ to $n$.

Then $A_0$ is the $R_0$-algebra $R_0[x_1,\ldots,x_n]/(1-\sum_m\eta^mx_m, x_ix_j - \sum_m\alpha_{ij}^mx_m)$; the relations ensure that $\{x_1,\ldots,x_n\}$ is a free $R_0$-basis for $A_0$.

My question is:

Can 2 be a zerodivisor in $R_0$, for some value of $n$?

For technical reasons, this would turn an ugly, intractable calculation for general rank-$n$ algebras into a nice, tidy one. Any other information about $R_0$ (is it a domain? how would I tell?) would be appreciated.

Prime-like elements of rings

2012-08-18T18:13:04Z

An element $p$ of a commutative ring $R$ is called "prime" if, for any $a,b\in R$, whenever $ab$ is a multiple of $p$, either $a$ or $b$ is a multiple of $p$.

Is there a word for the "prime-like" property that, whenever $ab$ is a multiple of $p^2$, either $a$ or $b$ is divisible by $p$? Or another, more usual concept in ring theory that this is connected to?

I ask because the "prime-likeness" of $2$ in $R$ seems to control whether the quadratic formula can be made to work for monic polynomials over $R$ (as long as $2$ is also not a zero-divisor). This is because, if the discriminant of $x^2 + bx + c$ is a square $b^2 - 4c = d^2$, then $(-b+d)(-b-d) = 4c$, so at least one (and hence both) of $(-b+d)$ and $(-b-d)$ are multiples of $2$ in $R$. Their halves are the two roots of $x^2 + bx + c$.

For example, $2$ is "prime-like" in $\mathbb{Z}[\sqrt{2}]$, which is easy to verify elementarily. Hence a monic quadratic over $\mathbb{Z}[\sqrt{2}]$ factors iff its discriminant is a square. But $2$ is not "prime-like" in $\mathbb{Z}[\sqrt{5}]$, since $(\sqrt{5}-1)(\sqrt{5}+1) = 4$. And indeed, the discriminant of $x^2 -x-1$ is a square in $\mathbb{Z}[\sqrt{5}]$, but the polynomial doesn't factor there.

Why are free groups residually finite?

2010-04-06T03:53:59Z

Why is it that every nontrivial word in a free group (it's easy to reduce to the case of, say, two generators) has a nontrivial image in some finite group? Equivalently, why is the natural map from a group to its profinite completion injective if the group is free?

Apparently, this follows from a result of Malcev's that finitely generated matrix groups over an arbitrary commutative ring are residually finite, but is there a more easily accessible proof if we only want the result for free groups?

Generalizing the Fundamental Theorem of Symmetric Polynomials

2012-02-23T21:58:48Z

The fundamental theorem of symmetric polynomials tells us that the ring $\mathbb{Z}[x_1,\ldots,x_n]^{S_n}$ of symmetric polynomials in $n$ variables is generated (without relations) by the elementary symmetric polynomials $e_i(\bar{x})$, for $i$ between $1$ and $n$. I'm looking for a reference in the literature for a similar theorem in more variables, which should look something like this:

Consider the action of $S_n$ on $\mathbb{Z}[x_1,\ldots,x_n,y_1,\ldots,y_n]=\mathbb{Z}[\bar{x},\bar{y}]$ given by permuting the $x_i$ and the $y_i$ simultaneously. The fixed subring $\mathbb{Z}[\bar{x},\bar{y}]^{S_n}$ is generated by the elementary symmetric polynomials $e_i(\bar{m})$, where $m=m(x,y)$ is a monomial. (For example, if $m(x,y)=x^2y$, then $e_1(\bar{m}) = x_1^2y_1 + x_2^2y_2 + \ldots$.)

As an example, consider the $S_2$-invariant polynomial $(x_1+y_1)(x_2+y_2)$. It can be written as $(x_1+x_2)(y_1+y_2) - (x_1 y_1 + x_2 y_2) + (x_1x_2) + (y_1y_2)$, i.e. $e_1(\bar x)e_1(\bar y) - e_1(\overline{xy}) + e_2(\bar{x}) + e_2(\bar y)$.

I'd also be interested to know what the relations are in such a presentation of $\mathbb{Z}[\bar{x},\bar{y}]^{S_n}$. Certainly we can do better by excluding the monomials $x^m$ and $y^m$ for $m\geq 2$, as each such $e_i(\bar x^m)$ is already covered by the ordinary fundamental theorem. There also seem to be a handful of other relations around $i=n$, such as the observation that $e_n(\overline{xy}) = e_n(\bar x)e_n(\bar y)$, and possibly others.

Does $S$ being a free rank-$n$ $R$-algebra imply that $S/R$ is free rank $n-1$?

2012-02-20T19:53:37Z

Suppose we have a (commutative) ring $R$ and an $R$-algebra $S$. Furthermore, suppose that $S\cong R^n$ as $R$-modules, that is, $S$ is free of rank $n$ as an $R$-module. Can we always choose $1$ to be a basis element for $S$? Equivalently, is it necessary that $S/R \cong R^{n-1}$?

If not, how about in the case that $R=\mathbb{Z}$?

This is true in the case $n=1$: if we have a ring homomorphism $\phi: R\to S$ and an $R$-module isomorphism $\psi: S\to R^1$, it's not hard to show that $\phi$ must also be an isomorphism, making $S/R\cong R^0$.

And it is true if $n=2$ and $R=\mathbb{Z}$: in that case it is known that $S\cong \mathbb{Z}[x]/p(x)$, where $p$ is some degree 2 monic polynomial, so that in particular $S$ is generated freely as a $\mathbb{Z}$-module by 1 and $x$.

Answer by Owen Biesel for Comparing set relations

2012-02-14T15:48:10Z

If you're comparing two relations $R$ and $S$, try choosing a maximal relation $T$ such that $T$ is equivalent to a subrelation $T'$ of $R$ and to a subrelation $T''$ of $S$. Then let the "distance" $d(R,S)$ from $R$ to $S$ be the cardinality of $(R\setminus T')\cup (S\setminus T'')$ (i.e. $|R|+|S|-2|T|$); this defines a metric on the set of relations, and it is the number of ordered pairs you have to add and subtract from $R$ to get something equivalent to $S$.

Or if you would rather have a similarity "measure", try setting $\mu(R,S)=2|T|/(|R|+|S|)$, with $T$ as above. This equals 1 iff $|T|=|R|=|S|$, i.e. $R$ and $S$ are equivalent, and equals 0 iff $R$ and $S$ label nonoverlapping sets of objects.

[Edited for minor mistakes and to add the following:]

For phylogenetic trees, you might want something slightly different, as the relations you get have the following property: for the sets of objects picked out by any two distinct labels, either they are disjoint, or one is strictly contained in the other. Perhaps you wouldn't mind allowing two relations to be equivalent up to reordering of labels and deleting duplicate labels?

In that case, each of the steps in the following path are distance 1 and the trees on either end are distance 2 apart, which agrees more with intuition than the earlier prescription of distances 2, 3, and 3, respectively.

(Picture from John Baez's post on Operads and the Tree of Life, which discusses work done on the topological space of phylogenetic trees.)

Answer by Owen Biesel for Does $\bf pSet$ admit products?

2012-02-07T23:17:27Z

If I'm reading your definition correctly, this category looks equivalent to the category ${\bf Set_*}$ of pointed sets and basepoint-preserving functions (the equivalence is by removing the basepoint from each pointed set: you're left with an ordinary set and possibly partial functions). So you should be able to take the ordinary product in ${\bf Set_*}$ and then pass it through the equivalence: the product of $X$ and $Y$ in ${\bf pSet}$ should be the disjoint union of the cartesian products $X\times Y$, $X\times\{*\}$ , and $Y\times\{*\}$ . The partial projection to $X$ is given by projection from $X\times Y$ and $X\times\{*\}$ and undefined on $Y\times{*}$, and the partial projection to $Y$ is similar.

And indeed, this works: if $C$ has partial functions $f$ and $g$ to $X$ and $Y$ respectively, then we get a partial function to $(X\times Y)\sqcup (X\times\{*\})\sqcup (Y\times\{*\})$ given by $c\mapsto (f(c),g(c))$ if both exist, $(f(c),*)$ or $(*,g(c))$ if only one does, and undefined if neither exists.

Answer by Owen Biesel for Colimits in a bigger universe

2011-02-17T16:02:02Z

No. I'll answer for the case of colimits as follows: Consider for example the category $O$ of ordinals (as a poset), and adjoin a terminal object $T$, making a larger category $C$. Then this terminal object is a (large) colimit over the diagram $O\to C$. However, a cocontinuous functor $C\to D$ can send $T$ anywhere that admits a cone under the diagram $O\to D$, not necessarily its colimit (if the colimit even exists).

Answer by Owen Biesel for Proper classes and their consequences

2010-12-04T23:13:14Z

Here's a basic answer to question 1: what makes a collection of sets a proper class? The answer has to do with models, so let's look at those for a moment.

A model of set theory, also called a "universe", is a collection $M$ of things we'll call "sets", but for now they don't have any extra structure, they're just points or objects. But a model also has some extra information in its definition, a relation $E\subset M\times M$. And I'll write the relation as an infix, so that $xEy$ is short for $(x,y)\in E$. This relation is how the model describes when one set is supposed to be an element of another: $xEy$ is supposed to satisfy all the axioms of set theory. That means $M$ and $E$ only make a model of set theory if statements like

For all $x,y\in M$, if $zEx$ holds whenever $zEy$ holds, then $x=y$. (Extensionality)

are true about $M$ and $E$.

Now, models of set theory don't have to "feel" like a universe of sets. For example, you can construct the "set" of real numbers in any model of set theory, and prove that the set of real numbers is uncountable. Well then, the model had better be uncountable for the real numbers to fit inside, right? No, in fact the Löwenheim-Skolem theorem implies that there's a model of set theory where $M$, the collection of all "sets", is countable. (Assuming there's any model at all, of course.)

Isn't that a contradiction? If $M$ is countable, then $r$ has a countable number of elements, so we can put them in one-to-one correspondence with the elements of $n$ (the "set" of natural numbers), and use Cantor's diagonal argument to find an element not on the list, etc.

Let's see why there actually isn't a contradiction: If $r\in M$ is the "set" of real numbers and $n\in M$ is the set of natural numbers, we can consider the collection of all "elements" of $r$, namely $R=\{x\in M: xEr\}$ , and the collection of "elements" of $n$, namely $N=\{x\in M: xEn\}$ Then if $M$ is a countable model, $R$ and $N$ are both countable, so we can find a bijection $N\to R$... But there the reasoning stops. In order to get a contradiction with Cantor's diagonal argument, what we actually need there to be is a "set" $f\in M$ such that $f$ satisfies the conditions to be a "function" from $n$ to $r$, but that isn't what we have.

That leads us to the notion of "class" and "proper class". If we're working with a model $M$, then sets are elements of $M$ and "classes" of sets are subsets of $M$. Now some classes correspond to sets: any set $x\in M$ gives us a class of its elements: X=$\{y\in M:yE x\}$. Since the axiom of extensionality means that a set is determined by its class of elements, it's natural to identify a set with its class of elements. In this way, we can ask whether a class $C\subset M$ corresponds to some set $c\in M$. If it does, i.e. $x\in C$ iff $x E c$, we can abuse terminology and call $C$ a set, but if there's no such $c$, we call $C$ a proper class.

As the other answers have pointed out, there are many reasons $C$ can fail to be a set and so be a proper class. $C$ could be too "big", like $M$ itself: $M$ never corresponds to a set $m\in M$ by Russel's paradox: we'd have $xE m$ iff $x\in M$ which is true, so $m$ would be a "set" of all "sets". Or $C$ could be a set that would give you something impossible if it existed, like a bijection between the set $r\in M$ of real numbers and $n\in M$ of natural numbers. Or $C$ could just be a subset of $M$ that's outside the scope of $M$ for no good reason, in which case there are standard ways of building a new model $M'\supset M$ in which $C\subset M\subset M'$ actually does correspond to an "set" $c\in M'$.

This is one way to look at how independence results are shown: you start with a model $M$ of set theory, and then build a new model $M'$ that is not only a model of set theory but also has other properties, such as every "subset" of "the real numbers" being "in bijection" either with "the real numbers" or with "the natural numbers", so that $M'$ satisfies the continuum hypothesis. Then you can rephrase that result as "If ZFC is consistent (has a model $M$), then so is ZFC+CH (there's a model $M'$ of both)."

Answer by Owen Biesel for Why are matrices ubiquitous but hypermatrices rare?

2010-12-02T22:16:56Z

Since a matrix is just how we write down a linear map $V\to W$ from one vector space to another, it seems to me that the prevalance of matrices over hypermatrices is just a reflection of the fact that we use categories so much more often than multicategories (where a morphism has a list of objects as its domain). And I feel that the large role categories play, with morphisms that just go from one object to another, is due to the way we look at the world in terms of states and processes, of where you are now and how to get where you're going, of being and becoming.

Of course, by using duals of vector spaces we can also use matrices to represent either functionals $V\otimes W\to k$ or elements $k\to V\otimes W$, but I feel that these uses are usually no more special than their generalizations for hypermatrices.

Answer by Owen Biesel for A question about the isometry group of a finite metric space

2010-11-16T00:41:40Z

In accordance with Huichi Huang's comment on secretman's answer, we can say the following: If no isometry sends $i$ to $j$, then there exists some $k$ (Edit: different from $i$ and $j$) with $d(i,k)\neq d(j,k)$. Why? Because if $d(i,k)=d(j,k)$ for all $k$, then the transposition $(ij)\in S_n$ is an isometry of $X$.

Answer by Owen Biesel for Sexy vacuity ....

2010-11-14T21:37:52Z

How many open covers does the empty topological space have? Not one, not none, but two: the empty cover $\varnothing$, since its union is $\bigcup\varnothing=\varnothing$, and the cover {$\varnothing$}, since its union is also $\bigcup${$\varnothing$}$\ =\varnothing$.

This comes up when using the Grothendieck plus-construction to sheafify a presheaf. Apply the construction to the (nonseparated) presheaf $P:\mathcal{O}(X)^{op}\to \mathrm{Set}$ sending every open set to the set $A$, with $|A|\geq 2$. Then the presheaf $P^+:\mathcal{O}(X)^{op}\to\mathrm{Set}$ agrees with $P$ on every open set except $\varnothing\subseteq X$, where $P^+(\varnothing)$ is now a one-element set {$*$}. This is because the matching families for the cover {$\varnothing$} of $\varnothing$ (of which there is one for each $a\in A$) are all set equal to the unique matching family for the refining cover $\varnothing\subseteq\ ${$\varnothing$} of $\varnothing$.

This elementary example comes from "Sheaves in Geometry and Logic", by Moerdijk and MacLane.

When can one extend a flat family from a subscheme to the whole scheme?

2010-09-30T18:03:50Z

Is there a nice condition on a closed subscheme $Y$ of $X$ such that for every flat family $Z\to Y$, there is a flat family $W\to X$ whose restriction to $Y$ is $Z$? In particular, I'm interested in the case when the closed subscheme is two lines in $\mathbb{P}^2$, or three planes in $\mathbb{P}^3$, or generally $n$ hyperplanes in $\mathbb{P}^n$.

Answer by Owen Biesel for Why are inverse images more important than images in mathematics?

2010-04-27T13:11:36Z

Questions 1, 3, and 4 have been very well explained in the other answers, but I have something to remark about Question 2.

Very frequently, objects that are meant to be like spaces will have some kind of algebraic data attached to them. But this algebraic data is attached contravariantly, that is, there's some functorial relationship between your category of objects and the opposite of the category of algebraic structures.

For example:

Sets and Boolean Algebras. The power-set functor mentioned in Sammy Black's answer actually gives a contravariant functor from sets to Boolean algebras. This functor actually embeds the category of sets into the opposite category of Boolean algebras, so sets may be regarded as Boolean algebras with certain properties, except the maps go the wrong way.
Schemes and Rings. A scheme is locally isomorphic to an object in the opposite category of commutative rings. In fact, the category of schemes admits a fully-faithful embedding into $Set^{Rng}$, the free cocompletion of $Rng^{op}$. This is called the "functor of points" approach to schemes.
Compact Hausdorff Spaces and Unital C*-Algebras. There's a contravariant equivalence between the category of compact Hausdorff spaces and the category of C*-algebras with unit.
Locales and Frames. A frame is a kind of distributive lattice, and is described in a completely algebraic way. It's space-like counterpart, called a locale, is studied in so-called "Pointless Topology" (don't laugh), and the category of locales is defined to be the opposite category of frames. This was inspired by the last example, which is:
Topological Spaces and their Lattices of Open Sets. To every topological space, there is associated a certain lattice (the lattice of open sets). The requirement is that this association be contravariantly functorial - that is, every map of topological spaces must give rise to a map of lattices in the opposite direction. And that's what we have: a continuous map is one that induces a well-defined inverse-image map taking open sets to open sets.

So the idea that open maps seem to be more straightforward (so to speak) than continuous maps may be a common one, but in fact it seems that we get better categories of spaces if we ask the algebraic data to be contravariant.

Answer by Owen Biesel for What is the "correct" category of multisets

2010-04-17T20:23:52Z

According to the way I understand your conditions, I think the answer is No. In particular, condition 2 seems to suggest that there should be unique maps {1}->{111} and {111}->{1}, and also that those maps be inverses of each other (since there is only one map {1}->{1} and only one {111}->{111}). Hence the map {1}->{111} is an isomorphism, so its truth value is "true" regardless of whether the latter multiset has three or any other number of 1s.

Edited to add: To me a very natural candidate for the category of multisets would be the category of sets equipped with an equivalence relation, whose morphisms are functions on the underlying set that preserve the equivalence relation. In other words, the category whose objects are surjections A->A' and whose morphisms from (A->A') to (B->B') are pairs of maps A->B and A'->B' making the square commute.

The idea is that for a multiset like {1122}, the set A has four elements (like the multiset should) and the set A' only has two elements (like the underlying set {12} does), and the surjection A->A' tells you which elements of A are "the same" and which are different. The commuting square condition tells you that if two elements are equal, so are their images under any map. (So there's no map from {55} to {12} sending one 5 to 1 and the other to 2. However, there are two distinct maps from {5} to {55}.)

This category does have small limits, and the monomorphisms from (A->A') to (B->B') are the ones whose underlying map A->B is injective. However, I don't know whether this category has a subobject classifier, or what it might look like if it exists.

Comment by Owen Biesel

2012-09-26T21:40:06Z

Great! This excellent answer absolutely settles the question, and provides a truly complete invariant.

Comment by Owen Biesel

2012-09-24T15:49:05Z

Yes, thank you Todd. I didn't realize that (a) "subtree" is already standard terminology and (b) it doesn't mean what I thought it should mean. I'll clarify.

Comment by Owen Biesel

2012-09-23T04:53:15Z

I just made mine $\tilde P(z) = P(z-1)$, so the recurrence relation for mine is $\tilde P'(z) = P'(z-1) = z P(z-1) + 1 = z\tilde P(z) +1$, which is simpler. I don't know if it's in the literature, but it's slightly easier to read of some of the graph's information from my polynomial than yours. I've tried to clarify in the edit.

Comment by Owen Biesel

2012-08-30T13:57:26Z

And yes, there are many names for $\mathbb{Z}[z,z^{-1}]$ - the relevant fact is that it represents the functor sending a ring $R$ to the set $R^∗$ of its units, i.e. the set of possible generators for $R$ as an $R$-module.

Comment by Owen Biesel

2012-08-30T13:55:12Z

@darij: fixed. It was a side-effect of complying with quid's request above; the "any" in "Is 2 a nonzerodivisor for any n" makes more sense, but when I edited I didn't catch the change due to the ambiguity you mentioned.

Comment by Owen Biesel

2012-08-29T22:16:24Z

@darij: I don't see why; in that case $R_0=\mathbb{Z}[\alpha,\eta]/(\alpha\eta-1)$ is the "walking unit" and $2$ is still a nonzerodivisor.

Comment by Owen Biesel

2012-08-29T18:11:33Z

@quid: Good point! Thanks for catching that.

Comment by Owen Biesel

2012-08-29T18:08:46Z

You're right - I work with commutative rings so much I forget there is another kind... I'll edit to make that explicit. :)

Comment by Owen Biesel

2012-08-02T14:56:40Z

Ah, now I see. The correspondence is via a magic square (subtracting 5 from each number in a standard $3\times 3$ square containing 1 through 9), and you can check manually that there are no extra relations of three numbers summing to 0.

Comment by Owen Biesel

2012-08-02T14:47:02Z

I'm unfamiliar with this generalization! How does the case $n=7$ reduce to ordinary tic-tac-toe?

Comment by Owen Biesel

2012-07-27T21:15:57Z

@Davidac897: I think the conjecture part of #3 is the first sentence: "The largest integer... is 462." If I'm reading the rest correctly, it's known that if the conjecture is false, it's only because of a single counterexample that must be greater than 200 billion.

Comment by Owen Biesel

2012-02-24T13:13:15Z

Even better - thank you so much!

Comment by Owen Biesel

2012-02-24T04:46:34Z

Post that as an answer and I'll accept it, thanks!

Comment by Owen Biesel

2012-02-20T21:18:21Z

Thanks so much! Just what I was looking for.

Comment by Owen Biesel

2012-02-15T17:27:18Z

1. Vanishingly small. 2. The amount of computer storage space in existence is vanishingly small in comparison.