Complete categorical deduction for satisfaction as injectivity

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Birkhoff (quasi-)variety categorical axiomatizability results have fascinated many scientists by their elegance, simplicity and generality. The key factor leading to their generality is that equations, conditional or not, can be regarded as special morphisms or arrows in a special category, where their satisfaction becomes injectivity, a simple and abstract categorical concept. A natural and challenging next step is to investigate complete deduction within the same general and elegant framework. We present a categorical deduction system for equations as arrows and show that, under appropriate finiteness requirements, it is complete for satisfaction as injectivity. A straightforward instantiation of our results yields complete deduction for several equational logics, in which conditional equations can be derived as well at no additional cost, as opposed to the typical method using the theorems of constants and of deduction. At our knowledge, this is a new result in equational logics.

Original languageEnglish (US)
Title of host publicationAlgebra, Meaning, and Computation
Subtitle of host publicationEssays Dedicated to Joseph A Goguen on the Occasion of His 65th Birthday
PublisherSpringer
Pages157-172
Number of pages16
ISBN (Print)354035462X, 9783540354628
StatePublished - Jan 1 2006
EventSymposium on Algebra, Meaning, and Computation - Essays Dedicated to Joseph A Goguen on the Occasion of His 65th Birthday - San Diego, CA, United States
Duration: Jun 27 2006Jun 29 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4060 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherSymposium on Algebra, Meaning, and Computation - Essays Dedicated to Joseph A Goguen on the Occasion of His 65th Birthday
Country/TerritoryUnited States
CitySan Diego, CA
Period6/27/066/29/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Complete categorical deduction for satisfaction as injectivity'. Together they form a unique fingerprint.

Cite this