Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-16T16:59:09.730Z Has data issue: false hasContentIssue false

Consistency of Natural Relations on Sets

Published online by Cambridge University Press:  01 September 1998

AKIRA MARUOKA
Affiliation:
Faculty of Engineering, Tohoku University, Sendai 980, Japan (e-mail: [email protected])
MIKE PATERSON
Affiliation:
Department of Computer Science, University of Warwick, Coventry CV4 7AL, England (e-mail: [email protected])
HIROTAKA KOIZUMI
Affiliation:
2nd Development Dept., 1st Basic Software Development Division, NEC Corporation, 4-14-22, Shibaura, Minato-ku, Tokyo 108, Japan (e-mail: [email protected])

Abstract

The natural relations for sets are those definable in terms of the emptiness of the subsets corresponding to Boolean combinations of the sets. For pairs of sets, there are just five natural relations of interest, namely, strict inclusion in each direction, disjointness, intersection with the universe being covered, or not. Let N denote {1, 2, …, n} and (N2) denote {(i, j)[mid ]i, jN and i<j}. A function μ on (N2) specifies one of these relations for each pair of indices. Then μ is said to be consistent on MN if and only if there exists a collection of sets corresponding to indices in M such that the relations specified by μ hold between each associated pair of the sets. Firstly, it is proved that if μ is consistent on all subsets of N of size three then μ is consistent on N. Secondly, explicit conditions that make μ consistent on a subset of size three are given as generalized transitivity laws. Finally, it is shown that the result concerning binary natural relations can be generalized to r-ary natural relations for arbitrary r[ges ]2.

Type
Research Article
Copyright
1998 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)