Access Restriction

Author Gabbay, Murdoch J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Nominal algebra ♦ Amgis-algebra ♦ First-order logic ♦ Fresh-finite limits ♦ Mathematical foundations ♦ Nominal lattices ♦ Semantics ♦ Sigma-algebra ♦ Variables
Abstract Call a semantics for a language with variables $\textit{absolute}$ when variables map to fixed entities in the denotation. That is, a semantics is absolute when the denotation of a variable $\textit{a}$ is a copy of itself in the denotation. We give a trio of lattice-based, sets-based, and algebraic absolute semantics to first-order logic. Possibly open predicates are directly interpreted as lattice elements/sets/algebra elements, subject to suitable interpretations of the connectives and quantifiers. In particular, universal quantification $∀\textit{a}.&phis;$ is interpreted using a new notion of $\textit{“fresh-finite”}$ limit &bigwedge $^{#a}$ ⟦&phi⟧⟧ and using a novel dual to substitution. The interest in this semantics is partly in the nontrivial and beautiful technical details, which also offer certain advantages over existing semantics. Also, the fact that such semantics exist at all suggests a new way of looking at variables and the foundations of logic and computation, which may be well suited to the demands of modern computer science.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 3
Page Count 66
Starting Page 1
Ending Page 66

Open content in new tab

   Open content in new tab
Source: ACM Digital Library