User sdcvvc - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T17:15:12Z http://mathoverflow.net/feeds/user/158 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35021/differentiability-of-computable-functions Differentiability of computable functions sdcvvc 2010-08-09T16:49:24Z 2010-08-10T21:47:07Z <p>Call <strong>a computable function</strong> a total function $\mathbb{R} \to \mathbb{R}$, for which there exists a Turing machine outputting arbitrary close approximation to $f(x)$ given arbitrary close approximation to $x$.</p> <ol> <li>Obviously not every computable function is differentiable (for example, absolute value). For arbitrary continuous functions, the set of points of differentiability is $\Pi_{3}^0$. Can this be improved for computable functions?</li> <li>Suppose $f$ is computable and continously differentiable everywhere. Must $f'$ be computable?</li> </ol> http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory/906#906 Answer by sdcvvc for Resources for learning practical category theory sdcvvc 2009-10-17T18:15:44Z 2010-01-25T22:13:09Z <p>Online resources:</p> <ul> <li><a href="http://www.youtube.com/user/TheCatsters" rel="nofollow">The Catsters channel</a></li> <li><a href="http://haskell.org/haskellwiki/User:Michiexile/MATH198" rel="nofollow">MATH198 course notes</a> - examples in Haskell</li> <li><a href="http://www.cs.manchester.ac.uk/~david/categories/book/book.pdf" rel="nofollow">Rydehard, Burstall: Computional Category Theory</a> - examples in ML</li> <li><a href="http://www.cs.manchester.ac.uk/~hsimmons/MAGIC-CATS/magic-cats.html" rel="nofollow">MAGIC course</a></li> <li><a href="http://www.cwru.edu/artsci/math/wells/pub/ctcs.html" rel="nofollow">Barr, Wells: Category theory for computing science</a></li> <li><a href="http://www.itu.dk/~birkedal/teaching/category-theory-Fall-2001/basiccat.ps.gz" rel="nofollow">Jaap van Oosten: basic category theory</a></li> <li><a href="http://www.maths.gla.ac.uk/~tl/ct/" rel="nofollow">Tom Leinster</a></li> <li><a href="http://cheng.staff.shef.ac.uk/catnotes/categorynotes-cheng.pdf" rel="nofollow">Eugenia Cheng</a></li> <li><a href="http://www.andrew.cmu.edu/course/80-413-713/notes/" rel="nofollow">Steve Awodey</a> - very similar to the book mentioned by Quadrescence</li> <li><a href="http://www.dcs.ed.ac.uk/home/dt/CT/" rel="nofollow">Daniele Turi</a></li> <li><a href="http://www.mathematik.tu-darmstadt.de/~streicher/CTCL.pdf" rel="nofollow">Thomas Streicher</a></li> </ul> <p>Books:</p> <ul> <li>"Basic category theory for computer scientists" by Benjamin Pierce</li> <li>MacLane - solid mathematical foundations, but hardly any references to computing</li> <li><a href="http://katmat.math.uni-bremen.de/acc/" rel="nofollow">Abstract and concrete categories</a> - might be considered too verbose, but it's full of examples</li> </ul> <p>Category theory in Haskell:</p> <ul> <li><a href="http://en.wikibooks.org/wiki/Haskell/Category%5Ftheory" rel="nofollow">Wikibooks introductory text</a></li> <li><a href="http://blog.sigfpe.com" rel="nofollow">sigfpe's blog</a> has a lot of category theory articles - (di)natural transformations, monads, Yoneda lemma...</li> <li><a href="http://comonad.com/reader/" rel="nofollow">Comonad.Reader</a></li> <li><a href="http://www.haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf" rel="nofollow">The Monad.Reader</a> - check "Calculating monads with category theory"</li> </ul> <p><a href="http://www.cs.le.ac.uk/people/akurz/books.html" rel="nofollow">Another list</a></p> http://mathoverflow.net/questions/8976/ordinals-that-are-not-sets Ordinals that are not sets sdcvvc 2009-12-15T11:16:37Z 2010-01-13T07:50:29Z <p>The class of all ordinal numbers $\mathbf{Ord}$, aside being a proper class, can be thought of an ordinal number (of course it contains all ordinal numbers that are sets, not itself). Then one could consider $\mathbf{Ord}+1$, $\mathbf{Ord}+\mathbf{Ord}$, $\mathbf{Ord} \cdot \mathbf{Ord}$ and so on. Does this extension of ordinals make sense/is interesting? Maybe it was described by someone? Could it go deeper - to create a "superclass" of all ordinals that are classes?</p> http://mathoverflow.net/questions/11591/suggestions-for-a-good-measure-theory-book/11593#11593 Answer by sdcvvc for Suggestions for a good Measure Theory book sdcvvc 2010-01-12T22:18:47Z 2010-01-12T22:18:47Z <p>Bartle, The Elements of Integration and Lebesgue Measure</p> http://mathoverflow.net/questions/8113/higher-rank-borel-sets Higher-rank Borel sets sdcvvc 2009-12-07T17:01:25Z 2010-01-01T23:18:29Z <p>What are interesting, illustrative examples of Borel sets, situated in Borel hierarchy higher than <code>$\Sigma^{0}_{2}$</code> /<code>$\Pi^{0}_{2}$</code>?</p> http://mathoverflow.net/questions/7687/clifford-algebra-as-an-adjunction/7694#7694 Answer by sdcvvc for Clifford algebra as an adjunction? sdcvvc 2009-12-03T18:08:30Z 2009-12-03T18:44:42Z <p>If I understand the definitions correctly:</p> <p>Let $C$ be the category of pairs (V,q) where V is a vector space on a fixed field and q is a quadratic form. A morphism $f: (V,q) \rightarrow (V',q')$ is a linear map $V \to V'$ preserving the quadratic form.</p> <p>Let $D$ be the category of unital algebras over the field. Morphisms are linear maps preserving multiplication and identity.</p> <p>We've got a forgetful functor $D \rightarrow C$ that maps an algebra V to the quadratic vector space $(V,q)$ where $q(x)=(x \cdot x) \cdot 1$. This functor has as left adjoint the Clifford algebra construction.</p> <p>(I'm inexperienced, so this might be plain wrong. But surely an adjoint functor is hiding here.)</p> http://mathoverflow.net/questions/279/questions-about-ordering-of-reals-and-irrationals Questions about ordering of reals and irrationals sdcvvc 2009-10-11T13:33:37Z 2009-12-01T16:56:26Z <p>Three problems from G.Rosenstein "Linear orderings" (from the end of Chapter 2 and beginning of Chapter 4):</p> <p>1) Is there a nondecreasing function from irrationals onto reals?</p> <p>2) Is there a nondecreasing function from reals onto irrationals?</p> <p>3) Is there an increasing function from reals into irrationals? (In other words, are reals a subordering of irrationals?)</p> <p>Any hints would be appreciated.</p> <p>(Please tag the question set-theory order-theory)</p> http://mathoverflow.net/questions/6337/increasing-bijection/6404#6404 Answer by sdcvvc for increasing bijection sdcvvc 2009-11-21T20:55:23Z 2009-11-21T21:07:03Z <p>The Stern-Brocot tree gives a representation of (Q<sup>+</sup>,&lt;) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,&lt;) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,&lt;) and sum of two trees corresponding to (Q-{0},&lt;).</p> <p>These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:</p> <pre><code> root(T1) merge(T1,T2) = / \ left(T1) root(T2) / \ merge(right(T1),left(T2)) right(T2) </code></pre> <p>(to be precise, this definition is <a href="http://mathoverflow.net/questions/740/co-induction-understanding" rel="nofollow">coinductive</a>)</p> <p>The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy. [Foo's answer gives probably much easier analysis; I just wanted to show the combinatorial "look" at the linear orders.]</p> http://mathoverflow.net/questions/761/undergraduate-level-math-books/4838#4838 Answer by sdcvvc for Undergraduate Level Math Books sdcvvc 2009-11-10T10:23:56Z 2009-11-10T10:23:56Z <p><a href="http://books.google.com/books?id=wp2A7ZBUwDgC" rel="nofollow">Geroch, Mathematical Physics</a></p> <p>Don't be scared by the title: it teaches algebra, topology and measure theory, using category-theoretic language.</p> http://mathoverflow.net/questions/4589/is-there-a-non-self-referencing-non-computable-function/4725#4725 Answer by sdcvvc for Is there a non self-referencing non-computable function? sdcvvc 2009-11-09T14:07:59Z 2009-11-09T14:07:59Z <p>Check this <a href="http://xorshammer.com/2008/09/04/a-geometrically-natural-uncomputable-function/" rel="nofollow">blog post</a>.</p> http://mathoverflow.net/questions/1722/free-high-quality-mathematical-writing-online/1857#1857 Answer by sdcvvc for Free, high quality mathematical writing online? sdcvvc 2009-10-22T09:55:01Z 2009-10-22T09:55:01Z <p><a href="http://mathdl.maa.org/mathDL/22/" rel="nofollow">MAA Writing Awards</a></p> http://mathoverflow.net/questions/273/finding-monochromatic-rectangles-in-a-countable-coloring-of-r2/292#292 Answer by sdcvvc for Finding monochromatic rectangles in a countable coloring of R^2 sdcvvc 2009-10-11T17:30:01Z 2009-10-12T07:58:52Z <p>This is equivalent to CH.</p> <p>Quoting "Problems and Theorems in Classical Set Theory" by Komjath and Totik, chapter 16, Continuum hypothesis:</p> <blockquote> <p>CH holds if and only if the plane can be decomposed into countably many parts none containing 4 different points a,b,c,d such that dist(a,b)=dist(c,d)</p> </blockquote> <p>This is a stronger requirement than your problem, so assuming CH the answer is no. Their solution, assuming CH is false, proves that there's a monochromatic rectangle.</p> <p><hr /></p> <p>Previous version, with added explanation about Hamel basis:</p> <p>Using </p> <blockquote> <p>CH holds if and only if R can be colored by countably many colors such that the equation x+y=u+v has no solution with different x,y,u,v of the same color.</p> </blockquote> <p>This gives a negative answer assuming CH. Explanation: consider R as a vector space over Q. Let A be some basis. Take any bijection A -> A + A, where + is disjoint sum. It induces a linear isomorphism f: R -> R * R. (You can think that there's a linear isomorphism between reals and complexes if that helps.) Then, if you were given a monochromatic rectangle a=(x1, y1), b=(x1+x2, y1), c=(x1, y1+y2), d=(x1+x2, y1+y2), certainly a+d=b+c. Using that isomorphism, f(a)+f(d)=f(b)+f(c) gives a monochromatic solution of quoted equation.</p> http://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield Comment by sdcvvc sdcvvc 2010-10-04T16:51:00Z 2010-10-04T16:51:00Z SO gave a right answer - your problem is equivalent to solving linear equation Ax=b in GF(2), given matrix A and b. http://mathoverflow.net/questions/22359/why-havent-certain-well-researched-classes-of-mathematical-object-been-framed-by Comment by sdcvvc sdcvvc 2010-04-23T21:29:10Z 2010-04-23T21:29:10Z To give a balanced point, some analytical concepts can be defined categorically: <a href="http://jstor.org/stable/2321167" rel="nofollow">jstor.org/stable/2321167</a>, <a href="http://www.maths.gla.ac.uk/~tl/glasgowpssl/banach.pdf" rel="nofollow">maths.gla.ac.uk/~tl/glasgowpssl/banach.pdf</a>. But doing any nontrivial computation using categories is impossible. http://mathoverflow.net/questions/18726/is-there-a-name-for-this-type-of-function Comment by sdcvvc sdcvvc 2010-03-19T12:24:38Z 2010-03-19T12:24:38Z You might check <a href="http://en.wikipedia.org/wiki/Iterated_binary_operation" rel="nofollow">en.wikipedia.org/wiki/Iterated_binary_operation</a> or <a href="http://en.wikipedia.org/wiki/Fold_(higher-order_function" rel="nofollow">en.wikipedia.org/wiki/Fold_(higher-order_function</a>). Please edit the question, currently it's vague and may be closed. http://mathoverflow.net/questions/17614/solving-ffxgx Comment by sdcvvc sdcvvc 2010-03-09T16:42:17Z 2010-03-09T16:42:17Z <a href="http://en.wikipedia.org/wiki/Functional_square_root" rel="nofollow">en.wikipedia.org/wiki/Functional_square_root</a>, <a href="http://answers.google.com/answers/threadview/id/542904.html" rel="nofollow">answers.google.com/answers/threadview/id/&hellip;</a> http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory/906#906 Comment by sdcvvc sdcvvc 2010-01-25T22:16:10Z 2010-01-25T22:16:10Z I wikified the answer. Additions are welcome. http://mathoverflow.net/questions/12918/average-distance-between-numbers-of-the-form-2a3b Comment by sdcvvc sdcvvc 2010-01-25T14:06:32Z 2010-01-25T14:06:32Z Might St&#248;rmer's theorem (<a href="http://en.wikipedia.org/wiki/St&#248;rmer" rel="nofollow">en.wikipedia.org/wiki/St&#248;rmer</a>'s_theorem) help here? http://mathoverflow.net/questions/12882/is-a-lattice-of-convex-sets-distributive Comment by sdcvvc sdcvvc 2010-01-25T13:43:52Z 2010-01-25T13:43:52Z Why this is tagged category-theory? http://mathoverflow.net/questions/11084/what-programming-languages-do-mathematicians-use/11090#11090 Comment by sdcvvc sdcvvc 2010-01-09T14:53:50Z 2010-01-09T14:53:50Z What are the libraries most used for mathematical Haskell? I've heard of many (DoCon, alternative versions of Prelude, Haskell for Maths), is there a single one I should choose? http://mathoverflow.net/questions/9930/algorithm-or-theory-of-diagram-chasing Comment by sdcvvc sdcvvc 2009-12-29T17:08:56Z 2009-12-29T17:08:56Z Related: <a href="http://www.cs.cornell.edu/~kozen/papers/Cat.pdf" rel="nofollow">cs.cornell.edu/~kozen/papers/Cat.pdf</a>, <a href="http://www.cs.cornell.edu/~kozen/papers/06ijcar-categories.pdf" rel="nofollow">cs.cornell.edu/~kozen/papers/&hellip;</a> http://mathoverflow.net/questions/9901/which-are-the-rigid-suborders-of-the-real-line/9932#9932 Comment by sdcvvc sdcvvc 2009-12-28T13:05:02Z 2009-12-28T13:05:02Z Rosenstein gives an example of a dense suborder of <code>$\mathbb{R}$</code> without any monotonic map into itself (that's stronger than rigid), without using CH in theorem 9.1. [Dushnik and Miller, Concerning similarity transformations of linearly ordered sets] http://mathoverflow.net/questions/8976/ordinals-that-are-not-sets Comment by sdcvvc sdcvvc 2009-12-15T13:07:27Z 2009-12-15T13:07:27Z Good point. Possible workaround: add some special element x to the class Ord and define the order in obvious way. This will be a well-order, but not an ordinal number. http://mathoverflow.net/questions/8583/can-i-define-the-polynomial-ring-ax-with-an-isomorphism-f-a-ax Comment by sdcvvc sdcvvc 2009-12-11T17:49:25Z 2009-12-11T17:49:25Z If A is a field, then A and A[x] are never isomorphic (since the former one is a field and the latter one isn't). The closest thing you might be searching for is the universal property of the polynomial ring <a href="http://en.wikipedia.org/wiki/Polynomial_ring#Universal_property_of_the_polynomial_ring" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a>. It doesn't rely on enumeration and basically says &quot;R[x] is the simplest ring that adjoints to R some element x without any special properties&quot; http://mathoverflow.net/questions/8113/higher-rank-borel-sets/8116#8116 Comment by sdcvvc sdcvvc 2009-12-07T17:37:25Z 2009-12-07T17:37:25Z I'd say $\mathbb{Q}$ is level 2, as a <code>$\Sigma^{0}&#95;{2}$</code> set. http://mathoverflow.net/questions/7687/clifford-algebra-as-an-adjunction/7694#7694 Comment by sdcvvc sdcvvc 2009-12-03T18:45:32Z 2009-12-03T18:45:32Z Thanks, corrected. http://mathoverflow.net/questions/7667/categorifying-analysis Comment by sdcvvc sdcvvc 2009-12-03T14:12:28Z 2009-12-03T14:12:28Z Related: <a href="http://mathoverflow.net/questions/6554/terminology-in-category-theory" rel="nofollow" title="terminology in category theory">mathoverflow.net/questions/6554/&hellip;</a>