Monadic Bounded Algebras

Galym Akishev, Robert Goldblatt

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of MBA's as powerset algebras of certain directed graphs with a set of "marked" points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly, elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r.

Original languageEnglish
Pages (from-to)1-40
Number of pages40
JournalStudia Logica
Volume96
Issue number1
DOIs
Publication statusPublished - 2010
Externally publishedYes

Fingerprint

Algebra
Logic
Subdirect Product
Free Algebras
Directed Graph
Predicate
Quantification
Finitely Generated
Completeness
Generator
Graph in graph theory
Model

Keywords

  • atom
  • basic quantifier/algebra
  • bounded existential quantifier
  • bounded graph
  • bounded morphism
  • complex algebra
  • finitely-generated
  • free algebra
  • free logic
  • functional algebra
  • model
  • monadic algebra
  • point-generated
  • semantically complete logic
  • simple algebra
  • special algebra
  • variety
  • virtual ideal

ASJC Scopus subject areas

  • Logic

Cite this

Akishev, G., & Goldblatt, R. (2010). Monadic Bounded Algebras. Studia Logica, 96(1), 1-40. https://doi.org/10.1007/s11225-010-9269-z

Monadic Bounded Algebras. / Akishev, Galym; Goldblatt, Robert.

In: Studia Logica, Vol. 96, No. 1, 2010, p. 1-40.

Research output: Contribution to journalArticle

Akishev, G & Goldblatt, R 2010, 'Monadic Bounded Algebras', Studia Logica, vol. 96, no. 1, pp. 1-40. https://doi.org/10.1007/s11225-010-9269-z
Akishev, Galym ; Goldblatt, Robert. / Monadic Bounded Algebras. In: Studia Logica. 2010 ; Vol. 96, No. 1. pp. 1-40.
@article{40858b8ae1f84e8e91d86cefee249773,
title = "Monadic Bounded Algebras",
abstract = "We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of MBA's as powerset algebras of certain directed graphs with a set of {"}marked{"} points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly, elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r.",
keywords = "atom, basic quantifier/algebra, bounded existential quantifier, bounded graph, bounded morphism, complex algebra, finitely-generated, free algebra, free logic, functional algebra, model, monadic algebra, point-generated, semantically complete logic, simple algebra, special algebra, variety, virtual ideal",
author = "Galym Akishev and Robert Goldblatt",
year = "2010",
doi = "10.1007/s11225-010-9269-z",
language = "English",
volume = "96",
pages = "1--40",
journal = "Studia Logica",
issn = "0039-3215",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Monadic Bounded Algebras

AU - Akishev, Galym

AU - Goldblatt, Robert

PY - 2010

Y1 - 2010

N2 - We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of MBA's as powerset algebras of certain directed graphs with a set of "marked" points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly, elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r.

AB - We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of MBA's as powerset algebras of certain directed graphs with a set of "marked" points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly, elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r.

KW - atom

KW - basic quantifier/algebra

KW - bounded existential quantifier

KW - bounded graph

KW - bounded morphism

KW - complex algebra

KW - finitely-generated

KW - free algebra

KW - free logic

KW - functional algebra

KW - model

KW - monadic algebra

KW - point-generated

KW - semantically complete logic

KW - simple algebra

KW - special algebra

KW - variety

KW - virtual ideal

UR - http://www.scopus.com/inward/record.url?scp=77955184935&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955184935&partnerID=8YFLogxK

U2 - 10.1007/s11225-010-9269-z

DO - 10.1007/s11225-010-9269-z

M3 - Article

VL - 96

SP - 1

EP - 40

JO - Studia Logica

JF - Studia Logica

SN - 0039-3215

IS - 1

ER -