Relation Graphs and Partial Clones on a 2-Element Set

In a recent paper, the authors show that the sublattice of partial clones that preserve the relation {(0,0),(0,1),(1,0)} is of continuum cardinality on 2. In this paper we give an alternative proof to this result by making use of a representation of relations derived from {(0,0),(0,1),(1,0)} in terms of certain types of graphs. As a by-product, this tool brings some light into the understanding of the structure of this uncountable sublattice of strong partial clones.

I. Introduction

Let be a finite set with . Without loss of generality we assume that . For a positive integer , an -ary partial function on is a map where is a subset of called the domain of . If dom , then is a total function (or operation) on . Let denote the set of all n-ary partial functions on and let . The set of all total operations on is denoted by .