Talk: Survey of mathematically applied computability theory

Despite being relatively small, my department has three faculty in finite combinatorics, in addition to having me in logic. I recently gave a series of two talks in our seminar to present a broad overview of classical computability theory, and to present some more recent applications to mathematics, via Reverse Mathematics and via Weihrauch Reducibility.

Continue reading

Posted in Talks | Leave a comment

Reverse Mathematics of Matroids

This post is about the paper Reverse Mathematics of Matroids by Jeff Hirst and me. We look at basis theorems for countable vector spaces, countable graphs, and countable enumerated matroids. These three kinds of structures turn out to be extremely similar from the point of view of their dependence relations.

Continue reading

Posted in Papers, Research | Leave a comment

An example with Dedekind cuts

In this post, I will briefly describe an example in computability theory that is well known, but not easy to find in the literature. It gives one reason why Dedekind cuts are difficult to work with computationally.

Theorem. There is no (uniform) algorithm that, given two left Dedekind cuts $A$ and $B$, produces a left cut for the number $A – B$.

Continue reading

Posted in Musings, Results worth knowing | Leave a comment

Talk on Reverse Mathematics and Ramsey Theory

This is a copy of my notes from a two-hour talk I gave at our local combinatorics seminar about Reverse Mathematics and Ramsey Theory. The audience consisted of our combinatorialists, who are not logicians, and so the talk is intended to introduce some ideas and viewpoints from my how we look at combinatorics in Reverse Mathematics, without getting into technical details.

Continue reading

Posted in Talks, Uncategorized | Leave a comment

Talk on the existence of connected components of graphs

This week I am attending a seminar at Dagstuhl on Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis. This post has slides from my talk and some blog-only remarks to expand on them.

Continue reading

Posted in Research, Talks | Leave a comment

Filter quantifiers

I have been supervising an undergraduate student in an independent study in topology this semester. We have just finished the Stone–Čech compactification, and the semester is ending, so I want to end with an ultrafilter based proof of Hindman’s theorem. There are several good proofs of this sort online, including Hindman’s Theorem Via Ultrafilters (PDF) by Leo Goldmakher and Ramsey Theory (PDF) by Imre Leader (lecture notes transcribed by Stiofáin Fordham). The latter is particularly nice because it uses the formalism of filter quantifiers.

Continue reading

Posted in Results worth knowing | 4 Comments

Talk on Reverse Mathematics and the Modal Logic of Reverse Mathematics

This is a transcription of notes from a talk I gave on November 1, 2013 to the interdisciplinary logic seminar at the University of Connecticut. I gave a general introduction to Reverse Mathematics and then spoke about my work with Alaeddine Saadaoui and Sean Sovine on the logic of implications between subsystems in in Reverse Math. This post is essentially my speaking notes for the talk.
Continue reading

Posted in Research, Talks | 3 Comments

Internal combinatorics and uniform reducibility

This post is a set of notes from a talk I gave on December 5th for the discrete mathematics seminar at Marshall University. I want to argue that logical analysis can reveal the “internal combinatorics” of theorems, using some recent results of Dorais, Dzafarov, Hirst, Mileti, and Shafer [DDHMS 2012] as a particular example of the process.
Continue reading

Posted in Musings, Research, Talks | Leave a comment

Quiz on public peer review

I have been required to complete a “responsible conduct of research” training module by the research office at my school. The reason I am commenting is that I was asked to answer the following question “true” or “false”. This is not meant to be an opinion, it is from a quiz on which I am supposed to maximize my score.

True or false: “A good alternative to the current peer review process would be web logs (BLOGS) where papers would be posted and reviewed by those who have an interest in the work.”

I thought that would be interesting to people who follow Boole’s rings. The correct answer, of course, was “false”. Here is the rationale they gave:

“Although the peer review process is evolving, the described system would probably not work very well. It is likely that the peer review process will evolve to minimize bias and conflicts of interest. It is, in the best interest of everyone involved in the research enterprise that the scientific review process be fair and rigorous.”

Just throwing it out there….

Posted in Musings | 8 Comments

Computable roots of computable functions

Here are several interesting results from computable analysis:

Theorem 1. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ and $\alpha$ is an isolated root of $f$, then $\alpha$ is computable.

Corollary 2. If $p(x)$ is a polynomial over $\mathbb{R}$ with computable coefficients, then every root of $p(x)$ is computable.

Theorem 3. There is a effective closed subset of $\mathbb{R}$ which is nonempty (in fact, uncountable) but which has no computable point.

Theorem 4. There is a computable function from $\mathbb{R}$ to $\mathbb{R}$ which has uncountably many roots but no computable roots.

Continue reading

Posted in Results worth knowing | Tagged , | 4 Comments