μ-definable sets of integers

DOI10.2307/2275338MaRDI QIDQ5287693zbMATH OpenOpenAlexFDO

Authors Robert S. Lubarsky

Publication date 17 August 1993

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275338

zbMATH Keywords

\(\mu\)-calculusadmissibilityfirst-order logicfixed pointsinductive definitionsprenex normal formreflection properties

Mathematics Subject Classification ID

Inductive definability (03D70)

Review text

The \(\mu\)-calculus is a language for including inductive definitions with first-order logic. In first-order logic, a formula \(\varphi\) with a distinguished free variable \(x\) can be taken to represent a set, \(\{x\mid \varphi(x)\}\). Then the Boolean connectives become operations on sets. The \(\mu\)-calculus merely adds one more, least fixed point. This paper shows that those sets of natural numbers definable in the \(\mu\)-calculus are exactly those that are in a certain initial segment of \(L\). The ordinals used to describe this segment are characterized by a hierarchy of reflection properties, only the lowest levels of which had been identified before [by \textit{W. Richter} and \textit{P. Aczel}, Generalized Recursion Theory, Proc. Symp. Oslo 1972, 301-381 (1974; Zbl 0318.02042)]. Along the way some prenex normal form theorems about the \(\mu\)-calculus are also proved.

Recommendations

• scientific article; zbMATH DE number 4187792
• On the \(\mu \)-calculus over transitive and finite transitive frames
• Results on the propositional \(\mu\)-calculus
• Rudiments of -calculus

Cites work

• scientific article; zbMATH DE number 3861143 (Why is no real title available?)
• Results on the propositional \(\mu\)-calculus

Cited in

(21)

• The modal mu-calculus alternation hierarchy is strict
• An intensional fixed point theory over first order arithmetic
• A Buchholz rule for modal fixed point logics
• On the universal and existential fragments of the \(\mu\)-calculus
• On fixpoint arithmetic and infinite time Turing machines
• Extending constructive operational set theory by impredicative principles
• Domain mu-calculus
• Fixpoints, games and the difference hierarchy
• 2003 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquim '03
• scientific article; zbMATH DE number 1882496 (Why is no real title available?)
• Fixpoint alternation: arithmetic, transition systems, and the binary tree
• On the Strength of the Uniform Fixed Point Principle in Intuitionistic Explicit Mathematics
• Fold/unfold transformations for fixpoint logic
• Parallel feedback Turing computability
• scientific article; zbMATH DE number 4187792 (Why is no real title available?)
• A fixed point theory over stratified truth
• The modal mu-calculus alternation hierarchy is strict
• Temporal verification of programs via first-order fixpoint logic
• Computational expressivity of (circular) proofs with fixed points
• The metamathematics of separated determinacy
• Higher-order feedback computation

This page was built for publication: μ-definable sets of integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5287693)