We investigate the set theoretical strength of some properties of normality, including Urysohn's Lemma, Tietze-Urysohn Extension Theorem, normality of disjoint unions of normal spaces, and normality of Fσ subsets of normal spaces.

The book is divided into two parts: Pragmatism and Realism, with brief introductions to each. In the Pragmatism section, the authors include Hilary Putnam himself, who gave the conference keynote address, Ruth Ann Putnam, Richard Warner, Robert Brandom, and Nicholas Rescher. The Realism section includes John Haldane, Tadeusz Szubka, John Heil, Wolfgang Künne, Gary Ebbs, and Charles Travis. Putnam replies, sometimes at length, to each one, and this is one of the more valuable features of the collection. The paper by (...) Putnam summarizes his current views and his latest version of realism. Missing in action, but discussed briefly by Putnam and some contributors, Richard Rorty has written quite a bit about Putnam, Putnam not as much on Rorty, and as these two eminent philosophers approach the end of their extensive careers, this would have been an excellent occasion for them to comment on their similarities and differences. Is Rorty really “the Evil Putnam”? Further, because Putnam has always been interested in the history and philosophy of science, it is ironic and regrettable that Kuhn gets only one brief mention, by Putnam in his reply to Rescher. He believes that Kuhn misinterprets “the significance of paradigm-change in a relativistic way,” and of course such a comment deserves defense. Both Kuhn and Rorty are directly relevant to Putnam’s arguments about the disconnect between metaphysics and physical law and it would good to have a more detailed account of his views on their historicism and “relativism.”. (shrink)

We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of all ${\cal F}$-free (...) structures, and the automorphism group of any free homogeneous structure over a finite relational language all contain a dense locally finite subgroup. We also show that any free homogeneous structure admits ample generics. (shrink)

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA0 to ATR0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR0 over RCA0.

We first show that the projection image of a discrete definable set is again discrete for an arbitrary definably complete locally o‐minimal structure. This fact together with the results in a previous paper implies a tame dimension theory and a decomposition theorem into good‐shaped definable subsets called quasi‐special submanifolds. Using this fact, we investigate definably complete locally o‐minimal expansions of ordered groups when the restriction of multiplication to an arbitrary bounded open box is definable. Similarly to o‐minimal expansions of (...) ordered fields, Łojasiewicz's inequality, Tietze's extension theorem and affiness of pseudo‐definable spaces hold true for such structures under the extra assumption that the domains of definition and the pseudo‐definable spaces are definably compact. Here, a pseudo‐definable space is a topological space having finite definable atlases. We also demonstrate Michael's selection theorem for definable set‐valued functions with definably compact domains of definition. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non-compact CSM. Both results rely on having (...) careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non-compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non-compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion-theoretic setting, then, for any such space X, there exists a Banach-Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact CSM. Both results rely on (...) having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact CSM. Both results rely on (...) having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

This paper aims to give a correct proof of Tait's conservative extension theorem. Tait's own proof is flawed in the sense that there are some invalid steps in his argument, and there is a counterexample to the main theorem from which the conservative extension theorem is supposed to follow. However, an analysis of Tait's basic idea suggests a correct proof of the conservative extension theorem and a corrected version of the main theorem.

This paper extends the classical extension theorem established by Edward Szpilrajn (Fundamenta Mathematicae, 16, pp. 386–389, 1930). Szpilrajn's theorem states that every quasi‐ordering has an ordering extension. Because of its usefulness in various themes of economics, it has been applied by many researchers. Important generalizations have been presented by two authors, Kenneth Arrow and Kotaro Suzumura, among others. First, we provide concise proofs of four extension theorems by Szpilrajn, Arrow and Suzumura. We then show an (...) extension of their extension theorems. (shrink)

Let X be a compact metric space. A closed set K $\subseteq$ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) $>$ r is Σ 0 1 allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA 0 , WKL (...) 0 and ACA 0 . We also give some applications of these concepts by discussing some versions of the Tietze extension theorem. In particular we prove an RCA 0 version of this result for weakly located closed sets. (shrink)

Let X be a compact metric space. A closed set K $\subseteq$ X is located if the distance function d exists as a continuous real-valued function on X; weakly located if the predicate d $>$ r is $\Sigma^0_1$ allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA$_0$, WKL$_0$ and ACA$_0$. We also give some (...) applications of these concepts by discussing some versions of the Tietze extension theorem. In particular we prove an RCA$_0$ version of this result for weakly located closed sets. (shrink)

The following two assertions are equivalent for an o-minimal expansion of an ordered group $$\mathcal M=(M,<,+,0,\ldots )$$. There exists a definable bijection between a bounded interval and an unbounded interval. Any definable continuous function $$f:A \rightarrow M$$ defined on a definable closed subset of $$M^n$$ has a definable continuous extension $$F:M^n \rightarrow M$$.

In this paper logics defined by finite Sugihara matrices, as well as RM itself, are discussed both in their matrix (semantical) and in syntactical version. For each such a logic a deduction theorem is proved, and a few applications are given.

In 1950, B.A. Trakhtenbrot showed that the set of first-order tautologies associated to finite models is not recursively enumerable. In 1999, P. Hájek generalized this result to the first-order versions of Łukasiewicz, Gödel and Product logics, w.r.t. their standard algebras. In this paper we extend the analysis to the first-order versions of axiomatic extensions of MTL. Our main result is the following. Let \ be a class of MTL-chains. Then the set of all first-order tautologies associated to the finite models (...) over chains in \, fTAUT\, is \ -hard. Let TAUT\ be the set of propositional tautologies of \. If TAUT\ is decidable, we have that fTAUT\ is in \. We have similar results also if we expand the language with the Δ operator. (shrink)

In [13], M. Tokarz specified some infinite family of consequence operations among all ones associated with the relevant logic RM or with the extensions of RM and proved that each of them admits a deduction theorem scheme. In this paper, we show that the family is complete in a sense that if C is a consequence operation with $C_{RM} \leq C$ and C admits a deduction theorem scheme, then C is equal to a consequence operation specified in [13]. (...) In algebraic terms, this means that the only quasivarieties of Sugihara algebras with the relative congruence extension property are the quasivarieties corresponding, via the algebraization process, to the consequence operations specified in [13]. (shrink)

May's Theorem [K. O. May, Econometrica 20 (1952) 680-684] characterizes majority voting on two alternatives as the unique preferential voting method satisfying several simple axioms. Here we show that by adding some desirable axioms to May's axioms, we can uniquely determine how to vote on three alternatives. In particular, we add two axioms stating that the voting method should mitigate spoiler effects and avoid the so-called strong no show paradox. We prove a theorem stating that any preferential voting (...) method satisfying our enlarged set of axioms, which includes some weak homogeneity and preservation axioms, agrees with Minimax voting in all three-alternative elections, except perhaps in some improbable knife-edged elections in which ties may arise and be broken in different ways. (shrink)

Guided by the example of gauge transformations associated with classical Yang-Mills fields, a very general class of transformations is considered. The explicit representation of these transformations involves not only the independent and the dependent field variables, but also a set of position-dependent parameters together with their first derivatives. The stipulation that an action integral associated with the field variables be invariant under such transformations gives rise to a set of three conditions involving the Lagrangian and its derivatives, together with derivatives (...) of the functions that define the transformations. These invariance identities constitute an extension of the classical theorem of Noether to general transformations of this kind. An application to the case of gauge fields demonstrates the existence of two distinct types of conservation laws for such fields. (shrink)

We introduce a new and general notion of canonical extension for algebras in the algebraic counterpart of any finitary and congruential logic . This definition is logic-based rather than purely order-theoretic and is in general different from the definition of canonical extensions for monotone poset expansions, but the two definitions agree whenever the algebras in are based on lattices. As a case study on logics purely based on implication, we prove that the varieties of Hilbert and Tarski algebras are (...) canonical in this new sense. (shrink)

Dummett's logic LC quantified, Q-LC, is shown to be characterized by the extended frame Q+, ,D, where Q+ is the set of non-negative rational numbers, is the numerical relation less or equal then and D is the domain function such that for all v, w Q+, Dv and if v w, then D v . D v D w . Moreover, simple completeness proofs of extensions of Q-LC are given.

We show that if $$ satisfies the first-order Zermelo–Fraenkel axioms of set theory when the membership relation is ${ \in _1}$ and also when the membership relation is ${ \in _2}$, and in both cases the formulas are allowed to contain both ${ \in _1}$ and ${ \in _2}$, then $\left \cong \left$, and the isomorphism is definable in $$. This extends Zermelo’s 1930 theorem in [6].

We extend Gurevich-Harrington's Restricted Memory Determinacy Theorem), which served in their paper as a tool to give their celebrated “short proof” of Robin's decision method for S2S. We generalize the determinacy problem by attaching to the game two opposing strategies called restraints, and by asking “which player has a strategy which is a refinement of the restraint for the player and such that it wins the game against the restraint of the opponent?” We give a solution for the Determinacy (...) with Restraints Problem in the class of strategies with restricted memory for the GH games. The solution includes a criterion for the winning player and an explicit class of winning strategies. A determinacy result which includes similar information was first discovered by Büchi and Landweber and extended by Büchi . However, these pioneering works do not consider the determinacy with restraints. Also, the explicit presentation of winning strategies in these insightful papers does not emphasize their modular construction as do GH's and our proofs. In our view, this is a source of a difficulty in understanding these papers. Games with restraints and modular construction of winning strategies have applications to the semantics, development and verification of concurrent programs. A concurrent program can be viewed as a strategy in a certain game and a program specification can be regarded as a combination of a winning condition and restraints for the game , A. Yakhnis and V. Yakhnis ). The modularity of a winning strategyfor the game helps to generate a concurrent program from the strategy that satisfies the specification ). It turns out that such program specification requirements as mutual exclusion and an absence of a lockout or a deadlock are naturally represented as Büchi's or Gurevich-Harrington's winning conditions. The present paper can be read independently of the paper by Gurevich and Harrington. (shrink)

LetKbe an algebraic number field andIKthe ring of algebraic integers inK. *Kand *IKdenote enlargements ofKandIKrespectively. LetxЄ *K–K. In this paper, we are concerned with algebraic extensions ofKwithin *K. For eachxЄ *K–Kand each natural numberd, YKis defined to be the number of algebraic extensions ofKof degreedwithin *K.xЄ *K–Kis called a Hilbertian element ifYK= 0 for alldЄ N,d> 1; in other words,Khas no algebraic extension within *K. In their paper [2], P. C. Gilmore and A. Robinson proved that the existence of (...) a Hilbertian element is equivalent to Hilbert's irreducibility theorem. In a previous paper [9], we gave many Hilbertian elements of nonstandard integers explicitly, for example, for any nonstandard natural numberω, 2ωPωand 2ω are Hilbertian elements in*Q, where pωis theωth prime number. (shrink)

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 Γ.

Sahlqvist formulas are a syntactically specified class of modal formulas proposed by Hendrik Sahlqvist in 1975. They are important because of their first-order definability and canonicity, and hence axiomatize complete modal logics. The first-order properties definable by Sahlqvist formulas were syntactically characterized by Marcus Kracht in 1993. The present paper extends Kracht's theorem to the class of ‘generalized Sahlqvist formulas' introduced by Goranko and Vakarelov and describes an appropriate generalization of Kracht formulas.

Three variants of Beth's definability theorem are considered. Let L be any normal extension of the provability logic G. It is proved that the first variant B1 holds in L iff L possesses Craig's interpolation property. If L is consistent, then the statement B2 holds in L iff L = G + {0}. Finally, the variant B3 holds in any normal extension of G.

Van Lambalgen's Theorem plays an important role in algorithmic randomness, especially when studying relative randomness. In this paper we extend van Lambalgen's Theorem by considering the join of infinitely many reals which are random relative to each other. In addition, we study computability of the reals in the range of Omega operators. It is known that $\Omega^{\phi'}$ is high. We extend this result to that $\Omega^{\phi^{(n)}}$ is $\textrm{high}_n$ . We also prove that there exists A such that, for (...) each n , the real $\Omega^A_M$ is $\textrm{high}_n$ for some universal Turing machine M by using the extended van Lambalgen's Theorem. (shrink)

Shelah develops the theory of \\) without the assumption that \\), going so far as to get generators for every \\) under some assumptions on I. Our main theorem is that we can also generalize Shelah’s trichotomy theorem to the same setting. Using this, we present a different proof of the existence of generators for \\) which is more in line with the modern exposition. Finally, we discuss some obstacles to further generalizing the classical theory.