The concept of a total ordering relation plays a fundamental role in mathematics. Sequences are a type of total ordering in which elements can occur more then once. Sequences in which no element appears more then once are no different then a total order. The importance of this concept derives from the importance of total orders. By combining the theory of total orders and sequences with set theory we can get the theory of relations which deals with sets of sequences.
Given a partial ordering relation, sequences in the partial order are called monotone non-decreasing if no two elements coming after one another are ever less then one another in the partial order. It is monotone increasing if they are not equal either. A partial ordering relation can be determined by its relation of monotone sequences. The typical definition of a partial ordering relation is the set of all monotone non-decreasing sequences in the partial order of size two. This relation of monotone non-decreasing sequences has the properties of reflexivity, anti-symmetry, and transitivity that characterize partial orders. This leads to a special kind of relation.
Given a partial order we can form a relation from its monotone non-decreasing sequences of a certain size. If it is finite height, we can form a relation consisting of its maximal monotone increasing sequences, and so on. In general, it is useful to consider relations consisting of sequences of any size using this understanding of order theory and sequences. The notion of a nary relation is merely a special case which consists of sequences of any particular size.
As a consequence, it is now useful to extend our understanding of relations beyond the theory of nary relations and specifically unary relations, binary relations, ternary relations, and quaternary relations, which is typically established. We can use concepts analogous to the theory of set systems to talk about special classes of relations. The rank of a relation is the size of its largest sequence. Sequences in a relation can be distinct or equal and so on. The theory of relations will play a foundational role in the construction of our new computer algebra system.
Saturday, September 8, 2018
Monday, September 3, 2018
Total order theory
My recent research into the theory of order topology led me to realize just how connected the theory of order topology and metric spaces is. A metric space can be partially characterized by the order topology of its distances, so that a metric space with discrete distances is itself discrete. In this way, order topology is connected not only to the theory of metric spaces but all of mathematical analysis. The results of this research, and a considerable examination of the theory of total orders in general is presented in the following paper.
https://drive.google.com/file/d/1RNg0yXtIad6ziTvjkzINajBknPl6n9wG/view?usp=sharing
https://drive.google.com/file/d/1RNg0yXtIad6ziTvjkzINajBknPl6n9wG/view?usp=sharing
Monday, July 30, 2018
Falsehood preserving boolean formulas
The particular class of falsehood preserving boolean formulas is of some interest to us, because it can be expressed with differences rather then with complements. So we can apply them to sets without having to deal with or define their complements. The most basic falsehood preserving logical connectives in set theory are the constant empty set and the identity. Beyond that there is union, intersection, difference, and symmetric difference which are among the four most important logical connectives in set theory. All of them are falsehood preserving because they do not take anything from the complement. They can be expressed with union, intersection, and difference without reference to complements. The symmetric difference is merely the difference between the union and the intersection. Other boolean formulas can be expressed using complements, when necessary, but it is useful to be able to express set theoretic operations without defining them.
Monday, April 30, 2018
Boolean formulas
Boolean formulas can be used to express constraint satisfaction problems in general, among other things. The manner in which we solve boolean formulas is defined by resolution. Assuming that a given boolean formula is effectively expressed in conjunctive normal formula we can apply resolution to any two clauses in the boolean formula which have complementary literals, which will get us a new clause which contains all literals that do not have complements. Well applying the resolution rule, if we get a clause that is simpler then some larger clause that contains it, we can eliminate the larger clauses. This is one way we can use deduction to solve logic problems.
Tuesday, March 13, 2018
Cauchy sequences of rational numbers
One of the important problems in analysis is determine how to represent real numbers. The natural definition which occurs from order theory is that a real number is defined by a Dedekind cut which is effectively a partition of the rational numbers into upper and lower sets relative to the real number. This defines the order theoretic properties of the real number. In order to make sense of the Dedekind cut, it is necessary to have a lower bound sequence and an upper bound sequence, the two of which together give an increasingly accurate interval approximation of the real number. The representation of a real number in terms of a sequence of intervals is equivalent to using two sequences anyways.
On the other hand, if we take the metric definition rather then the order definition we get Cauchy sequences which are sequences that satisfy the Cauchy criterion which states that consecutive numbers get increasing close together as the sequence goes on. We can represent any given number then using a cauchy sequence of rational numbers. In an implementation sense, this can be defined using a function between the set of natural numbers and the set of rational numbers, both of which are countable so this can be implemented computationally. A single sequence may not be enough to compute the order properties of the number, but it is enough to define the number in terms of the metric space.
On the other hand, if we take the metric definition rather then the order definition we get Cauchy sequences which are sequences that satisfy the Cauchy criterion which states that consecutive numbers get increasing close together as the sequence goes on. We can represent any given number then using a cauchy sequence of rational numbers. In an implementation sense, this can be defined using a function between the set of natural numbers and the set of rational numbers, both of which are countable so this can be implemented computationally. A single sequence may not be enough to compute the order properties of the number, but it is enough to define the number in terms of the metric space.
Wednesday, February 21, 2018
Scattered total orders
A totally ordered set is hereditary discrete if it is locally finite. A locally finite total order can be of four types: bounded, lower bounded, upper bounded, and unbounded. The bounded locally finite total orders can be further classified based upon their cardinality because they are finite. The lower bounded locally finite total order describes the non-negative integers $\omega$ and an upper bounded locally finite total order describes the non-positive integers $-\omega$ which are their order dual. The unbounded locally finite total order describes the integers $\mathbb{Z}$. All hereditary discrete total orders are suborders of the integers, which makes the integers the most advanced number system that can be used to describe hereditary discrete ordering structures.
The bounds of these hereditary discrete total orders can be visualized by using an arrow diagram. This leads to the description of the natural numbers as -> their order dual as <- and the integers as the bidirectional arrow <->. The unbounded order can be described as a dot point or a number which simply states what the cardinality of the order. In this way, we can see how locally finite total orders are described by the manner in which they are bounded or unbounded.
Scattered orders are distinguished from hereditary discrete ones in that some of their subsets have points that are limits of isolated points rather then being isolated themselves. Scattered orders can be formed from the ordinal sum of one another. At the most basic level, we can take the ordinal sum of some finite number of hereditary discrete total orders. An example is the total order [-> <-] which describes a pair of orders that are both pointed in the same direction to an unbounded extent. We can also get the double arrow [-> ->] and the double back arrow [<- <-] both of these orders are ordinal numbers and their duals respectively as they use only one type of arrow. We can also add bounds on established orders [-> .], [. <-], [. <->], [<-> .], [. <-> .]. These can be extended to any number of elements like [-> -> <- <-] which is two double arrows going to the same direction.
Some scattered orders are well founded or converse well founded, depending upon rather or they have all their arrows going in the same direction or in other words rather they have minimal or maximal elements. These well orders correspond to ordinal numbers, which are a particular type of scattered ordering. The process of chaining together these total orders can be extended infinitely in either direction. This leads to the ordinal of the second power $\omega^2$ which is equivalent to the sequence [-> -> -> ...] going on infinitely. There is also its order dual $-\omega^2$ which is equivalent to the sequence [... <- <- <-]. These are some of the ordinal scattered orders with an unbounded number of locally finite total orders chained together.
The total orders can also be combined together in a non-ordinal manner like [<- <- <- ...] which continually chains together an infinite number of back arrows going in a forwards direction. This is not an ordinal because the arrows are chained together in a different direction then the arrows are going themselves. Its order dual is [... -> -> ->] which is an infinite number of forward arrows chained together in a backwards direction. We can also chain together integer sets like [<-> <-> <-> ...] and [... <-> <-> <->]. If we chain together these locally finite orders in a manner that is unbounded in both directions then we can get a new type of total order. An example of this is the order [... -> -> <- <- ...] which is an infinite number of arrows pointing chained together from both sides pointing towards the same point. Other examples include [... -> -> -> ...] and [... <- <- <- ...]. Notice that no orders of this type are ordinals or reverse ordinal no matter what arrows are chained together in them. If we then combine together an unbounded order in an unbounded manner we get [... <-> <-> <-> ...] which is $\mathbb{Z}^2$ which is the next type of order we are going to consider.
A locally finite total order is defined as one in which for any pair of elements within the total order there is only a finite number of points between them. Each point is contained in a single set which is defined by all the points that are finitely reachable from that point. The sets form the locally finite components of the total order which partition the order. Every scattered total order can be described as an ordinal sum of locally finite total orders in this manner. The next level is to describe total orders that are the ordinal sum of a locally finite number of locally finite components. This leads precisely to $\mathbb{Z}^2$.
Continuing this process we can then get those total orders which are defined as the locally finite ordered sum of $\mathbb{Z}^2$ components. This includes ordinal numbers like $2\omega^2$, $2\omega^2+\omega$ and $\omega^2+2\omega+1$ as well as their inverses like $-2\omega^2$, $-2\omega^2-\omega$ and $-2\omega^2-\omega-1$. Ordinals of different types can be chained together to get orders like [$\omega$,$-\omega^2$] and [$\omega^2$,$-\omega$]. Another example that is defined by chaining together orders that aren't all ordinals is [$\omega^2, \mathbb{Z}, -\omega^2$]. All these orders defined so far, have been a finite combination of $\mathbb{Z}^2$ components. If we combine them together infintely we can get the ordinal number $\omega^3$ and the reverse ordinal $-\omega^3$ and continuing on infinitely in both directions we can get $\mathbb{Z}^3$. This is the order consisting of a locally finite amount of $\mathbb{Z}^2$ components. Continuing on in this manner we can get $\mathbb{Z}^4$, $\mathbb{Z}^5$, $\mathbb{Z}^6$, $\mathbb{Z}^7$,$\mathbb{Z}^8$, onwards to infinity to get $\mathbb{Z}^\omega$ which describes all scattered orders with a finite degree of nesting of locally finite components.
Considering everything that we have seen here we can now classify scattered total orders. The simplest type of scattered total order is the integers $\mathbb{Z}$ which are locally finite. The next simplest type of scattered total order is the $\mathbb{Z}^2$ which consists of a locally finite sum of locally finite components. This can be continued to some degree to get the powers of $\mathbb{Z}$ which are the orders $\mathbb{Z}^\alpha$ where $\alpha$ is some ordinal number. By an important theorem from Hausdorff, we know that the scattered total orders can be described by these general powers of the integers.
The bounds of these hereditary discrete total orders can be visualized by using an arrow diagram. This leads to the description of the natural numbers as -> their order dual as <- and the integers as the bidirectional arrow <->. The unbounded order can be described as a dot point or a number which simply states what the cardinality of the order. In this way, we can see how locally finite total orders are described by the manner in which they are bounded or unbounded.
Scattered orders are distinguished from hereditary discrete ones in that some of their subsets have points that are limits of isolated points rather then being isolated themselves. Scattered orders can be formed from the ordinal sum of one another. At the most basic level, we can take the ordinal sum of some finite number of hereditary discrete total orders. An example is the total order [-> <-] which describes a pair of orders that are both pointed in the same direction to an unbounded extent. We can also get the double arrow [-> ->] and the double back arrow [<- <-] both of these orders are ordinal numbers and their duals respectively as they use only one type of arrow. We can also add bounds on established orders [-> .], [. <-], [. <->], [<-> .], [. <-> .]. These can be extended to any number of elements like [-> -> <- <-] which is two double arrows going to the same direction.
Some scattered orders are well founded or converse well founded, depending upon rather or they have all their arrows going in the same direction or in other words rather they have minimal or maximal elements. These well orders correspond to ordinal numbers, which are a particular type of scattered ordering. The process of chaining together these total orders can be extended infinitely in either direction. This leads to the ordinal of the second power $\omega^2$ which is equivalent to the sequence [-> -> -> ...] going on infinitely. There is also its order dual $-\omega^2$ which is equivalent to the sequence [... <- <- <-]. These are some of the ordinal scattered orders with an unbounded number of locally finite total orders chained together.
The total orders can also be combined together in a non-ordinal manner like [<- <- <- ...] which continually chains together an infinite number of back arrows going in a forwards direction. This is not an ordinal because the arrows are chained together in a different direction then the arrows are going themselves. Its order dual is [... -> -> ->] which is an infinite number of forward arrows chained together in a backwards direction. We can also chain together integer sets like [<-> <-> <-> ...] and [... <-> <-> <->]. If we chain together these locally finite orders in a manner that is unbounded in both directions then we can get a new type of total order. An example of this is the order [... -> -> <- <- ...] which is an infinite number of arrows pointing chained together from both sides pointing towards the same point. Other examples include [... -> -> -> ...] and [... <- <- <- ...]. Notice that no orders of this type are ordinals or reverse ordinal no matter what arrows are chained together in them. If we then combine together an unbounded order in an unbounded manner we get [... <-> <-> <-> ...] which is $\mathbb{Z}^2$ which is the next type of order we are going to consider.
A locally finite total order is defined as one in which for any pair of elements within the total order there is only a finite number of points between them. Each point is contained in a single set which is defined by all the points that are finitely reachable from that point. The sets form the locally finite components of the total order which partition the order. Every scattered total order can be described as an ordinal sum of locally finite total orders in this manner. The next level is to describe total orders that are the ordinal sum of a locally finite number of locally finite components. This leads precisely to $\mathbb{Z}^2$.
Continuing this process we can then get those total orders which are defined as the locally finite ordered sum of $\mathbb{Z}^2$ components. This includes ordinal numbers like $2\omega^2$, $2\omega^2+\omega$ and $\omega^2+2\omega+1$ as well as their inverses like $-2\omega^2$, $-2\omega^2-\omega$ and $-2\omega^2-\omega-1$. Ordinals of different types can be chained together to get orders like [$\omega$,$-\omega^2$] and [$\omega^2$,$-\omega$]. Another example that is defined by chaining together orders that aren't all ordinals is [$\omega^2, \mathbb{Z}, -\omega^2$]. All these orders defined so far, have been a finite combination of $\mathbb{Z}^2$ components. If we combine them together infintely we can get the ordinal number $\omega^3$ and the reverse ordinal $-\omega^3$ and continuing on infinitely in both directions we can get $\mathbb{Z}^3$. This is the order consisting of a locally finite amount of $\mathbb{Z}^2$ components. Continuing on in this manner we can get $\mathbb{Z}^4$, $\mathbb{Z}^5$, $\mathbb{Z}^6$, $\mathbb{Z}^7$,$\mathbb{Z}^8$, onwards to infinity to get $\mathbb{Z}^\omega$ which describes all scattered orders with a finite degree of nesting of locally finite components.
Considering everything that we have seen here we can now classify scattered total orders. The simplest type of scattered total order is the integers $\mathbb{Z}$ which are locally finite. The next simplest type of scattered total order is the $\mathbb{Z}^2$ which consists of a locally finite sum of locally finite components. This can be continued to some degree to get the powers of $\mathbb{Z}$ which are the orders $\mathbb{Z}^\alpha$ where $\alpha$ is some ordinal number. By an important theorem from Hausdorff, we know that the scattered total orders can be described by these general powers of the integers.
Wednesday, February 14, 2018
Order topology
Given a totally ordered set, we can form an open topology on that set from the set of open rays consisting of all the points that are either strictly greater or strictly less then a given point. The order topology also contains the open intervals of the set. The first concept that can be derived from the order topology is that of an isolated point. An isolated point is a singleton set of the order topology. A discrete total order consists entirely of isolated points. A point is considered to be near isolated if it always contains an isolated point in any open set containing it.
A scattered topological space is strictly near isolated. These scattered topological points consist of both isolated points, and limits of isolated points. Scattered topologies include discrete topologies as a special case. In this sense, they are somewhat of a generalization of discrete topologies. Points are often defined by the existence of a topological subspace that contains them. A scattered point is a point that is contained within some scattered topology. Scattered total orders are defined as total orders with a scattered topology.
A topological space that contains no isolated points is dense in itself, which makes it relatively less restricted then these other types of topological spaces. The other spaces are defined based upon forbidding dense subspaces. A space can include dense subspaces as well as isolated points and be neither type of topology. A point can be characterized based upon rather it is contained in a dense in itself. Dense total orders are defined as total orders with a dense in itself topology. The real numbers themselves have a dense in itself topology.
A metric space is defined based upon a totally ordered set of distances. The character that a metric space can take is determined by the order topology of its set of distances. If a metric space has a discrete set of distances then it is necessarily going to be a discrete metric. For example, the path metric on a graph uses only integer distances so it will necessarily only form a discrete metric. In the same sense, if a scattered set of distances is used, then the metric space will necessarily be scattered as well. As a result, being either discrete or scattered is transferred from the order topology of the distances to the metric space. In this sense, the order topology is perhaps the most fundamental concept in the theory of metric spaces.
It is useful to define a metric space associated with a given partial order. In a locally finite order this can be defined based upon the path metric of the covering graph. If the order has a different topology, however, then it is necessary to define a different type of metric space on it. In particular, if an order has a dense topology then the path metric may no longer suffice and it will be necessary to define some other concept of distance between points. So a dense metric can be created so that it can be associated with the dense order.
A scattered topological space is strictly near isolated. These scattered topological points consist of both isolated points, and limits of isolated points. Scattered topologies include discrete topologies as a special case. In this sense, they are somewhat of a generalization of discrete topologies. Points are often defined by the existence of a topological subspace that contains them. A scattered point is a point that is contained within some scattered topology. Scattered total orders are defined as total orders with a scattered topology.
A topological space that contains no isolated points is dense in itself, which makes it relatively less restricted then these other types of topological spaces. The other spaces are defined based upon forbidding dense subspaces. A space can include dense subspaces as well as isolated points and be neither type of topology. A point can be characterized based upon rather it is contained in a dense in itself. Dense total orders are defined as total orders with a dense in itself topology. The real numbers themselves have a dense in itself topology.
A metric space is defined based upon a totally ordered set of distances. The character that a metric space can take is determined by the order topology of its set of distances. If a metric space has a discrete set of distances then it is necessarily going to be a discrete metric. For example, the path metric on a graph uses only integer distances so it will necessarily only form a discrete metric. In the same sense, if a scattered set of distances is used, then the metric space will necessarily be scattered as well. As a result, being either discrete or scattered is transferred from the order topology of the distances to the metric space. In this sense, the order topology is perhaps the most fundamental concept in the theory of metric spaces.
It is useful to define a metric space associated with a given partial order. In a locally finite order this can be defined based upon the path metric of the covering graph. If the order has a different topology, however, then it is necessary to define a different type of metric space on it. In particular, if an order has a dense topology then the path metric may no longer suffice and it will be necessary to define some other concept of distance between points. So a dense metric can be created so that it can be associated with the dense order.
Subscribe to:
Posts (Atom)