Month: October 2020

Divergent potentialism: A modal analysis with an application to choice sequences

Posted on by

Ethan Brauer, Øystein Linnebo, and Stewart Shapiro

Modal logic has recently been used to analyze potential infinity and potentialism more generally. However, this analysis breaks down in cases of divergent possibilities, where the modal logic is weaker than S4.2. This talk has three aims. First, we use the intuitionistic theory of free choice sequences to motivate the need for a modal analysis of divergent potentialism and explain the challenge of connecting the ordinary theory of choice sequences with our modal explication. Then, we use the so-called Beth-Kripke semantics for intuitionistic logic to overcome those challenges. Finally, we apply the resulting modal analysis of divergent potentialism to make choice sequences comprehensible in classical terms.

Computing Perfect Matchings in Graphs

Posted on by

Tyler Markkanen

A matching of a graph is any set of edges in which no two edges share a vertex. Steffens gave a necessary and sufficient condition for countable graphs to have a perfect matching (i.e., a matching that covers all vertices). We analyze the strength of Steffens’ theorem from the viewpoint of computability theory and reverse mathematics. By first restricting to certain kinds of graphs (e.g., graphs with bounded degree and locally finite graphs), we classify some weaker versions of Steffens’ theorem. We then analyze Steffens’ corollary on the existence of maximal matchings, which is critical to his proof of the main theorem. Finally, using methods of Aharoni, Magidor, and Shore, we give a partial result that helps hone in on the computational strength of Steffens’ theorem. Joint with Stephen Flood, Matthew Jura, and Oscar Levin.