Scott induction and closure under \(\omega\)-sups
type: Item
instance of: scholarly article
title: Scott induction and closure under \(\omega\)-sups
zbMATH Open document ID: 0611.68008
DOI: 10.1016/0304-3975(86)90179-9
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: The paper presents a attempt to giving a semantic analysis of Scott's induction axiom of LCF, the logic of continuous functionals, \[ (\forall f)[R(f,\perp)\wedge \forall x[R(f,x)\to R(f,f(x))]\to R(f,Yf)]. \] This axiom is valid for relations \(R\subseteq [P\to P]\times P\) satisfying the condition \[ (*)\quad (\forall f)\{x: R(f,x)\} \] is closed under \(\omega\)-sups, which has often been used as a method for proving that certain definable R satisfies Scott's induction axiom. The paper proves that (*) is not a necessary condition, and hence the proof method is not complete. From certain definability and effectiveness aspects of the relation between being Scott-induction and closed under \(\omega\)-sups, some interesting classes of \(\omega\)-cpo's are shown to be finitely axiomatized in the language of LCF.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03B40
zbMATH DE Number: 3988696
zbMATH Keywords: logic computable functionals
zbMATH Keywords: complete partial orders
zbMATH Keywords: Scott's induction axiom
zbMATH Keywords: LCF
zbMATH Keywords: logic of continuous functionals
author: Ana Pasztor
author: Richard Statman
reviewed by: Jiří Zlatuška
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90179-9
OpenAlex ID: W1971339442
cites work: Q5331549
cites work: Set theory. An introduction to large cardinals
cites work: Edinburgh LCF. A mechanized logic of computation
cites work: Q5573961
description: scientific article; zbMATH DE number 3988696