Open Collections

Many-valued generalizations of two finite intervals in Post’s lattice

University of British Columbia

A study due to Emil Post shows that, although the lattice of clones in two-valued algebraic logic is countably infinite, there exist oniy finitely many clones that contain both constants, and only finitely many that contain the negation function. There are, however, uncountably many k-valued clones for all k > 2; in fact, it is known that uncountably many clones contain all constants. The constants of two-valued logic can also be regarded as the set of noninvertible, unary functions on a two element domain. It is shown here that, for values of k greater than two, there remain only finitely many k-valued clones containing all such functions. Similarly, one can generalize the set of clones in Post’s lattice that contain the negation function to those k-valued clones that contain all invertible, unary functions. Once again, there are only finitely many such clones, and they can be described explicitly. These two generalizations of sets of two-valued clones are presented with an introduction to the study of the lattice of clones, and a survey of relevant results. We also note and discuss the fact that the latter result serves to give a description of all homogeneous relation algebras over a finite underlying set.

Thesis/Dissertation

application/pdf

2009-02-28

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/5287

Computer Science

University of British Columbia

UBCV

DSpace