# Approximating Approximate Reasoning: Fuzzy Sets and the Ershov Hierarchy

 Authors Luca San Mauro Università degli Studi di Roma La Sapienza Abstract Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice L. In this paper, we combine the Ershov Hierarchy and fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. In particular, we focus on the fuzzy n-c.e. sets which form the finite levels of this hierarchy. Intuitively, a fuzzy set is n-c.e. if its membership function can be approximated by changing monotonicity at most n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} times. We prove that the Fuzzy Ershov Hierarchy does not collapse; that, in analogy with the classical case, each fuzzy n-c.e. set can be represented as a Boolean combination of fuzzy c.e. sets; but that, contrary to the classical case, the Fuzzy Ershov Hierarchy does not exhaust the class of all Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} fuzzy sets. Keywords No keywords specified (fix it) Categories No categories specified (categorize this paper) Buy the book Find it on Amazon.com DOI 10.1007/978-3-030-88708-7_1 Options Mark as duplicate Export citation Request removal from index

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,214

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)

## References found in this work BETA

No references found.

## Citations of this work BETA

No citations found.

## Similar books and articles

The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
New Trends and Open Problems in Fuzzy Logic and Approximate Reasoning.Didier Dubois & Henri Prade - 1996 - Theoria: Revista de Teoría, Historia y Fundamentos de la Ciencia 11 (3):109-121.
Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
Fuzzy in 3–D: Two Contrasting Paradigms.Sarah Greenfield & Francisco Chiclana - 2015 - Archives for the Philosophy and History of Soft Computing 2015 (2).
Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.
Approximate Similarities and Poincaré Paradox.Giangiacomo Gerla - 2008 - Notre Dame Journal of Formal Logic 49 (2):203-226.

## Analytics

2022-03-10

Total views
1 ( #1,546,110 of 2,507,555 )