Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-10T23:53:10.065Z 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: maruoka@ecei.tohoku.ac.jp)
MIKE PATERSON
Affiliation:
Department of Computer Science, University of Warwick, Coventry CV4 7AL, England (e-mail: msp@dcs.warwick.ac.uk)
HIROTAKA KOIZUMI
Affiliation:
2nd Development Dept., 1st Basic Software Development Division, NEC Corporation, 4-14-22, Shibaura, Minato-ku, Tokyo 108, Japan (e-mail: koizumi@d2.uxd.fc.nec.co.jp)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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