Literal and symbolic ontology

The mathematical ontology can contain at least two components (1) the literal ontology which doesn't deal with symbolic elements and (2) the symbolic ontology. I already specified that the core mathematical collection types are sets, multisets, and sequences. So the literal ontology could include things like sets of sets, multisets of sets, sets of multisets, multisets of multisets, sets of sets of sets, and so on well multisets of sequences and sets of sequences are multirelations and relations respectively. Each of these different types of classes form different elements of the mathematical ontology constructed just from core data types.

The symbolic ontology can include symbols like the symbols referring to addition and multiplication, and in this way, it can deal with all the other types of data structures encountered in mathematics. All mathematical structures must be representable by some finite symbolic structure in order for them to be reasoned about. So we can classify types of polynomials like univariate polynomials, quadratic univariate polynomials, linear univariate functions, multivariable polynomials, etc. Lattice polynomials can be formed symbolically as related to lattices from abstract algebra. Eventually, even differential equations can be represented as symbolic expressions.

Mathematical equivalence relations

The only significant difference between mathematics and computation is that mathematical data structures can be implemented in multiple ways, like how a number can be a floating point number or a fraction. The same is basically true in computable set theory, as it is necessary to have multiple representations of sets. Von Neumann ordinals for example, grow exponentially so it makes more sense to represent them with a different data type with a single number rather then an exponentially large tree. Mathematics deals with abstract interfaces then rather then particular data types.

It remains to implement an equivalence relation to see if different data types have the same mathematical value. The axiom of extensionality, one of the fundamental axioms of set theory, states that two sets are equal if they have the same members regardless of their representation. It is therefore necessary to have an equivalence relation on sets that recursively check them for equality. Likewise, it is generally useful to have an equivalence relation for numbers, Clojure for example has == to check the equality of numbers and most programming languages have something similar. Mathematical meaning can be defined by an equivalence relation between computable data structures. Then mathematical ontology is the classification of objects up to the mathematical equivalence relation.

Clojure multisets

The only core mathematical data structure that is missing from Clojure is multisets. Clojure already provides implementations of all the other core data structures. One good thing about Clojure is its generic collections interfaces, so all collections are seqable, countable, etc. This solves the problem of providing all the core data structures necessary for Clojure. Of course, the same core data structures are the basis of any ideal Lisp dialect so for Common Lisp you could use FSet.

(deftype Multiset [multiplicities]
  clojure.lang.Seqable
  (seq [this]
    (if (empty? multiplicities)
      nil
      (apply
       concat
       (map
        (fn [key]
          (repeat (get multiplicities key) key))
        (keys multiplicities)))))
  
  clojure.lang.Counted
  (count [this]
    (apply + (vals multiplicities)))

  Object
  (equals [this x]
    (and
     (instance? Multiset x)
     (.equals (.multiplicities this) (.multiplicities x))))
  (hashCode [this]
    (hash-combine (hash multiplicities) Multiset))
  (toString [this]
    (str "*{" (clojure.string/join " " (seq this)) "}")))

(defmethod print-method Multiset [v ^java.io.Writer w]
  (.write w (.toString v)))

In my posts last month on degree reductions and set theory in a multiset theoretic context I explained the need for multisets and why they are fundamentally useful even for combinatorial set theory. It is easy then to get the multiset of some collection which is why every collection type is a structural multiset.

(defn multiset
  [coll]

  (Multiset. (frequencies coll)))

The core collection types are lists, sets, and multisets as they are general collections of items. Most other concepts can be constructed from them. An ideal Lisp dialect should focus on lists, sets, and multisets. A great deal can be done by restricting yourself to a few core data types. Maps like {:x 1, :y 2} are not fundamental because they are a special type of binary relation. What interests me is how to build an ontology of these core data types to begin with consisting of computable predicate functions.

Core data structures

The core data structures of any reasoning system capable of dealing with symbolic expressions will be relatively Lisp-like: it will have lists and related collections as well as atoms. I will talk about these data structures and how they fit into a mathematical context. In the purest sense of the original Lisp programming can be made to be virtually indistinguishable from mathematics.

Collection data structures:
The most important collection structures are sets, multisets, and lists. All of these can be described mathematically as corresponding to a collection monoid. The collection monoid for sets is union, for multisets it is sum, and for lists it is concatenation. A partial order emerges from each of these monoids, describing how each collection can be decomposed and recombined in the collection monoid. These are the subsets, submultisets, and consecutive subsequences ordering.

• Set
• Multisets
• Lists

All of these things are mathematical data structures which are also used in computation. Lists may have multiple implementations like vectors and sequences, but then we can get their meaning with a mathematical equality relation. A vector and a sequence with the same values are mathematically equal if they have the same elements. As a consequence, we can get to the mathematical meaning of lists. Multisets are underused, but they are worth including as well because they have a monoid associated with them.

As I described previously, ontologically these collection data structures belong to the broader class of structural multisets. Actually, all of these collection structures are partially ordered multisets or partitioned posets. The isomorphism type of a multiset is the isomorphism type of a partition of a set, and the isomorphism type of a list is the isomorphism type of the partition of a total order.

One thing that is worth commenting on is the fact that hash maps are not listed here. Clojure implements these and hash a literal syntax for them. Mathematically, however, they can be better understood as special types of binary relations which can already be described with sets and lists. Then hash maps belong to the broader mathematical ontological category of binary relations, which is well understood. Hash maps are a specialized binary relation data structure. When you call seq on one you even get a collection of ordered pairs.

Atomic data structures:
There isn't much to comment on here as the atomic data structures are roughly what you get from Clojure and related languages. There are two types of atomic data structures: the numeric data structures and the text related data structures. In order to get the mathematical meaning from a numeric data structure, it is necessary again to have a mathematical equivalence relation so that a floating point number with the same value is equal to a rational with the same value. Text related data structures like symbols have no mathematical meaning here, but they are going to be useful eventually for the symbolic representation of data structures like polynomials.

Basics of the ontology of mathematics

Our mathematical ontology will start with some structures that are distributive lattice ordered like sets, multisets, and magnitude numbers. We can group the notions of sets and multisets together as unordered collections. Sets can be considered special classes of multisets, or at least unordered collections, whose elements are all distinct. An ontology of multisets can be constructed which includes sets as a member as well as other classes like equal multisets, whose members are all the same, singular multisets who have only one element, unique multisets, order two multisets, powerful multisets, regular multisets, and so on. Then classes of sets are special elements of this ontology.

Likewise, an ontology of magnitude numbers could be constructed. The most obvious thing to include within this ontology is the rational numbers. Then different computable subclasses of the rational numbers can be included hierarchically, and there is a whole theory of classes of magnitude numbers based upon total order theory which I can talk about more later. Scattered sets of rational numbers include integers, natural numbers, negative integers, unit fractions, half integers, and so on. Dense sets of rational numbers include intervals like the set of rational numbers from zero to one.

Nested types of this structures can be constructed to get sets of sets, sets of multisets, multisets of sets, and multisets of multisets as well as multisets of numbers and sets of numbers. Additive partitions for example can be classified as multisets of positive integers. Then additive divisions can be classified as the intersection of additive partitions and equal multisets. One thing that is noticeably missing from this ontology is the notion of an ordered pair or a list. Based upon our multiset theoretic foundation, lists will be classified as structured multisets.



Anything that is a structure other then an unordered collection like a set or a multiset is a structural multiset of some kind. It follows that relations are sets of structural multisets and particularly sets of ordered multisets. Given a relation we can also produce some multiset of multisets from the relation by getting the multiset of underlying multisets of the structures in the relation. This is only a set of multisets in the special case in which the relation is fully antisymmetric. This is a greater degree of distinctiveness then simply being a relation rather then a multirelation.

The classification of different types of lists and sequences will proceed from the fact that they are ordered multisets. Each different type of multiset will produce a different type of ordered multiset corresponding to it. An ordered additive paritition for example is often called a composition. An ordered family is a distinct list of sets and an ordered multifamily is any list of sets. Different classes of ordered multisets emerge from different types of relations, but of course, there are also special types of sequences based upon their own definition. Monotone sequences for example are a special type of sequence whose classification is not based upon the underlying multiset. This produces an ontology of sets, multisets, lists, and magnitude numbers.

Eventually relations and set systems can be used to construct the different types of structured sets like rings, fields, topologies, metrics, measures, graphs, hypegraphs, categories, pointed sets, partially ordered sets, and so on. Elements can include any of the elements of these different abstract structures, like complex numbers as elements of a particular field. This would lead to a much more comprehensive ontology of mathematics. Notice that here I focused mainly on numbers, sets, multisets, and lists and nested collections of them. That is because these are the basic structures needed to create symbolic expressions. The only thing missing is text related structures like characters, strings, and symbols and then we can describe all the data structures used in symbolic expressions. This is necessary because ultimately a significant portion of the structures encountered like polynomials will be defined symbolically rather then literally.

Constructing an ontology of mathematics

A formal ontology and knowledge base dedicated to mathematical concepts should be constructed. It is immediately evident that the foundation of this ontology should be set theory, but even more generally it should be based upon distributive lattice theory which is the theory of lattices whose elements are most like sets. All the foundational concepts of ontology like classes and relations are essentially set theoretical so ontology and set theory belong together. A major component of this ontology should the ontology of set systems.

An important part of mathematical ontology historically has been the construction of all the concepts of mathematics using set theory. This lead to things like defining ordered pairs as kuratowski pair set systems and defining numbers as Von Neumann ordinals. All of these different classes of sets themselves can be organized hierarchically into an ontology, but so far as I can tell no one else has done that. The best example of a project of this sort is graphclasses but it has a limited scope and isn't based upon set theory or multiset theory.

Mathematics requires a set theoretic ontology of categories of structures and their relations. Well the starting foundation will be sets, multisets, and related structures this ontology can be extended to include all kinds of structural sets and multisets as well as symbolic expressions like polynomials. In doing so, all mathematical constructs can be categorized into an ontology. I will describe how this can be done.