Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRelation algebras of Sugihara, Belnap, Meyer, and Church
86
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Algebras introduced by, or attributed to, Sugihara, Belnap, Meyer, and Church are representable as algebras of binary relations with set-theoretically defined operations. They are definitional reducts or subreducts of proper relation algebras. The representability of Sugihara matrices yields sound and complete set-theoretical semantics for R-mingle.
rate research
Read More
For any pair of ordinals $alpha<beta$, $sf CA_alpha$ denotes the class of cylindric algebras of dimension $alpha$, $sf RCA_{alpha}$ denote the class of representable $sf CA_alpha$s and $sf Nr_alpha CA_beta$ ($sf Ra CA_beta)$ denotes the class of $alpha$-neat reducts (relation algebra reducts) of $sf CA_beta$. We show that any class $sf K$ such that $sf RaCA_omega subseteq sf Ksubseteq RaCA_5$, $sf K$ is not elementary, i.e not definable in first order logic. Let $2<n<omega$. It is also shown that any class $sf K$ such that $sf Nr_nCA_omega cap {sf CRCA}_nsubseteq {sf K}subseteq mathbf{S}_csf Nr_nCA_{n+3}$, where $sf CRCA_n$ is the class of completely representable $sf CA_n$s, and $mathbf{S}_c$ denotes the operation of forming complete subalgebras, is proved not to be elementary. Finally, we show that any class $sf K$ such that $mathbf{S}_dsf Ra CA_omega subseteq {sf K}subseteq mathbf{S}_csf RaCA_5$ is not elementary. It remains to be seen whether there exist elementary classes between $sf RaCA_omega$ and $mathbf{S}_dsf RCA_{omega}$. In particular, for $mgeq n+3$, the classes $sf Nr_nCA_m$, $sf CRCA_n$, $mathbf{S}_dsf Nr_nCA_m$, where $mathbf{S}_d$ is the operation of forming dense subalgebras are not first order definable.
We study some finite integral symmetric relation algebras whose forbidden cycles are all 2-cycles. These algebras arise from a finite field construction due to Comer. We consider conditions that allow other finite algebras to embed into these Comer algebras, and as an application give the first known finite representation of relation algebra $34_{65}$, one of whose atoms is flexible. We conclude with some speculation about how the ideas presented here might contribute to a proof of the flexible atom conjecture.
Let 2<nleq l<m< omega. Let L_n denote first order logic restricted to the first n variables. We show that the omitting types theorem fails dramatically for the n--variable fragments of first order logic with respect to clique guarded semantics, and for its packed n--variable fragments. Both are modal fragments of L_n. As a sample, we show that if there exists a finite relation algebra with a so--called strong l--blur, and no m--dimensional relational basis, then there exists a countable, atomic and complete L_n theory T and type Gamma, such that Gamma is realizable in every so--called m--square model of T, but any witness isolating Gamma cannot use less than $l$ variables. An $m$--square model M of T gives a form of clique guarded semantics, where the parameter m, measures how locally well behaved M is. Every ordinary model is k--square for any n<k<omega, but the converse is not true. Any model M is omega--square, and the two notions are equivalent if M is countable. Such relation algebras are shown to exist for certain values of l and m like for nleq l<omega and m=omega, and for l=n and mgeq n+3. The case l=n and m=omega gives that the omitting types theorem fails for L_n with respect to (usual) Tarskian semantics: There is an atomic countable L_n theory T for which the single non--principal type consisting of co--atoms cannot be omitted in any model M of T. For n<omega, positive results on omitting types are obained for L_n by imposing extra conditions on the theories and/or the types omitted. Positive and negative results on omitting types are obtained for infinitary variants and extensions of L_{omega, omega}.
Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras $bf A$. We provide a complete classification for the case that $bf A$ is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation $mathfrak{B}$. We can then study the computational complexity of the network satisfaction problem of ${bf A}$ using the universal-algebraic approach, via an analysis of the polymorphisms of $mathfrak{B}$. We also use a Ramsey-type result of Nev{s}etv{r}il and Rodl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
In this article we investigate the notion and basic properties of Boolean algebras and prove the Stones representation theorem. The relations of Boolean algebras to logic and to set theory will be studied and, in particular, a neat proof of completeness theorem in propositional logic will be given using Stones theorem from Boolean algebra.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
