# Lisp AI

## Tuesday, March 13, 2018

## 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.

## Tuesday, January 30, 2018

### Subgraphs of connected graphs

Given a connected graph as well a subset of the vertices of the connected graph, we can form a subgraph of the connected graph containing only the vertices in that subset. This subgraph need not be connected itself, or even non empty as it could consist of disconnected points. The interesting property of the subgraph then is actually its metric rather then its adjacency relation. We can form a metric on the subgraph by determining the distance between each point in the parent graph based upon the shortest path metric.

## Tuesday, January 2, 2018

## Sunday, December 31, 2017

### Metric properties of graphs

Given a connected graph, we can form a metric space from the graph in which the distance between any two points is determined by the shortest path between them. The shortest path between two points need not be unique, unless the graph is a geodetic graph. This metric space is always going to be a discrete space, and a very particular type of discrete space which is generated by the unit distances between its points. The most interesting metric property of any vertex in a graph is its eccentricity which is the greatest distance between the vertex and any other point. The radius and the diameter of a graph are distance related properties determined by the minimum and the maximum eccentricity respectively.

## Thursday, August 24, 2017

### Geodetic graphs

Geodetic graphs have the particular property that each pair of points has a unique shortest path between them, or geodesic. Trees are a special case of geodetic graphs in which each pair of points has a unique path in general between them. Block graphs are sometimes called clique trees, they include trees and also happen to be the chordal geodetic graphs.

Subscribe to:
Posts (Atom)