Generalizations of enumeration reducibility using recursive infinitary propositional sentences
type: Item
instance of: scholarly article
title: Generalizations of enumeration reducibility using recursive infinitary propositional sentences
zbMATH Open document ID: 0769.03025
DOI: 10.1016/0168-0072(92)90026-V
author: C. J. Ash
published in: Annals of Pure and Applied Logic
publication date: 1993-04-01T00:00:00Z
review text: Call \(B\) enumeration reducible to \(A\) \((B\leq_ e A)\) iff for every set \(S\), if \(A\) is r.e. in \(S\), then \(B\) is r.e. in \(S\). This paper shows a generalization of this correspondence: the relation between sets \(A\) and \(B\) that for every set \(S\) if \(A\) is \(\Sigma^ 0_ \alpha\) in \(S\) then \(B\) is \(\Sigma^ 0_ \beta\) in \(S\), is equivalent to the condition that \(B\) is definable from \(A\) in a particular way involving recursive infinitary propositional sentences. Some further generalizations involving infinitely many sets and ordinals are also established.
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 149960
zbMATH Keywords: enumeration reducibility
zbMATH Keywords: infinitary propositional logic
reviewed by: Xizhong Zheng
MaRDI profile type: Publication
cites work: Generic copies of countable structures
cites work: Maximal Arithmetical Reducibilities
cites work: Q5573961
cites work: Arithmetical Reducibilities II
full work available at URL: 0168-0072(92)90026-v
OpenAlex ID: W2038095589
description: scientific article; zbMATH DE number 149960