Hahn’s embedding theorem asserts that linearly ordered abelian groups embed in some lexicographic product of real groups. Hahn’s theorem is generalized to a class of residuated semigroups in this paper, namely, to odd involutive commutative residuated chains which possess only finitely many idempotent elements. To this end, the partial lexicographic product construction is introduced to construct new odd involutive commutative residuated lattices from a pair of odd involutive commutative residuated lattices, and a representation theorem (...) for odd involutive commutative residuated chains which possess only finitely many idempotent elements, by means of linearly ordered abelian groups and the partial lexicographic product construction is presented. (shrink)

Let be the class of odd involutive even the notion of partial lex products is not sufficiently general. One more tweak is needed, a slightly even more complex construction, called partial sublex product, introduced here.

I introduce a mathematical account of expectation based on a qualitative criterion of coherence for qualitative comparisons between gambles (or random quantities). The qualitative comparisons may be interpreted as an agent’s comparative preference judgments over options or more directly as an agent’s comparative expectation judgments over random quantities. The criterion of coherence is reminiscent of de Finetti’s quantitative criterion of coherence for betting, yet it does not impose an Archimedean condition on an agent’s comparative judgments, it does not require the (...) binary relation reflecting an agent’s comparative judgments to be reflexive, complete or even transitive, and it applies to an absolutely arbitrary collection of gambles, free of structural conditions (e.g., closure, measurability, etc.). Moreover, unlike de Finetti’s criterion of coherence, the qualitative criterion respects the principle of weak dominance, a standard of rational decision making that obliges an agent to reject a gamble that is possibly worse and certainly no better than another gamble available for choice. Despite these weak assumptions, I establish a qualitative analogue of de Finetti’s Fundamental Theorem of Prevision, from which it follows that any coherent system of comparative expectations can be extended to a weakly ordered coherent system of comparative expectations over any collection of gambles containing the initial set of gambles of interest. The extended weakly ordered coherent system of comparative expectations satisfies familiar additivity and scale invariance postulates (i.e., independence) when the extended collection forms a linear space. In the course of these developments, I recast de Finetti’s quantitative account of coherent prevision in the qualitative framework adopted in this article. I show that comparative previsions satisfy qualitative analogues of de Finetti’s famous bookmaking theorem and his Fundamental Theorem of Prevision.The results of this article complement those of another article (Pedersen, Strictly coherent preferences, no holds barred, Manuscript, 2013). I explain how those results entail that any coherent weakly ordered system of comparative expectations over a unital linear space can be represented by an expectation function taking values in a (possibly non-Archimedean) totally ordered field extension of the system of real numbers. The ordered field extension consists of formal power series in a single infinitesimal, a natural and economical representation that provides a relief map tracing numerical non-Archimedean features to qualitative non-Archimedean features. (shrink)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...) importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense. (shrink)

We prove some embedding theorems for classical conditional logic, covering 'finitely cumulative' logics, 'preferential' logics and what we call 'semi-monotonic' logics. Technical tools called 'partial frames' and 'frame morphisms' in the context of neighborhood semantics are used in the proof.

Some results on the upper end of the lattice of all modal propositional logics.

We provide a new criterion for embedding.

We generalize two classical results on cylindric algebra to certain expansions of cylindric algebras where the extra operations are defined via first order formulas. The first result is the Neat Embedding Theorem of Henkin and the second is Monk's classical non-finitizability result of the class of representable algebras. As a corollary we obtain known classical results of Johnson and Biro published in the Journal of Symbolic logic.

We construct an algebra of generalized functions endowed with a canonical embedding of the space of Schwartz distributions.We offer a solution to the problem of multiplication of Schwartz distributions similar to but different from Colombeau’s solution.We show that the set of scalars of our algebra is an algebraically closed field unlike its counterpart in Colombeau theory, which is a ring with zero divisors. We prove a Hahn–Banach extension principle which does not hold in Colombeau theory. We establish a (...) connection between our theory with non-standard analysis and thus answer, although indirectly, a question raised by Colombeau. This article provides a bridge between Colombeau theory of generalized functions and non-standard analysis. (shrink)

Metaphysics, geometry, and the problems with diagrams -- The Pythagorean theorem: Euclid I.47 and VI.31 -- Thales and geometry: Egypt, Miletus, and beyond -- Pythagoras and the famous theorems -- From the Pythagorean theorem to the construction of the cosmos out of right triangles.

We prove that every countable non-standard model of WKL0 has a proper initial part isomorphic to itself. This theorem enables us to carry out non-standard arguments over WKL0.

For a quasi variety of algebras K, the Higman Theorem is said to be true if every recursively presented K-algebra is embeddable into a finitely presented K-algebra; the Generalized Higman Theorem is said to be true if any K-algebra which is recursively presented over its finitely generated subalgebra is embeddable into a K-algebra which is finitely presented over this subalgebra. We suggest certain general conditions on K under which the Higman Theorem implies the Generalized Higman Theorem; (...) a finitely generated K-algebra A is embeddable into every existentially closed K-algebra containing a finitely generated K-algebra B if and only if the word problem for A is Q-reducible to the word problem for B. The quasi varieties of groups, torsion-free groups, and semigroups satisfy these conditions. (shrink)

In recent years, the receipt and the perception of information has changed in ways which have fueled fears about the fates of our democracies. However, real information on these possibilities or the direction of these changes does not exist. Into this gap, Hahn and colleagues bring the power of Condorcet's (1785) Jury Theorem to show that changes in our information networks have affected voter inter‐dependence so that it is likely that voters are now collectively more ignorant even if (...) individual voter competence remains unchanged. (shrink)

A full separation theorem for the derivable rules of intuitionistic linear logic without bounds, 0 and exponentials is proved. Several structural consequences of this theorem for subreducts of (commutative) residuated lattices are obtained. The theorem is then extended to the logic LR+ and its proof is extended to obtain the finite embeddability property for the class of square increasing residuated lattices.

Karl Hahn, Jahrgang 1937, war bis zu seiner Emeritierung im Jahr 2003 Professor für Politische Theorie und Ideengeschichte an der Westfälischen Wilhelms-Universität Münster. Hierbei hat er die Klassiker der abendländischen Geistesgeschichte nicht in einem kanonisch-schematischen Profil gelehrt, sondern die jeweiligen Themen und Theoreme mit lebensfüllender Leidenschaft vermittelt. Seine Vorlesungen und Seminare an der Universität zeugen, wie auch seine Vorträge und Tagungsbeiträge, von einem streitbaren Geist, der stets auch um die aktualisierende Bezugnahme bemüht war. Stets hat er pointiert Stellung bezogen, (...) auch gegen den Mainstream des Faches, das er kritisch hinterfragt hat. Ob Platon, Fichte oder auch Simone Weil: Bei Karl Hahn stehen philosophische Überlegungen für eine Suche nach der Vollendung des Daseins in seinen unendlich vielen und offenen Aussagemöglichkeiten. Hahns großes Lebensthema war und ist hierbei das tragische Element des menschlichen Wesens, dessen Kleinheit und Begrenztheit angesichts der großen Fragen der menschlichen Existenz. Das hat er seinen Studierenden mit auf den Weg gegeben. Und auch den Kolleginnen und Kollegen, die bereit waren, zuzuhören. Mit dem vorliegenden Band wird der Wissenschaftler zum Anlass seines 80. Geburtstages geehrt, der seine Verdienste nicht in der flüchtigen Wertschätzung des Feuilletons, sondern grundsätzlich im Diskurs der Seminarräume und Kongressveranstaltungen erworben hat. (shrink)

According to Kant’s philosophy of geometry, Euclidean geometry is synthetic _a priori_. The advent of non-Euclidean geometries proved this position at least problematic, if not obsolete. However, based on Nash’s embedding theorems we show that a weaker notion of _preeminence_ supports the view that Euclidean geometry, even though not strictly _a priori_, enjoys a more fundamental status than non-Euclidean geometries.

The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling (...) the classical proof of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is ${\bf {\Sigma^{0}_{2}}}$ -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions. (shrink)

We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and (...) the class of Sep-computable multivalued functions. Extending work of Brattka, we show that a natural multivalued function associated with the Hahn-Banach Extension Theorem is Sep-complete. (shrink)

How we judge the similarity between stimuli in the world is connected ultimately to how we represent them. Because of this, decisions about how we model similarity, either in terms of human behavior or patterns of neural activity, can provide key insights into how representations are structured and organized. Despite this, psychology and cognitive neuroscience continue to be dominated by a narrow range of similarity models, particularly those that characterize similarity as distance within “cognitive space.” Despite the appeal of such (...) models, their topological nature places fundamental constraints on their ability to capture relationships between objects and events in the world. To probe this, we created a stimulus set in which the predicted similarity relationships (based on an alternative model of similarity) could not be simply embedded within Euclidean space. This approach revealed that the spatial model distorts these predictions, and the perceived similarities of human observers. These findings indicate that cognitive spaces—that underlie much recent work probing both visual and conceptual representations in cognitive neuroscience—are limited in fundamental ways that restrict their theoretical and practical utility. (shrink)

The main result is that for every recursively enumerable existential consistent theory Γ , there exists a finitely presented SQ-universal group H such that Γ is satisfied in every nontrivial quotient of H. Furthermore if Γ is satisfied in some group with a soluble word problem, then H can be taken with a soluble word problem. We characterize the finitely generated groups with soluble word problem as the finitely generated groups G for which there exists a finitely presented group H (...) all of the nontrivial quotients of which embed G. We prove also that for every countable group G, there exists a 2-finitely generated SQ-universal group H such that every nontrivial quotient of H embeds G. (shrink)

We propose a simple notion of "extender" for coding large elementary embeddings of models of set theory. As an application we present a self-contained proof of the theorem by D. Martin and J. Steel that infinitely many Woodin cardinals imply the determinacy of every projective set.

We present Woodin's proof that if there exists a measurable Woodin cardinal δ, then there is a forcing extension satisfying all $\Sigma _{2}^{2}$ sentences ϕ such that CH + ϕ holds in a forcing extension of V by a partial order in V δ . We also use some of the techniques from this proof to show that if there exists a stationary limit of stationary limits of Woodin cardinals, then in a homogeneous forcing extension there is an elementary (...) class='Hi'>embedding j: V → M with critical point $\omega _{1}^{V}$ such that M is countably closed in the forcing extension. (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)

First-order intuitionistic and classical Nelson–Wansing and Arieli–Avron–Zamansky logics, which are regarded as paradefinite and connexive logics, are investigated based on Gentzen-style sequent calculi. The cut-elimination and completeness theorems for these logics are proved uniformly via theorems for embedding these logics into first-order intuitionistic and classical logics. The modified Craig interpolation theorems for these logics are also proved via the same embedding theorems. Furthermore, a theorem for embedding first-order classical Arieli–Avron–Zamansky logic into first-order intuitionistic Arieli–Avron–Zamansky logic is (...) proved using a modified Gödel–Gentzen negative translation. The failure of a theorem for embedding first-order classical Nelson–Wansing logic into first-order intuitionistic Nelson–Wansing logic is also shown. (shrink)

We work in set theory ZF without axiom of choice. Though the Hahn-Banach theorem cannot be proved in ZF, we prove that every Gateaux-differentiable uniformly convex Banach space E satisfies the following continuous Hahn-Banach property: if p is a continuous sublinear functional on E, if F is a subspace of E, and if f: F → ℝ is a linear functional such that f ≤ p|F then there exists a linear functional g : E → ℝ such (...) that g extends f and g ≤ p. We also prove that the continuous Hahn-Banach property on a topological vector space E is equivalent to the classical geometrical forms of the Hahn-Banach theorem on E. We then prove that the axiom of Dependent choices DC is equivalent to Ekeland's variational principle, and that it implies the continuous Hahn-Banach property on Gateaux-differentiable Banach spaces. Finally, we prove that, though separable normed spaces satisfy the continuous Hahn-Banach property, they do not satisfy the whole Hahn-Banach property in ZF+DC. (shrink)

We consider the very weak paracomplete and paraconsistent logics that are obtained by a straightforward weakening of Classical Logic, as well as some of their maximal extensions that are a fragment of Classical Logic. We prove that these logics may be faithfully embedded in Classical Logic, and that the interpolation theorem obtains for them.

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (ATR_0) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraïssé's conjecture restricted to well-orderings.

We show a transfer principle for the property that all types realised in a given elementary extension are definable. It can be written as follows: a Henselian valued field is stably embedded in an elementary extension if and only if its value group is stably embedded in its corresponding extension, its residue field is stably embedded in its corresponding extension, and the extension of valued fields satisfies a certain algebraic condition. We show for instance that all types over the (...) class='Hi'>Hahn field $$\mathbb {R}((\mathbb {Z}))$$ are definable. Similarly, all types over the quotient field of the Witt ring $$W(\mathbb {F}_p^{\text {alg}})$$ are definable. This extends a work of Cubides and Delon and of Cubides and Ye. (shrink)

By a classical theorem of Harvey Friedman, every countable nonstandard model $\mathcal {M}$ of a sufficiently strong fragment of ZF has a proper rank-initial self-embedding j, i.e., j is a self-embedding of $\mathcal {M}$ such that $j[\mathcal {M}]\subsetneq \mathcal {M}$, and the ordinal rank of each member of $j[\mathcal {M}]$ is less than the ordinal rank of each element of $\mathcal {M}\setminus j[\mathcal {M}]$. Here, we investigate the larger family of proper initial-embeddings j of models $\mathcal {M}$ (...) of fragments of set theory, where the image of j is a transitive submodel of $\mathcal {M}$. Our results include the following three theorems. In what follows, $\mathrm {ZF}^-$ is $\mathrm {ZF}$ without the power set axiom; $\mathrm {WO}$ is the axiom stating that every set can be well-ordered; $\mathrm {WF}$ is the well-founded part of $\mathcal {M}$ ; and $\Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ is the full scheme of dependent choice of length $\alpha $.Theorem A.There is an $\omega $ -standard countable nonstandard model $\mathcal {M}$ of $\mathrm {ZF}^-+\mathrm {WO}$ that carries no initial self-embedding $j:\mathcal {M} \longrightarrow \mathcal {M}$ other than the identity embedding.Theorem B.Every countable $\omega $ -nonstandard model $\mathcal {M}$ of $\ \mathrm {ZF}$ is isomorphic to a transitive submodel of the hereditarily countable sets of its own constructible universe $L^{\mathcal {M}}$.Theorem C.The following three conditions are equivalent for a countable nonstandard model $\mathcal {M}$ of $\mathrm {ZF}^{-}+\mathrm {WO}+\forall \alpha \ \Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $. There is a cardinal in $\mathcal {M}$ that is a strict upper bound for the cardinality of each member of $\mathrm {WF}$. $\mathrm {WF}$ satisfies the powerset axiom.For all $n \in \omega $ and for all $b \in M$, there exists a proper initial self-embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ such that $b \in \mathrm {rng}$ and $j[\mathcal {M}] \prec _n \mathcal {M}$. (shrink)

We give a sharper version of a theorem of Rosický, Trnková and Adámek [13], and a new proof of a theorem of Rosický [12], both about colimits in categories of structures. Unlike the original proofs, which use category-theoretic methods, we use set-theoretic arguments involving elementary embeddings given by large cardinals such as $\alpha$-strongly compact and $C^{(n)}$-extendible cardinals.

The Local Computation Framework has been used to improve the efficiency of computation in various uncertainty formalisms. This paper shows how the framework can be used for the computation of logical deduction in two different ways; the first way involves embedding model structures in the framework; the second, and more direct, way involves embedding sets of formulae. This work can be applied to many of the logics developed for different kinds of reasoning, including predicate calculus, modal logics, possibilistic (...) logics, probabilistic logics and non-monotonic logics. (shrink)

This paper introduces the state space theory of consciousness, positing that the cortex processes information through delay coordinate embedding operationalized by recurrent neural network engines. This leverages the power of Takens' theorem, giving rise to representations of reality as points within state space. Consciousness is posited to arise at the highest order engines amongst hierarchical and parallel engine pathways. Consciousness is cast as a dynamic process rather than as a neuronal state, reconciling dualist intuitions with a monist perspective. (...) Neuronal representations develop uniquely in each individual due to history-dependent training of these engines, accounting for the privacy of qualia while also addressing cortical plasticity and the heuristic nature of cortical processing. Posited engines exhibit non-linear dynamics that are sensitive to initial conditions, explaining phenomena such as ambiguous figure interpretation and offering a pathway to explaining free will. The state space theory aligns with and expands upon major theories (e.g.higher-order theories, global workspace theories, integrated information theory), essentially providing a computational mechanism that unifies elements of these theories. Future work will explore neural mechanisms and validate predictions. (shrink)

In this paper, a theorem on the existence of complete embedding of partially ordered monoids into complete residuated lattices is shown. From this, many interesting results on residuated lattices and substructural logics follow, including various types of completeness theorems of substructural logics.

Consider the problem which set V of propositional variables suffices for whenever, where, and ⊢c and ⊢i denote derivability in classical and intuitionistic implicational logic, respectively. We give a direct proof that stability for the final propositional variable of the (implicational) formula A is sufficient; as a corollary one obtains Glivenko's theorem. Conversely, using Glivenko's theorem one can give an alternative proof of our result. As an alternative to stability we then consider the Peirce formula. It is an (...) easy consequence of the result above that adding a single instance of the Peirce formula suffices to move from classical to intuitionistic derivability. Finally we consider the question whether one could do the same for minimal logic. Given a classical derivation of a propositional formula not involving ⊥, which instances of the Peirce formula suffice as additional premises to ensure derivability in minimal logic? We define a set of such Peirce formulas, and show that in general an unbounded number of them is necessary. (shrink)

An important technique in large cardinal set theory is that of extending an elementary embedding j: M → N between inner models to an elementary embedding j*: M[G] → N[G*] between generic extensions of them. This technique is crucial both in the study of large cardinal preservation and of internal consistency. In easy cases, such as when forcing to make the GCH hold while preserving a measurable cardinal (via a reverse Easton iteration of α-Cohen forcing for successor cardinals (...) α), the generic G* is simply generated by the image of G. But in difficult cases, such as in Woodin's proof that a hypermeasurable is sufficient to obtain a failure of the GCH at a measurable, a preliminary version of G* must be constructed (possibly in a further generic extension of M[G]) and then modified to provide the required G*. In this article we use perfect trees to reduce some difficult cases to easy ones, using fusion as a substitute for distributivity. We apply our technique to provide a new proof of Woodin's theorem as well as the new result that global domination at inaccessibles (the statement that d (κ) is less than 2κ for inaccessible κ, where d (κ) is the dominating number at κ) is internally consistent, given the existence of 0#. (shrink)

A theoretical development is carried to establish fundamental results about rank-initial embeddings and automorphisms of countable non-standard models of set theory, with a keen eye for their sets of fixed points. These results are then combined into a “geometric technique” used to prove several results about countable non-standard models of set theory. In particular, back-and-forth constructions are carried out to establish various generalizations and refinements of Friedman’s theorem on the existence of rank-initial embeddings between countable non-standard models of the (...) fragment \ + \-Separation of \; and Gaifman’s technique of iterated ultrapowers is employed to show that any countable model of \ can be elementarily rank-end-extended to models with well-behaved automorphisms whose sets of fixed points equal the original model. These theoretical developments are then utilized to prove various results relating self-embeddings, automorphisms, their sets of fixed points, strong rank-cuts, and set theories of different strengths. Two examples: The notion of “strong rank-cut” is characterized in terms of the theory \, and in terms of fixed-point sets of self-embeddings. (shrink)

The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.

In [3], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. While [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a “Pull-back (...) class='Hi'>Theorem”, saying that if Φ is a Turing computable embedding of K into K’, then for any computable infinitary sentence φ in the language of K’, we can find a computable infinitary sentence φ* in the language of K such that for all. (shrink)

Stephen Barker argues that a possible worlds semantics for the counterfactual conditional of the sort proposed by Stalnaker and Lewis cannot accommodate certain examples in which determinism is true and a counterfactual Q > R is false, but where, for some P, the compound counterfactual P > (Q > R) is true. I argue that the completeness theorem for Lewis’s system VC of counterfactual logic shows that Stalnaker–Lewis semantics does accommodate Barker’s example, and I argue that its doing so (...) should be understood as showing that the example is an exception to Lewis’s Time’s Arrow requirements. (shrink)

Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer (...) and Hinman, we improve on the result of Binns and Simpson by showing that for any ${\mathcal{U} < _s \mathcal{V}}$ , we can lattice embed FD(ω) into ${\mathcal{P}_s}$ strictly between ${deg_s(\mathcal{U})}$ and ${deg_s({\mathcal V})}$ . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. (shrink)

We compare several methods of implementing the display (sequent) calculus RA for relation algebra in the logical frameworks Isabelle and Twelf. We aim for an implementation enabling us to formalise within the logical framework proof-theoretic results such as the cut-elimination theorem for RA and any associated increase in proof length. We discuss issues arising from this requirement.

We construct a faithful interpretation of ukasiewicz's logic in product logic (both propositional and predicate). Using known facts it follows that the product predicate logic is not recursively axiomatizable.We prove a completeness theorem for product logic extended by a unary connective of Baaz [1]. We show that Gödel's logic is a sublogic of this extended product logic.