Wednesday, December 26, 2012

Enumerative combinatorics

I have successfully enumerated a variety of mathematical structures by establishing a bijection between them and the natural numbers. Here are the first few sets and multisets:
(#{} #{0} #{1} #{0 1} #{2} #{0 2} #{1 2} #{0 1 2})
({} {0 1} {0 2} {1 1} {0 3} {1 2} {1 1, 0 1} {2 1})

The integers can be enumerated by defining the sign place as the first bit in a number and the absolute value as the value defined by the other bits:
(0 -0.0 1 -1 2 -2 3 -3 4 -4 5 -5)

The positive rational numbers can be enumerated by mapping over the enumeration of the multisets with an enumeration of the prime numbers and the enumeration of the integers.
(1 2 1/2 3 4 1/3 6 5 1/4 9)

All rational numbers can enumerated by using three places: a sign place with cardinality two, a natural part, and a fractional part. The fractional part is enumerated using eulers totient function.

Friday, December 14, 2012

Finite lattices

I have implemented the means to get the greatest upper bound and lowest upper bound of elements of a finite partial ordering relation. This can be used to completely define finite lattices such as the boolean lattice:
(transform-lattice
(enum false true)
(finite-lattice
[[0 1]
[1 1]]))

The partial ordering relation of a set is described by its adjacency matrix. This implies that the lattices module requires the adjacency matrices library as a dependency.