User sdcvvc - MathOverflow

Differentiability of computable functions

2010-08-09T16:49:24Z

Call a computable function 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$.

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?
Suppose $f$ is computable and continously differentiable everywhere. Must $f'$ be computable?

Answer by sdcvvc for Resources for learning practical category theory

2009-10-17T18:15:44Z

Online resources:

The Catsters channel
MATH198 course notes - examples in Haskell
Rydehard, Burstall: Computional Category Theory - examples in ML
MAGIC course
Barr, Wells: Category theory for computing science
Jaap van Oosten: basic category theory
Tom Leinster
Eugenia Cheng
Steve Awodey - very similar to the book mentioned by Quadrescence
Daniele Turi
Thomas Streicher

Books:

"Basic category theory for computer scientists" by Benjamin Pierce
MacLane - solid mathematical foundations, but hardly any references to computing
Abstract and concrete categories - might be considered too verbose, but it's full of examples

Category theory in Haskell:

Wikibooks introductory text
sigfpe's blog has a lot of category theory articles - (di)natural transformations, monads, Yoneda lemma...
Comonad.Reader
The Monad.Reader - check "Calculating monads with category theory"

Another list

Ordinals that are not sets

2009-12-15T11:16:37Z

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?

Answer by sdcvvc for Suggestions for a good Measure Theory book

2010-01-12T22:18:47Z

Bartle, The Elements of Integration and Lebesgue Measure

Higher-rank Borel sets

2009-12-07T17:01:25Z

What are interesting, illustrative examples of Borel sets, situated in Borel hierarchy higher than $\Sigma^{0}_{2}$ / $\Pi^{0}_{2}$ ?

Answer by sdcvvc for Clifford algebra as an adjunction?

2009-12-03T18:08:30Z

If I understand the definitions correctly:

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.

Let $D$ be the category of unital algebras over the field. Morphisms are linear maps preserving multiplication and identity.

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.

(I'm inexperienced, so this might be plain wrong. But surely an adjoint functor is hiding here.)

Questions about ordering of reals and irrationals

2009-10-11T13:33:37Z

Three problems from G.Rosenstein "Linear orderings" (from the end of Chapter 2 and beginning of Chapter 4):

1) Is there a nondecreasing function from irrationals onto reals?

2) Is there a nondecreasing function from reals onto irrationals?

3) Is there an increasing function from reals into irrationals? (In other words, are reals a subordering of irrationals?)

Any hints would be appreciated.

(Please tag the question set-theory order-theory)

Answer by sdcvvc for increasing bijection

2009-11-21T20:55:23Z

The Stern-Brocot tree gives a representation of (Q⁺,<) 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,<) 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,<) and sum of two trees corresponding to (Q-{0},<).

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:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

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.]

Answer by sdcvvc for Undergraduate Level Math Books

2009-11-10T10:23:56Z

Geroch, Mathematical Physics

Don't be scared by the title: it teaches algebra, topology and measure theory, using category-theoretic language.

Answer by sdcvvc for Is there a non self-referencing non-computable function?

2009-11-09T14:07:59Z

Check this blog post.

Answer by sdcvvc for Free, high quality mathematical writing online?

2009-10-22T09:55:01Z

MAA Writing Awards

Answer by sdcvvc for Finding monochromatic rectangles in a countable coloring of R^2

2009-10-11T17:30:01Z

This is equivalent to CH.

Quoting "Problems and Theorems in Classical Set Theory" by Komjath and Totik, chapter 16, Continuum hypothesis:

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)

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.

Previous version, with added explanation about Hamel basis:

Using

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.

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.

Comment by sdcvvc

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.

Comment by sdcvvc

2010-04-23T21:29:10Z

To give a balanced point, some analytical concepts can be defined categorically: jstor.org/stable/2321167, maths.gla.ac.uk/~tl/glasgowpssl/banach.pdf. But doing any nontrivial computation using categories is impossible.

Comment by sdcvvc

2010-03-19T12:24:38Z

You might check en.wikipedia.org/wiki/Iterated_binary_operation or en.wikipedia.org/wiki/Fold_(higher-order_function). Please edit the question, currently it's vague and may be closed.

Comment by sdcvvc

2010-03-09T16:42:17Z

en.wikipedia.org/wiki/Functional_square_root, answers.google.com/answers/threadview/id/…

Comment by sdcvvc

2010-01-25T22:16:10Z

I wikified the answer. Additions are welcome.

Comment by sdcvvc

2010-01-25T14:06:32Z

Might Størmer's theorem (en.wikipedia.org/wiki/Størmer's_theorem) help here?

Comment by sdcvvc

2010-01-25T13:43:52Z

Why this is tagged category-theory?

Comment by sdcvvc

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?

Comment by sdcvvc

2009-12-29T17:08:56Z

Comment by sdcvvc

2009-12-28T13:05:02Z

Rosenstein gives an example of a dense suborder of $\mathbb{R}$ 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]

Comment by sdcvvc

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.

Comment by sdcvvc

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 en.wikipedia.org/wiki/…. It doesn't rely on enumeration and basically says "R[x] is the simplest ring that adjoints to R some element x without any special properties"

Comment by sdcvvc

2009-12-07T17:37:25Z

I'd say $\mathbb{Q}$ is level 2, as a $\Sigma^{0}_{2}$ set.

Comment by sdcvvc

2009-12-03T18:45:32Z

Thanks, corrected.

Comment by sdcvvc

2009-12-03T14:12:28Z