User justin hilburn - MathOverflow

Answer by Justin Hilburn for Best online mathematics videos?

2012-07-28T21:20:45Z

They filmed the FRG Conference on Topology and Field Theories and put the lectures on youtube.

Answer by Justin Hilburn for What is some good introduction to lambda calculus?

2011-10-21T00:25:38Z

Proof and Types is a good place to learn about the Curry-Howard isomorphism.

Answer by Justin Hilburn for Why is a topology made up of 'open' sets?

2010-03-26T02:49:12Z

After reading the comments on Sigfpe's answer I realized that it would be useful to make a rigorous argument to explain why "rulers" or as like to call them "observable properties" should be open sets. In the process I'd like to explain how we can view general topology as an idealized version of computation by interpreting topological spaces as data types and continuous maps as computable functions.

Computationally an observable property $P$ of a data type $A$ corresponds to a semi-decision procedure. In other words a computable function $\chi_P: A \to Unit$ which returns the unique value $()$ of type $Unit$ if $a \in A$ has the property $P$ and runs forever otherwise. We can interpret $P$ as a subset of $A$ and $\chi_P$ as it's characteristic function. Clearly observable properties pull back under computable functions since if $f:B \to A$ is a computable function $\chi_P \circ f$ is a semi-decision procedure.

Let's translate this into topological language. If we interpret $A$ and $B$ as topological spaces and $f:B \to A$ as a continuous map we have that $f^{-1}(P)$ is observable if $P$ is. Thus it makes sense to interpret observable properties as open sets. We can make this correspondence more precise if we notice that every open set $P$ in $A$ corresponds to a map $\chi_P: A \to \mathbb{S}$ where $\mathbb{S}$ is the Sierpinski space. Thus in our translation $Unit$ corresponds to $\mathbb{S}$, the open point of $\mathbb{S}$ corresponds to $()$, and the closed point $\bot$ of $\mathbb{S}$ corresponds to nontermination.

Now a question remains: why did we choose to represent observable properties by open sets instead of closed sets? The answer lies in the way observable properties behave under intersection and union. Let $P$ and $Q$ be observable properties. The intersection $P \cap Q$ is an observable property we can write a semi-decision procedure $\chi_{P \cap Q}$ by running $\chi_P$ and $\chi_Q$ in succession. Similarly notice that $P \cup Q$ is observable since we can write a semi-decision procedure $\chi_{P \cup Q}$ that runs $\chi_P$ and $\chi_Q$ in parallel and outputs $()$ if one of $\chi_P$ and $\chi_Q$ does. If you have an infinite number of computers it is clear that you can generalize this construction to an infinite union $\bigcup_{i \in I} P_i$ by running all the $\chi_{P_i}$ in parallel. However this will not work for an infinite intersection $\bigcap_{n \in \mathbb{N}} P_n$ because if $\chi_{P_n}$ takes $n$ seconds to terminate, then even running all the $\chi_{P_n}$ in parallel will not help.

I can't help but list out a few other things to ponder in light of this dictionary:

A space $X$ is discrete if $=:X\times X \to \mathbb{S}$ is continuous
A space $X$ is Hausdorff if $\neq: X\times X \to \mathbb{S}$ is continuous
A space $X$ is compact if the map $\forall_X: (X \to \mathbb{S}) \to \mathbb{S}$ is continuous
An observable property $P$ of $T$ is decidable if and only if $P$ is clopen
On a sequential machine we can write a semi-decision procedure for a countable union of observable properties but not an uncountable union. Does this say anything about topology?

Here are some nice references:

Alex Simpson - Topological Spaces from a Computational Perspective
Martin Escardo - Synthetic Topology of Data Types and Classical Spaces

Answer by Justin Hilburn for Are there any mathematical objects that exist but have no concrete examples?

2011-04-23T01:42:56Z

You should look at Handbook of Analysis and its Foundations by Eric Schecter. Here is an excerpt from the preface:

Students and researchers need examples; it is a basic precept of pedagogy that every abstract idea should be accompanied by one or more concrete examples. Therefore, when I began writing this book (originally a conventional analysis book), I resolved to give examples of everything. However, as I searched through the literature, I was unable to find explicit examples of several important pathological objects, which I now call intangibles:

finitely additive probabilities that are not countably additive, elements of $(l_\infty)^*- l_1$(a customary corollary of the Hahn- Banach Theorem), universal nets that are not eventually constant, free ultrafilters (used very freely in nonstandard analysis!), well orderings for R, inequivalent complete norms on a vector space, etc. In analysis books it has been customary to prove the existence of these and other pathological objects without constructing any explicit examples, without explaining the omission of examples, and without even mentioning that anything has been omitted. Typically, the student does not consciously notice the omission, but is left with a vague uneasiness about these unillustrated objects that are so difficult to visualize.

I could not understand the dearth of examples until I accidentally ventured beyond the traditional confines of analysis. I was surprised to learn that the examples of these mysterious objects are omitted from the literature because they must be omitted: Although the objects exist, it can also be proved that explicit constructions do not exist. That may sound paradoxical, but it merely reflects a peculiarity in our language: The customary requirements for an "explicit construction" are more stringent than the customary requirements for an "existence proof." In an existence proof we are permitted to postulate arbitrary choices, but in an explicit construction we are expected to make choices in an algorithmic fashion. (To make this observation more precise requires some definitions, which are given in 14.76 and 14.77.)

Though existence without examples has puzzled some analysts, the relevant concepts have been a part of logic for many years. The nonconstructive nature of the Axiom of Choice was controversial when set theory was born about a century ago, but our understanding and acceptance of it has gradually grown. An account of its history is given by Moore [1982]. It is now easy to observe that nonconstructive techniques are used in many of the classical existence proofs for pathological objects of analysis. It can also be shown, though less easily, that many of those existence theorems cannot be proved by other, constructive techniques. Thus, the pathological objects in question are inherently unconstructible.

The paradox of existence without examples has become a part of the logicians' folklore, which is not easily accessible to nonlogicians. Most modern books and papers on logic are written in a specialized, technical language that is unfamiliar and nonintuitive to outsiders: Symbols are used where other mathematicians are accustomed to seeing words, and distinctions are made which other mathematicians are accustomed to blurring -- e.g., the distinction between first-order and higher-order languages. Moreover, those books and papers of logic generally do not focus on the intangibles of analysis.

On the other hand, analysis books and papers invoke nonconstructive principles like magical incantations, without much accompanying explanation and -- in some cases -- without much understanding. One recent analysis book asserts that analysts would gain little from questioning the Axiom of Choice. I disagree. The present work was motivated in part by my feeling that students deserve a more "honest" explanation of some of the non-examples of analysis -- especially of some of the consequences of the Hahn- Banach Theorem. When we cannot construct an explicit example, we should say so. The student who cannot visualize some object should be reassured that no one else can visualize it either. Because examples are so important in the learning process, the lack of examples should be discussed at least briefly when that lack is first encountered; it should not be postponed until some more advanced course or ignored altogether.

Answer by Justin Hilburn for Background to learn about manifolds

2011-04-10T22:43:43Z

I have really enjoyed browsing through Novikov and Taimanov. It starts out with very modest prerequisites and covers quite a bit of material.

Once you have the basics down I would recommend the new book by Peter Michor. It is one of the few sources I have found that "stresses naturality and functoriality from the beginning and is as coordinate-free as possible."

Answer by Justin Hilburn for Best online mathematics videos?

2011-02-20T06:07:53Z

I am surprised no one has mentioned that the Kavli Institute for Theoretical Physics, the Simons Center for Geometry and Physics, and the Perimeter Institute often tape conferences.

Answer by Justin Hilburn for Decent Texts on Categorical Logic

2011-01-25T07:13:44Z

My answer here has a number of good references: http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory/1954#1954

I don't recommend Goldblatt (Here is an article by Colin Mclarty that elaborates on why http://www.jstor.org/pss/687825).

Answer by Justin Hilburn for Resources for learning practical category theory

2009-10-22T21:31:13Z

Since sdvccv already pointed out a number of good sources for learning category theory as applied to CS, I will try and provide some guide posts.

My favorite book on the subject is Practical Foundations of Mathematics by Paul Taylor since he does a really good job of giving you a big picture (unfortunately he doesn't always give you enough details if you don't already have a logic background). Bart Jacobs book Categorical Logic and Type Theory is also very readable.

In general I think the most important thing to understand in order to apply categories to computer science is the Curry-Howard-Lambek correspondence which loosely states that lambda calculii, intuitionist logics, and cartesian closed categories (categories where you have products and function spaces) are the same thing. Proofs and Types which was transcribed from some of Girard's lecture notes is an excellent source for the Curry-Howard part of the correspondence. Steve Awodey's book and these notes by Samson Abramsky are good places to see this translated into categorical language. For connections to Topoi Mac Lane's Sheaves in Geometry and Logic looks good.

Next you will probably want to learn about categorical and universal algebra. One of the more immediate and accessible applications of these ideas is the theory of algebraic data types (categorically: initial algebras for polynomial functors) and maps and folds between them. Monads are also a part of this subject since they are type constructors (endofunctors) that also have a multiplication and unit. Haskell do notation corresponds to forming the Kliesli category for a monad.

The nascent field of universal coalgebra has been very useful for formalizing notions of state and observation. There are also some emerging connections between coalgebra and modal logic.

Finally, if you aren't worn out you may want to learn about Stone duality which is a way of relating "logics of observable properties" and topology. For computer scientist Stone duality is primarily useful for giving a logical interpretation to domain theory, but mathematicians may recognize the duality between commutative rings and Zariski spectra as a special case.

Answer by Justin Hilburn for Computer Science for Mathematicians

2011-01-05T18:56:10Z

Theory A (Algorithms/Complexity):

Kleinberg, Tardos - Algorithms
Easley, Kleinberg - Networks Crowds and Markets
Nisan, Tardos, Vazirani - Algorithmic Game Theory
Arora, Barak - Computational Complexity: A Modern Approach

Theory B (Logic/Semantics/Automated Reasoning):

Benjamin Pierce - Types and Programming Languages
Benjamin Pierce - Software Foundations in Coq (Really lets you see how to translate theory into practice)
The links here
Harrison - Practical Logic and Automated Theorem Proving

Answer by Justin Hilburn for Propositional logic with categories

2010-10-24T01:30:23Z

This paper by Abramsky relates Joyal's Lemma on the collapse of a cartesian closed category with a dualizing object to no cloning theorems and no deleting theorems in quantum mechanics.

Answer by Justin Hilburn for Gossip about Grothendieck and distributive lattices

2010-09-19T03:50:35Z

Johnstone expressed a similar sentiment in the introduction to his book on Stone Spaces (you can read it on Amazon) where he gave a fairly detailed account of how the Stone representation theorem and the theory of continuous lattices it inspired anticipated some of the formalism of modern algebraic geometry.

Answer by Justin Hilburn for Interesting applications of the Pigeon-hole Principle

2010-08-19T22:25:45Z

The impossibility of a lossless compression scheme for binary strings that reduces the size of every input follows easily from the pigeon hole principle.

Answer by Justin Hilburn for book for probability

2010-05-11T13:18:23Z

I really enjoyed this unfinished book by Rota and Baclawski on probability and random processes. It is extremely well written (like everything else by Rota) and covers a number of interesting topics like Markov processes, entropy and information, and Brownian motion.

Answer by Justin Hilburn for Books about history of recent mathematics

2010-05-07T00:25:14Z

Leo Corry - Modern Algebra and the Rise of Mathematical Structures (here is a review)

Answer by Justin Hilburn for How should one present curl and divergence in an undergraduate multivariable calculus class?

2010-04-19T20:49:18Z

Note: I wrote this when the title was still "What is the divergence? What is the curl?"

A nice geometric interpretation of the divergence is that it measures the rate of expansion of a fixed volume in the flow defined by the vector field. There is a very concrete way to see this by comparing the volume of an small cube to the volume of a parallelepiped given by considering where the corners of the cube are dragged by the flow in an infinitesimal length of time (it is easiest to work out the analogous case of a square with corners (x,y), (x+dx,y), (x,y+dy), (x+dx,y+dy) in the plane). I imagine the fact that the determinant measures volume can be used to explain the presence of the cross product. A more sophisticated (and conceptual) way to prove this fact is to note that the divergence can be defined on any manifold with a volume form as the Lie derivative of the volume form (contract the volume form with the vector field and then take the exterior derivative).

I have also seen a result generalizing the curl to arbitrary dimension by noting that we can identify 2-forms with skew-symmetric matrices (elements of the Lie algebra of SO(n)) if we have an inner product. I'd be curious to hear how exponentiating this infinitesimal rotation relates to integrating the vector field.

Answer by Justin Hilburn for How much of the current logic is about syntax?

2010-01-14T00:02:58Z

To elaborate slightly on Neel's post: the fact that not all proofs in intuitionist and substructural logics are identified is a strength and not a weakness when viewed through the lens of the Curry-Howard isomorphism which shows that logic has computational content.

Basically the Curry-Howard isomorphism states that propositions in intuitionist logic can be identified with types in a programming language and proofs can be identified with programs. In classical logic all proofs of a given proposition are identified so classical logic is too impoverished to serve as a model for computation. In other words, the fact that there are multiple proofs of the same proposition in intuitionist logic is what allows us to have multiple programs with the same type.

Answer by Justin Hilburn for Most helpful math resources on the web

2009-10-23T20:00:00Z

Everything by John Baez. In particular This Week's Finds in Mathematical Physics, the n-Category Cafe, and the n-Lab. He has an amazing ability to make even the most esoteric topics seem obvious and inevitable.

Comment by Justin Hilburn

2013-02-26T20:45:17Z

If you are interested in Cech-cocycles representing Stiefel-Whitney classes you could look at: link.springer.com/article/… I know that this isn't exactly what you wanted, but Cheyne's answer seems to imply that what you wanted isn't possible anyway.

Comment by Justin Hilburn

2011-05-19T07:04:53Z

There is always estatis.coders.fm/falso

Comment by Justin Hilburn

2011-02-01T02:27:08Z

@Dror: Care to elaborate?

Comment by Justin Hilburn

2011-01-25T07:10:59Z

McLarty wrote a whole article in response to the historical inaccuracies in Goldblatt's book jstor.org/stable/687825

Comment by Justin Hilburn

2011-01-25T03:51:43Z

Have you looked at any of the books on Geometric Algebra/Calculus by Hestenes and his collaborators. They try and do all of analytic geometry and linear algebra using Clifford Algebras to do coordinate free computations. Hestenes even wrote a book on classical mechanics from this perspective.

Comment by Justin Hilburn

2011-01-10T23:34:00Z

I generally like Pierce's style but I wasn't a huge fan of BCTfCS. I think Awodey is a really good choice for a gentle introduction.

Comment by Justin Hilburn

2011-01-06T18:14:41Z

Gah! Why can't I add references to this without bumping things to the first page!

Comment by Justin Hilburn

2010-12-20T06:18:37Z

Great answer. I would only note that there is a large area of computer science known as Domain Theory that tries to make the notion of decidability a la Turing the same as the notion of decidability given by considering maps into the Sierpinski space. Here is a short primer on these ideas: homepages.inf.ed.ac.uk/als/Teaching/MSfS/l3.ps

Comment by Justin Hilburn

2010-09-20T22:12:38Z

@Mark: In Indiscrete Thoughts Rota was referring to pointless topology which is the subject of Stone Spaces.

Comment by Justin Hilburn

2010-07-02T05:59:38Z

math.andrej.com/2010/03/29/…

Comment by Justin Hilburn

2010-05-06T03:36:22Z

I just want to third the recommendation of John Stillwell's book.

Comment by Justin Hilburn

2010-05-02T21:36:34Z

Awodey is excellent and should be well within reach. It is often tackled by computer scientists and logicians with minimal (or even no) knowledge of algebra.

Comment by Justin Hilburn

2010-05-02T05:46:45Z

You might want to take a look at Algebra (3ed) by Mac Lane/Birkhoff. They do a good job of introducing categorical language as needed to illuminate results from classical algebra.

Comment by Justin Hilburn

2010-03-26T20:48:25Z

@Qiaochu: I have heard of such things but I don't know the details. Maybe this paper by Paul Taylor can help: paultaylor.eu/ASD/loccpct#foufct

Comment by Justin Hilburn

2010-03-26T03:44:42Z

@Mio: I wrote up an answer where I explain exactly why you can't make rulers be closed sets.