2
$\begingroup$

The class $\textsf{Cs}_{\omega}^{reg}\cap \textsf{Lf}_{\omega}$ of locally finite and regular cylindric set algebras (of dimension $\omega$) can be seen as the algebraic counterpart of first-order models (details below).

I also know that we can associate, to each model, a representable cylindric algebra in $RCA_{\alpha}$, where $\alpha$ denotes the number of variables in our signature.

  • What is the relation between $\textsf{RCA}_{\alpha}$ and $\textsf{Cs}_{\alpha}^{reg}\cap \textsf{Lf}_{\alpha}$, where $\alpha$ is some at most countable ordinal?

In particular, I am interested in the equational definability of the regularity property. The definition of regularity for cylindric set algebras is always given by explicit reference to tuples from the underlying `domain set' -- the set of tuples $U^{\alpha}$ which serves as basis of the given cylindric algebra (i.e. the cylindric algebra is an algebra over $\mathcal{P}(U^{\alpha})$).

  • Is it possible to define regularity using only the language of cylindric algebras?

  • Is the class of regular, locally finite cylindric set algebras equationally definable ?

A more general question: suppose we want to give a complete semantics for first-order logic in terms of cylindric algebras. That is, we want each model to be given by a pair $(\mathfrak{A}, [\cdot])$ where $\mathfrak{A}$ is a cylindric algebra and $[\cdot]$ a valuation mapping each formula to an element $a\in\mathfrak{A}$ in the usual way. Can we do so in such a way that the required class of cylindric algebras is a variety? Can we characterise the class of all such pairs $(\mathfrak{A}, [\cdot])$ in an abstract way, without mention of the underlying set of tuples $U^{\alpha}$ representing the domain of some 'corresponing' first-order model?

What are the natural classes of algebras that could serve as candidates for this?

(if not, can we do so for a first-order language without equality? or with finitely many variables?)


Some more details:

Fix a signature (first-order language).

To each first-order model $\mathfrak{M}$ there corresponds an $\omega$-dimensional cylindric set algebra $\textsf{Cs}^{\mathfrak{M}}$, obtained by mapping each formula to the set of tuples in $\textsf{dom}(\mathfrak{M})$ that satisfy it. Such an algebra $\textsf{Cs}^{\mathfrak{M}}$ is always locally finite and regular. Conversely, each locally finite and regular cylindric set algebra $\textsf{A}$ has a corresponding model $\mathfrak{M}$ such that $\textsf{A}=\textsf{Cs}^{\mathfrak{M}}$.

$\endgroup$

1 Answer 1

3
$\begingroup$

$RCA$ is defined to be $SP(Cs)$, the subalgebras of products of cylindric set algebras. It is written $Gs$ in Henkin, Monk, and Tarski's book Cylindric Algebras Volumes I and II. (Or pedantically $IGs$, the isomorphic copies.) It turns out this is a variety, and that book HMT II gives equations characterizing it in section 4.1.

So by definition, every algebra in the class $Cs^{reg}\cap Lf$ (which is sometimes written $Csf$ for short) is in $RCA$. Another way that these are related is that $HSP(Csf)=RCA$ (see 3.1.108 and 3.1.123 in HMT II), at least for dimension 2 and higher.

The regularity property is not equationally definable. Indeed, the class $Cs^{reg}$ of regular cylindric set algebras cannot be isolated from the class $Cs$ of cylindric set algebras by an equational theory: $HSP(Cs^{reg})=HSP(Cs)=RCA$ (see 3.1.108 in HMT II). Furthermore, the universal theory of $Cs$ and $Cs^{reg}$ are the same as well, and so there is no universal characterization of regularity (see the discussion following theorem 4.1.48 in HMT II).

The class $Csf$ is not equationally definable. It is not even first order definable (see 3.1.100 in HMT II).

One kind of completeness theorem would be to give an axiomatization of the equational theory of $Csf_\omega$. Since $HSP(Csf_\omega)=RCA_\omega$, we can also take the models to be in this class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.