Bashicu matrix system

File:Cobson.png

Bashicu matrix system (BMS) is an ordinal notation system invented by BashicuHyudora. It is a sequence system, with the sequences in question being two-dimensional arrays of natural numbers (i.e. sequences of columns, where columns are sequences of natural numbers and have the same length). It is also an expansion system. The arrays, however, are only a concise encoding of a deeper underlying structure. In reality, BMS is about structures called "respecting forests" - sequences of elements with infinitely many "ancestry" relations.

Original definition

BMS is an expansion system with the base of the standard form being \( \{(\underbrace{0,0,...,0,0}_n)(\underbrace{1,1,...,1,1}_n) : n\in\mathbb{N}\} \) and the expansion \( A[n] \) of an array \( A \) at a natural number \( n \) being defined in the following way:

1. The parent of an entry \( x \) (an entry is a natural number in the array) is the last entry \( y \) before it in the same row, such that the entry directly above \( y \) (if it exists) is an ancestor of the entry above \( x \), and \( y<x \). The ancestors of an entry \( x \) are defined recursively as the parent of \( x \) and the ancestors of the parent of \( x \).
2. If \( A \) is empty, then \( A[n]=A \) for all natural numbers \( n \). Otherwise let \( C \) be the last column of \( A \), and let \( m_0 \) be maximal such that the \( m_0 \)-th element of \( C \) has a parent if such an \( m_0 \) exists, otherwise \( m_0 \) is undefined. Let \( G \) and \( B_0 \) be arrays such that \( A=G+B_0+(C) \), where \( + \) is concatenation, and the first column in \( B_0 \) contains the parent of the \( m_0 \)-th element of \( C \) if \( m_0 \) is defined, otherwise \( B_0 \) is empty.
3. Say that an entry in \( B_0 \) "ascends" if it is in the first column of \( B_0 \) or has an ancestor in the first column of \( B_0 \). Define \( B_1,B_2,...,B_n \) as copies of \( B_0 \), but in each \( B_i \), each ascending entry \( x \) is increased by \( i \) times the difference between the entry in \( C \) in the same row as \( x \) and the entry in the first column of \( B_0 \) in the same row as \( x \).
4. \( A[n]=G+B_0+B_1+...+B_n \), where \( + \) is again concatenation.

Interpretation

The definition uses parenthood and ancestry extensively, and can in fact be restated entirely in terms of that. The numbers are only there to encode this structure, similarly to how the numbers in Primitive Sequence System are only there to encode the hydra. Instead of considering individual entries and their parents/ancestors, it may be easier to consider a whole column \( C \) and its \( m \)-parent/\( m \)-ancestor for each \( m\in\mathbb{N} \), meaning the column containing the parent/ancestor of the \( m \)-th number in \( C \).

So this way, we have a structure \( A \) consisting of a finite sequence of elements (each represented by a column), and an infinite sequence of partial orders (\( m \)-ancestry), each partial order respecting the one before, and all of them respecting the order in which the elements appear in the sequence (a relation \( R \) respects a relation \( R' \) if \( R(x_1,x_2,...,x_n)\Rightarrow R'(x_1,x_2,...,x_n) \) for all \( x_1,x_2,...,x_n \), or equivalently, if \( R\subseteq R' \) using the usual encoding of relations as sets of ordered pairs).

Then if we let \( m_0 \) be minimal such that the last element of the sequence in \( A \) has an \( m_0 \)-parent, \( A[n] \) is the structure obtained from \( A \) by replacing the last element with \( n \) copies of the elements from its \( m_0 \)-parent to the element right before the last element, and letting the \( m \)-parent of the \( i \)-th copy of an element \( C \) be:
- The \( i \)-th copy of the \( m \)-parent of \( C \), if the \( m \)-parent of \( C \) is among the copied elements.
- The previous copy of \( C \) if \( C \) is the \( m_0 \)-parent of the removed element and \( m<m_0 \).
- The \( m \)-parent of \( C \) otherwise.

The equivalence of this and the original definition is essentially lemma 2.5 from the claimed proof of well-foundedness.

It can also be restated as a reflection property.^{(to be clarified)}

Well-orderedness and order types

For a long time, the problem of finding a proof of its well-orderedness was a famous problem in apeirology, but now there is at least a claimed proof. The proof utilizes stability, so the problem of finding a self-contained proof that BMS is well-ordered remains open for now. A related open problem is the well-orderedness of Y sequence, which is similar enough to BMS (below the limit of BMS) that it can be considered an extension.

BMS is expected to reach ordinals as high as a good ordinal collapsing function for ordinals that are \( \alpha-\Sigma_n- \)stable for some \( \alpha\in Ord \) and \( n\in\mathbb{N} \). However, because no such function has been defined yet, this is currently unprovable, considering the informal use of "good". The largest array for which an explicit value was proven is \( (0,0,0)(1,1,1) \), and that value is \( \psi(\Omega_\omega) \) using Buchholz's OCF.

Conversion algorithms

Note that the correctness of algorithms further than \((0,0,0)(1,1,1)\) is not proven. Let \(\varepsilon\) denote the empty array, and \(o(A)\) denote the converting-to-ordinals function.

Up to \(\varepsilon_0\)

1. \(o(\varepsilon) = 0\).
2. If we have an array \(A\), Then, we must have \(A = (0)A_0(0)A_1(0)A_2...(0)A_n\) for positive \(n\), where each of the \(A_i\) do not contain \((0)\) columns. Then, \(o(A) = \omega^{o(A_0^*)}+\omega^{o(A_1^*)}+...+\omega^{o(A_n^*)}\), where \(A^*\) denotes \(A\) with the first entries of each of its columns reduced by one.

References