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.

We consider three mathematical theorems in the paper:

  1. VSB: Every countable vector space over $\mathbb{Q}$ has a basis.
  2. GAC: Every countable graph has a maximal set of vertices no two of which are in the same component.
  3. EMB: Every e-matroid has a basis.

Here an e-matroid consists of a countable set $M$ and an enumeration $e(1)$, $e(2)$, $\ldots$ of finite “dependent” subsets of $M$. A set that is does not contain any dependent subset is declared to be “independent”. The following axioms are required:

  1. The empty set is not dependent.
  2. Finite supersets of dependent sets are dependent. This is formally stated as
    $$(\forall i)(\forall Y \in [M]^{<\mathbb{N}})[ e(i) \subseteq Y \to (\exists j) (e(j) = Y)].$$
  3. Exchange: if $X$ and $Y$ are independent finite sets with $|X| < |Y|$ then there is some $z \in Y$ such that $X \cup \{z\}$ is independent.

These axioms are familiar from matroid theory, and indeed each e-matroid is a matroid in the classical sense, if we take the range of $e$ as the collection of dependent sets.

Each of the three mathematical theorems VSB, GAC, and EMB can be considered as a principle of second-order arithmetic and as a problem in the sense of Weihrauch. For example, here is how to read VSB in these ways:

  • Principle form of VSB: Every countable vector space over $\mathbb{Q}$ has a basis
  • Problem form of VSB: Consider the set $$\{ (V,B) : V \text{ is a countable vector space over } \mathbb{Q}, B \text{ is a basis for } V\}$$ as a Weihrauch problem.

The theorems GAC and EMB can be read similarly in each of the two ways.

Previous work

It is well known in the Reverse Mathematics literature that VSB is equivalent as a principle to $\mathrm{ACA}_0$ over $\mathrm{RCA}_0$.

In a previous paper “On the existence of a connected component of a graph“, Kirill Gura, Jeff Hist and I studied the strength of GAC as a problem as a principle and a Weihrauch problem, showing that the principle is equivalent to $\mathrm{ACA}_0$ over $\mathrm{RCA}_0$ and the problem is strongly Weihrauch equivalent to $\widehat{\mathsf{C}}_{\mathbb{N}}$, which is the parallelization of the closed choice principle $\mathsf{C}_\mathbb{N}$.

In that paper, we also studied a finitary version of GAC, which we call $\mathrm{GAC}_n$, which states that, if there is a set of $n$ nodes such that every node is connected to at least one of these by a path, then graph has a maximal antichain. We showed that GAC is provable in $\mathrm{RCA}_0$ as a principle, while as a problem it is strongly Weihrauch equivalent to $\mathsf{C}_\mathbb{N}$. Note that, in the problem form, the number $n$ is provided as part of the input of the problem.

Summary of results

In our new paper, Jeff and I study similar restricted versions $\mathrm{VSB}_n$ and $\mathrm{EMB}_n$ of VSB and EMB.

We also study slightly modified versions $\mathrm{GAC}_{<\omega}$, $\mathrm{VSB}_{<\omega}$ and $\mathrm{EMB}_{<\omega}$. These postulate an upper bound on the size of an independent set. For example, $\mathrm{EMB}_{<\omega}$ postulates that there is an $n$ such that every set of size $n$ is dependent. In the problem form of these theorems, the bound $n$ is provided as part of the input.

Therefore, there are nine theorems of interest in our paper, counting three versions of each of $\mathrm{VSB}_{<\omega}$, $\mathrm{VSB}_{<\omega}$, and $\mathrm{GAC}_{<\omega}$. We show that there are very close relationships between the theorems, in all three versions. The following table summarizes the results. The results for GAC and $\mathrm{GAC}_n$ are from the paper by Gura, Hirst and Mummert, as is the Reverse Mathematics result for $\mathsf{GAC}_{<\omega}$, and the results for VSB are classical. The rest of the results in the table are established in the new paper.

VSB
GAC
EMB
$\mathrm{VSB}_{<\omega}$
$\mathrm{VSB}_{<\omega}$
$\mathrm{GAC}_{<\omega}$
$\mathrm{VSB}_{n}$
$\mathrm{VSB}_{n}$
$\mathrm{GAC}_{n}$
Principle is equivalent
over $\mathsf{RCA}_0$ to:
$\mathrm{ACA}_0$ $\Sigma^0_2$ induction
with parameters
$\mathrm{RCA}_0$
Property is strongly
Weihrauch equivalent to:
$\widehat{\mathsf{C}}_{\mathbb{N}}$ $\mathsf{C}_{\text{max}}$ $\mathsf{C}_{\mathbb{N}}$

Here $\mathsf{C}_{\text{max}}$ is a principle which says the following: if $e$ is an enumeration of finite nonempty subsets of $\mathbb{N}$, and there is an $n > 0$ such that every set of size $n$ is enumerated, then there is a maximal-under-$\subseteq$ set that is not enumerated. This is, as far as we know, a new principle between $\widehat{\mathsf{C}}_{\mathbb{N}}$ and $\mathsf{C}_{\mathbb{N}}$. I suspect it is strictly between them, in the sense of Weihrauch reducibility, but this is still an open problem.

One particularly interesting aspect of this work is the equivalences with $\Sigma^0_2$ induction. The tables shows several relatively natural theorems have nontrivial induction strength in Reverse Mathematics. The fact that these are all equivalent to $\mathsf{C}_{\text{max}}$ suggests that we should explore the strength of the Weihrauch principle in more detail.

This entry was posted in Papers, Research. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *