Finite Unambiguity is Not Equivalent to Unambiguity
For a while I believed finite unambiguity to be equivalent to the other definitions of unambiguity.
Definition 1. Finite Unambiguity finite-unambiguity
Define a grammar to be finitely unambiguous if .
There is likely a better name for this.
Definition 2. Unambiguity as Subterminality unambiguity-as-subterminality
A grammar is unambiguous if the unique map into the terminal object is a monomorphism. That is, is a subobject of .
Definition 3. Unambiguity as Unique Map into Codomain unambiguity-as-unique-map
A grammar is unambiguous if for all grammars and maps we have .
In a category with terminal objects, this is equivalent to unambiguity defined via subterminality.
Definition 3.1. Unambiguity as Subterminality unambiguity-as-subterminality
A grammar is unambiguous if the unique map into the terminal object is a monomorphism. That is, is a subobject of .
We may use an analogy from the category of sets, however I had missed the infinite case when translating this idea to grammars.
It is true that if a grammar is unambiguous, then it is finitely unambiguous. However, the converse does not hold unless the grammar has finitely many parse trees for each string. This finiteness condition is a semantic one. If this proof of unambiguity were to be internalized, then it could maybe be captured through the lens of some grammar of finite cardinals.
Let . is finitely unambiguous but not unambiguous. The isomorphism between and amounts to building a bijection between and , which is straightforward.