This paper highlights some connections between work on truth approximation and work in social epistemology, in particular work on peer disagreement. In some of the literature on truth approximation, questions have been addressed concerning the efficiency of research strategies for approximating the truth. So far, social aspects of research strategies have not received any attention in this context. Recent findings in the field of opinion dynamics suggest that this is a mistake. How scientists exchange and take into account (...) information about each others’ beliefs may greatly influence the accuracy and speed with which the scientific community as a whole approximates the truth. On the other hand, social epistemologists concerned with peer disagreement have so far neglected the question of how practices of responding to disagreements with peers fare with respect to the goal of approximating the truth. Again, work on opinion dynamics shows that this may be a mistake, and that how we ought to respond to disagreements with our peers may depend on the specific purposes of our investigations. (shrink)

Suppose that scientific realists believe that a successful theory is approximately true, and that constructive empiricists believe that it is empirically adequate. Whose belief is more likely to be false? The problem of underdetermination does not yield an answer to this question one way or the other, but the pessimistic induction does. The pessimistic induction, if correct, indicates that successful theories, both past and current, are empirically inadequate. It is arguable, however, that they are approximately true. Therefore, scientific realists overall (...) take less epistemic risk than constructive empiricists. (shrink)

The main question addressed in this paper is whether some false sentences can constitute evidence for the truth of other propositions. In this paper it is argued that there are good reasons to suspect that at least some false propositions can constitute evidence for the truth of certain other contingent propositions. The paper also introduces a novel condition concerning propositions that constitute evidence that explains a ubiquitous evidential practice and it contains a defense of a particular condition concerning the possession (...) of evidence. The core position adopted here then is that false propositions that are approximately true reports of measurements can constitute evidence for the truth of other propositions. So, it will be argued that evidence is only quasi-factive in this very specific sense. (shrink)

We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV₁ + dWPHP(PV).

There is good reason to suppose that our best physical theories, quantum mechanics and special relativity, are false if taken together and literally. If they are in fact false, then how should they count as providing knowledge of the physical world? One might imagine that, while strictly false, our best physical theories are nevertheless in some sense probably approximately true. This paper presents a notion of local probable approximate truth in terms of descriptive nesting relations between current and subsequent theories. (...) This notion helps explain how false physical theories might nevertheless provide physical knowledge of a variety that is particularly salient to diachronic empirical inquiry. (shrink)

A new approach for a uniform classification of the computably approximable real numbers is introduced. This is an important class of reals, consisting of the limits of computable sequences of rationals, and it coincides with the 0'-computable reals. Unlike some of the existing approaches, this applies uniformly to all reals in this class: to each computably approximable real x we assign a degree structure, the structure of all possible ways available to approximate x. So the main criterion for such classification (...) is the variety of the effective ways we have to approximate a real number. We exhibit extreme cases of such approximation structures and prove a number of related results. (shrink)

It is proposed that we use the term “approximation” for inexact description of a target system and “idealization” for another system whose properties also provide an inexact description of the target system. Since systems generated by a limiting process can often have quite unexpected, even inconsistent properties, familiar limit systems used in statistical physics can fail to provide idealizations, but are merely approximations. A dominance argument suggests that the limiting idealizations of statistical physics should be demoted to approximations.

We show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several applications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy to the collapse of the polynomial-time hierarchy.

Traditional theories construe approximate truth or truthlikeness as a measure of closeness to facts, singular facts, and idealization as an act of either assuming zero of otherwise very small differences from facts or imagining ideal conditions under which scientific laws are either approximately true or will be so when the conditions are relaxed. I first explain the serious but not insurmountable difficulties for the theories of approximation, and then argue that more serious and perhaps insurmountable difficulties for the theory (...) of idealization force us to sever its close tie to approximation. This leads to an appreciation of lawlikeness as a measure of closeness to laws, which I argue is the real measure of idealization whose main purpose is to carve nature at its joints. (shrink)

In this article, we offer a detailed study of two important episodes in the early history of high-energy physics, namely the development of the Chew and the Nambu-Jona-Lasinio models. Our study reveals that both models resulted from the combination of an old Hamiltonian, which had been introduced by earlier researchers, and two new approximation methods developed by Chew and by Nambu and Jona-Lasinio. These new approximation methods, furthermore, were the key component behind the models’ success. We take this (...) historical investigation to support two philosophical theses about the manner in which scientific modelling operates in high-energy physics. Both of these theses run counter to a view that is commonly accepted among philosophers of science: the view that all approximations can be embedded within an equivalent idealized system, and that whatever role the former might play in scientific modelling is therefore parasitic on the much more substantial work performed by the latter. Our first thesis, which we call “Distinctness,” states that approximation methods constitute an independent category of theoretical output from idealized systems. We thus believe that approximations and idealized systems constitute two independent types of objects, both of which are essential to the practice of modelling. Our second, more radical thesis is called “Content Determination.” Our claim here is that approximation methods can in fact be essential to assigning determinate physical content to the idealized systems with which they jointly operate. As we show, this is due to the fact that quantum field theory allows for a very thin characterization of idealized systems only, making the use of approximations necessary to supply additional content. We conclude the paper with a few reflections about the manner in which our two theses can be used to articulate David Kaiser’s views on the “vanishing of scientific theory” in physics after WWII. (shrink)

Aspects of a formal theory of approximate generalizations, according to which they have degrees of truth measurable by the proportions of their instances for which they are true, are discussed. The idealizability of laws in theories of fundamental measurement is considered: given that the laws of these theories are only approximately true "in the real world", does it follow that slight changes in the extensions of their predicates would make them exactly true?

This paper describes a theory of accuracy or approximate truth and applies it to problems in the realist interpretation of scientific theories. It argues not only that realism requires approximate truth, but that an adequate theory of approximation also presupposes some elements of a realist interpretation of theories. The paper distinguishes approximate truth from vagueness, probability and verisimilitude, and applies it to problems of confirmation and deduction from inaccurate premises. Basic results are cited, but details appear elsewhere. Objections are (...) surveyed, including arguments by Miller, Laymon, and Laudan. Comparison is made with Niiniluoto's theory of verisimilitude, and the utility of his theory for realism assessed. (shrink)

This paper, which is based on recent empirical research at the University of Leeds, the University of Edinburgh, and the University of Bristol, presents two difficulties which arise when condensed matter physicists interact with molecular biologists: (1) the former use models which appear to be too coarse-grained, approximate and/or idealized to serve a useful scientific purpose to the latter; and (2) the latter have a rather narrower view of what counts as an experiment, particularly when it comes to computer simulations, (...) than the former. It argues that these findings are related; that computer simulations are considered to be undeserving of experimental status, by molecular biologists, precisely because of the idealizations and approximations that they involve. The complexity of biological systems is a key factor. The paper concludes by critically examining whether the new research programme of ‘systems biology’ offers a genuine alternative to the modelling strategies used by physicists. It argues that it does not. (shrink)

This paper, which is based on recent empirical research at the University of Leeds, the University of Edinburgh, and the University of Bristol, presents two difficulties which arise when condensed matter physicists interact with molecular biologists: the former use models which appear to be too coarse-grained, approximate and/or idealized to serve a useful scientific purpose to the latter; and the latter have a rather narrower view of what counts as an experiment, particularly when it comes to computer simulations, than the (...) former. It argues that these findings are related; that computer simulations are considered to be undeserving of experimental status, by molecular biologists, precisely because of the idealizations and approximations that they involve. The complexity of biological systems is a key factor. The paper concludes by critically examining whether the new research programme of ‘systems biology’ offers a genuine alternative to the modelling strategies used by physicists. It argues that it does not. (shrink)

A real number is recursively approximable if there is a computable sequence of rational numbers converging to it. If some extra condition to the convergence is added, then the limit real number might have more effectivity. In this note we summarize some recent attempts to classify the recursively approximable real numbers by the convergence rates of the corresponding computable sequences ofr ational numbers.

In this paper, we investigate the problem of truth approximation via belief merging, i.e., we ask whether, and under what conditions, a group of inquirers merging together their beliefs makes progress toward the truth about the underlying domain. We answer this question by proving some formal results on how belief merging operators perform with respect to the task of truth approximation, construed as increasing verisimilitude or truthlikeness. Our results shed new light on the issue of how rational (dis)agreement (...) affects the inquirers’ quest for truth. In particular, they vindicate the intuition that scientific inquiry, and rational discussion in general, benefits from some heterogeneity in opinion and interaction among different viewpoints. The links between our approach and related analyses of truth tracking, judgment aggregation, and opinion dynamics, are also highlighted. (shrink)

In this paper, a criticism of the traditional theories of approximation and idealization is given as a summary of previous works. After identifying the real purpose and measure of idealization in the practice of science, it is argued that the best way to characterize idealization is not to formulate a logical model – something analogous to Hempel's D-N model for explanation – but to study its different guises in the praxis of science. A case study of it is then (...) made in thermostatistical physics. After a brief sketch of the theories for phase transitions and critical phenomena, I examine the various idealizations that go into the making of models at three difference levels. The intended result is to induce a deeper appreciation of the complexity and fruitfulness of idealization in the praxis of model-building, not to give an abstract theory of it. (shrink)

We revive the idea that a deductive-nomological explanation of a scientific theory by its successor may be defensible, even in those common and troublesome cases where the theories concerned are mutually incompatible; and limiting, approximating and counterfactual assumptions may be required in order to define a logical relation between them. Our solution is based on a general characterization of limiting relations between physical theories using the method of nonstandard analysis.

We investigate the logical and conceptual connections between abductive reasoning construed as a process of belief change, on the one hand, and truth approximation, construed as increasing (estimated) verisimilitude, on the other. We introduce the notion of ‘(verisimilitude-guided) abductive belief change’ and discuss under what conditions abductively changing our theories or beliefs does lead them closer to the truth, and hence tracks truth approximation conceived as the main aim of inquiry. The consequences of our analysis for some recent (...) discussions concerning belief revision aiming at truth approximation and inference to the best explanation are also highlighted. (shrink)

The so-called Preface Paradox seems to show that one can rationally believe two logically incompatible propositions. We address this puzzle, relying on the notions of truthlikeness and approximate truth as studied within the post-Popperian research programme on verisimilitude. In particular, we show that adequately combining probability, approximate truth, and truthlikeness leads to an explanation of how rational belief is possible in the face of the Preface Paradox. We argue that our account is superior to other solutions of the paradox, including (...) a recent one advanced by Hannes Leitgeb (Analysis 74.1). (shrink)

Research on the cognitive abilities involved in decision making has shown that, under objective risk conditions (i.e., when explicit information about possible outcomes and risks is available), superior decisions are especially predicted by executive functions and exact number processing skills, also referred to as objective numeracy. So far, decision-making research has mainly focused on exact number processing skills, such as performing calculations or transformations of symbolic numbers. There is evidence that such exact numeric skills are based on approximate number processing (...) (ANP) skills, which enable quick and accurate processing of non-symbolic numbers (e.g. Chen and Li, 2014). Very few studies, however, have investigated ANP skills in the context of risky decision making and have analyzed direct associations among the aforementioned sub functions. Possible interactions between the closely related skills have not been considered. The current study (N = 128) examines interactions of ANP skills with executive functions and objective numeracy, in predicting risky choice behavior. ANP skills are represented by the accuracy in a dot-comparison task. Decision making is measured by two versions of the Game of Dice Task (GDT), which place different emphases on the reflection of potential risks. The results show two-way as well as three-way interactions between the measures of ANP skills, executive functions, and objective numeracy in predicting risky decisions in both GDT versions. The riskiest decisions were most frequently made in case of low scores in all of the three competencies, while good performance in any one of them resulted in significant reductions of disadvantageous decisions. The findings indicate that high ANP skills can positively affect choice behavior in individuals who have weaknesses in reflectively attributed skills, namely executive functions and objective numeracy. Potential compensatory effects and mechanisms of ANP in decision making are discussed. (shrink)

Causality is the most important topic in the history of western science, and since the beginning of the statistical paradigm, its meaning has been reconceptualized many times. Causality entered into the realm of multi-causal and statistical scenarios some centuries ago. Despite widespread critics, today deep learning and machine learning advances are not weakening causality but are creating a new way of finding correlations between indirect factors. This process makes it possible for us to talk about approximate causality, as well as (...) about a situated causality. (shrink)

Approximation involves representing things in ways that might be close to the truth but are nevertheless false. Given the widespread reliance on approximations in science and everyday life, here we ask whether it is conceptually possible for false approximations to qualify as knowledge. According to the factivity account, it is impossible to know false approximations, because knowledge requires truth. According to the representational adequacy account, it is possible to know false approximations, if they are close enough to the truth (...) for present purposes. In this paper, we adopt an experimental methodology to begin testing these two theories. When an agent provides a false and practically inadequate answer, both theories predict that people will deny knowledge. But the theories disagree about an agent who provides a false but practically adequate answer: the factivity hypothesis again predicts knowledge denial, whereas the representational adequacy hypothesis predicts knowledge attribution. Across two experiments, our principal finding was that people tended to attribute knowledge for false but practically adequate answers, which supports the representational adequacy account. We propose an interpretation of existing findings that preserves a conceptual link between knowledge and truth. According to this proposal, truth is not necessary for knowledge, but it is a feature of prototypical knowledge. (shrink)

Inspired by the recent work on approximations of classical logic, we present a method that approximates several modal logics in a modular way. Our starting point is the limitation of the n-degree of introspection that is allowed, thus generating modaln-logics. The semantics for n-logics is presented, in which formulas are evaluated with respect to paths, and not possible worlds. A tableau-based proof system is presented, n-SST, and soundness and completeness is shown for the approximation of modal logics image and (...) image. (shrink)

The problem of approximating a propositional calculus is to find many-valued logics which are sound for the calculus (i.e., all theorems of the calculus are tautologies) with as few tautologies as possible. This has potential applications for representing (computationally complex) logics used in AI by (computationally easy) many-valued logics. It is investigated how far this method can be carried using (1) one or (2) an infinite sequence of many-valued logics. It is shown that the optimal candidate matrices for (1) can (...) be computed from the calculus. (shrink)

Arguably, there is no substantial, general answer to the question of what makes for the approximate truth of theories. But in one class of cases, the issue seems simply resolved. A wide class of applied dynamical theories can be treated as two-component theories—one component specifying a certain kind of abstract geometrical structure, the other giving empirical application to this structure by claiming that it replicates, subject to arbitrary scaling for units etc., the geometric structure to be found in some real-world (...) dynamical phenomenon. In such a case, a theory is approximately true just if the one geometric structure approximately replicates the other (and if problems remain here, they are problems in geometry, of specifying suitable metric approximation relations, not conceptual problems). This article amplifies and defends this simple approach to approximate truth for dynamical theories. (shrink)

We give a formalism for approximate isomorphism in continuous logic simultaneously generalizing those of two papers by Ben Yaacov [2] and by Ben Yaacov, Doucha, Nies, and Tsankov [6], which are largely incompatible. With this we explicitly exhibit Scott sentences for the perturbation systems of the former paper, such as the Banach‐Mazur distance and the Lipschitz distance between metric spaces. Our formalism is simultaneously characterized syntactically by a mild generalization of perturbation systems and semantically by certain elementary classes of two‐sorted (...) structures that witness approximate isomorphism. As an application, we show that the theory of any ‐tree or ultrametric space of finite radius is stable, improving a result of Carlisle and Henson [8]. (shrink)

When addressing cultural and religious differences in the clinical setting we need to be realists. Despite our public homage to pluralism and good intentions, it is just not possible to overcome all the differences that might exist and achieve perfect understanding of others. Try as we may, we will never be able to see perfectly the world through another's eyes. Instead of reaching for such perfection, we should instead reach for an approximation of shared understanding that will promote discourse (...) and civility when peoples of different races, genders, cultures, religions, and sexual preferences interact in the clinic. (shrink)

The standard theory for belief revision provides an elegant and powerful framework for reasoning about how a rational agent should change its beliefs when confronted with new information. However, the agents considered are extremely idealized. Some recent models attempt to tackle the problem of plausible belief revision by adding structure to the belief bases and using nonstandard inference operations. One of the key ideas is that not all of an agent's beliefs are relevant for an operation of belief change.In this (...) paper we incorporate the insights pertaining to local change and relevance sensitivity with the use of approximate inference relations. These approximate inference relations offer us partial solutions at any stage of the revision process. The quality of the approximations improves as we allow for more and more resources to be used. We are provided with upper and lower bounds to what would be obtained with the use of classical inference. (shrink)

What role does our knowledge about the ideal society play in guiding policymaking in the real world? One intuitive answer is to approximate. Namely, we have a duty to approximate the ideal within the relevant constraints of feasibility. However, political philosophers seem to have what might be called ‘approximatophobia'. Many philosophers, including idealists such as David Estlund, warn against approximation. Their criticism is chiefly motivated by ‘the problem of second best’, which points out that your second-best option may not (...) be closest to your best option. This paper aims to dispel ‘approximatophobia'. The difficulty posed by the problem of second best is often overstated. More positively, I present a novel defence of approximation, arguing that approximation of an ideal can be a reasonably reliable default strategy of action guidance in the real world. Difficulties that may afflict the project of approximation can be mitigated by sophistication of the project of approximation. After showing that critics of approximation overstep their mark in issuing the strong or moderate warning against approximation, I propose an account of sophisticated approximation. It seeks a series of reforms that make existing social institutions closer to the ideal based on careful selection of frame of analysis. Three virtuous correlations are identified as indicators for successful project of approximation, linking descriptive similarity to desirability, feasibility and knowledge of the ideal. I also explain a two-staged strategy of sophisticating the way you approximate the ideal, with an expected positive feedback effect. (shrink)

This paper focuses on the interpretation of the Italian approximative adverb quasi 'almost' by primarily looking at cases in which it modifies temporal connectives, a domain which, to our knowledge, has been largely unexplored thus far. Consideration of this domain supports the need for a scalar account of the semantics of quasi (close in spirit to Hitzeman's semantic analysis of almost, in: Canakis et al. (eds) Papers from the 28th regional meeting of the Chicago Linguistic Society, 1992). When paired with (...) suitable analyses of temporal connectives, such an account can provide a simple explanation of the patterns of implication that are observed when quasi modifies locational (e. g. quando 'when'), directional (e. g. fino 'until' and da 'since'), and event-sequencing temporal connectives (e. g. prima 'before' and dopo ' after'). A challenging empirical phenomenon that is observed is a contrast between the modification of fino and da by quasi, on the one hand, and the modification of prima and dopo by the same adverb, on the other. While quasi fino and quasi da behave symmetrically, a puzzling asymmetry is observed between quasi prima and quasi dopo. To explain the asymmetry, we propose an analysis of prima and dopo on which the former has the meaning of the temporal comparative più presto 'earlier', while the latter is seen as an atomic predicate denoting temporal succession between events (Del Prete, Nat Lang Semantics 16: 157-203, 2008). We show that the same pattern of implication observed for quasi prima is attested when quasi modifies overt comparatives, and propose a pragmatic analysis of this pattern that uniformly applies to both cases, thus providing new evidence for the claim that prima is underlyingly a comparative. A major point of this paper is a discussion of the notion of scale which is relevant for the semantics of quasi', in particular, we show that the notion of Horn (entailment-based) scale is not well-suited for handling modification of temporal connectives, and that a more general notion of scale is required in order to provide a uniform analysis of quasi as a cross-categorial modifier. (shrink)

The technical results presented here on continuity and approximate implication are obviously incomplete. In particular, a syntactic characterization of approximate implication is highly desirable. Nevertheless, I believe the results above do show that the theory has considerable promise for application to the areas mentioned at the top of the paper.Formulation and defense of realist interpretations of science, for example, require approximate truth because we hardly ever have evidence that a particular scientific theory corresponds perfectly with a portion of the real (...) world. Realists need to assert, then, that evidence for a theory is evidence for its approximate truth, not its truth (see [3] and [18]). Approximate truth is, however, a vague notion, and specification of quantity terms and of a sense of approximation are needed to make precise applications of it. Suitability of both vocabulary and sense of approximation depend on the subject matter, and their selection is a partly empirical matter that raises complex issues. In light of the number of common inferences which are not continuous, realists also need to be concerned about indiscriminate use of deductive logic to derive consequences from approximately true theories. These issues will be considered further in a future paper.Approximate truth also has potential application in areas of artificial intelligence that require inference from inaccurate data. In the ‘qualitative’ physical theories of de Kleer and Brown [6], for example, ‘qualitative’ values are derived by partitioning the real numbers into regions. Inferences leading from inside to outside a region must be identified and avoided, and approximate implication and continuity may prove useful in doing this. More generally, growing use of predicate logic as a programming language invites application of the theory of approximate truth as a symbolic substitute for numerical evaluation of computation errors. This too will be the subject of a future paper. (shrink)

We call an $\alpha \in \mathbb {R}$ regainingly approximable if there exists a computable nondecreasing sequence $(a_n)_n$ of rational numbers converging to $\alpha $ with $\alpha - a_n n}$ for infinitely many n. Similarly, there exist regainingly approximable sets whose initial segment complexity infinitely often reaches the maximum possible for c.e. sets. Finally, there is a uniform algorithm splitting regular real numbers into two regainingly approximable numbers that are still regular.

Is calculation possible without language? Or is the human ability for arithmetic dependent on the language faculty? To clarify the relation between language and arithmetic, we studied numerical cognition in speakers of Mundurukú, an Amazonian language with a very small lexicon of number words. Although the Mundurukú lack words for numbers beyond 5, they are able to compare and add large approximate numbers that are far beyond their naming range. However, they fail in exact arithmetic with numbers larger than 4 (...) or 5. Our results imply a distinction between a nonverbal system of number approximation and a language-based counting system for exact number and arithmetic. (shrink)

Approximate coherentism suggests that imperfectly rational agents should hold approximately coherent credences. This norm is intended as a generalization of ordinary coherence. I argue that it may be unable to play this role by considering its application under learning experiences. While it is unclear how imperfect agents should revise their beliefs, I suggest a plausible route is through Bayesian updating. However, Bayesian updating can take an incoherent agent from relatively more coherent credences to relatively less coherent credences, depending on the (...) data observed. Thus, comparative rationality judgments among incoherent agents are unduly sensitive to luck. (shrink)

In many areas of scientific inquiry, the phenomena under investigation are viewed as functions on the real numbers. Since observational precision is limited, it makes sense to view these phenomena as bounded functions on the rationals. One may translate the basic notions of recursion theory into this framework by first interpreting a partial recursive function as a function on Q. The standard notions of inductive inference carry over as well, with no change in the theory. When considering the class of (...) computable functions on Q, there are a number of natural ways in which to define the distance between two functions. We utilize standard metrics to explore notions of approximate inference — our inference machines will attempt to guess values which converge to the correct answer in these metrics. We show that the new inference notions, NV∞, EX∞, and BC∞, infer more classes of functions than their standard counterparts, NV, EX, and BC. Furthermore, we give precise inclusions between the new inference notions and those in the standard inference hierarchy. We also explore weaker notions of approximate inference, leading to inference hierarchies analogous to the EXn and BCn hierarchies. Oracle inductive inference is also considered, and we give sufficient conditions under which approximate inference from a generic oracle G is equivalent to approximate inference with only finitely many queries to G. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We give a purely computational (...) characterization of this class and show that, relative to an oracle, it does not contain the problem CPLS, a strengthening of PLS. As CPLS is provably total in the theory [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program of separating the levels of the bounded arithmetic hierarchy by low-complexity sentences. Our main technical tool is an extension of the “fixing lemma” from [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], a form of switching lemma, which we use to show that a random partial oracle from a certain distribution will, with high probability, determine an entire computation of a [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic. (shrink)

In this paper we give an axiom system of a logic which we call an approximation logic (AL), whose Lindenbaum-Tarski algebra is a strong Bunge algebra (or simply s-Bunge algebra), and show thatFor every s-Bunge algebra , a quotient algebra by a maximal filter is isomorphic to the simplest nontrivial s-Bunge algebra ;The Lindenbaum algebra of AL is an s-Bunge algebra;AL is complete;AL is decidable.

We investigate extensions of S. Solecki's theorem on closing off finite partial isometries of metric spaces [11] and obtain the following exact equivalence: any action of a discrete group Γ by isometries of a metric space is finitely approximable if and only if any product of finitely generated subgroups of Γ is closed in the profinite topology on Γ.

Scientific models describe natural phenomena at different levels of abstraction. Abstract descriptions can provide the basis for interventions on the system and explanation of observed phenomena at a level of granularity that is coarser than the most fundamental account of the system. Beckers and Halpern (2019), building on work of Rubenstein et al. (2017), developed an account of abstraction for causal models that is exact. Here we extend this account to the more realistic case where an abstract causal model offers (...) only an approximation of the underlying system. We show how the resulting account handles the discrepancy that can arise between low- and high-level causal models of the same system, and in the process provide an account of how one causal model approximates another, a topic of independent interest. Finally, we extend the account of approximate abstractions to probabilistic causal models, indicating how and where uncertainty can enter into an approximate abstraction. (shrink)

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. (shrink)