919:
The most complete set of results of this nature is
Chapter C of Carnap (1958), where the notation is rather distant from that of this entry. Chapter 3.2 of Suppes (1960) contains fewer results, presented as ZFC theorems and using a notation that more resembles that of this entry. Neither Carnap nor
1450:(FOL) formulas containing no more than three variables. (A given variable can be quantified multiple times and hence quantifiers can be nested arbitrarily deeply by "reusing" variables.) Surprisingly, this fragment of FOL suffices to express
2415:
1424:
consists entirely of equations manipulated using nothing more than uniform replacement and the substitution of equals for equals. Both rules are wholly familiar from school mathematics and from
2558:
in the 1970s with the help of Steven Givant; this collaboration resulted in the monograph by Tarski and Givant (1987), the definitive reference for this subject. For more on the history of
2222:
1700:
798:
768:
2311:
2337:
2520:
took it much further and became fascinated with its philosophical power. The work of DeMorgan and Peirce came to be known mainly in the extended and definitive form
2278:
2251:
2153:
852:, this fact is trivial. After each of the following axioms is shown the number of the corresponding theorem in Chapter 3 of Suppes (1960), an exposition of ZFC:
3091:
2109:), it is nevertheless turned into a relation algebra using the same definitions of the operations. Its importance resides in the definition of a
3144:
2748:
1491:
1483:
3118:
3101:
3004:
2521:
375:
Since residuated
Boolean algebras are axiomatized with finitely many identities, so are relation algebras. Hence the latter form a
115:
2581:
3264:
2083:
is itself an equivalence relation, namely the complete relation consisting of all pairs. While 2 is not a subalgebra of 2 when
154:
2824:
122:
and his students, starting in the 1940s. Tarski and Givant (1987) applied relation algebra to a variable-free treatment of
2342:
1517:
to some relation algebra consisting of binary relations on some set, and closed under the intended interpretation of the
3254:
3259:
3132:
2638:
1696:
406:
376:
2693:
2688:
2613:
512:
the • operator (even though it distributes over ∨ like a meet does), nor is the 1 of the
Boolean algebra the
505:
329:
39:
3053:
2439:
1708:
1687:
is representable (Tarski and Givant 1987). That not every relation algebra is representable is a fundamental way
602:
414:
2162:
3249:
3244:
2643:
2156:
1664:
Essentially these axioms imply that the universe has a (non-surjective) pairing relation whose projections are
651:
529:
383:
of relation algebras. Expanding the above definition as equations yields the following finite axiomatization.
178:
81:
46:
2658:
1712:
3150:
2113:
as any relation algebra isomorphic to a subalgebra of the relation algebra 2 for some equivalence relation
126:, with the implication that mathematics founded on set theory could itself be conducted without variables.
2965:
2668:
2517:
1522:
1185:
994:
369:
107:
201:, such that these operations and constants satisfy certain equations constituting an axiomatization of a
2781:
2673:
2530:
1570:
1534:
2590:
783:
753:
2070:
1455:
1342:
1303:
1148:
1130:
252:
237:
123:
2970:
2949:"The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations"
3228:
2915:
2853:
2786:
2698:
2678:
2469:
2425:
2283:
2125:
1495:
1443:
1268:
1207:
1090:
225:
150:
3078:
3070:
2983:
2932:
2841:
2776:
2683:
2648:
2509:
1704:
1471:
1467:
1463:
1433:
1245:
1226:
1167:
1112:
736:
210:
103:
20:
2316:
1462:
is, in effect, a way of algebraizing nearly all mathematics, while dispensing with FOL and its
3097:
3000:
2910:
2744:
2633:
2623:
1447:
598:
325:
245:
233:
214:
189:
96:
2948:
360:. The latter condition can be thought of as the relational counterpart of the equation 1/(1/
3220:
3062:
2975:
2924:
2833:
2703:
2628:
2493:
2155:
is a relation algebra with the obvious
Boolean algebra operations, composition given by the
1812:
1787:
The motivating example of a relation algebra depends on the definition of a binary relation
1451:
1425:
662:
655:
241:
66:
31:
2256:
2230:
2131:
3216:
3024:
3017:
3013:
2618:
2608:
1411:
966:
944:
885:
202:
111:
58:
54:
205:. Roughly, a relation algebra is to a system of binary relations on a set containing the
2999:. Studies in Logic and the Foundations of Mathematics. Vol. 150. Elsevier Science.
1418:
are discussed at length in Tarski and Givant (1987), and more briefly in Givant (2006).
3036:
2905:. Studies in Logic and the Foundations of Mathematics. Vol. 147. Elsevier Science.
2653:
2542:
proved that a particular formula in which the quantifiers were nested four deep had no
936:
258:
Following Jónsson and
Tsinakis (1993) it is convenient to define additional operations
248:
206:
1432:
proofs are carried out in a manner familiar to all mathematicians, unlike the case in
328:
over the usual one is that a relation algebra can then be defined in full simply as a
3238:
3171:
3048:
2956:
2936:
2889:
2873:
2811:
2806:
2763:
2722:
2539:
2225:
1558:
1316:
396:
119:
3082:
2987:
2913:; Tsinakis, Constantine (1993). "Relation algebras as residuated Boolean algebras".
2845:
2822:
Givant, Steven (2006). "The calculus of relations as a foundation for mathematics".
2586:
3224:
2944:
2858:
2550:
until Tarski (1941) began writing about it. His students have continued to develop
2497:
2485:
1872:
1538:
1530:
1475:
312:˘. Hence a relation algebra can equally well be defined as an algebraic structure
3125:
3157:
2885:
2869:
2417:. The image of this homomorphism is the set of all right-invariant relations on
1368:
1355:
1329:
410:
229:
27:
2117:
on some set. The previous section says more about the relevant metamathematics.
1728:
by interpreting conjunction as composition (the monoid multiplication •), i.e.
3197:
2837:
2785:
76: 447–470. Translated as "On possibilities in the calculus of relatives" in
1514:
1032:
2571:
2059:
An important generalization of the previous example is the power set 2 where
1820:
1059:
1004:
3204:
3164:
3185:
3178:
2663:
2589:, Relation Algebra as programming language using the Ampersand compiler,
1290:
3119:
Constructing
Allegory from Relation Algebra and Representation Theorems.
1845:, as per example (1) above, the standard interpretation of • is instead
1703:, are always representable as sets of subsets of some set, closed under
118:. The equational form of relation algebra treated here was developed by
3074:
2979:
2928:
1827:
is a
Boolean algebra. While 2 can be made a relation algebra by taking
533:
57:. The motivating example of a relation algebra is the algebra 2 of all
2538:, but acknowledged him only as the inventor of the notation. In 1912,
2594:
2473:
525:
395:
below are adapted from Givant (2006: 283), and were first set out by
42:
3221:
Exploring (Finite) Relation
Algebras Using Tools Written in Haskell.
3212:
3066:
2575:
3138:
2725:(1948) "Abstract: Representation Problems for Relation Algebras,"
1744:. This interpretation requires that converse interpret identity (
2775:
Korselt did not publish his finding. It was first published in
884:
The following table shows how many of the usual properties of
845:
508:(1933). Note that the meet of the implied Boolean algebra is
177:, the Boolean constants 0 and 1, the relational operations of
892:
equalities or inequalities. Below, an inequality of the form
372:, and some authors use reciprocal as a synonym for converse.
3165:
1680:(Proof by Maddux, see Tarski & Givant 1987: 8.4(iii)).
1521:
operations. It is easily shown, e.g. using the method of
3133:
A Completeness Result for
Relation Algebra with Binders.
2591:
Journal of Logical and Algebraic Methods in Programming
2582:
ARA / An Automatic Theorem Prover for Relation Algebras
735:
is Tarski's equational form of the fact, discovered by
1565:
is itself a variety. In 1964, Donald Monk showed that
224:
relations and closed under these five operations as a
2345:
2319:
2286:
2259:
2253:. There is a relation algebra homomorphism embedding
2233:
2165:
2134:
2093:(since in that case it does not contain the relation
786:
756:
102:
Relation algebra emerged in the 19th-century work of
3117:
Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa, "
3016:(1970) "Relation algebras and function semigroups",
2410:{\displaystyle R_{A}=\{(g,h)\in G\times G:h\in Ag\}}
3158:
Computer Aided Investigations of Relation Algebras.
2813:
Introduction to Symbolic Logic and its Applications
2739:Chris Brink; Wolfram Kahl; Gunther Schmidt (1997).
2593:, Volume 100, April 2018, Pages 113–129. (see also
2546:equivalent. This fact led to a loss of interest in
1701:
Stone's representation theorem for Boolean algebras
2857:
2810:
2409:
2331:
2305:
2272:
2245:
2216:
2147:
792:
762:
2198:
504:This axiomatization of Boolean algebra is due to
3126:Generic Programming with Relations and Functors.
3096:. Providence RI: American Mathematical Society.
2572:RelMICS / Relational Methods in Computer Science
2424:If group sum or product interprets composition,
658:property of conversion relative to composition.
3093:A Formalization of Set Theory without Variables
2428:interprets converse, group identity interprets
880:Expressing properties of binary relations in RA
3124:Richard Bird, Oege de Moor, Paul Hoogendijk, "
2791:A Source Book in Mathematical Logic, 1879–1931
2779:(1915) "Über Möglichkeiten im Relativkalkül,"
1577:which is finitely axiomatized by definition.
1541:proved the existence of equations holding in
1482:can express Peano arithmetic and set theory,
16:Type of Boolean algebra with extra structures
8:
3179:Origins of the Calculus of Binary Relations.
3151:Foundations of Relations and Kleene Algebra.
2554:down to the present day. Tarski returned to
2404:
2359:
2240:
2234:
2211:
2182:
1337:is strongly connected and a partial order.
924:of this entry, or in an equational manner.
3198:An FCA interpretation of Relation Algebra.
2217:{\displaystyle A^{-1}=\{a^{-1}\!:a\in A\}}
1932:. This interpretation uniquely determines
1605:such that (Tarski and Givant 1987: §8.4):
920:Suppes formulated their results using the
19:For the concept related to databases, see
2969:
2350:
2344:
2318:
2291:
2285:
2264:
2258:
2232:
2189:
2170:
2164:
2139:
2133:
1724:Any Boolean algebra can be turned into a
1363:is connected and a strict partial order.
785:
755:
3186:The Second Calculus of Binary Relations.
3051:(1941). "On the calculus of relations".
1823:2 consisting of all binary relations on
1498:. (N.B. The Boolean algebra fragment of
926:
3090:Tarski, Alfred; Givant, Steven (1987).
3043:(Dover reprint ed.). Van Nostrand.
2715:
2741:Relational Methods in Computer Science
2159:, the converse by the inverse subset (
1553:is a proper subvariety of the variety
902:is shorthand for the Boolean equation
603:involution with respect to composition
255:for such systems of binary relations.
7:
3207:" Links to publications and software
290:. Jónsson and Tsinakis showed that
3225:Relation Algebra Tools with Haskell
2077:. This is a generalization because
2901:Hirsch, R.; Hodkinson, I. (2002).
2595:https://ampersandtarski.github.io/
650:Axiom B6 defines conversion as an
14:
1549:. Hence the variety generated by
848:theorems; for the purely Boolean
1085:(Injective surjective function)
793:{\displaystyle \leftrightarrow }
763:{\displaystyle \leftrightarrow }
2793:. Harvard Univ. Press: 228–251.
1507:representable relation algebras
1484:Gödel's incompleteness theorems
1350:is transitive and irreflexive.
195:˘, and the relational constant
82:composition of binary relations
2825:Journal of Automated Reasoning
2743:. Springer. pp. 4 and 8.
2500:as well as of Boolean algebra.
2484:become well-known theorems of
2374:
2362:
2111:representable relation algebra
2021:then establishes the converse
1533:, that is, axiomatizable by a
1513:, are those relation algebras
1324:is an antisymmetric preorder.
787:
757:
308:, and that both were equal to
1:
3031:. Cambridge University Press.
2306:{\displaystyle 2^{G\times G}}
1672:. It is a theorem that every
1298:is transitive and reflexive.
888:can be expressed as succinct
3131:R.P. de Freitas and Viana, "
2534:drew strongly on Schröder's
1502:is complete and decidable.)
251:of relation algebras is not
2562:, see Maddux (1991, 2006).
2224:), and the identity by the
2029:as consisting of all pairs
1940:as consisting of all pairs
1752:), and that both residuals
1442:can express any (and up to
999:functional and left-total.
654:, whereas B7 expresses the
342:is an involution, that is,
91:, and with the converse of
3281:
2894:Cylindric Algebras, Part 2
2878:Cylindric Algebras, Part 1
2694:Spatial-temporal reasoning
2689:Residuated Boolean algebra
2614:Allegory (category theory)
2332:{\displaystyle A\subset G}
2099:, the top element 1 being
1768:interpret the conditional
330:residuated Boolean algebra
110:, which culminated in the
65:, that is, subsets of the
40:residuated Boolean algebra
18:
3181:" A historical treatment.
3054:Journal of Symbolic Logic
2903:Relation Algebra by Games
2838:10.1007/s10817-006-9062-x
2524:gave it in Vol. 3 of his
2440:one-to-one correspondence
1589:is a Q-relation algebra (
1311:is a symmetric preorder.
661:Converse and composition
324:. The advantage of this
80:interpreted as the usual
3205:Relation Algebra and FCA
2313:which sends each subset
2157:product of group subsets
1886:belongs to the relation
1523:pseudoelementary classes
368:for ordinary arithmetic
232:of a set containing the
2659:Predicate functor logic
1894:just when there exists
3265:Mathematical relations
3039:(1972) . "Chapter 3".
3029:Relational Mathematics
2995:Maddux, Roger (2006).
2892:; Monk, J. D. (1985).
2876:; Monk, J. D. (1971).
2411:
2333:
2307:
2274:
2247:
2218:
2149:
1978:consists of all pairs
1756: \
1456:axiomatic set theories
794:
764:
2817:. Dover Publications.
2782:Mathematische Annalen
2674:Relation construction
2531:Principia Mathematica
2412:
2334:
2308:
2275:
2273:{\displaystyle 2^{G}}
2248:
2246:{\displaystyle \{e\}}
2219:
2150:
2148:{\displaystyle 2^{G}}
2128:. Then the power set
1593:) if, in addition to
1571:finite axiomatization
1545:that did not hold in
1535:universal Horn theory
1494:, incompletable, and
1458:ever proposed. Hence
795:
765:
203:calculus of relations
3041:Axiomatic Set Theory
2343:
2317:
2284:
2257:
2231:
2163:
2132:
2071:equivalence relation
1509:, forming the class
1343:Strict partial order
784:
754:
234:identity permutation
124:axiomatic set theory
3255:Mathematical axioms
3229:McMaster University
2916:Algebra Universalis
2787:Jean van Heijenoort
2727:Bulletin of the AMS
2699:Theory of relations
2679:Relational calculus
1597:, there exist some
1581:Q-relation algebras
1444:logical equivalence
318:, ∧, ∨, , 0, 1, •,
151:algebraic structure
143:, ∧, ∨, , 0, 1, •,
3260:Mathematical logic
2980:10.1007/BF00370681
2929:10.1007/BF01195378
2777:Leopold Loewenheim
2684:Relational algebra
2649:Logic of relatives
2639:Extension in logic
2634:Cylindric algebras
2505:Historical remarks
2407:
2329:
2303:
2270:
2243:
2214:
2145:
2006:. The translation
1990:such that for all
1952:such that for all
1434:mathematical logic
1356:Strict total order
1227:Strongly connected
790:
760:
737:Augustus De Morgan
665:over disjunction:
228:is to a system of
155:Boolean operations
153:equipped with the
104:Augustus De Morgan
21:Relational algebra
3145:Relation algebras
2997:Relation Algebras
2750:978-3-211-82971-4
2624:Cartesian product
1448:first-order logic
1428:generally. Hence
1403:
1402:
1054:˘ is left-total)
1027:˘ is functional)
989:˘ is surjective)
844:These axioms are
236:and closed under
97:converse relation
3272:
3107:
3086:
3044:
3032:
3025:Schmidt, Gunther
3014:Schein, Boris M.
3010:
2991:
2973:
2964:(3–4): 421–455.
2953:
2940:
2906:
2897:
2896:. North Holland.
2881:
2880:. North Holland.
2865:
2863:
2860:Naive Set Theory
2849:
2818:
2816:
2794:
2773:
2767:
2761:
2755:
2754:
2736:
2730:
2720:
2704:Triadic relation
2629:Cartesian square
2494:proper extension
2463:
2433:
2420:
2416:
2414:
2413:
2408:
2355:
2354:
2339:to the relation
2338:
2336:
2335:
2330:
2312:
2310:
2309:
2304:
2302:
2301:
2279:
2277:
2276:
2271:
2269:
2268:
2252:
2250:
2249:
2244:
2226:singleton subset
2223:
2221:
2220:
2215:
2197:
2196:
2178:
2177:
2154:
2152:
2151:
2146:
2144:
2143:
2123:
2108:
2098:
2092:
2082:
2068:
2055:
2040:
2020:
1989:
1961:
1951:
1931:
1916:
1901:
1897:
1885:
1871:. That is, the
1870:
1844:
1813:cartesian square
1810:
1804:
1697:Boolean algebras
1671:
1667:
1660:
1644:
1625:
1604:
1600:
1452:Peano arithmetic
1426:abstract algebra
1406:Expressive power
1398:
1285:
1263:
1240:
1221:
1202:
1180:
1162:
1143:
1125:
1107:
1084:
1049:
1022:
984:
961:
927:
915:
901:
886:binary relations
840:
799:
797:
796:
791:
769:
767:
766:
761:
728:
691:
656:antidistributive
646:
621:
593:
574:
541:
517:
500:
472:
441:
359:
347: ◁ (
341:
323:
307:
286:˘ •
274:˘, and, dually,
223:
200:
148:
136:relation algebra
67:cartesian square
59:binary relations
36:relation algebra
32:abstract algebra
3280:
3279:
3275:
3274:
3273:
3271:
3270:
3269:
3250:Algebraic logic
3245:Boolean algebra
3235:
3234:
3217:Gunther Schmidt
3114:
3104:
3089:
3067:10.2307/2268577
3047:
3037:Suppes, Patrick
3035:
3023:
3018:Semigroup Forum
3007:
2994:
2971:10.1.1.146.5668
2951:
2943:
2911:Jónsson, Bjarni
2909:
2900:
2884:
2868:
2864:. Van Nostrand.
2852:
2821:
2805:
2802:
2797:
2774:
2770:
2762:
2758:
2751:
2738:
2737:
2733:
2721:
2717:
2713:
2708:
2619:Binary relation
2609:Algebraic logic
2604:
2568:
2507:
2443:
2429:
2418:
2346:
2341:
2340:
2315:
2314:
2287:
2282:
2281:
2260:
2255:
2254:
2229:
2228:
2185:
2166:
2161:
2160:
2135:
2130:
2129:
2121:
2104:
2094:
2084:
2078:
2060:
2042:
2030:
2007:
1979:
1953:
1941:
1936: \
1918:
1903:
1899:
1895:
1875:
1866: :
1854: •
1846:
1828:
1806:
1796:
1780: ∨
1721:
1669:
1665:
1651:
1632:
1613:
1602:
1598:
1583:
1454:and almost all
1446:, exactly the)
1412:metamathematics
1408:
1373:
1273:
1250:
1231:
1212:
1190:
1172:
1153:
1135:
1117:
1095:
1064:
1037:
1010:
1007:
971:
949:
903:
893:
882:
819:
782:
781:
752:
751:
698:
673:
628:
613:
581:
550:
537:
513:
479:
448:
425:
415:complementation
413:, ∨, and unary
407:Boolean algebra
389:
351: ◁
343:
337: ◁
333:
313:
303: ▷
295: ◁
291:
278: ▷
270: •
262: ◁
244:. However, the
217:
196:
173:, and negation
157:of conjunction
138:
132:
112:algebraic logic
55:unary operation
24:
17:
12:
11:
5:
3278:
3276:
3268:
3267:
3262:
3257:
3252:
3247:
3237:
3236:
3233:
3232:
3210:
3209:
3208:
3201:
3191:
3190:
3189:
3182:
3169:
3168:
3167:
3161:
3154:
3147:
3136:
3129:
3122:
3113:
3112:External links
3110:
3109:
3108:
3102:
3087:
3049:Tarski, Alfred
3045:
3033:
3021:
3011:
3005:
2992:
2941:
2907:
2898:
2890:Tarski, Alfred
2882:
2874:Tarski, Alfred
2866:
2850:
2832:(4): 277–322.
2819:
2807:Carnap, Rudolf
2801:
2798:
2796:
2795:
2768:
2766:(1941), p. 87.
2756:
2749:
2731:
2714:
2712:
2709:
2707:
2706:
2701:
2696:
2691:
2686:
2681:
2676:
2671:
2666:
2661:
2656:
2654:Logical matrix
2651:
2646:
2641:
2636:
2631:
2626:
2621:
2616:
2611:
2605:
2603:
2600:
2599:
2598:
2584:
2580:Carsten Sinz:
2578:
2574:maintained by
2567:
2564:
2522:Ernst Schröder
2506:
2503:
2502:
2501:
2422:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2370:
2367:
2364:
2361:
2358:
2353:
2349:
2328:
2325:
2322:
2300:
2297:
2294:
2290:
2267:
2263:
2242:
2239:
2236:
2213:
2210:
2207:
2204:
2201:
2195:
2192:
2188:
2184:
2181:
2176:
2173:
2169:
2142:
2138:
2118:
2057:
1795:as any subset
1785:
1748: =
1736:is defined as
1720:
1717:
1662:
1661:
1645:
1626:
1582:
1579:
1407:
1404:
1401:
1400:
1371:
1365:
1364:
1358:
1352:
1351:
1345:
1339:
1338:
1332:
1326:
1325:
1319:
1313:
1312:
1306:
1300:
1299:
1293:
1287:
1286:
1271:
1265:
1264:
1248:
1242:
1241:
1229:
1223:
1222:
1210:
1204:
1203:
1188:
1182:
1181:
1170:
1164:
1163:
1151:
1145:
1144:
1133:
1127:
1126:
1115:
1109:
1108:
1093:
1087:
1086:
1062:
1056:
1055:
1035:
1029:
1028:
1008:
1001:
1000:
997:
991:
990:
969:
963:
962:
947:
941:
940:
937:If and only if
934:
881:
878:
842:
841:
789:
759:
730:
729:
692:
648:
647:
622:
595:
594:
575:
502:
501:
473:
442:
388:
385:
379:, the variety
322:, ◁ , ▷)
165:, disjunction
131:
128:
116:Ernst Schröder
108:Charles Peirce
15:
13:
10:
9:
6:
4:
3:
2:
3277:
3266:
3263:
3261:
3258:
3256:
3253:
3251:
3248:
3246:
3243:
3242:
3240:
3230:
3226:
3222:
3218:
3214:
3213:Kahl, Wolfram
3211:
3206:
3202:
3199:
3195:
3194:
3192:
3187:
3183:
3180:
3176:
3175:
3173:
3172:Vaughan Pratt
3170:
3166:
3162:
3159:
3155:
3152:
3148:
3146:
3143:
3142:
3140:
3137:
3134:
3130:
3127:
3123:
3120:
3116:
3115:
3111:
3105:
3103:9780821810415
3099:
3095:
3094:
3088:
3084:
3080:
3076:
3072:
3068:
3064:
3060:
3056:
3055:
3050:
3046:
3042:
3038:
3034:
3030:
3026:
3022:
3019:
3015:
3012:
3008:
3006:9780444520135
3002:
2998:
2993:
2989:
2985:
2981:
2977:
2972:
2967:
2963:
2959:
2958:
2957:Studia Logica
2950:
2946:
2945:Maddux, Roger
2942:
2938:
2934:
2930:
2926:
2923:(4): 469–78.
2922:
2918:
2917:
2912:
2908:
2904:
2899:
2895:
2891:
2887:
2883:
2879:
2875:
2871:
2867:
2862:
2861:
2855:
2854:Halmos, P. R.
2851:
2847:
2843:
2839:
2835:
2831:
2827:
2826:
2820:
2815:
2814:
2808:
2804:
2803:
2799:
2792:
2788:
2784:
2783:
2778:
2772:
2769:
2765:
2760:
2757:
2752:
2746:
2742:
2735:
2732:
2728:
2724:
2723:Alfred Tarski
2719:
2716:
2710:
2705:
2702:
2700:
2697:
2695:
2692:
2690:
2687:
2685:
2682:
2680:
2677:
2675:
2672:
2670:
2667:
2665:
2662:
2660:
2657:
2655:
2652:
2650:
2647:
2645:
2642:
2640:
2637:
2635:
2632:
2630:
2627:
2625:
2622:
2620:
2617:
2615:
2612:
2610:
2607:
2606:
2601:
2596:
2592:
2588:
2585:
2583:
2579:
2577:
2573:
2570:
2569:
2565:
2563:
2561:
2557:
2553:
2549:
2545:
2541:
2540:Alwin Korselt
2537:
2533:
2532:
2528:(1890–1905).
2527:
2523:
2519:
2516:in 1860, but
2515:
2511:
2504:
2499:
2495:
2491:
2487:
2483:
2479:
2475:
2472:as well as a
2471:
2467:
2462:
2458:
2454:
2450:
2446:
2441:
2437:
2432:
2427:
2426:group inverse
2423:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2371:
2368:
2365:
2356:
2351:
2347:
2326:
2323:
2320:
2298:
2295:
2292:
2288:
2265:
2261:
2237:
2227:
2208:
2205:
2202:
2199:
2193:
2190:
2186:
2179:
2174:
2171:
2167:
2158:
2140:
2136:
2127:
2119:
2116:
2112:
2107:
2102:
2097:
2091:
2087:
2081:
2076:
2072:
2067:
2063:
2058:
2054:
2050:
2046:
2038:
2034:
2028:
2024:
2018:
2014:
2010:
2005:
2001:
1997:
1993:
1987:
1983:
1977:
1973:
1969:
1965:
1960:
1956:
1949:
1945:
1939:
1935:
1930:
1926:
1922:
1915:
1911:
1907:
1893:
1889:
1883:
1879:
1874:
1869:
1865:
1861:
1857:
1853:
1849:
1843:
1839:
1835:
1831:
1826:
1822:
1818:
1814:
1809:
1803:
1799:
1794:
1790:
1786:
1783:
1779:
1775:
1771:
1767:
1763:
1759:
1755:
1751:
1747:
1743:
1739:
1735:
1731:
1727:
1723:
1722:
1718:
1716:
1714:
1710:
1706:
1702:
1698:
1694:
1691:differs from
1690:
1686:
1681:
1679:
1675:
1658:
1654:
1649:
1646:
1643:
1639:
1635:
1630:
1627:
1624:
1620:
1616:
1611:
1608:
1607:
1606:
1596:
1592:
1588:
1580:
1578:
1576:
1572:
1568:
1564:
1560:
1559:Alfred Tarski
1556:
1552:
1548:
1544:
1540:
1536:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1503:
1501:
1497:
1493:
1489:
1486:apply to it;
1485:
1481:
1477:
1473:
1469:
1465:
1461:
1457:
1453:
1449:
1445:
1441:
1437:
1435:
1431:
1427:
1423:
1419:
1417:
1413:
1405:
1396:
1392:
1388:
1384:
1380:
1376:
1372:
1370:
1367:
1366:
1362:
1359:
1357:
1354:
1353:
1349:
1346:
1344:
1341:
1340:
1336:
1333:
1331:
1328:
1327:
1323:
1320:
1318:
1317:Partial order
1315:
1314:
1310:
1307:
1305:
1302:
1301:
1297:
1294:
1292:
1289:
1288:
1284:
1280:
1276:
1272:
1270:
1267:
1266:
1261:
1257:
1253:
1249:
1247:
1244:
1243:
1238:
1234:
1230:
1228:
1225:
1224:
1219:
1215:
1211:
1209:
1206:
1205:
1201:
1197:
1193:
1189:
1187:
1186:Antisymmetric
1184:
1183:
1179:
1175:
1171:
1169:
1166:
1165:
1160:
1156:
1152:
1150:
1147:
1146:
1142:
1138:
1134:
1132:
1129:
1128:
1124:
1120:
1116:
1114:
1111:
1110:
1106:
1102:
1098:
1094:
1092:
1089:
1088:
1083:
1079:
1075:
1071:
1067:
1063:
1061:
1058:
1057:
1053:
1048:
1044:
1040:
1036:
1034:
1031:
1030:
1026:
1021:
1017:
1013:
1009:
1006:
1003:
1002:
998:
996:
993:
992:
988:
982:
978:
974:
970:
968:
965:
964:
960:
956:
952:
948:
946:
943:
942:
938:
935:
932:
929:
928:
925:
923:
917:
914:
910:
906:
900:
897: ≤
896:
891:
887:
879:
877:
875:
871:
867:
863:
859:
855:
851:
847:
839:
835:
831:
827:
823:
817:
814:
813:
812:
810:
806:
802:
780:
776:
772:
750:
746:
742:
738:
734:
726:
722:
718:
714:
710:
706:
702:
696:
693:
689:
685:
681:
677:
671:
668:
667:
666:
664:
659:
657:
653:
644:
640:
636:
632:
626:
623:
620:
616:
611:
608:
607:
606:
604:
600:
592:
588:
584:
579:
576:
573:
569:
565:
561:
557:
553:
548:
545:
544:
543:
540:
535:
531:
528:under binary
527:
523:
519:
516:
511:
507:
499:
495:
491:
487:
483:
477:
474:
471:
467:
463:
459:
455:
451:
446:
443:
440:
436:
432:
428:
423:
420:
419:
418:
416:
412:
409:under binary
408:
404:
400:
398:
394:
386:
384:
382:
378:
373:
371:
367:
363:
358:
354:
350:
346:
340:
336:
331:
327:
321:
317:
311:
306:
302:
298:
294:
289:
285:
281:
277:
273:
269:
265:
261:
256:
254:
250:
247:
243:
239:
235:
231:
227:
221:
216:
212:
208:
204:
199:
194:
191:
187:
183:
180:
176:
172:
168:
164:
160:
156:
152:
146:
142:
137:
129:
127:
125:
121:
120:Alfred Tarski
117:
113:
109:
105:
100:
98:
94:
90:
86:
83:
79:
75:
71:
68:
64:
60:
56:
52:
48:
44:
41:
37:
33:
29:
22:
3193:Priss, Uta:
3139:Peter Jipsen
3092:
3061:(3): 73–89.
3058:
3052:
3040:
3028:
2996:
2961:
2955:
2920:
2914:
2902:
2893:
2886:Henkin, Leon
2877:
2870:Henkin, Leon
2859:
2829:
2823:
2812:
2790:
2780:
2771:
2759:
2740:
2734:
2726:
2718:
2587:Stef Joosten
2576:Wolfram Kahl
2559:
2555:
2551:
2547:
2543:
2535:
2529:
2525:
2518:C. S. Peirce
2513:
2508:
2498:group theory
2489:
2486:group theory
2481:
2477:
2465:
2460:
2456:
2452:
2448:
2444:
2435:
2430:
2114:
2110:
2105:
2100:
2095:
2089:
2085:
2079:
2074:
2065:
2061:
2052:
2048:
2044:
2036:
2032:
2026:
2022:
2016:
2012:
2008:
2003:
1999:
1995:
1991:
1985:
1981:
1975:
1971:
1967:
1963:
1958:
1954:
1947:
1943:
1937:
1933:
1928:
1924:
1920:
1913:
1909:
1905:
1891:
1887:
1881:
1877:
1873:ordered pair
1867:
1863:
1859:
1855:
1851:
1847:
1841:
1837:
1833:
1829:
1824:
1816:
1807:
1801:
1797:
1792:
1788:
1781:
1777:
1773:
1769:
1765:
1761:
1757:
1753:
1749:
1745:
1741:
1737:
1733:
1729:
1725:
1709:intersection
1699:, which, by
1692:
1688:
1684:
1682:
1677:
1673:
1663:
1656:
1652:
1647:
1641:
1637:
1633:
1628:
1622:
1618:
1614:
1609:
1594:
1590:
1586:
1584:
1574:
1566:
1562:
1561:showed that
1554:
1550:
1546:
1542:
1539:Roger Lyndon
1531:quasivariety
1526:
1518:
1510:
1506:
1504:
1499:
1487:
1479:
1476:modus ponens
1459:
1439:
1438:
1429:
1421:
1420:
1415:
1409:
1394:
1390:
1386:
1382:
1378:
1374:
1360:
1347:
1334:
1321:
1308:
1295:
1282:
1278:
1274:
1259:
1255:
1251:
1236:
1232:
1217:
1213:
1199:
1195:
1191:
1177:
1173:
1158:
1154:
1140:
1136:
1122:
1118:
1104:
1100:
1096:
1081:
1077:
1073:
1069:
1065:
1051:
1046:
1042:
1038:
1024:
1019:
1015:
1011:
986:
980:
976:
972:
958:
954:
950:
930:
921:
918:
912:
908:
904:
898:
894:
889:
883:
873:
869:
865:
861:
857:
853:
849:
843:
837:
833:
829:
825:
821:
815:
808:
804:
800:
778:
774:
770:
748:
744:
740:
732:
731:
724:
720:
716:
712:
708:
704:
700:
694:
687:
683:
679:
675:
669:
660:
649:
642:
638:
634:
630:
624:
618:
614:
609:
596:
590:
586:
582:
577:
571:
567:
563:
559:
555:
551:
546:
538:
521:
520:
514:
509:
503:
497:
493:
489:
485:
481:
475:
469:
465:
461:
457:
453:
449:
444:
438:
434:
430:
426:
421:
402:
401:
392:
390:
380:
374:
365:
361:
356:
352:
348:
344:
338:
334:
319:
315:
309:
304:
300:
296:
292:
287:
283:
279:
275:
271:
267:
263:
259:
257:
230:permutations
219:
197:
192:
185:
181:
174:
170:
166:
162:
158:
144:
140:
135:
133:
101:
92:
88:
84:
77:
73:
69:
62:
50:
35:
25:
2526:Vorlesungen
2103:instead of
2073:on the set
1557:. In 1955,
1537:. In 1950,
1496:undecidable
1468:quantifiers
1464:connectives
1436:generally.
1330:Total order
1304:Equivalence
1149:Irreflexive
1131:Coreflexive
530:composition
411:disjunction
391:The axioms
246:first-order
238:composition
179:composition
28:mathematics
3239:Categories
2800:References
2764:Tarski, A.
2644:Involution
2492:becomes a
2488:, so that
2442:, so that
2041:such that
1970:. Dually,
1902:such that
1713:complement
1515:isomorphic
1492:incomplete
1478:. Because
1472:turnstiles
1269:Idempotent
1208:Asymmetric
1091:Transitive
1033:Surjective
967:Left-total
945:Functional
807:˘ ≤
663:distribute
652:involution
601:()˘ is an
518:constant.
506:Huntington
370:reciprocal
332:for which
130:Definition
47:involution
2966:CiteSeerX
2937:120642402
2711:Footnotes
2510:De Morgan
2434:, and if
2396:∈
2384:×
2378:∈
2324:⊂
2296:×
2206:∈
2191:−
2172:−
1821:power set
1791:on a set
1573:, unlike
1246:Connected
1168:Symmetric
1113:Reflexive
1060:Bijection
1005:Injective
788:↔
758:↔
536:identity
399:in 1948.
326:signature
213:(1), and
211:universal
61:on a set
3083:11899579
3027:(2010).
2988:12165812
2947:(1991).
2856:(1960).
2846:26324546
2809:(1958).
2789:, 1967.
2669:Relation
2664:Quantale
2602:See also
2566:Software
2512:founded
1974: /
1858: )
1805:, where
1776:(i.e., ¬
1764: /
1719:Examples
1393:∧
1385:∧
1377:∧
1291:Preorder
1216:∧
1194:∧
1157:∧
995:Function
777:≤
747:≤
599:converse
532:(•) and
253:complete
215:identity
190:converse
51:converse
45:with an
43:expanded
3075:2268577
3020:1: 1–62
2729:54: 80.
2464:, then
2069:is any
1868:xRy.ySz
1811:is the
1569:has no
1525:, that
739:, that
534:nullary
377:variety
242:inverse
95:as the
72:, with
49:called
3100:
3081:
3073:
3003:
2986:
2968:
2935:
2844:
2747:
2474:monoid
1819:. The
1711:, and
1683:Every
1595:B1-B10
1474:, and
597:Unary
526:monoid
397:Tarski
393:B1-B10
387:Axioms
249:theory
149:is an
3227:from
3079:S2CID
3071:JSTOR
2984:S2CID
2952:(PDF)
2933:S2CID
2842:S2CID
2470:group
2468:is a
2438:is a
2126:group
2124:be a
2025:˘ of
2002:then
1998:, if
1966:then
1962:, if
1705:union
1676:is a
1529:is a
1389:) • (
1369:Dense
1262:˘ = 1
1239:˘ = 1
1220:˘ = 0
850:B1-B3
832:)) ∨
824:˘ • (
719:) ∨ (
682:)˘ =
637:)˘ =
617:˘˘ =
562:) = (
524:is a
488:) ∨ (
460:) = (
405:is a
226:group
209:(0),
207:empty
38:is a
3223:and
3215:and
3098:ISBN
3001:ISBN
2745:ISBN
2459:˘ =
2447:˘ •
2120:Let
2051:) ∈
2011:= ¬(
1927:) ∈
1917:and
1912:) ∈
1760:and
1695:and
1668:and
1655:˘ •
1636:˘ •
1617:˘ •
1601:and
1505:The
1410:The
1198:˘ ≤
1176:˘ =
1080:˘ =
1068:˘ •
1045:˘ •
1018:˘ ≤
953:˘ •
876:23.
872:16,
868:26,
864:14,
860:45,
856:27,
773:˘ •
707:) •
686:˘ ∨
641:˘ •
570:) •
496:) =
468:) ∨
417:():
364:) =
355:) =
240:and
188:and
147:, ˘)
106:and
87:and
53:, a
34:, a
30:and
3063:doi
2976:doi
2925:doi
2834:doi
2496:of
2280:in
2004:xSz
2000:yRz
1994:in
1968:xSz
1964:xRy
1898:in
1862:= ∃
1815:of
1693:QRA
1685:QRA
1678:RRA
1674:QRA
1659:= 1
1591:QRA
1585:An
1567:RRA
1563:RRA
1551:RRA
1543:RRA
1527:RRA
1511:RRA
1490:is
1414:of
1381:≤ (
1161:= 0
846:ZFC
816:B10
733:B10
711:= (
554:• (
510:not
452:∨ (
114:of
26:In
3241::
3219::
3174::
3141::
3077:.
3069:.
3057:.
2982:.
2974:.
2962:50
2960:.
2954:.
2931:.
2921:30
2919:.
2888:;
2872:;
2840:.
2830:37
2828:.
2560:RA
2556:RA
2552:RA
2548:RA
2544:RA
2536:RA
2514:RA
2490:RA
2482:B7
2478:B4
2476:.
2455:•
2451:=
2088:≠
2064:⊆
2047:,
2035:,
2015:\¬
1984:,
1957:∈
1946:,
1923:,
1908:,
1890:•
1880:,
1840:∧
1836:=
1832:•
1800:⊆
1784:).
1772:→
1732:•
1726:RA
1715:.
1707:,
1689:RA
1650::
1648:Q2
1640:≤
1631::
1629:Q1
1621:≤
1612::
1610:Q0
1587:RA
1575:RA
1555:RA
1547:RA
1519:RA
1500:RA
1488:RA
1480:RA
1470:,
1466:,
1460:RA
1440:RA
1430:RA
1422:RA
1416:RA
1399:.
1281:=
1277:•
1258:∨
1254:∨
1235:∨
1139:≤
1121:≤
1103:≤
1099:•
1076:•
1072:=
1041:≤
1014:•
979:•
975:≤
957:≤
939::
933:is
922:RA
916:.
911:=
890:RA
874:B9
870:B8
866:B7
862:B6
858:B5
854:B4
836:=
828:•
818::
811:.
803:•
743:•
723:•
715:•
703:∨
697::
695:B9
678:∨
672::
670:B8
633:•
627::
625:B7
612::
610:B6
605::
589:=
585:•
580::
578:B5
566:•
558:•
549::
547:B4
542::
492:∨
484:∨
478::
476:B3
464:∨
456:∨
447::
445:B2
437:∨
433:=
429:∨
424::
422:B1
381:RA
299:=
282:=
266:=
134:A
99:.
3231:.
3203:"
3200:"
3196:"
3188:"
3184:"
3177:"
3163:"
3160:"
3156:"
3153:"
3149:"
3135:"
3128:"
3121:"
3106:.
3085:.
3065::
3059:6
3009:.
2990:.
2978::
2939:.
2927::
2848:.
2836::
2753:.
2597:)
2480:-
2466:L
2461:I
2457:R
2453:R
2449:R
2445:R
2436:R
2431:I
2421:.
2419:G
2405:}
2402:g
2399:A
2393:h
2390::
2387:G
2381:G
2375:)
2372:h
2369:,
2366:g
2363:(
2360:{
2357:=
2352:A
2348:R
2327:G
2321:A
2299:G
2293:G
2289:2
2266:G
2262:2
2241:}
2238:e
2235:{
2212:}
2209:A
2203:a
2200::
2194:1
2187:a
2183:{
2180:=
2175:1
2168:A
2141:G
2137:2
2122:G
2115:E
2106:X
2101:E
2096:X
2090:X
2086:E
2080:X
2075:X
2066:X
2062:E
2056:.
2053:R
2049:y
2045:x
2043:(
2039:)
2037:x
2033:y
2031:(
2027:R
2023:R
2019:)
2017:I
2013:y
2009:ў
1996:X
1992:z
1988:)
1986:y
1982:x
1980:(
1976:R
1972:S
1959:X
1955:x
1950:)
1948:z
1944:y
1942:(
1938:S
1934:R
1929:S
1925:z
1921:y
1919:(
1914:R
1910:y
1906:x
1904:(
1900:X
1896:y
1892:S
1888:R
1884:)
1882:z
1878:x
1876:(
1864:y
1860:z
1856:S
1852:R
1850:(
1848:x
1842:S
1838:R
1834:S
1830:R
1825:X
1817:X
1808:X
1802:X
1798:R
1793:X
1789:R
1782:x
1778:y
1774:x
1770:y
1766:y
1762:x
1758:x
1754:y
1750:y
1746:ў
1742:y
1740:∧
1738:x
1734:y
1730:x
1670:B
1666:A
1657:B
1653:A
1642:I
1638:B
1634:B
1623:I
1619:A
1615:A
1603:B
1599:A
1397:)
1395:I
1391:R
1387:I
1383:R
1379:I
1375:R
1361:R
1348:R
1335:R
1322:R
1309:R
1296:R
1283:R
1279:R
1275:R
1260:R
1256:R
1252:I
1237:R
1233:R
1218:R
1214:R
1200:I
1196:R
1192:R
1178:R
1174:R
1159:I
1155:R
1141:I
1137:R
1123:R
1119:I
1105:R
1101:R
1097:R
1082:I
1078:R
1074:R
1070:R
1066:R
1052:R
1050:(
1047:R
1043:R
1039:I
1025:R
1023:(
1020:I
1016:R
1012:R
987:R
985:(
983:˘
981:R
977:R
973:I
959:I
955:R
951:R
931:R
913:B
909:B
907:∨
905:A
899:B
895:A
838:B
834:B
830:B
826:A
822:A
820:(
809:A
805:B
801:C
779:B
775:C
771:A
749:C
745:B
741:A
727:)
725:C
721:B
717:C
713:A
709:C
705:B
701:A
699:(
690:˘
688:B
684:A
680:B
676:A
674:(
645:˘
643:A
639:B
635:B
631:A
629:(
619:A
615:A
591:A
587:I
583:A
572:C
568:B
564:A
560:C
556:B
552:A
539:I
522:L
515:I
498:A
494:B
490:A
486:B
482:A
480:(
470:C
466:B
462:A
458:C
454:B
450:A
439:A
435:B
431:B
427:A
403:L
366:x
362:x
357:x
353:x
349:I
345:I
339:x
335:I
320:I
316:L
314:(
310:x
305:I
301:x
297:x
293:I
288:y
284:x
280:y
276:x
272:y
268:x
264:y
260:x
222:)
220:I
218:(
198:I
193:x
186:y
184:•
182:x
175:x
171:y
169:∨
167:x
163:y
161:∧
159:x
145:I
141:L
139:(
93:R
89:S
85:R
78:S
76:•
74:R
70:X
63:X
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.