Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2025)

<Previous Article In Volume
Next Article In Volume>

Properties of Some Δ0 Definable Sets on Models of KPU

Authors
Alfonso B. Labao1, *, Shigeki Hagihara2, Henry N. Adorna1
1Department of Computer Science, College of Engineering, University of the Philippines, Diliman, Philippines
2Chitose Institute of Science and Technology, Chitose, Hokkaido, Japan
*Corresponding author. Email: ablabao@up.edu.ph
Corresponding Author
Alfonso B. Labao
Available Online 30 April 2026.
DOI
10.2991/978-94-6239-638-8_5How to use a DOI?
Keywords
logic; computability; recursion theory
Abstract

It is a standard result in recursion theory that sets of natural numbers recognized by Turing Machines can be mapped bijectively to Δ1 sets in  HF (i.e. the hereditarily finite sets). On the other hand, there are other sets in HF , such as the Δ0 sets, whose relationship to concrete computational models may be of interest for further research. Unlike Δ1 sets, Δ0 sets are defined by bounded quantification relative to certain interpretations of a language. In the standard set-theoretic language L that involves only the set membership symbol (ϵ), some sets can be shown to be not Δ0 using a model-theoretic proof. In this paper however, we investigate how membership in these sets can be defined by a Δ0 formula under a new language L+ that incorporates additional function symbols f, g, h and symbols s, t. The paper studies models of KPU (i.e. the Kripke Platek Axioms with Urelements) that have well-defined interpretations of the symbols f, g, h. We present several corollaries that follow from this result along with some generalizations of Δ0 sets. Among the results indicate that well-foundedness of elements of sets defined by Δ0 formulas of L+ is independent of KPU.

Copyright
© 2026 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2025)
Series
Atlantis Highlights in Computer Sciences
Publication Date
30 April 2026
ISBN
978-94-6239-638-8
ISSN
2589-4900
DOI
10.2991/978-94-6239-638-8_5How to use a DOI?
Copyright
© 2026 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Cite this article

risenwbib
TY  - CONF
AU  - Alfonso B. Labao
AU  - Shigeki Hagihara
AU  - Henry N. Adorna
PY  - 2026
DA  - 2026/04/30
TI  - Properties of Some Δ₀ Definable Sets on Models of KPU
BT  - Proceedings of the  Workshop on Computation: Theory and Practice (WCTP 2025)
PB  - Atlantis Press
SP  - 50
EP  - 60
SN  - 2589-4900
UR  - https://doi.org/10.2991/978-94-6239-638-8_5
DO  - 10.2991/978-94-6239-638-8_5
ID  - Labao2026
ER  -