Search

Let 2 < n < ω. Then CAn denotes the class of cylindric algebras of dimension n, RCAn denotes the class of representable CAns, CRCAn denotes the class of completely representable CAns, and NrnCAω(⊆ CAn) denotes the class of n-neat reducts of CAωs. The elementary closure of the class CRCAns (Kn) and the nonelementary class At(NrnCAω) are characterized using two-player zero-sum games, where At is the operator of forming atom structures. It is shown that Kn is not finitely axiomatizable and that it coincides with the class of atomic algebras in the elementary closure of ScNrnCAω where Sc is the operation of forming complete subalgebras. For any class L such that AtNrnCAω ⊆ L ⊆ AtKn, it is proved that SPCmL = RCAn, where Cm is the dual operator to At; that of forming complex algebras. It is also shown that any class K between CRCAn ∩ SdNrnCAω and ScNrnCAn+3 is not first order definable, where Sd is the operation of forming dense subalgebras, and that for any 2 < n < m, any l ≥ n + 3 any any class K such that At(NrnCAm ∩ CRCAn) ⊆ K ⊆ AtScNrnCAl, K is not not first order definable either. [ABSTRACT FROM AUTHOR]

Fix a finite ordinal n ≥ 3 and let α be an arbitrary ordinal. Let CAn denote the class of cylindric algebras of dimension n and RA denote the class of relation algebras. Let PAα(PEAα) stand for the class of polyadic (equality) algebras of dimension α. We reprove that the class CRCAn of completely representable CAns, and the class CRRA of completely representable RAs are not elementary, a result of Hirsch and Hodkinson. We extend this result to any variety V between polyadic algebras of dimension n and diagonal free CAns. We show that that the class of completely and strongly representable algebras in V is not elementary either, reproving a result of Bulian and Hodkinson. For relation algebras, we can and will, go further. We show the class CRRA is not closed under =1,ω. In contrast, we show that given α ≥ ω, and an atomic A 2 PEAα, then for any n < !, NrnA is a completely representable PEAn. We show that for any α ≥ ω, the class of completely representable algebras in certain reducts of PAαs, that happen to be varieties, is elementary. We show that for α ≥ ω, the the class of polyadic-cylindric algebras dimension α, introduced by Ferenczi, the completely representable algebras (slightly altering representing algebras) coincide with the atomic ones. In the last algebras cylindrifications commute only one way, in a sense weaker than full fledged commutativity of cylindrifications enjoyed by classical cylindric and polyadic algebras. Finally, we address closure under Dedekind-MacNeille completions for cylindric-like algebras of dimension n and PAαs for α an infinite ordinal, proving negative results for the first and positive ones for the second. [ABSTRACT FROM AUTHOR]

Fix 2 < n < ω and let CAn denote the class of cyindric algebras of dimension n. Roughly CAn is the algebraic counterpart of the proof theory of first order logic restricted to the first n variables which we denote by Ln. The variety RCAn of representable CAns reflects algebraically the semantics of Ln. Members of RCAn are concrete algebras consisting of genuine n-ary relations, with set theoretic operations induced by the nature of relations, such as projections referred to as cylindrifications. Although CAn has a finite equational axiomatization, RCAn is not finitely axiomatizable, and it generally exhibits wild, often unpredictable and unruly behavior. This makes the theory of CAn substantially richer than that of Boolean algebras, just as much as Lω,ω is richer than propositional logic. We show using a so-called blow up and blur construction that several varieties (in fact infinitely many) containing and including the variety RCAn are not atom-canonical. A variety V of Boolean algebras with operators is atom canonical, if whenever 𝔄 ∈ V is atomic, then its Dedekind-MacNeille completion, sometimes referred to as its minimal completion, is also in V. From our hitherto obtained algebraic results we show, employing the powerful machinery of algebraic logic, that the celebrated Henkin-Orey omitting types theorem, which is one of the classical first (historically) cornerstones of model theory of Lω,ω, fails dramatically for Ln even if we allow certain generalized models that are only locallly clasfsical. It is also shown that any class K such that N r n C A ω ∩ CRC A n ⊆ ¯ K ⊆ ¯ S c N r n C A n + 3 , where CRCAn is the class of completely representable CAns, and Sc denotes the operation of forming dense (complete) subalgebras, is not elementary. Finally, we show that any class K such that S d RaC A ω ⊆ ¯ K ⊆ ¯ S c RaC A 5 is not elementary, where Sd denotes the operation of forming dense subalgebra. [ABSTRACT FROM AUTHOR]

The notion of positive implicative soju ideal in BCK-algebra is introduced, and several properties are investigated. Relations between soju ideal and positive implicative soju ideal are considered, and characterizations of positive implicative soju ideal are established. Finally, extension property for positive implicative soju ideal is constructed. [ABSTRACT FROM AUTHOR]

In this paper we consider, from a computational point of view, the problem of classifying logics within the Leibniz and Frege hierarchies typical of abstract algebraic logic. The main result states that, for logics presented syntactically, this problem is in general undecidable. More precisely, we show that there is no algorithm that classifies the logic of a finite consistent Hilbert calculus in the Leibniz and in the Frege hierarchies. [ABSTRACT FROM AUTHOR]

We prove that any equational basis that defines representable relation algebras (RRA) over weakly representable relation algebras (wRRA) must contain infinitely many variables. The proof uses a construction of arbitrarily large finite weakly representable but not representable relation algebras whose “small” subalgebras are representable. [ABSTRACT FROM AUTHOR]

Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in a possibly incomplete table, and not necessarily containing the overall effect. In this generality, the MLEs under Poisson and multinomial sampling are not always identical. This paper deals with the theory of maximum likelihood estimation in the case when there are observed zeros in the data. A unique MLE to such data is shown to always exist in the set of pointwise limits of sequences of distributions in the original model. This set is equal to the closure of the original model with respect to the Bregman information divergence. The same variant of iterative scaling may be used to compute the MLE whether it is in the original model or in its closure. [ABSTRACT FROM AUTHOR]

We relate Orlicz-Hardy inequalities on a Euclidean domain to fatness conditions on the complement. For certain iterated log-scale distortions of Ln, this relationship is necessary and sufficient, extending results of Buckley and Koskela, and others. [ABSTRACT FROM AUTHOR]

Following Jiang Guanghao and Xu Luoshan's concept of conjugative, dually conjugative, normal and dually normal relations on sets, the concept of quasi-regular relations is introduced. Characterizations of quasi-regular relations are obtained and it is shown when an anti-order relation is quasi-regular. Some nontrivial examples of quasi-regular relations are given. At the end we introduce dually quasi-regular relations and give a connection between these two types of relations. [ABSTRACT FROM AUTHOR]

Given a simple atomic relation algebra $${\mathcal{A}}$$ and a finite n ≥ 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra $${\mathcal{P}}$$ such that for any subsignature L of the signature of $${\mathcal{P}}$$ that contains the boolean operations and cylindrifications, the L-reduct of $${\mathcal{P}}$$ is completely representable if and only if $${\mathcal{A}}$$ is completely representable. If $${\mathcal{A}}$$ is finite then so is $${\mathcal{P}}$$ . It follows that there is no algorithm to determine whether a finite n-dimensional cylindric algebra, diagonal-free cylindric algebra, polyadic algebra, or polyadic equality algebra is representable (for diagonal-free algebras this was known). We also obtain a new proof that the classes of completely representable n-dimensional algebras of these types are non-elementary, a result that remains true for infinite dimensions if the diagonals are present, and also for infinite-dimensional diagonal-free cylindric algebras. [ABSTRACT FROM AUTHOR]

We prove that the equational complexity function for the variety of representable relation algebras is bounded below by a log-log function. [ABSTRACT FROM AUTHOR]

We consider all positive fragments of Tarski's representable relation algebras and determine whether the equational and quasiequational theories of these fragments are finitely axiomatizable in first-order logic. We also look at extending the signature with reflexive, transitive closure and the residuals of composition. [ABSTRACT FROM AUTHOR]

Abstract: Coalgebras can be seen as a natural abstraction of Kripke frames. In the same sense, coalgebraic logics are generalised modal logics. In this paper, we give an overview of the basic tools, techniques and results that connect coalgebras and modal logic. We argue that coalgebras unify the semantics of a large range of different modal logics (such as probabilistic, graded, relational, conditional) and discuss unifying approaches to reasoning at this level of generality. We review languages defined in terms of the so-called cover modality, languages induced by predicate liftings as well as their common categorical abstraction, and present (abstract) results on completeness, expressiveness and complexity in these settings, both for basic languages as well as a number of extensions, such as hybrid languages and fixpoints. [Copyright &y& Elsevier]

Abstract: We generalize stochastic Kripke models and Markov transition systems to stochastic right coalgebras. These are coalgebras for a functor with as an endofunctor on the category of analytic spaces, and is the subprobability functor. The modal operators are generalized through predicate liftings which are set-valued natural transformations involving the functor. Two states are equivalent iff they cannot be separated by a formula. This equivalence relation is used to construct a cospan for logical equivalent coalgebras under a separation condition for the set of predicate liftings. Consequently, behavioral and logical equivalence are really the same. From the cospan we construct a span. The central argument is a selection argument giving us the dynamics of a mediating coalgebra from the domains of the cospan. This construction is used to establish that behavioral equivalent coalgebras are bisimilar, yielding the equivalence of all three characterizations of a coalgebra’s behavior as in the case of Kripke models or Markov transition systems. [Copyright &y& Elsevier]

The essential concept of cause-effect space of resources is pioneered in this paper, along with the CEGRA (cause-effect grey relational analysisl which is predicated on the basis of cause-effect incidenceness and comparisons. [ABSTRACT FROM AUTHOR]

We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first-order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. There has been extensive research on increasing the expressive power of WA by adding new operations [1, 4, 11, 13, 20]. Extensions of this kind usually also have decidable universal theories. Here we give an example – extending WA's with set-theoretic projection elements – where this is not the case. These “logical” connectives are set-theoretic counterparts of the axiomatic quasi-projections that have been investigated in the representation theory of relation algebras [22, 6, 19]. We prove that the quasi-equational theory of the extended class PWA is not recursively enumerable. By adding the difference operator D one can turn WA and PWA to discriminator classes where each universal formula is equivalent to some equation. Hence our result implies that the projections turn the decidable equational theory of “WA + D ” to non-recursively enumerable (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In [10] it is claimed that the set of predicate tautologies of all complete BL-chains and the set of all standard tautologies (i. e., the set of predicate formulas valid in all standard BL-algebras) coincide. As noticed in [11], this claim is wrong. In this paper we show that a complete BL-chain B satisfies all standard BL-tautologies iff for any transfinite sequence (ai: i ∈ I) of elements of B, the condition ∧i ∈ I (a2i) = (∧i ∈ Iai)2 holds in B. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Letn > 2. A weakly representable relation algebra that is not strongly representable is constructed. It is proved that the set of all n by n basic matrices forms a cylindric basis that is also a weakly but not a strongly representable atom structure. This gives an example of a binary generated atomic representable cylindric algebra with no complete representation. An application to first order logic is given. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Abstract: The relational product construction is often consider as an abstract version of cartesian products. The existence of those products is strongly connected with the representability of that category. In this paper we investigate a canonical weakening of the notion of a relational product. Unlike the strong version, any (small) category of relations can be embedded into a suitable category providing all weak relational products. Furthermore, we provide several examples, and we study the categorical properties of the new construction. [Copyright &y& Elsevier]

In this paper we develop an algebraic/categorical theory of bisimulations using relational methods. We define a general notion, which is capable of handeling different version of bisimilarity in a common context. Furthermore, the approach relates bisimulations with the notion of a covering known from the theory of graphs and their applications in topology and complex analysis. [ABSTRACT FROM AUTHOR]

We consider relational periods where the relation is a compatibility relation on words induced by a relation on letters. We introduce three types of periods, namely global, external and local relational periods, and we compare their properties by proving variants of the theorem of Fine and Wilf for these periods. [ABSTRACT FROM AUTHOR]

Abstract.  In this paper we show that every quasi-projective relation algebra (QRA) has within it cylindric algebras (CAs) of all finite dimensions greater than two such that (i) they are term-definable in the QRA, (ii) they have a relation algebraic reduct that is isomorphic to the QRA and (iii) these isomorphisms are also term-definable. Furthermore, these CAs form a sequence such that each of them is isomorphic to a neat reduct of the higher dimensional ones, and these isomorphisms are also term-definable. These observations yield a new proof of the representation theorem of QRAs, due to Tarski, that is fundamentally different from both his original proof and Maddux’s, who generalized Tarski’s theorem to a much wider class of algebras. [ABSTRACT FROM AUTHOR]

Abstract.??We study MV-relation-algebras, appearing by abstracting away from the concrete many-valued relations and the operations on them, such as composition and converse. MV-relation-algebras are MV generalizations of the relation algebras developed by A. Tarski and his school starting from the late forties. Some facts about ideals, congruences, and various types of elements are proved. A characterization of the ?natural? MV-relation-algebras (a parameterized analogue of the classicalfullproperrelation algebras) is also provided, as well as a first-order elementary description of matrix MV-relation algebras. [ABSTRACT FROM AUTHOR]

To solve problems of Magnus and Stallings stated in the 1960s, we construct a balanced presentation of the trivial group such that no defining relator of this presentation could be replaced by a free generator and the group, given by the altered presentation, would still be trivial. Some other related problems on balanced presentations of the trivial group are discussed. [ABSTRACT FROM AUTHOR]

This article focuses on the importance of the equals sign in students' understanding of algebra. It is recommended that teachers begin to help their students develop algebraic thinking in the elementary grades, especially the equals sign, about which many children have misconceptions. According to the article, if students use relational thinking, they can solve number sentences by focusing on the relationships between numbers in an equation. The article provides an assessment of a case study on eighteen children over five sessions of ethnically and linguistically diverse students.

In the article we characterize, in terms of quivers and relations, the admissible algebras with formal two-ray modules introduced in Bobiński and Skowroński (2003b). [ABSTRACT FROM AUTHOR]

The aim of this survey paper is to summarize the most recent results on pre-Hilbert-space logics and their corresponding measure spaces. [ABSTRACT FROM AUTHOR]

We investigate the complexity of the typability problem for the relational algebra. This problem consists of deciding, for a given relational algebra expression, whether there exists an assignment of types to variables occurring in the expression such that the expression is well-typed under the assignment. We obtain that the problem is NP-complete in general. In particular, we show that the problem becomes NP-hard due to (1) the cartesian product operator, (2) the selection operator on arbitrary sets of typed predicates, (3) the selection operator on “well-behaved” sets of typed predicates together with join and projection or renaming. However, the problem is in P when (1) we only allow union, difference, join and selection on “well-behaved” sets of typed predicates, or (2) we allow all operators except cartesian product, where the set of selection predicates can mention at most one base type. Most of these results follow from a close connection of the typability problem to non-uniform constraint satisfaction. [ABSTRACT FROM AUTHOR]

Region Connection Calculus (RCC) is the most widely studied formalism of Qualitative Spatial Reasoning. It has been known for some time that each connected regular topological space provides an RCC model. These 'standard' models are inevitable uncountable and regions there cannot be represented finitely. This paper, however, draws researchers' attention to RCC models that can be constructed from finite models hierarchically. Compared with those 'standard' models, these countable models have the nice property that regions where can be constructed in finite steps from basic ones. We first investigate properties of three countable models introduced by Düuntsch, Stell, Li and Ying, resp. In particular, we show that (i) the contact relation algebra of our minimal model is not atomic complete; and (ii) these three models are non-isomorphic. Second, for each n>0, we construct a countable RCC model that is a sub-model of the standard model over the Euclidean unit n-cube; and show that all these countable models are non-isomorphic. Third, we show that every finite model can be isomorphically embedded in any RCC model. This leads to a simple proof for the result that each consistent spatial network has a realization in any RCC model. [ABSTRACT FROM AUTHOR]

Abstract: Given a finite set E, a relation with base is a mapping such that for all . The restriction of R to a subset X of E is R considered as a mapping from into . Given an integer and a relation R with base E, we call -reconstruction of R every relation with the same base, any restriction of which to a subset X of E with up to k elements is isomorphic to the restriction of R to X. The relation R is -reconstructible when each -reconstruction of R is isomorphic to R. In this work, the structure of the non--reconstructible relations is studied for all . This study leads to an introduction of the minimal non--reconstructible relations and to characterization of the class of such relations for all . This class includes in particular the class of the indecomposable non--reconstructible relations. [Copyright &y& Elsevier]

Many formalisms for qualitative spatial and temporal reasoning fit into a pattern exemplified by Allen's temporal interval calculus. Constraint‐based reasoning using Allen's calculus can benefit from some of its main properties: (a) the underlying constraint algebra is a relation algebra, in Tarski's sense; (b) testing path‐consistency is a complete method for testing consistency for well‐determined subclasses of relations; (c) atomic path‐consistent networks are consistent and determine unique qualitative configurations; (d) the first order theory associated to the calculus is aleph‐zero categorical. When considering analogous calculi, many of the properties mentioned above no longer hold. The main object of this paper is to examine some of the new questions which arise. In order to do so, we use the idea of weak representations of the algebras as a unifying concept. [ABSTRACT FROM AUTHOR]

Relation algebras were invented by Tarski and his collaborators in the middle of the 20th century. The concept of integrality arose naturally early in the history of the subject, as did various constructions of finite integral relation algebras. Later the concept of finite-dimensionality was introduced for classifying nonrepresentable relation algebras. This concept is closely connected to the number of variables used in proofs in first-order logic. Some results on these topics are presented in chronological order. [Copyright &y& Elsevier]

According to the emerging MPEG-7 standard, the semantic description of multimedia documents is expressed in terms of semantic entities such as objects, events, concepts, and relations among them. The semantic entities can be used as index terms, in order to support the semantic search process. In this paper, we propose a method that a) applies fuzzy relational operations (closure, composition) and fuzzy rules to expand a semantic encyclopedia and b) uses the encyclopedia to associate the semantic entities with the aid of a fuzzy thesaurus. This method is shown to reduce the need for human intervention in creating semantic descriptions of multimedia documents, as well as correct for incompleteness and inconsistency. [ABSTRACT FROM AUTHOR]

Let 1 < n < ω and β > n. We show that the class NrnCAβ of n-dimensional neat reducts of β-dimensional cylindric algebras is not closed under forming elementary subalgebras. This solves a long-standing open problem of Tarski and his co-authors Andréka, Henkin, Monk and Németi. The proof uses genuine model-theoretic arguments. [ABSTRACT FROM AUTHOR]

We propose a definition of weak o-minimality for structures expanding a Boolean algebra. We study this notion, in particular we show that there exist weakly o-minimal non o-minimal examples in this setting. [ABSTRACT FROM AUTHOR]

The article presents a supplementation to the article "Finitary Algebraic Logic" that was written by the author in the previous issue of the journal. It offers corrections to errors committed in the said issue that were relevant to semiassociative relation algebra and algebraic logic. It explains the difference between a strong point-density and point-density, noting that strong point-density is preserved under homomorphisms while point-density is not.

The article presents the notion of syllogistic of a theory in a situations system. It shows the connections between the syllogistic and the relation algebras and the mathematical formulation that defines the first-order theory containing the binary predicate symbols, the syllogistic theses of a theory, and the propositions of a theory. It also cites the mathematical theorem of the syllogistics of the transitive relation theory, Keynes syllogistic, and syllogistic geometry.

We prove that persistently finite algebras are not created by completions of algebras, in any ordered discriminator variety. A persistently finite algebra is one without infinite simple extensions. We prove that finite measurable relation algebras are all persistently finite. An application of these theorems is that the variety generated by the completions of representable relation algebras does not contain all relation algebras. This answers Problem 1.1(1) from Maddux's 2018 Algebra Universalis paper in the negative. At the same time, we confirm the suggestion in that paper that the finite maximal relation algebras constructed in M. Frias and R. Maddux's 1997 Algebra Universalis paper are not in the variety generated by the completions of representable relation algebras. We prove that there are continuum many varieties between the variety generated by the completions of representable relation algebras and the variety of relation algebras. [ABSTRACT FROM AUTHOR]

This note is an addendum to clarify credit for universal relational systems and their properties. [ABSTRACT FROM AUTHOR]

In the paper, the systems of axioms for classes of groupoids and partially ordered groupoids of relations with the operation of bi-directional intersection are found. [ABSTRACT FROM AUTHOR]

The article reports on a study published within the issue related to mathematics students' understanding of distinction between the concepts of function and relation in Greece. It examines students' awareness of the discrimination between function and relation, and the discrimination between the dependent and the independent variables. It presents results of the questionnaires and interviews that students experienced difficulties in answering them. It states that the students' examples and their application of the definition explored a constrained perception of the function concept. Therefore, in order to overcome the obstacle of confusing the function with a relation, it suggests a teaching of function oriented towards activities which demand the measure of a magnitude.