Tuesday, May 28, 2019
Mathematical theories of semantic relations
All of the different semantic relations which make up an ontology have certain mathematical theories associated with them. In summary, the mathematical theories of equivalence relations, partial orders, and boolean algebras and set systems can be used to better understand certain semantic relations. This is why these concepts play a fundamental role, the theory of synonymy is the most important of all of these because it introduces the fundamental idea of the ontology of equivalence relations.
Thursday, May 16, 2019
Mathematical theories of taxonomy and hyponymy
Set theory is the mathematical context in which relations of taxonomy and hyponymy are defined. Set theory defines a hierarchy of concepts of sets, set systems, sets of sets of sets, etc. Sets and proper classes are taxonomically related to one another if they are subsets or subclasses of one another. So taxonomy can be described by the mathematical theory of set inclusion.
Hyponomy is distinguished from taxonomy by the fact that it describes instances rather then subclasses. So the instances of hyponymy relations need not be classes themselves. Hyponomy is particularly interesting when it is applied to sets and classes. To give an example, the class of antisymmetric binary relations is a taxonomical subclass of the class of binary relations and it is an hyponym of the class of subclass closed families.
A mathematical taxonomy will include all the different sets and classes of mathematical structures, elements, and expressions that any given mathematical theory will have. A mathematical taxonomy is provided by graphclasses, but otherwise there does not seem to be a general mathematical taxonomy available. The mathematical taxonomy could be enriched with hyponomy and related relations to create a general formal ontology of mathematics.
Hyponomy is distinguished from taxonomy by the fact that it describes instances rather then subclasses. So the instances of hyponymy relations need not be classes themselves. Hyponomy is particularly interesting when it is applied to sets and classes. To give an example, the class of antisymmetric binary relations is a taxonomical subclass of the class of binary relations and it is an hyponym of the class of subclass closed families.
A mathematical taxonomy will include all the different sets and classes of mathematical structures, elements, and expressions that any given mathematical theory will have. A mathematical taxonomy is provided by graphclasses, but otherwise there does not seem to be a general mathematical taxonomy available. The mathematical taxonomy could be enriched with hyponomy and related relations to create a general formal ontology of mathematics.
Wednesday, May 15, 2019
Mathematical theories of meronomy
Merenomical relations have three axioms : reflexivity, antisymmetry, and transitivity.
Multiples:
A multiple is an element of a partial order whose set of proper predecessors is upper bounded. It is then a multiple of the upper bound of its set of proper predecessors, and elements can be multiples of multiples and so on. This leads to the multiset theoretic representation of the elements of a partial order.
Join irreducibles
It can easily be seen that the join irreducible elements of a finite lattice are precisely the multiples of other elements, with atoms being the elements that cover the lower bound. A multiatomistic lattice is one whose join irreducibles are either atoms or multiples of them. Multiatomistic distributive lattices describe multiset inclusion. In the infinite case, the relation between join irreducibles and multiples of elements still holds, but it doesn't in the case that joins are restricted to pairs of elements. In that case it is only true when the elements of the lattice are lower isolated.
Suprema irreducibles
Elements of a partial order are called suprema irreducible if they are not included in the suprema of their set of proper predecessors. This concept doesn't seem to appear in the literature, so I introduced it myself as a generalization of the join irreducible elements of a lattice. Well elements of lattices can be represented by multisets (or simply sets in the case in which the lattice is atomistic) the case of general partial orders is somewhat different. Two elements of a general partial order may have the same set of suprema irreducible predecessors. The set of suprema irreducible predecessors forms a monotone function which may produce the same output for different values.
The special case of ordered collections motivates the definition of suprema irreducibles. Consider the set of ordered collections partially ordered by inclusion. In this well known partial order, the only suprema irreducibles are the equal lists. These suprema irreducibles are actually all multiatomic elements of the partial order, because they are all multiples of the singular lists. This makes the partial ordering on ordered collections multiatomistic. Emerging from this relation is the underlying multiset of any ordered collection which describes the suprema irreducible predecessors of the collection. Two elements may have the same underlying multiset, so this function loses information but it is still monotone. Since this function information these elements can be seen to have additional structure about them (structural multisets) which together with the underlying multiset describes the structure.
Structural multisets
These leads to the theory of structural multisets, which are general data structures that have an underlying multiset as well as other sets and multisets about them which describe their structure. Included within the merenomic relation of structural multisets is the notion of an induced structure, which is a structure induced by taking a submultiset of the underlying multiset of a structure. Induced substructural orderings are not necessarily lattices, and can be used to describe general partial ordering relations. The partial ordering on ordered collections is an induced substructural ordering on its multiset-theoretic suprema irreducible representations. Well ordered collections are represented as structural multisets, other structures like rings can be represented as structured sets. All composite structures can be described by structural multisets.
- Reflexive: everything is a part of itself
- Antisymmetric: nothing is a part of its parts
- Transitive: everything that is a part of something which is a part of something else is a part of that something else
Multiples:
A multiple is an element of a partial order whose set of proper predecessors is upper bounded. It is then a multiple of the upper bound of its set of proper predecessors, and elements can be multiples of multiples and so on. This leads to the multiset theoretic representation of the elements of a partial order.
Join irreducibles
It can easily be seen that the join irreducible elements of a finite lattice are precisely the multiples of other elements, with atoms being the elements that cover the lower bound. A multiatomistic lattice is one whose join irreducibles are either atoms or multiples of them. Multiatomistic distributive lattices describe multiset inclusion. In the infinite case, the relation between join irreducibles and multiples of elements still holds, but it doesn't in the case that joins are restricted to pairs of elements. In that case it is only true when the elements of the lattice are lower isolated.
Suprema irreducibles
Elements of a partial order are called suprema irreducible if they are not included in the suprema of their set of proper predecessors. This concept doesn't seem to appear in the literature, so I introduced it myself as a generalization of the join irreducible elements of a lattice. Well elements of lattices can be represented by multisets (or simply sets in the case in which the lattice is atomistic) the case of general partial orders is somewhat different. Two elements of a general partial order may have the same set of suprema irreducible predecessors. The set of suprema irreducible predecessors forms a monotone function which may produce the same output for different values.
The special case of ordered collections motivates the definition of suprema irreducibles. Consider the set of ordered collections partially ordered by inclusion. In this well known partial order, the only suprema irreducibles are the equal lists. These suprema irreducibles are actually all multiatomic elements of the partial order, because they are all multiples of the singular lists. This makes the partial ordering on ordered collections multiatomistic. Emerging from this relation is the underlying multiset of any ordered collection which describes the suprema irreducible predecessors of the collection. Two elements may have the same underlying multiset, so this function loses information but it is still monotone. Since this function information these elements can be seen to have additional structure about them (structural multisets) which together with the underlying multiset describes the structure.
Structural multisets
These leads to the theory of structural multisets, which are general data structures that have an underlying multiset as well as other sets and multisets about them which describe their structure. Included within the merenomic relation of structural multisets is the notion of an induced structure, which is a structure induced by taking a submultiset of the underlying multiset of a structure. Induced substructural orderings are not necessarily lattices, and can be used to describe general partial ordering relations. The partial ordering on ordered collections is an induced substructural ordering on its multiset-theoretic suprema irreducible representations. Well ordered collections are represented as structural multisets, other structures like rings can be represented as structured sets. All composite structures can be described by structural multisets.
Tuesday, May 7, 2019
Mathematical theories of synonmy and equivalence
I will begin the analysis of semantic relations with the relations of synonymy and equivalence because this is an area of study that is significantly under-explored. The theory of equivalence relations is one thing that sets this ontology project apart from others like it. The theory of equivalence is often taken for granted in traditional mathematics as it starts with sets that have an equivalence relation already attached to them. The ontology of equivalence relations should be a significant part of any project in ontology with formally defined semantics.
As multisets have an equivalence relation on their elements, we can classify them by the extent to which their elements are equal to one another. Multiset repetitiveness is a metric which effectively describes the extent to which a multiset has elements which are equal to one another. Different classes of multisets then can be formed based upon different degrees of repetitiveness, as near sets are sets which have at most one repeated element, and sets have no repeated elements. Max multiplicity two multisets have at most one repetition for each individual element so they are a generalization of near multisets. In this way, sets emerge in the multiset ontology based upon the extent of equivalent elements in them.
Well sets are classifiable as multisets which have the least amount of equal elements there is a conjugate notion. Equal multisets have members that are all completely equal to one another, and near equal multisets have at most one element not equal to all the others, well max order two multisets have at most two distinct elements. In this way the equivalence relations on multisets can be classified either by the degree of equality of the degree of distinctiveness. The equal multisets are the most equal and sets are the most distinct. Refinement is the process of making things more distinct, well coarsification is the process of making things more equal.
Functional coarsification occurs when given some multiset, some function can be applied to each member of the multiset in a similar manner to the higher-order function map applied to lists. This then produces a new multiset that is at least as coarse, or more coarse then the previous one. Consider the power set, {{} {0} {1} {2} {0 1} {0 2} {1 2} {0 1 2}} applying the cardinality function to each member produces {0,1,1,1,2,2,2,3} which is more coarse because it is a multiset with equal elements rather then simply a set. In this way, functions as simple as cardinality can be used to produce multisets with equal members from sets. The lack of widespread support for multisets is part of the larger issue of a lack of a theory of equivalence.
Equivalence relations are especially applicable to structures like lists which have different specific slots associated with them like the first element, the second element, and so on. The same is true of records and related data structures, essentially they have already established properties structurally associated with them. This leads to the ontology of equivalence relations on pairs, which are defined by the amount of data that can be acquired from the pairs. The pair of pairs relation produces no information, the equal first gets the first element, the equal second gets the second element, and the equal pairs gets the combination of both the first and second elements. These properties are combined in a partial order based upon the amount of information acquired by them.
A similar ontology of equivalence relations can be used to describe the properties of triples, quadruples, and related sorts of ordered collection structures. Multisets themselves have various properties that can be further partially ordered like signature, repetitiveness, the underlying set, order, max multiplicity, etc which leads to an ontology of equivalence relations of multisets which is the next aspect of describing multisets besides the ontology of multisets themselves. The ontology of equivalence relations should include more then just the containment relations described above, but also information about independence and covering so that rather two properties are complementary can be decided.
The ontology displayed below consists of classes of binary multirelations with zero or more distinctiveness relations associated with them. Binary multirelations have no distinctiveness relations. Binary relations have one distinctiveness relation: the identity, which means that no two elements can be the same. This is the same as saying that they are essentially sets. Unary operations are further distinct with respect with respect to their first element, inverse unary operations are distinct with respect to their second element, and reversible unary operations are distinct with respect to both. Unique relations are distinct with respect to the trivial equivalence relation because they have no more then one element. All these distinctiveness relations together form the free distributive lattice on two elements.
One can immediately see that sets and functions both emerge in the same manner in the multiset theoretic ontology : from distinctiveness relations. Sets emerge from distinctiveness with respect to identity, and functions emerge from stronger notions of distinctiveness. In fact the set theoretic definition of functions is based upon the condition that each of the first elements of the relation is distinct from one another. All these relations of distinctiveness are displayed above with respect to containment.
Function and map like properties can be acquired from any collection with some kind of distinctiveness relation. The ontology of equivalence relations on numbers was described previously, so based upon that consider absolute-value distinct collections of integers. The oriented range {1,-2,3,-4,5,-6,7,-8,9} is an example of such a collection with a distinctiveness relation with respect to the absolute value. This can be considered then as a function from the range to certain signs like {1 +, 2 -, 3 +, 4 -, 5 +, 6 -, 7 +, 8 -, 9 +}. This demonstrates that functions, just like sets, are an emergent property of distinctiveness relations.
Ontology of multisets
The difference between sets and multisets is that multisets can have repeated, or equal elements. This means that every multiset theoretically comes equipped with an equivalence relation associated with it, which tells which elements are equal to one another. Multisets can therefore be classified, ontologically, based upon the equivalence relation between elements of them. Every theory of equality should therefore start with the ontology of multisets as multisets can be classified based upon the equivalence relations on them.As multisets have an equivalence relation on their elements, we can classify them by the extent to which their elements are equal to one another. Multiset repetitiveness is a metric which effectively describes the extent to which a multiset has elements which are equal to one another. Different classes of multisets then can be formed based upon different degrees of repetitiveness, as near sets are sets which have at most one repeated element, and sets have no repeated elements. Max multiplicity two multisets have at most one repetition for each individual element so they are a generalization of near multisets. In this way, sets emerge in the multiset ontology based upon the extent of equivalent elements in them.
Well sets are classifiable as multisets which have the least amount of equal elements there is a conjugate notion. Equal multisets have members that are all completely equal to one another, and near equal multisets have at most one element not equal to all the others, well max order two multisets have at most two distinct elements. In this way the equivalence relations on multisets can be classified either by the degree of equality of the degree of distinctiveness. The equal multisets are the most equal and sets are the most distinct. Refinement is the process of making things more distinct, well coarsification is the process of making things more equal.
Functional coarsification occurs when given some multiset, some function can be applied to each member of the multiset in a similar manner to the higher-order function map applied to lists. This then produces a new multiset that is at least as coarse, or more coarse then the previous one. Consider the power set, {{} {0} {1} {2} {0 1} {0 2} {1 2} {0 1 2}} applying the cardinality function to each member produces {0,1,1,1,2,2,2,3} which is more coarse because it is a multiset with equal elements rather then simply a set. In this way, functions as simple as cardinality can be used to produce multisets with equal members from sets. The lack of widespread support for multisets is part of the larger issue of a lack of a theory of equivalence.
Ontology of equivalence relations
The ontology of equivalence relations is not about classifying equivalence relations themselves, but rather about creating an ontology consisting of equivalence relations and the relations between them. Equivalence relations form a lattice, with operations of containment, independence, and covering produced together with them. The combination of independence and covering also produces complementation, so an ontology of equivalence relations should include knowledge about which equivalence relations are complementary to one another.- Containment : an equivalence relation is contained in another if it is finer then it
- Independence : two equivalence relations are independent if their meet is minimal
- Covering : two equivalence relations cover one another if their join is maximal
Equivalence relations are especially applicable to structures like lists which have different specific slots associated with them like the first element, the second element, and so on. The same is true of records and related data structures, essentially they have already established properties structurally associated with them. This leads to the ontology of equivalence relations on pairs, which are defined by the amount of data that can be acquired from the pairs. The pair of pairs relation produces no information, the equal first gets the first element, the equal second gets the second element, and the equal pairs gets the combination of both the first and second elements. These properties are combined in a partial order based upon the amount of information acquired by them.
A similar ontology of equivalence relations can be used to describe the properties of triples, quadruples, and related sorts of ordered collection structures. Multisets themselves have various properties that can be further partially ordered like signature, repetitiveness, the underlying set, order, max multiplicity, etc which leads to an ontology of equivalence relations of multisets which is the next aspect of describing multisets besides the ontology of multisets themselves. The ontology of equivalence relations should include more then just the containment relations described above, but also information about independence and covering so that rather two properties are complementary can be decided.
Ontology of binary multirelations
The ontology of equivalence relations can be used to classify multirelations. The ontology of equivalence relations of ordered pairs is especially important to the classification of binary multirelations as they consist of ordered pairs. Given a multiset and an equivalence relation, the multiset is distinct with respect to that equivalence relation if no two elements in the multiset are equal with respect to that equivalence relation.The ontology displayed below consists of classes of binary multirelations with zero or more distinctiveness relations associated with them. Binary multirelations have no distinctiveness relations. Binary relations have one distinctiveness relation: the identity, which means that no two elements can be the same. This is the same as saying that they are essentially sets. Unary operations are further distinct with respect with respect to their first element, inverse unary operations are distinct with respect to their second element, and reversible unary operations are distinct with respect to both. Unique relations are distinct with respect to the trivial equivalence relation because they have no more then one element. All these distinctiveness relations together form the free distributive lattice on two elements.
One can immediately see that sets and functions both emerge in the same manner in the multiset theoretic ontology : from distinctiveness relations. Sets emerge from distinctiveness with respect to identity, and functions emerge from stronger notions of distinctiveness. In fact the set theoretic definition of functions is based upon the condition that each of the first elements of the relation is distinct from one another. All these relations of distinctiveness are displayed above with respect to containment.
Function and map like properties can be acquired from any collection with some kind of distinctiveness relation. The ontology of equivalence relations on numbers was described previously, so based upon that consider absolute-value distinct collections of integers. The oriented range {1,-2,3,-4,5,-6,7,-8,9} is an example of such a collection with a distinctiveness relation with respect to the absolute value. This can be considered then as a function from the range to certain signs like {1 +, 2 -, 3 +, 4 -, 5 +, 6 -, 7 +, 8 -, 9 +}. This demonstrates that functions, just like sets, are an emergent property of distinctiveness relations.
Theory of functions
The theory of functions must start from the theory of equivalence relations as every function has a kernel associated with it which states that two elements are equal when they are equal with respect to the function. This describes completely the irreversiblity of the function, as functions tend to lose information and be irreversible. The extent to which functions lose or gain information is described by the containment ordering of equivalence relations. To make a function reversible all that is needed is a complementary equivalence relation. This is how reversible destructuring operations are produced.References
Computer-aided research of synonymy and antonymy https://www.aclweb.org/anthology/C69-5801Saturday, May 4, 2019
Semantic relations
Every ontology is based upon information concepts like classes and individuals and the semantic relations between them. In order to describe the organization of an ontology it is a good idea to take the different semantic relations between elements as a starting point. Each of the different semantic relations like synonomy, antonymy, hyponomy, merenomy, and holonymy play a fundamental role in ontology. Each of them is worth reviewing separately in more detail.
- Synonmy and antonymy : equal and opposite elements
- Hyponomy and taxonomy : generalization and specialization
- Mereonomy and holonymy : relating parts and their wholes
Friday, May 3, 2019
Generalized list processing
Lisp is commonly characterized by list processing, as lists are the fundamental data structure of Lisp. Generalizations of lists can be formed by equivalence classes to get sets, multisets, and related structures which are essentially just lists with certain amount of the ordering removed. A generalized Lisp programming language can deal with these other list-like structures such as sets and multisets (sets are even introduced in Clojure) which is especially important as sets are typically used as the foundation of mathematics. Generalized list processing deals with sets, multisets, lists, and related structures.
It can be seen that most programming in general is largely List processing, and this fact is best realized in Lisp dialects. There are some programming languages which take the associative array or some equivalent as the fundamental structure and these languages and others so commonly used do not get people to realize the truth of List processing. Lisp isn't just about homoiconity but also its choice of data structures. It just happens that it chose the type of data structure most suited for defining programs. To deal with the problem of associative arrays, I will instead reduce them to binary relations which are lists of pairs, which will be an important part of our ontology.
It can be seen that most programming in general is largely List processing, and this fact is best realized in Lisp dialects. There are some programming languages which take the associative array or some equivalent as the fundamental structure and these languages and others so commonly used do not get people to realize the truth of List processing. Lisp isn't just about homoiconity but also its choice of data structures. It just happens that it chose the type of data structure most suited for defining programs. To deal with the problem of associative arrays, I will instead reduce them to binary relations which are lists of pairs, which will be an important part of our ontology.
Thursday, May 2, 2019
Equivalence classes of lists
Equivalence relations can be formed that determine that certain lists are equal to one another. One way of doing that is to take the orbit of a class of permutation groups acting on lists. These are equivalence relations that determine that lists are equal to one another up to a reordering. Different types of equivalence classes of lists are produced from symmetric groups, alternating groups, cyclic groups, and so on. Generally, transitive groups are selected here to determine collection classes.
Symmetric lists:
The first thing to realize is that symmetric lists are multisets, which means that any list can be treated as a multiset by simply ignoring its ordering. In this sense, it is perhaps not necessary to have a different data type for multisets, sets, etc (except for the purpose of creating an equivalence class). Then the important question is which operations on lists are invariant under reordering, the multiplicity function for example is invariant under reordering.
Alternating lists
Alternating lists are similar to symmetric lists, in the sense that they have relatively few permutations. Generally speaking, collections of this type are rarely mentioned.
Cyclic lists:
Cyclic lists or circular lists, are lists which are invariant up to rotation. Cyclic linked lists provide a possible implementation. Even though these are perhaps the next most useful class of lists, after examining the different types of collections determined by permutations, I concluded that symmetric lists are the most fundamental because they are a partially ordered multiset, so the most important collections are related to partially ordered multisets and aren't simply general relations.
Symmetric lists:
The first thing to realize is that symmetric lists are multisets, which means that any list can be treated as a multiset by simply ignoring its ordering. In this sense, it is perhaps not necessary to have a different data type for multisets, sets, etc (except for the purpose of creating an equivalence class). Then the important question is which operations on lists are invariant under reordering, the multiplicity function for example is invariant under reordering.
Alternating lists
Alternating lists are similar to symmetric lists, in the sense that they have relatively few permutations. Generally speaking, collections of this type are rarely mentioned.
Cyclic lists:
Cyclic lists or circular lists, are lists which are invariant up to rotation. Cyclic linked lists provide a possible implementation. Even though these are perhaps the next most useful class of lists, after examining the different types of collections determined by permutations, I concluded that symmetric lists are the most fundamental because they are a partially ordered multiset, so the most important collections are related to partially ordered multisets and aren't simply general relations.
Wednesday, May 1, 2019
ANSI Common Lisp
I finished most of ANSI Common Lisp. I got this one because it was made by Paul Graham who is well known in the Lisp community, and I have been trying to read as many programming books as possible. There seem to be more books on Lisp dialects then on virtual machines. Anyways, I already mentioned FSet as a possibility to add better support for sets and multisets to Common Lisp. Another possibility is to simply treat lists like sets and multisets. The Common Lisp function member is already available to you and a multiplicity function is easy to implement. One could imagine that my post on core data structures perhaps wasn't even necessary, all that is necessary is a Lisp.
Subscribe to:
Posts (Atom)