Let X be an infinite internal set in an ω1-saturated nonstandard universe. Then for any coloring of [X] k , such that the equivalence E of having the same color is countably determined and there is no infinite internal subset of [X] k with all its elements of different colors (i.e., E is condensating on X), there exists an infinite internal set Z⊆X such that all the sets in [Z] k have the same color. This Ramsey-type result is (...) obtained as a consequence of a more general one, asserting the existence of infinite internal Q-homogeneous sets for certain Q ⊆ [[X] k ] m , with arbitrary standard k≥ 1, m≥ 2. In the course of the proof certain minimal condensating countably determined sets will be described. (shrink)

Answers are given to two questions concerning the existence of some sparse subsets of $\mathscr{H} = \{0, 1,..., H - 1\} \subseteq * \mathbb{N}$ , where H is a hyperfinite integer. In § 1, we answer a question of Kanovei by showing that for a given cut U in H, there exists a countably determined set $X \subseteq \mathscr{H}$ which contains exactly one element in each U-monad, if and only if U = a · N for some $a (...) \in \mathscr{H} \backslash \{0\}$ . In §2, we deal with a question of Keisler and Leth in [6]. We show that there is a cut $V \subseteq \mathscr{H}$ such that for any cut U, (i) there exists a U-discrete set $X \subseteq \mathscr{H}$ with X + X = H (mod H) provided $U \subsetneqq V$ , (ii) there does not exist any U-discrete set $X \subseteq \mathscr{H}$ with X + X = H (mod H) provided $\supsetneqq V$ . We obtain some partial results for the case U = V. (shrink)

We prove that every countably determined set C is U-meager if and only if every internal subset A of C is U-meager, provided that the cofinality and coinitiality of the cut U are both uncountable. As a consequence we prove that for such cuts a countably determined set C which intersects every U-monad in at most countably many points is U-meager. That complements a similar result in [KL]. We also give some partial solutions to some (...) open problems from [KL]. We prove that the set K = {1,...,H}, where H is an infinite integer, cannot be expressed as a countable union of countably determined sets each of which is U-meager for some cut U with min{cf (U), ci (U)} ≥ ω1. Also, every Borel, Σ1 m or countably determined set C which is U-meager for every cut U is a countable union of Borel, Σ1 m or countably determined sets respectively, which are U-nowhere dense for every cut U. Further, the class of Borel U-meager sets for min{cf(U), ci(U)} ≥ ω1 coincides with the least family of sets containing internal U-meager sets and closed with respect to the operation of countable union and intersection. The same is true if the phrase "U-meager sets" is replaced by "U-meager for every cut U.". (shrink)

Adjoin, to a countable standard model M of Zermelo-Fraenkel set theory (ZF), a countable set A of independent Cohen generic reals. If one attempts to construct the model generated over M by these reals (not necessarily containing A as an element) as the intersection of all standard models that include M ∪ A, the resulting model fails to satisfy the power set axiom, although it does satisfy all the other ZF axioms. Thus, there is no smallest ZF model including M (...) ∪ A, but there are minimal such models. These are classified by their sets of reals, and there is one minimal model whose set of reals is the smallest possible. We give several characterizations of this model, we determine which weak axioms of choice it satisfies, and we show that some better known models are forcing extensions of it. (shrink)

The paper introduces the notion of size of countable sets, which preserves the Part-Whole Principle. The sizes of the natural and the rational numbers, their subsets, unions, and Cartesian products are algorithmically enumerable as sequences of natural numbers. The method is similar to that of Numerosity Theory, but in comparison it is motivated by Bolzano’s concept of infinite series, it is constructive because it does not use ultrafilters, and set sizes are uniquely determined. The results mostly agree, but some (...) differ, such as the size of rational numbers. However, set sizes are only partially, not linearly, ordered. Quid pro quo. (shrink)

We introduce a novel set-intersection operator called ‘most-intersection’ based on the logical quantifier ‘most’, via natural density of countable sets, to be used in determining the majority chara...

The separation, uniformization, and other properties of the Borel and projective hierarchies over hyperfinite sets are investigated and compared to the corresponding properties in classical descriptive set theory. The techniques used in this investigation also provide some results about countably determined sets and functions, as well as an improvement of an earlier theorem of Kunen and Miller.

The idea of this paper is to explore the existence of canonical countably saturated models for different classes of structures. It is well-known that, under CH, there exists a unique countably saturated linear order of cardinality \. We provide some examples of pairwise non-isomorphic countably saturated linear orders of cardinality \, under different set-theoretic assumptions. We give a new proof of the old theorem of Harzheim, that the class of countably saturated linear orders has a uniquely (...) determined one-element basis. From our proof it follows that this minimal linear order is a Fraïssé limit of certain Fraïssé class. In particular, it is homogeneous with respect to countable subsets. Next we prove the existence and uniqueness of the uncountable version of the random graph. This graph is isomorphic to \,\in \cup \ni )\), where \\) is the set of hereditarily countable sets, and two sets are connected if one of them is an element of the other. In the last section, an example of a prime countably saturated Boolean algebra is presented. (shrink)

An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R (...) of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language. (shrink)

Gelfond and Lifschitz proposed the notion of a stable model of a logic program. We establish that the set of all stable models in a Herbrand universe of a recursive logic program is, up to recursive renaming, the set of all infinite paths of a recursive, countably branching tree, and conversely. As a consequence, the problem, given a recursive logic program, of determining whether it has at least one stable model, is Σ11-complete. Due to the equivalences established in the (...) authors' previous nonmonotone rule systems papers ), this applies equally to truth maintenance systems and default logics. (shrink)

In this paper we prove under some set theoretical assumptions that if T is a countable unstable theory then there is a pair of models of T such that Ehrenfeucht-Fraïssé games between these models of large variety of lengths are non-determined.

We give positive answers to two open questions from [15]. (1) For every set C countably determined over A, if C is Π 0 α (Σ 0 α ) then it must be Π 0 α (Σ 0 α ) over A, and (2) every Borel subset of the product of two internal sets X and Y all of whose vertical sections are Π 0 α (Σ 0 α ) can be represented as an intersection (union) of Borel (...) sets with vertical sections of lower Borel rank. We in fact show that (2) is a consequence of the analogous result in the case when X is a measurable space and Y a complete separable metric space (Polish space) which was proved by A. Louveau and that (1) is equivalent to the property shared by the inverse standard part map in Polish spaces of preserving almost all levels of the Borel hierarchy. (shrink)

Takeuti introduced an infinitary proof system for determinate logic and showed that for transitive models of Zermelo-Fraenkel set theory with the Axiom of Dependent Choice that contain all reals, the cut-elimination theorem is equivalent to the Axiom of Determinacy, and in particular contradicts the Axiom of Choice. We consider variants of Takeuti's theorem without assuming the failure of the Axiom of Choice. For instance, we show that if one removes atomic formulae of infinite arity from the language of Takeuti's proof (...) system, then cut elimination is equivalent to a determinacy hypothesis provable, e.g., in ZFC + “there are infinitely many Woodin cardinals.” A slight extension of the proof system admits cut elimination for countable sequents under the same assumptions. A simple modification of the proof system yields analogs of the results above for the Axiom of Real Determinacy and uncountably many Woodin cardinals. (shrink)

The model theoretic `back and forth' construction of isomorphisms and automorphisms is based on the proof by Cantor that the theory of dense linear orderings without endpoints is ℵ 0 -categorical. However, Cantor's method is slightly different and for many other structures it yields an injection which is not surjective. The purpose here is to examine Cantor's method (here called `going forth') and to determine when it works and when it fails. Partial answers to this question are found, extending those (...) earlier given by Cameron. We also give fuller characterisations of when forth suffices for model theoretic classes such as structures containing Jordan sets for the automorphism group, and ℵ 0 -categorical ω-stable structures. The work is based on the author's Ph.D. thesis. (shrink)

Let M be a structure for a language L on a set M of urelements. HYP(M) is the least admissible set above M. In § 1 we show that pp(HYP(M)) [ = the collection of pure sets in HYP(M] is determined in a simple way by the ordinal α = ⚬(HYP(M)) and the $\mathscr{L}_{\propto\omega}$ theory of M up to quantifier rank α. In § 2 we consider the question of which pure countable admissible sets are of the form pp(HYP(M)) (...) for some M and show that all sets L α (α admissible) are of this form. Other positive and negative results on this question are obtained. (shrink)

The centerpiece of Jeffrey Bub's book Interpreting the Quantum World is a theorem (Bub and Clifton 1996) which correlates each member of a large class of no-collapse interpretations with some 'privileged observable'. In particular, the Bub-Clifton theorem determines the unique maximal sublattice L(R,e) of propositions such that (a) elements of L(R,e) can be simultaneously determinate in state e, (b) L(R,e) contains the spectral projections of the privileged observable R, and (c) L(R,e) is picked out by R and e alone. In (...) this paper, we explore the issue of maximal determinate sets of observables using the tools provided by the algebraic approach to quantum theory; and we call the resulting algebras of determinate observables, "maximal *beable* subalgebras". The capstone of our exploration is a generalized version of Bub and Clifton's theorem that applies to arbitrary (i.e., both mixed and pure) quantum states, to Hilbert spaces of arbitrary (i.e., both finite and infinite) dimension, and to arbitrary observables (including those with a continuous spectrum). Moreover, in the special case covered by the original Bub-Clifton theorem, our theorem reproduces their result under strictly weaker assumptions. This added level of generality permits us to treat several topics that were beyond the reach of the original Bub-Clifton result. In particular: (a) We show explicitly that a (non-dynamical) version of the Bohm theory can be obtained by granting privileged status to the position observable. (b) We show that Clifton's (1995) characterization of the Kochen-Dieks modal interpretation is a corollary of our theorem in the special case when the density operator is taken as the privileged observable. (c) We show that the 'uniqueness' demonstrated by Bub and Clifton is only guaranteed in certain special cases -- viz., when the quantum state is pure, or if the privileged observable is compatible with the density operator. We also use our results to articulate a solid mathematical foundation for certain tenets of the orthodox Copenhagen interpretation of quantum theory. For example, the uncertainty principle asserts that there are strict limits on the precision with which we can know, simultaneously, the position and momentum of a quantum-mechanical particle. However, the Copenhagen interpretation of this fact is not simply that a precision momentum measurement necessarily and uncontrollably disturbs the value of position, and vice-versa; but that position and momentum can never in reality be thought of as simultaneously determinate. We provide warrant for this stronger 'indeterminacy principle' by showing that there is no quantum state that assigns a sharp value to both position and momentum; and, a fortiori, that it is mathematically impossible to construct a beable algebra that contains both the position observable and the momentum observable. We also prove a generalized version of the Bub-Clifton theorem that applies to "singular" states (i.e., states that arise from non-countably-additive probability measures, such as Dirac delta functions). This result allows us to provide a mathematically rigorous reconstruction of Bohr's response to the original EPR argument -- which makes use of a singular state. In particular, we show that if the position of the first particle is privileged (e.g., as Bohr would do in a position measuring context), the position of the second particle acquires a definite value by virtue of lying in the corresponding maximal beable subalgebra. But then (by the indeterminacy principle) the momentum of the second particle is not a beable; and EPR's argument for the simultaneous reality of both position and momentum is undercut. (shrink)

Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect to bounded complexity (...) types in the Scott set. For example, if ? is a nonstandard model of PA, then ? represents the Scott set ? = n∈ω | ?⊧“the nth prime divides a” | a∈?.The notion of forcing yields two main results. The first characterizes the sets of natural numbers computable in all models of a given theory representing a given Scott set. We show that the characteristic function of such a set must be enumeration reducible to a complete existential type which is consistent with the given theory and is an element of the given Scott set.The second provides a sufficient condition for the existence of a structure ? such that ? represents a countable jump ideal and ? does not compute an enumeration of a given family of sets ?. This second result is of particular interest when the family of sets which cannot be enumerated is ? = Rep[Th(?)]. Under this additional assumption, the second result generalizes a result on TA [6] and on certain other completions of PA [10]. For example, we show that there also exist models of completions of ZF from which one cannot enumerate the family of sets represented by the theory. (shrink)

We continue the investigations initiated in the recent papers where Bayes logics have been introduced to study the general laws of Bayesian belief revision. In Bayesian belief revision a Bayesian agent revises his prior belief by conditionalizing the prior on some evidence using the Bayes rule. In this paper we take the more general Jeffrey formula as a conditioning device and study the corresponding modal logics that we call Jeffrey logics, focusing mainly on the countable case. The containment relations among (...) these modal logics are determined and it is shown that the logic of Bayes and Jeffrey updating are very close. It is shown that the modal logic of belief revision determined by probabilities on a finite or countably infinite set of elementary propositions is not finitely axiomatizable. The significance of this result is that it clearly indicates that axiomatic approaches to belief revision might be severely limited. (shrink)

It is true in the Cohen, Solovay-random, dominaning, and Sacks generic extension, that every countable ordinal-definable set of reals belongs to the ground universe. It is true in the Solovay collapse model that every non-empty OD countable set of sets of reals consists of \ elements.

Let κ R be the least ordinal κ such that L κ (R) is admissible. Let $A = \{x \in \mathbb{R} \mid (\exists\alpha such that x is ordinal definable in L α (R)}. It is well known that (assuming determinacy) A is the largest countable inductive set of reals. Let T be the theory: ZFC - Replacement + "There exists ω Woodin cardinals which are cofinal in the ordinals." T has consistency strength weaker than that of the theory ZFC + (...) "There exists ω Woodin cardinals", but stronger than that of the theory ZFC + "There exists n Woodin Cardinals", for each n ∈ ω. Let M be the canonical, minimal inner model for the theory T. In this paper we show that A = R ∩ M. Since M is a mouse, we say that A is a mouse set. As an application, we use our characterization of A to give an inner-model-theoretic proof of a theorem of Martin which states that for all n, every Σ * n real is in A. (shrink)

We determine the consistency strength of determinacy for projective games of length ω^2. Our main theorem is that $\Pi _{n + 1}^1$-determinacy for games of length ω^2 implies the existence of a model of set theory with ω + n Woodin cardinals. In a first step, we show that this hypothesis implies that there is a countable set of reals A such that M_n(A), the canonical inner model for n Woodin cardinals constructed over A, satisfies $A = R$ and the (...) Axiom of Determinacy. Then we argue how to obtain a model with ω + n Woodin cardinal from this. We also show how the proof can be adapted to investigate the consistency strength of determinacy for games of length ω^2 with payoff in $R^R\Pi _1^1$ or with σ-projective payoff. (shrink)

If there is a homeomorphic embedding of one set into another, the sets are said to be topologically comparable. Friedman and Hirst have shown that the topological comparability of countable closed subsets of the reals is equivalent to the subsystem of second order arithmetic denoted byATR 0. Here, this result is extended to countable closed locally compact subsets of arbitrary complete separable metric spaces. The extension uses an analogue of the one point compactification of ℝ.

In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.After giving the necessary preliminaries, we first study the uniform computational strength of the Cantor–Bendixson theorem in (...) the Weihrauch lattice. This work falls into the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. We concentrate on problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. As far as we know, this is the first systematic study of problems at the level of $\mathbf {\Pi }^1_1\mathsf {-CA}_0$ in the Weihrauch lattice. We show that the strength of some of the problems we study depends on the topological properties of the Polish space under consideration, while others have the same strength once the space is rich enough.We continue considering problems related to (induced) subgraphs. We provide results on the (effective) Wadge complexity of sets of graphs, that are also used to determine the Weihrauch degree of certain decision problems. The decision problems we consider are defined for a fixed graph G, and they take as input a graph H, answering whether G is an (induced) subgraph of H: we also consider the opposite problem (i.e., answering whether H is an induced subgraph of G). We conclude this part on (induced) subgraphs considering the Weihrauch degree of “search problems.”These problems are defined for a fixed graph G, and they take as input a graph H such that G is an (induced) subgraph H: the output is a copy of G in H. In both cases, we highlight differences and analogies between the subgraph and the induced subgraph relation.We then move our attention to algorithmic learning theory, and we present the framework we use to study the learnability of families of algebraic structures: here, given a countable family of pairwise nonisomorphic structures $\mathfrak {K}$, a learner receives larger and larger pieces of an arbitrary copy of a structure in $\mathfrak {K}$ and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. We say that $\mathfrak {K}$ is learnable if there exists a learner which eventually stabilizes to a correct guess. The framework was lacking a method for comparing the complexity of nonlearnable families, and so we propose a solution to this problem using tools coming from invariant descriptive set theory. To do so, we first prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation $E_0$ of eventual agreement on infinite binary sequences and then, replacing $E_0$ with Borel equivalence relations of higher complexity, we obtain a new hierarchy of learning problems. This leads to the notion of E-learnability, where a family of structures $\mathfrak {K}$ is E-learnable, for a Borel equivalence relation E, if there is a continuous reduction from the isomorphism relation associated with $\mathfrak {K}$ to E. It is then natural to ask how the notion of E-learnability interacts with “classical” learning paradigms.Finally, we study the number of mind changes that a learner needs to learn a given family, both from a topological and a combinatorial point of view, and we consider how the complexity of a learner (in terms of Turing reducibility) affects the number of mind changes for learning a given family.Abstract prepared by Vittorio Cipriani.E-mail: [email protected]: https://air.uniud.it/handle/11390/1252226. (shrink)

In a recent article, I have explored the historical, mathematical, and philosophical issues related to the new theory of numerosities. The theory of numerosities provides a context in which to assign numerosities to infinite sets of natural numbers in such a way as to preserve the part-whole principle, namely if a set A is properly included in B then the numerosity of A is strictly less than the numerosity of B. Numerosities assignments differ from the standard assignment of size provided (...) by Cantor’s cardinality assignments. In this talk, I generalize some specific worries emerging from the theory of numerosities to a line of thought resulting in what I call a ‘good company’ objection to Hume’s Principle (HP). The talk has four main parts. The first takes a historical look at 19th-century attributions of equality of numbers in terms of one-one correlations and argues that there was no agreement as to how to extend such determinations to infinite sets of objects. This leads to the second part where I show that there are countably infinite many abstraction principles that are ‘good’, in the sense that they share the same virtues of HP and from which we can derive the axioms of second order arithmetic. The third part connects this material to a debate on Finite Hume Principle between Heck and MacBride and states the ‘good company’ objection. Finally, the last part gives a tentative taxonomy of possible neo-logicist responses to the ‘good company’ objection and makes a foray into the relevance of this material for the issue of cross-sortal identifications for abstractions. (shrink)

In standard probability theory, probability zero is not the same as impossibility. But many have suggested that only impossible events should have probability zero. This can be arranged if we allow infinitesimal probabilities, but infinitesimals do not solve all of the problems. We will see that regular probabilities are not invariant over rigid transformations, even for simple, bounded, countable, constructive, and disjoint sets. Hence, regular chances cannot be determined by space-time invariant physical laws, and regular credences cannot satisfy seemingly (...) reasonable symmetry principles. Moreover, the examples here are immune to the objections against Williamson’s infinite coin flips. (shrink)

Observables on hypergraphs are described by event-valued measures. We first distinguish between finitely additive observables and countably additive ones. We then study the spectrum, compatibility, and functions of observables. Next a relationship between observables and certain functionals on the set of measures M(H) of a hypergraph H is established. We characterize hypergraphs for which every linear functional on M(H) is determined by an observable. We define the concept of an “effect” and show that observables are related to effect-valued (...) measures. Finally, we define “operational” transformations from M(H) to itself and show that they can be described as a certain combination of effects. (shrink)

It is well known that, in a topological space, the open sets can be characterized using ?lter convergence. In ZF , we cannot replace filters by ultrafilters. It is proven that the ultra?lter convergence determines the open sets for every topological space if and only if the Ultrafilter Theorem holds. More, we can also prove that the Ultra?lter Theorem is equivalent to the fact that uX = kX for every topological space X, where k is the usual Kuratowski closure operator (...) and u is the Ultra?lter Closure with uX := {x ∈ X: [U converges to x and A ∈ U ]}. However, it is possible to built a topological space X for which uX ≠ kX, but the open sets are characterized by the ultra?lter convergence. To do so, it is proved that if every set has a free ultra?lter, then the Axiom of Countable Choice holds for families of non-empty finite sets. It is also investigated under which set theoretic conditions the equality u = k is true in some subclasses of topological spaces, such as metric spaces, second countable T0-spaces or {ℝ}. (shrink)

Semantic justifications of the classical rules of logical inference typically make use of a notion of bivalent truth, understood as a property guaranteed to attach to a sentence or its negation regardless of the prospects for speakers to determine it as so doing. For want of a convincing alternative account of classical logic, some philosophers suspicious of such recognition-transcending bivalence have seen no choice but to declare classical deduction unwarranted and settle for a weaker system; intuitionistic logic in particular, buttressed (...) by assertion-conditional semantics, is often considered to enjoy a degree of meaning-theoretical respectability unattainable by classical logic.The decision to forgo the classical inference rules is not always made lightly. Thus, Dummett: " In the resolution of the conflict between [the view that generally accepted classical modes of inference ought to be theoretically accommodated, and the demand that any such accommodation be achieved without recourse to bivalence] lies, as I see it, one of the most fundamental and intractable problems in the theory of meaning; indeed, in all philosophy. "The present article ventures to suggest that the conflict need not be irresoluble. Helping ourselves only to such conceptual resources as are standardly invoked by proponents of intuitionistic logic, we shall formulate a rudimentary meaning theory for a selection of logical constants, define a relation of valid inferability, and prove that the latter includes all of classical first-order logic. The result is essentially that reported in Sandqvist as Theorem 2.20.2. TheoryWe will be considering a standard-syntax first-order language with ⊃, ⊥ and ∀ as its only primitive logical constants. We assume countable supplies of individual constants, individual functors , and predicates , as well as a denumerably infinite set of individual variables. By a basic 1 formula we will mean one that …[Full Text of this Article]. (shrink)

The post-modern, post-enlightenment debate on the nature of being begins with Heidegger’s assertion that the “ancient interpretation of the being of beings” is informed by “the determination of the sense of being as ... ‘presence.’”[i] This understanding, which reduces being to temporal presence, is supposed to have set all subsequent philosophical reflection. At its origin is “Aristotle’s essay on time.” In Heidegger’s reading, Aristotle interprets entities with regard to the present, equating their being with temporal presence. He also takes time (...) itself as a present entity--i.e., “as just one being among others.”[ii] In an interpretation that is essentially “oriented to the world,” Aristotle thus collapses being and temporal presence to the point that the countable nows are, in their presence, taken as entities. Aristotle’s essay, Heidegger claims, “has essentially determined every subsequent account of time--Bergson’s included.” Even “the Kantian interpretation of time” remains under its sway.[iii] Given this, the “destruction” of the tradition that Heidegger proposes[iv] is a destruction of this account.[v] Only through such a destruction can we uncover what the Aristotelian account conceals. In making time objective, it hides Dasein’s (or human being’s) role in temporalization. The project of Being and Time is to uncover this through “the repeated interpretation of the structures of Dasein ... as modes of temporalization.”[vi]. (shrink)

Given an abstract logic L = L(Q i ) i ∈ I generated by a set of quantifiers Q i , one can construct for each type τ a topological space S τ exactly as one constructs the Stone space for τ in first-order logic. Letting T be an arbitrary directed set of types, the set $S_T = \{(S_\tau, \pi^\tau_\sigma)\mid\sigma, \tau \in T, \sigma \subset \tau\}$ is an inverse topological system whose bonding mappings π τ σ are naturally determined (...) by the reduct operation on structures. We relate the compactness of L to the topological properties of S T . For example, if I is countable then L is compact iff for every τ each clopen subset of S τ is of finite type and S τ is homeomorphic to $\underset{lim}S_T$ , where T is the set of finite subtypes of τ. We finally apply our results to concrete logics. (shrink)

It is folklore that if a continuous function on a complete metric space has approximate roots and in a uniform manner at most one root, then it actually has a root, which of course is uniquely determined. Also in Bishop's constructive mathematics with countable choice, the general setting of the present note, there is a simple method to validate this heuristic principle. The unique solution even becomes a continuous function in the parameters by a mild modification of the uniqueness (...) hypothesis. Moreover, Brouwer's fan theorem for decidable bars turns out to be equivalent to the statement that, for uniformly continuous functions on a compact metric space, the crucial uniform “at most one” condition follows from its non-uniform counterpart. This classification in the spirit of the constructive reverse mathematics, as propagated by Ishihara and others, sharpens an earlier result obtained jointly with Berger and Bridges. (shrink)

In this paper we shall answer some questions in the set theory of L, the universe of all sets constructible from the reals. In order to do so, we shall assume ADL, the hypothesis that all 2-person games of perfect information on ω whose payoff set is in L are determined. This is by now standard practice. ZFC itself decides few questions in the set theory of L, and for reasons we cannot discuss here, ZFC + ADL yields the (...) most interesting “completion” of the ZFC-theory of L.ADL implies that L satisfies “every wellordered set of reals is countable”, so that the axiom of choice fails in L. Nevertheless, there is a natural inner model of L, namely HODL, which satisfies ZFC.. The superscript “L” indicates, here and below, that the notion in question is to be interpreted in L.) HODL is reasonably close to the full L, in ways we shall make precise in § 1. The most important of the questions we shall answer concern HODL: what is its first order theory, and in particular, does it satisfy GCH?These questions first drew attention in the 70's and early 80's. (shrink)

The main theorem of this article is that every countable model of set theory 〈M, ∈M〉, including every well-founded model, is isomorphic to a submodel of its own constructible universe 〈LM, ∈M〉 by means of an embedding j : M → LM. It follows from the proof that the countable models of set theory are linearly pre-ordered by embeddability: if 〈M, ∈M〉 and 〈N, ∈N〉 are countable models of set theory, then either M is isomorphic to a submodel of N (...) or conversely. Indeed, these models are pre-well-ordered by embeddability in order-type exactly ω1+ 1. Specifically, the countable well-founded models are ordered under embeddability exactly in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory M is universal for all countable well-founded binary relations of rank at most OrdM; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the proof method shows that if M is any nonstandard model of PA, then every countable model of set theory — in particular, every model of ZFC plus large cardinals — is isomorphic to a submodel of the hereditarily finite sets 〈 HFM, ∈M〉 of M. Indeed, 〈 HFM, ∈M〉 is universal for all countable acyclic binary relations. (shrink)

A relational structure \ is called reversible iff each bijective homomorphism from \ onto \ is an isomorphism, and linear orders are prototypical examples of such structures. One way to detect new reversible structures of a given relational language L is to notice that the maximal or minimal elements of isomorphism-invariant sets of interpretations of the language L on a fixed domain X determine reversible structures. We isolate certain syntactical conditions providing that a satisfiable \-theory defines a class of interpretations (...) having extreme elements on a fixed domain and detect several classes of reversible structures. For some of these classes, we characterize the corresponding reversible extreme interpretations. In particular, we characterize the reversible countable ultrahomogeneous graphs. (shrink)

We introduce Lascar strong types in excellent classes and prove that they coincide with the orbits of the group generated by automorphisms fixing a model. We define a new independence relation using Lascar strong types and show that it is well-behaved over models, as well as over finite sets. We then develop simplicity and show that, under simplicity, the independence relation satisfies all the properties of nonforking in a stable first order theory. Further, simplicity for an excellent class, as well (...) as the independence relation itself, is uniquely determined. Finally, we show that an excellent class is simple if and only if it has extensible U-rank . We deduce that any excellent class of finite U-rank is simple, and that any uncountably categorical excellent class has an expansion with countably many constants which is simple. (shrink)

In his classic book “the Foundations of Statistics” Savage developed a formal system of rational decision making. The system is based on (i) a set of possible states of the world, (ii) a set of consequences, (iii) a set of acts, which are functions from states to consequences, and (iv) a preference relation over the acts, which represents the preferences of an idealized rational agent. The goal and the culmination of the enterprise is a representation theorem: Any preference relation that (...) satisfies certain arguably acceptable postulates determines a (finitely additive) probability distribution over the states and a utility assignment to the consequences, such that the preferences among acts are determined by their expected utilities. Additional problematic assumptions are however required in Savage's proofs. First, there is a Boolean algebra of events (sets of states) which determines the richness of the set of acts. The probabilities are assigned to members of this algebra. Savage's proof requires that this be a σ-algebra (i.e., closed under infinite countable unions and intersections), which makes for an extremely rich preference relation. On Savage's view we should not require subjective probabilities to be σ-additive. He therefore finds the insistence on a σ-algebra peculiar and is unhappy with it. But he sees no way of avoiding it. Second, the assignment of utilities requires the constant act assumption: for every consequence there is a constant act, which produces that consequence in every state. This assumption is known to be highly counterintuitive. The present work contains two mathematical results. The first, and the more difficult one, shows that the σ-algebra assumption can be dropped. The second states that, as long as utilities are assigned to finite gambles only, the constant act assumption can be replaced by the more plausible and much weaker assumption that there are at least two non-equivalent constant acts. The second result also employs a novel way of deriving utilities in Savage-style systems -- without appealing to von Neumann-Morgenstern lotteries. The paper discusses the notion of “idealized agent" that underlies Savage's approach, and argues that the simplified system, which is adequate for all the actual purposes for which the system is designed, involves a more realistic notion of an idealized agent. (shrink)

Noetherian type and Noetherian π-type are two cardinal functions which were introduced by Peregudov in 1997, capturing some properties studied earlier by the Russian School. Their behavior has been shown to be akin to that of the cellularity, that is the supremum of the sizes of pairwise disjoint non-empty open sets in a topological space. Building on that analogy, we study the Noetherian π-type of κ-Suslin Lines, and we are able to determine it for every κ up to the first (...) singular cardinal. We then prove a consequence of Changʼs Conjecture for ℵω regarding the Noetherian type of countably supported box products which generalizes a result of Lajos Soukup. We finish with a connection between PCF theory and the Noetherian type of certain Pixley–Roy hyperspaces. (shrink)

The fundamental question in reverse mathematics is to determine which set existence axioms are required to prove particular theorems of mathematics. In addition to being interesting in their own right, answers to this question have consequences in both effective mathematics and the foundations of mathematics. Before discussing these consequences, we need to be more specific about the motivating question.Reverse mathematics is useful for studying theorems of either countable or essentially countable mathematics. Essentially countable mathematics is a vague term that is (...) best explained by an example. Complete separable metric spaces are essentially countable because, although the spaces may be uncountable, they can be understood in terms of a countable basis. Simpson gives the following list of areas which can be analyzed by reverse mathematics: number theory, geometry, calculus, differential equations, real and complex analysis, combinatorics, countable algebra, separable Banach spaces, computability theory, and the topology of complete separable metric spaces. Reverse mathematics is less suited to theorems of abstract functional analysis, abstract set theory, universal algebra, or general topology.Section 2 introduces the major subsystems of second order arithmetic used in reverse mathematics: RCA0, WKL0, ACA0, ATR0 and – CA0. Sections 3 through 7 consider various theorems of ordered group theory from the perspective of reverse mathematics. Among the results considered are theorems on ordered quotient groups, groups and semigroup conditions which imply orderability, the orderability of free groups, Hölder's Theorem, Mal'tsev's classification of the order types of countable ordered groups. (shrink)

We give an analysis over a variation of causal sets where the light cone of an event is represented by finitely branching trees with respect to any given arbitrary dynamics. We argue through basic topological properties of Cantor space that under certain assumptions about the universe, spacetime structure and causation, given any event x, the number of all possible future worldlines of x within the many-worlds interpretation is uncountable. However, if all worldlines extending the event x are ‘eventually deterministic’, then (...) the cardinality of the set of future worldlines with respect to x is exactly ℵ0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\aleph _0$$\end{document}, i.e., countably infinite. We also observe that if there are countably many future worldlines with respect to x, then at least one of them must be necessarily ‘decidable’ in the sense that there is an algorithm which determines whether or not any given event belongs to that worldline. We then show that if there are only finitely many worldlines in the future of an event x, then they are all decidable. We finally point out the fact that there can be only countably many terminating worldlines. (shrink)

We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of (...) MBA's as powerset algebras of certain directed graphs with a set of "marked" points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly $2^{3.2^{r.} } ^{2^{{\rm{2}}^{{\rm{r - 1}}} } } $ elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r. (shrink)

We study a strengthening of the notion of a perfectly meager set. We say that a subset A of a perfect Polish space X is countably perfectly meager in X, if for every sequence of perfect subsets $\{P_n: n \in \mathbb N\}$ of X, there exists an $F_\sigma $ -set F in X such that $A \subseteq F$ and $F\cap P_n$ is meager in $P_n$ for each n. We give various characterizations and examples of countably perfectly meager sets. (...) We prove that not every universally meager set is countably perfectly meager correcting an earlier result of Bartoszyński. (shrink)

We follow [8] in asking when a set of ordinals $X \subseteq \alpha$ is a countable union of sets in K, the core model. We show that, analogously to L, and X closed under the canonical Σ 1 Skolem function for K α can be so decomposed provided K is such that no ω-closed filters are put on its measure sequence, but not otherwise. This proviso holds if there is no inner model of a weak Erdős-type property.

Among the many sorts of problems encountered in decision theory, allocation problems occupy a central position. Such problems call for the assignment of a nonnegative real number to each member of a finite set of entities, in such a way that the values so assigned sum to some fixed positive real number s. Familiar cases include the problem of specifying a probability mass function on a countable set of possible states of the world, and the distribution of a certain sum (...) of money, or other resource, among various enterprises. In determining an s-allocation it is common to solicit the opinions of more than one individual, which leads immediately to the question of how to aggregate their typically differing allocations into a single “consensual” allocation. Guided by the traditions of social choice theory decision theorists have taken an axiomatic approach to determining acceptable methods of allocation aggregation. In such approaches so-called “independence” conditions have been ubiquitous. Such conditions dictate that the consensual allocation assigned to each entity should depend only on the allocations assigned by individuals to that entity, taking no account of the allocations that they assign to any other entities. While there are reasons beyond mere simplicity for subjecting allocation aggregation to independence, this radically anti-holistic stricture has frequently proved to severely limit the set of acceptable aggregation methods. As we show in what follows, the limitations are particularly acute in the case of three or more entities which must be assigned nonnegative values summing to some fixed positive number s. For if the set V⊆[0,s] of values that may be assigned to these entities satisfies some simple closure conditions and Vis finite, then independence allows only for dictatorial or imposed aggregation. This theorem builds on and extends a theorem of Bradley and Wagner and, when V={0,1}, yields as a corollary an impossibility theorem of Dietrich on judgment aggregation. (shrink)

The paper presents an outline of the general theory of countable arithmetically saturated models of PA and some of its applications. We consider questions concerning the automorphism group of a countable recursively saturated model of PA. We prove new results concerning fixed point sets, open subgroups, and the cofinality of the automorphism group. We also prove that the standard system of a countable arithmetically saturated model of PA is determined by the lattice of its elementary substructures.

According to the math tea argument, there must be real numbers that we cannot describe or define, because there are uncountably many real numbers, but only countably many definitions. And yet, the existence of pointwise-definable models of set theory, in which every individual is definable without parameters, challenges this conclusion. In this article, I introduce a flexible new method for constructing pointwise-definable models of arithmetic and set theory, showing furthermore that every countable model of Zermelo-Fraenkel ZF set theory and (...) of Peano arithmetic PA has a pointwise-definable end extension. In the arithmetic case, I use the universal algorithm and its Σ n generalizations to build a progressively elementary tower making any desired individual a n definable at each stage n, while preserving these definitions through to the limit model, which can thus be arranged to be pointwise definable. A similar method works in set theory, and one can moreover achieve V = L in the extension or indeed any other suitable theory holding in an inner model of the original model, thereby fulfilling the resurrection phenomenon. For example, every countable model of ZF with an inner model with a measurable cardinal has an end extension to a pointwise-definable model of ZFC + V = L[μ]. (shrink)

A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider its effective power over a cohesive set of natural numbers. A cohesive set is an infinite set of natural numbers that is indecomposable with respect to computably enumerable sets. It plays the role of an ultrafilter, and the elements of a cohesive power are the equivalence classes of certain partial computable functions determined by the (...) cohesive set. Thus, unlike many classical ultrapowers, a cohesive power is a countable structure. In this paper we focus on cohesive powers of graphs, equivalence structures, and computable structures with a single unary function satisfying various properties, which can also be viewed as directed graphs. For these computable structures, we investigate the isomorphism types of their cohesive powers, as well as the properties of cohesive powers when they are not isomorphic to the original structure. (shrink)

The notion of absolute independence, considered in this paper has a clear algebraic meaning and is a strengthening of the usual notion of logical independence. We prove that any consistent and countable set in classical prepositional logic has an absolutely independent axiornatization.