most recent 30 from http://mathoverflow.net 2013-05-25T08:41:13Z http://mathoverflow.net/feeds/user/7674 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts vincenzoml 2011-10-07T22:27:24Z 2011-10-09T02:01:28Z

<p>In the category Set of sets and functions, consider the functor F(X) = X * X where * is the product (its action on arrows is just F(f) = f * f). Does this functor preserve pushouts? Or at least pushouts of pairs of epimorpisms?</p>

http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known vincenzoml 2011-01-11T14:54:42Z 2011-06-23T01:54:40Z

<p>We can define a subclass of the regular languages. Fix an alphabet Sigma. Define the "circular" languages (actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, that's a different class of languages). </p> <p>A language L is circular iff. for all words w in Sigma*, we have:</p> <p>w belongs to L if and only if, for all integers k > 0, w^k belongs to L.</p> <p>Is this class of languages known? I am interested in:</p> <ul> <li><p>a name for it</p></li> <li><p>decidability of the problem, given an automaton (in particular: a DFA), whether the accepted language obeys to the above definition</p></li> <li><p>a "nice" characterization (e.g. equational?) of the definition.</p></li> </ul>

http://mathoverflow.net/questions/32791/how-is-the-right-adjoint-f-to-the-inverse-image-functor-f-described-for-f vincenzoml 2010-07-21T11:40:57Z 2010-07-22T15:02:59Z

<p>For $C,D$ small categories, and $f : C \to D$ a functor between them, there is a precomposition, or "inverse image", functor $f^* = (-) \circ f : Set^D \to Set^C$. It has a left and a right adjoint. What are their definitions, and in particular what is the right adjoint $f_*$? I couldn't find a definition in terms of functor categories, just "topological" ones.</p>

http://mathoverflow.net/questions/32182/question-answer-bisimulation vincenzoml 2010-07-16T14:50:20Z 2010-07-19T20:33:37Z

<p>I often come across relations that would be defined as a bisimulation, except that the label match can be "inexact", that is, in the bisimulation game, a move labelled with "a" can be replied to with "b" according to a predefined set of rules. A simple tentative definition would be</p> <p>Let $C$ be an alphabet, $\delta : A \to \mathcal P (C \times A)$ a transition system over the set of states $A$. Let $Q : C \to C$ be a total function. A symmetric relation $R \subseteq A \times A$ is a Q-bisimulation iff. $(x,y) \in R$ and $(a,x') \in \delta x$ implies that there is $y'\in A$ such that $(b,y')\in \delta x$, $(b =Qa)$ and $(x',y')\in R$.</p> <p>Did anybody ever see such a bisimulation? There are the special cases called "normalized bisimulation" where, roughly, the set of labels is a preorder, and the reply can be a smaller element, but I would like something like the above definition. If such a notion exists, is there a coalgebraic version of it?</p> <p>Indeed, the question holds also in the more general case when $Q$ is not just a function but a relation, and the condition $b=Qa$ becomes $(a,b) \in Q$. </p>

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-11T16:46:18Z 2011-10-11T16:46:18Z

Ah yes of course, point-wise and not using AC. I was trapped into my argument; then I am satisfied at the moment.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-11T14:50:10Z 2011-10-11T14:50:10Z

I was just not thinking that hard; at the moment I needed a proof in Set; but indeed I would hope that holds in Set^C too, as a start.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-11T13:34:47Z 2011-10-11T13:34:47Z

The canonical map extends to P trough i &#176; f^2 = j &#176; g^2. Commutativity and uniqueness easily follow. Call h the canonical map from P as a pushout to W^2. Then h commutes with the projections of W^2 and the projections of P as a product therefore it is the unique isomorphism between these two products.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-11T13:23:34Z 2011-10-11T13:23:34Z

Proof for binary pushouts: for f : A -&gt; B, g : A -&gt; C call W the pushout object of f,g with m : B -&gt; W, n : C -&gt; W. Similarly (P,i,j) is the pullback of f^2,g^2. We shall prove that P is a product of W with itself. Observe that m &#176; pi_1 : B^2 -&gt; W and n&#176; pi_1 : C^2 -&gt; W commuting with f^2 and g^2, therefore we have a map P -&gt; W. Similarly for m&#176;pi_2 and m&#176;pi_2. These two canonical maps from P to W are the projections. Let (C,p,q) be a cone on W,W. Call k', k'' : W -&gt; A two arbitrary choices of half-inverses of k = n&#176;g = m &#176; f. Then there is a unique map from C to A^2, which extends to P.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-11T13:15:27Z 2011-10-11T13:15:27Z

Hi again. After thinking hard, I found a more direct and more categorical proof that uses the fact that all epi split in Set, so it would hold in any such categories. It would be nice if someone could check this. First we shall prove that the square functor (or any finite power) preserves pushouts of epis. Then one can define the wide pushouts as filtered colimits of pushouts directly (did not check thoroughly, but should follow from Todd's argument on wide coproducts in a coslice).

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-10T10:24:28Z 2011-10-10T10:24:28Z

The argument that finite powers preserve filtered colimits is very neat. Many thanks for the precise answer. At the moment I am very happy with that, but at some point I am curious to check if all functors that preserve say, k-filtered colimits, preserve pushouts of epis of size less than k. Many facts on polynomials come from just preservation of filtered colimits.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts vincenzoml 2011-10-09T08:14:28Z 2011-10-09T08:14:28Z

@martin: yes I did. I get easily confused when reasoning on equivalence classes. But the categorical proof would also clarify what specific features of the category Set one has to use, so how general is the fact that the unique arrow in the lemma is mono.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-08T10:39:56Z 2011-10-08T10:39:56Z

And a third question (perhaps I should open a new one, but I may edit this one with the more general answer): it seems obvious to me that the functor FX = X+X preserves coproducts and coequalisers. Other generalisations of the above arguments lead me to state the following: All polynomial functors preserve wide pushouts if at least one of the arrows in the cocone is epic. I ask for a confirmation, but it seems quite easy to prove it.

http://mathoverflow.net/questions/77498/the-binary-product-preserves-pushouts/77501#77501 vincenzoml 2011-10-08T09:35:14Z 2011-10-08T09:35:14Z

I have 2 more related questions 1) the argument seems to extend without problems to wide pushouts of epis, can you confirm this? 2) can the lemma be proved categorically (a reference is sufficient)? I am convinced of it but can't really write down a simple proof, reasoning about elements of quotients is difficult.

http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known vincenzoml 2011-01-13T13:04:40Z 2011-01-13T13:04:40Z

Yes I am interested in the regular languages that satisfy the condition I spelled. In fact I am only interested in languages that don't contain the empty word, but that's a separate condition. Sorry for the crosspost, I did not know what was the most appropriate place for the question. Maybe following up just on cstheory is better. A language is not circular if L=M* (and L=M+ does not fix this) as Lukasz Grabowski points out with his example. Yuval Filmus: is what you say that obvious? How do you identify the generators (your &quot;r&quot;).

http://mathoverflow.net/questions/32791/how-is-the-right-adjoint-f-to-the-inverse-image-functor-f-described-for-f/32808#32808 vincenzoml 2010-07-22T12:00:35Z 2010-07-22T12:00:35Z

Michael, thanks! This helped me understand the definition in MacLane. But reading p. 237-238 (in the second edition) that is, the definition you spell out above, and having made calculations, it seems to me that there's a typo above: the index category of the limit is $(d \downarrow f)$ and the limit is indexed over $d \to f(c)$. For the rest, a very clear explanation.

http://mathoverflow.net/questions/32791/how-is-the-right-adjoint-f-to-the-inverse-image-functor-f-described-for-f vincenzoml 2010-07-21T14:23:29Z 2010-07-21T14:23:29Z

Peter: Mac Lane and Moerdijk define $f_*$ in the &quot;topological&quot; way, that is (p. 68 of the copy you linked) $(f_*F)V=F(f^{−1})V$. But it is not clear to me how this definition gives us (from a presheaf $F : Set^C$) a presheaf $f_*F: Set^D$. That is: 1) What is now $F(f^{−1})(V)$? f may be non-injective on objects. 2) What is the action of $f_*F$ on arrows? $C$ may even be a discrete category, so $f^{−1}$ of a arrow in $D$ may be undefined.

http://mathoverflow.net/questions/32791/how-is-the-right-adjoint-f-to-the-inverse-image-functor-f-described-for-f vincenzoml 2010-07-21T14:09:18Z 2010-07-21T14:09:18Z

Pietro: I might be wrong here, but $f^*$ seems to be covariant, with $f^*(F : Set^D) = F\circ f$ and $f^*(\gamma : F \to G)_{c : C} = \gamma_{fc} : Ffc \to Gfc$.