BINARY RELATIONS AND PERMUTATION-GROUPS

被引：5

作者：

ANDREKA, H

DUNTSCH, I

NEMETI, I

机构：

[1] HUNGARIAN ACAD SCI,INST MATH,H-1363 BUDAPEST,HUNGARY

[2] UNIV ULSTER,FAC INFORMAT,JORDANSTOWN BT37 0QB,NORTH IRELAND

来源：

MATHEMATICAL LOGIC QUARTERLY | 1995年 / 41卷 / 02期

关键词：

RELATION ALGEBRAS; GALOIS CLOSURE; CLONES OF OPERATIONS;

D O I：

10.1002/malq.19950410207

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We discuss some new properties of the natural Galois connection among set relation algebras, permutation groups, and first order logic. In particular, we exhibit infinitely many permutational relation algebras without a Galois closed representation, and we also show that every relation algebra on a set with at most six elements is Galois closed and essentially unique. Thus, we obtain the surprising result that on such sets, logic with three variables is as powerful in expression as full first order logic.

引用

页码：197 / 216

页数：20

共 20 条

[1]

ANDREKA H, 1992, MICH MATH J, V39, P371

[2]

ANDREKA H, 1994, EXPRESSIBILITY PROPE

[3]

ANDREKA H, 1991, ALGEBRAIC LOGIC, P431

[4]

ANDREKA H, 1988, REPRESENTATIONS SMAL

[5]

CANNON J, 1987, LANGUAGE GROUP THEOR

[6]

DUNTSCH I, 1994, IN PRESS J SYMBOLIC

[7]

FAGIN R, 1987, SPRINGER LECT NOTES, V470, P3

[8]

Givant S., 1987, AM MATH SOC C PUBLIC, V41

[9]

Gratzer G, 1979, UNIVERSAL ALGEBRA

[10] LANGUAGES THAT CAPTURE COMPLEXITY CLASSES [J].

IMMERMAN, N .

SIAM JOURNAL ON COMPUTING, 1987, 16 (04) :760-778

← 1 2 →