BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Carl Mummert

Carl Mummert contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.LOmath.GNLogic in Computer Science

Trust snapshot

Quick read

Trust 21 - Emerging
11works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2020arXiv

The logical strength of König's edge coloring theorem

König's edge coloring theorem says that a bipartite graph with maximal degree $n$ has an edge coloring with no more than $n$ colors. We explore the computability theory and Reverse Mathematics aspects of this theorem. Computable bipartite graphs with degree bounded by $n$ have computable edge colorings with $n+1$ colors, but the theorem that there is an edge coloring with $n$ colors is equivalent to WKLo over RCAo. This gives an additional proof of a theorem of Hirst: WKLo is equivalent over RCAo to the principle that every countable bipartite $n$-regular graph is the union of $n$ complete matchings. We describe open questions related to Vizing's edge coloring theorem and a countable form of Birkhoff's theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Reverse Mathematics of Matroids

Matroids generalize the familiar notion of linear dependence from linear algebra. Following a brief discussion of founding work in computability and matroids, we use the techniques of reverse mathematics to determine the logical strength of some basis theorems for matroids and enumerated matroids. Next, using Weihrauch reducibility, we relate the basis results to combinatorial choice principles and statements about vector spaces. Finally, we formalize some of the Weihrauch reductions to extract related reverse mathematics results. In particular, we show that the existence of bases for vector spaces of bounded dimension is equivalent to the induction scheme for $Σ^0_2$ formulas.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the existence of a connected component of a graph

We study the reverse mathematics and computability of countable graph theory, obtaining the following results. The principle that every countable graph has a connected component is equivalent to $\mathsf{ACA}_0$ over $\mathsf{RCA}_0$. The problem of decomposing a countable graph into connected components is strongly Weihrauch equivalent to the problem of finding a single component, and each is equivalent to its infinite parallelization. For graphs with finitely many connected components, the existence of a connected component is either provable in $\mathsf{RCA}_0$ or is equivalent to induction for $Σ^0_2$ formulas, depending on the formulation of the bound on the number of components.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The modal logic of Reverse Mathematics

The implication relationship between subsystems in Reverse Mathematics has an underlying logic, which can be used to deduce certain new Reverse Mathematics results from existing ones in a routine way. We use techniques of modal logic to formalize the logic of Reverse Mathematics into a system that we name s-logic. We argue that s-logic captures precisely the "logical" content of the implication and nonimplication relations between subsystems in Reverse Mathematics. We present a sound, complete, decidable, and compact tableau-style deductive system for s-logic, and explore in detail two fragments that are particularly relevant to Reverse Mathematics practice and automated theorem proving of Reverse Mathematics results.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reverse mathematics and properties of finite character

We study the reverse mathematics of the principle stating that, for every property of finite character, every set has a maximal subset satisfying the property. In the context of set theory, this variant of Tukey's lemma is equivalent to the axiom of choice. We study its behavior in the context of second-order arithmetic, where it applies to sets of natural numbers only, and give a full characterization of its strength in terms of the quantifier structure of the formula defining the property. We then study the interaction between properties of finite character and finitary closure operators, and the interaction between these properties and a class of nondeterministic closure operators.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the strength of the finite intersection principle

We study the logical content of several maximality principles related to the finite intersection principle ($F\IP$) in set theory. Classically, these are all equivalent to the axiom of choice, but in the context of reverse mathematics their strengths vary: some are equivalent to $\ACA$ over $\RCA$, while others are strictly weaker, and incomparable with $\WKL$. We show that there is a computable instance of $F\IP$ all of whose solutions have hyperimmune degree, and that every computable instance has a solution in every nonzero c.e.\ degree. In terms of other weak principles previously studied in the literature, the former result translates to $F\IP$ implying the omitting partial types principle ($\mathsf{OPT}$). We also show that, modulo $Σ^0_2$ induction, $F\IP$ lies strictly below the atomic model theorem ($\mathsf{AMT}$).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Reverse mathematics and equivalents of the axiom of choice

We study the reverse mathematics of countable analogues of several maximality principles that are equivalent to the axiom of choice in set theory. Among these are the principle asserting that every family of sets has a $\subseteq$-maximal subfamily with the finite intersection property and the principle asserting that if $P$ is a property of finite character then every set has a $\subseteq$-maximal subset of which $P$ holds. We show that these principles and their variations have a wide range of strengths in the context of second-order arithmetic, from being equivalent to $\mathsf{Z}_2$ to being weaker than $\mathsf{ACA}_0$ and incomparable with $\mathsf{WKL}_0$. In particular, we identify a choice principle that, modulo $Σ^0_2$ induction, lies strictly below the atomic model theorem principle $\mathsf{AMT}$ and implies the omitting partial types principle $\mathsf{OPT}$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Reverse mathematics and uniformity in proofs without excluded middle

We show that when certain statements are provable in subsystems of constructive analysis using intuitionistic predicate calculus, related sequential statements are provable in weak classical subsystems. In particular, if a $Π^1_2$ sentence of a certain form is provable using E-HA${}^ω$ along with the axiom of choice and an independence of premise principle, the sequential form of the statement is provable in the classical system RCA. We obtain this and similar results using applications of modified realizability and the \textit{Dialectica} interpretation. These results allow us to use techniques of classical reverse mathematics to demonstrate the unprovability of several mathematical principles in subsystems of constructive analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stationary and convergent strategies in Choquet games

If NONEMPTY has a winning strategy against EMPTY in the Choquet game on a space, the space is said to be a Choquet space. Such a winning strategy allows NONEMPTY to consider the entire finite history of previous moves before making each new move; a stationary strategy only permits NONEMPTY to consider the previous move by EMPTY. We show that NONEMPTY has a stationary winning strategy for every second countable T1 Choquet space. More generally, NONEMPTY has a stationary winning strategy for any T1 Choquet space with an open-finite basis. We also study convergent strategies for the Choquet game, proving the following results. (1) A T1 space X is the open image of a complete metric space if and only if NONEMPTY has a convergent winning strategy in the Choquet game on X. (2) A T1 space X is the compact open image of a metric space if and only if X is metacompact and NONEMPTY has a stationary convergent strategy in the Choquet game on X. (3) A T1 space X is the compact open image of a complete metric space if and only if X is metacompact and NONEMPTY has a stationary convergent winning strategy in the Choquet game on X.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Topological aspects of poset spaces

We study two classes of spaces whose points are filters on partially ordered sets. Points in MF spaces are maximal filters, while points in UF spaces are unbounded filters. We give a thorough account of the topological properties of these spaces. We obtain a complete characterization of the class of countably based MF spaces: they are precisely the second-countable T_1 spaces with the strong Choquet property. We apply this characterization to domain theory to characterize the class of second-countable spaces with a domain representation.

0 citations0 reviewsNo code linkedOpen access