In [2], Jockusch and Shore have introduced a new hierarchy of sets and operators called the REA hierarchy. In this note we prove analogues of the Friedberg Jump Theorem and the Sacks Jump Theorem for many REA operators. MSC: 03D25, 03D55.

. We prove a jump inversion theorem for the enumeration jump and a minimal pair type theorem for the enumeration reducibilty. As an application some results of Selman, Case and Ash are obtained.

We prove two antibasis theorems for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} classes. The first is a jump inversion theorem for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} classes with respect to the global structure of the Turing degrees. For any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P\subseteq 2^\omega}$$\end{document}, define S(P), the degree spectrum of P, to be the set of all Turing degrees a such that there exists (...) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \in P}$$\end{document} of degree a. For any degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document}, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}^{-1}({\bf a) = \{b : b' = a \}}}$$\end{document}. We prove that, for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document} and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class P, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}^{-1} ({\bf a}) \subseteq S(P)}$$\end{document} then P contains a member of every degree. For any degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document} such that a is recursively enumerable (r.e.) in 0', let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${Jump_{\bf \leq 0'} ^{-1}({\bf a)=\{b : b \leq 0' \textrm{and} b' = a \}}}$$\end{document}. The second theorem concerns the degrees below 0'. We prove that for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a\geq 0'}}$$\end{document} which is recursively enumerable in 0' and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class P, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}_{\bf \leq 0'} ^{-1}({\bf a)} \subseteq S(P)}$$\end{document} then P contains a member of every degree. (shrink)

We investigate the relationship of the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low 2.

Central limit theorem for the functional of jump Markov process. Nguyễn Văn Hữu, Vương Quân Hoàng và Trần Minh Ngọc. Báo cáo: Hội nghị toàn quốc lần thứ III “Xác suất - Thống kê: Nghiên cứu, ứng dụng và giảng dạy” (tr. 34). Ba Vì, Hà Tây, ngày 12-14 tháng 05 năm 2005. Viện Toán học / Trường Đại học Khoa học tự nhiên / Đại học Quốc gia Hà Nội.

Some conditions are given to ensure that for a jump homogeneous Markov process $\{X(t),t\ge 0\}$ the law of the integral functional of the process $T^{-1/2} \int^T_0\varphi(X(t))dt$ converges to the normal law $N(0,\sigma^2)$ as $T\to \infty$, where $\varphi$ is a mapping from the state space $E$ into $\bbfR$.

The jump operator on the ω-enumeration degrees was introduced in [I.N. Soskov, The ω-enumeration degrees, J. Logic Computat. 17 1193–1214]. In the present paper we prove a jump inversion theorem which allows us to show that the enumeration degrees are first order definable in the structure of the ω-enumeration degrees augmented by the jump operator. Further on we show that the groups of the automorphisms of and of the enumeration degrees are isomorphic. In the second part (...) of the paper we study the jumps of the ω-enumeration degrees below . We define the ideal of the almost zero degrees and obtain a natural characterization of the class H of the ω-enumeration degrees below which are high n for some n and of the class L of the ω-enumeration degrees below which are low n for some n. (shrink)

One of the main problems in effective model theory is to find an appropriate information complexity measure of the algebraic structures in the sense of computability. Unlike the commonly used degrees of structures, the structure degree measure is total. We introduce and study the jump operation for structure degrees. We prove that it has all natural jump properties (including jump inversion theorem, theorem of Ash), which show that our definition is relevant. We study the relation (...) between the structure degree jump (in the sense of Soskov) and the jump degrees of a structure (in the sense of Jockusch) and give necessary and sufficient conditions for their existence in the terms of structure degrees. We show some properties, distinguishing the structure degrees from the enumeration degrees. (shrink)

We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are (...) not 0′-dominated. A further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails. Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable. (shrink)

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing Jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. Until Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. (...) In this paper we introduce a new neighborhood of theorems which are almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own they are very weak. We generalize several conservativity classes ( $\Pi _{1}^{1}$, r- $\Pi _{2}^{1}$, and Tanaka) and show that all our examples (and many others) are conservative over RCA $_{0}$ in all these senses and weak in other recursion theoretic ways as well. We provide denizens, both mathematical and logical. These results answer a question raised by Hirschfeldt and reported in Montalbán [2011] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second order arithmetic. (shrink)

This paper is an investigation of the relationship between G\"odel's second incompleteness theorem and the well-foundedness of jump hierarchies. It follows from a classic theorem of Spector's that the relation $\{(A,B) \in \mathbb{R}^2 : \mathcal{O}^A \leq_H B\}$ is well-founded. We provide an alternative proof of this fact that uses G\"odel's second incompleteness theorem instead of the theory of admissible ordinals. We then derive a semantic version of the second incompleteness theorem, originally due to Mummert and (...) Simpson, from this result. Finally, we turn to the calculation of the ranks of reals in this well-founded relation. We prove that, for any $A\in\mathbb{R}$, if the rank of $A$ is $\alpha$, then $\omega_1^A$ is the $(1 + \alpha)^{\text{th}}$ admissible ordinal. It follows, assuming suitable large cardinal hypotheses, that, on a cone, the rank of $X$ is $\omega_1^X$. (shrink)

Theorems of hyperarithmetic analysis occupy an unusual neighborhood in the realms of reverse mathematics and recursion-theoretic complexity. They lie above all the fixed iterations of the Turing jump but below ATR $_{0}$. There is a long history of proof-theoretic principles which are THAs. Until the papers reported on in this communication, there was only one mathematical example. Barnes, Goh, and Shore [1] analyze an array of ubiquity theorems in graph theory descended from Halin’s [9] work on rays in graphs. (...) They seem to be typical applications of ACA $_{0}$ but are actually THAs. These results answer Question 30 of Montalbán’s Open Questions in Reverse Mathematics [19] and supply several other natural principles of different and unusual levels of complexity.This work led in [25] to a new neighborhood of the reverse mathematical zoo: almost theorems of hyperarithmetic analysis. When combined with ACA $_{0}$ they are THAs but on their own are very weak. Denizens both mathematical and logical are provided. Generalizations of several conservativity classes are defined and these ATHAs as well as many other principles are shown to be conservative over RCA $_{0}$ in all these senses and weak in other recursion-theoretic ways as well. These results answer a question raised by Hirschfeldt and reported in [19] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong or very strong going up a standard hierarchy and at the end being stronger than full second-order arithmetic. (shrink)

Halin in 1965 proved that if a graph has [Formula: see text] many pairwise disjoint rays for each [Formula: see text] then it has infinitely many pairwise disjoint rays. We analyze the complexity of this and other similar results in terms of computable and proof theoretic complexity. The statement of Halin’s theorem and the construction proving it seem very much like standard versions of compactness arguments such as König’s Lemma. Those results, while not computable, are relatively simple. They only (...) use arithmetic procedures or, equivalently, finitely many iterations of the Turing jump. We show that several Halin-type theorems are much more complicated. They are among the theorems of hyperarithmetic analysis. Such theorems imply the ability to iterate the Turing jump along any computable well ordering. Several important logical principles in this class have been extensively studied beginning with work of Kreisel, H. Friedman, Steel and others in the 1960s and 1970s. Until now, only one purely mathematical example was known. Our work provides many more and so answers Question 30 of Montalbán’s Open Questions in Reverse Mathematics in 2011. Some of these theorems including ones in Halin in 1965 are also shown to have unusual proof theoretic strength as well. (shrink)

This work is devoted to studying the stochastic stabilization of a class of neutral-type complex-valued neural networks with partly unknown Markov jump. Firstly, in order to reduce the conservation of our stability conditions, two integral inequalities are generalized to the complex-valued domain. Secondly, a state-feedback controller is designed to investigate the stability of the neutral-type CVNNs with H ∞ performance, making the stability problem a further extension, and then, the stabilization of the CVNNs with H ∞ performance is investigated (...) through a sampling-based event-triggered control for the first time that the transmission event is not triggered except when it violates the event-triggered condition. Finally, two examples are given to illustrate the validity and correctness of our obtained theorems. (shrink)

It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best possible (...) in various senses. (shrink)

We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent (...) to the conjunction of the statement asserting the existence of a 2-random relative to any given set and the principle of Σ2 collection. (shrink)

We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish (...) two different logical versions of the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is “given.” Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets. (shrink)

We formulate an abstract version of the finite injury method in the form of the Baire category theorem. The theorem has the following corollaries: The Friedberg-Muchnik pair of recursively enumerable degrees, the Sacks splitting theorem, the existence of a minimal degree below 0′ and the Shoenfield jump theorem.

We consider implicit definability over the natural number system $\mathbb{N},+,\times,=$. We present a new proof of two theorems of Leo Harrington. The first theorem says that there exist implicitly definable subsets of $\mathbb{N}$ which are not explicitly definable from each other. The second theorem says that there exists a subset of $\mathbb{N}$ which is not implicitly definable but belongs to a countable, explicitly definable set of subsets of $\mathbb{N}$. Previous proofs of these theorems have used finite- or infinite-injury (...) priority constructions. Our new proof is easier in that it uses only a nonpriority oracle construction, adapted from the standard proof of the Friedberg jump theorem. (shrink)

Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider (...) whether the analogue of the Jump Theorem holds for the bounded jump: do we have A≤bTB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \le _{bT}B$$\end{document} if and only if Ab≤1Bb\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A^b \le _1 B^b$$\end{document}? We show the forward direction holds but not the reverse. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

A classical theorem in computability is that every promptly simple set can be cupped in the Turing degrees to some complete set by a low c.e. set. A related question due to A. Nies is whether every promptly simple set can be cupped by a superlow c.e. set, i. e. one whose Turing jump is truth-table reducible to the halting problem θ'. A negative answer to this question is provided by giving an explicit construction of a promptly simple (...) set that is not superlow cuppable. This problem relates to effective randomness and various lowness notions. (shrink)

Logic in Action/Doron Avital Nothing is more difficult, and therefore more precious, than to be able to decide (Napoleon Bonaparte) Introduction -/- This book was born on the battlefield and in nights of secretive special operations all around the Middle East, as well as in the corridors and lecture halls of Western Academia best schools. As a young boy, I was always mesmerized by stories of great men and women of action at fateful cross-roads of decision-making. Then, like as today, (...) I felt the full weight of the moment of truth as it confronts the individual, the man or woman of action, with the imminent necessity to decide. Alongside, as I was climbing up the ladder of education, I found myself just as well captivated by the great intellectual stories of our times, in particular 20th century analytic philosophy and, at its core, the machinery of modern logic. How do then the cool contemplative modes of the philosophical and analytic outlooks, that are better fitting of the philosopher's armchair at the fireplace, hang together with the heat of the battlefield or the angst of the ticking clock of time left to the completion of a daring special operation? Growing up I was pondering exactly that. Not accidently, and in fact as consequence, I have chosen a course in life that challenged me to visit the poles of both theory and practice. I set myself on a mission to unravel the tension between the contemplative inquiry, supposedly theoretical, aiming at the logical structure of things, and the uncompromising test of life and action. The puzzle of the gap between theory and practice has become ever since the guiding question of my life. -/- Not long ago, I met two friends, Avner Shor, a veteran combat soldier of the special forces unit I eventually commanded, and Aviram Halevi, a fellow officer with whom I served. Why will we not put into writing the ideas that guided us during our years of military action, we wondered. At that time, I used to deliver the keynote lectures to the senior officers' course of Israel central intelligence organization, the Mossad. For this I already had to put some of these ideas in writing. Avner was quick to introduce me with a notable publisher and even helped me write the first chapter. With Aviram I sat to many meetings, where he would challenge me with key questions, and we followed them with memories of operations and battles, aiming to draw the required lessons. This served me well when I finally sat down to write the first draft of the book. The result was more extensive than me and my friends had expected. I had to add a particularly long chapter dealing with the story of modern philosophy and logic. This was required, I felt, as no decision-making process lives in an intellectual vacuum. Knowingly or subconsciously, the intellectual climate of the time guides us for better or worse with the decisions we finally take. The initial draft was naturally cumbersome and inaccessible. But here I had the privilege of meeting a particularly talented editor, Rami Rothholtz. I found in Rami both an editor and a critical reader. As an infantry combat soldier at youth and now a senior journalist and editor, Rami insisted on simplifying and refining my ideas. Had it not been for his work, this book would have been literally unreadable. *** I opened my book with a brief description of a single night of a special operation deep at the Lebanon Bekaa valley, far away from Israel northern border. The mission was to kidnap a senior terror leader known to be holding in captivity an Israeli pilot. This was also the last special operation I commanded in my military career. A single special operation night, but what had to precede it? For sure, many months of intense and skillful preparations. What is Planning? This is the question with which I open up chapter (2) of the book. I confront in this chapter two approaches to planning. The first is the one I saw as a mission to myself to cultivate in my many years of military service. The second is the one I saw as representing a deep-rooted fallacy that holds a firm grip on today's conventional wisdom about planning. To further examine the logic of the competing models, I was required in chapter (3) to analyze the concept of "The Standard". I argue that the false model of planning has its roots in an attitude of an uncompromising adherence to the power of literal obedience to standards and rules. The standard, or what is outlined by a rule as prescribing a future course of action, is seen as an answer to the fundamental tension between theory (planning) and practice (execution). I argue in contrast that the standard does not produce an answer but rather what I call: "A Well-Defined Question". In essence, it is a meticulously-well-planned invitation to exercise a fresh judgment. A judgement that has as an anchor the default answer that the standard produces but is open to extension as it confronts the new frame of reference of the test of reality. In chapter (4), I present a new tool for planning and execution: "The Polygon of Risks" or "The Polygon of Execution". The Polygon is a geometric illustration of the underlying tension that exists between all dimensions of the operational project. The construction and conceptualization of the trade-offs that exist between the various dimensions - segments of the polygon - is the first topic on the planner's agenda. I position the concepts of "Daring" and "Taking Proactive and Well-Informed Risks" as necessary logical constituents of the polygon and show how in contrast the false model of planning is responsible for an operational culture that is risk-averse. It encourages, in fact, the piling up of false securities at the segments' level that eventually lead to the collapse of the polygon. The necessary trade-offs relationships that exist between the segments of the polygon express the fundamental tension between partnership and competition: partnership in a joint goal and competition over resources, both material and abstract. When this tension is not managed well, that is, when the players' local optimizations overshadow the global optimization required for the success of the project, the execution polygon collapses. In this scenario, we may find the setting of the bar of "High Standards" in a players' spheres of responsibility to conceal a hidden agenda of personal insurances taken against a possible failure. Once the overall risk is not mitigated by way of collaborative joint executional dialogue, the process that leads to a collapse of the polygon is literally unstoppable. *** In chapter (5), I discuss "(Fateful) Decisions". I examine the way in which we should translate the polygon into sequential critical decisions on the timeline. The execution polygon is not a rigid scaffolding but a dynamic conceptual illustration of the -/- project. It will need now to be converted into successive decision junctions. We will find the content of a decision and its timing on the timeline to be inseparable. The right decision is the one that is taken at the right time. The moment of decision is in fact the last moment of deliberation, the first moment available for action, i.e. the first possible "Can" is also the latest possible "Must". Deciding too soon is analog to the "Jumping of the Gun". The decision maker is forcing a pre-conceived answer to a state of affairs not ripe for an answer, e.g. the target in the shooting range is not yet erected. Late to decide and the decision maker may envision what he or she should have done but reality is no longer available for them to harness it right, e.g. consider a tennis player's frustration when reviewing a too-late-to-react move in the video replay. I review in this chapter many fateful decisions, both historical, from Napoleon's Waterloo, to a Bridge Too Far of WWII, to the failed rescue attempt of American hostages at the time of the Iranian Revolution, as well as fateful decisions I had to take in the course of my military life, both in combat and in special operations, and show the sense in which they all answer to our analysis. The theme of chapter (6) is "The Moment of Truth". This is the moment when everything is on the line and from which there is no turning back. I discuss the formative repetitive structure of the schooling and simulation phase and contrast it with the "One Shot, One Opportunity" nature of the moment of truth. This is extremely helpful when we analyze the logical structure of failures as unwarranted repetitions of past lessons. The schooling curriculum indeed consists of important abstractions drawn from lessons of the past. However, it is when we project them in a fashion that is literal or mechanical that we cross path with the possibility of a failure. The paradox of education is that what we must repeat in school and simulation must be extended and not repeated in real life. What is required of us so we do not fall into the fallacy of repetition in face of the moment of truth is the core subject of the discussion of this chapter. In chapter (7), I took a lengthy philosophical detour surveying the intellectual drama of modern logic, and in general, the story of 20th century analytic philosophy. Readers who choose to bypass the somehow demanding narrative of this drama can do so and still keep the argumentative thread of the book. However, even by way of skipping the more technical parts, I would still urge the readers to delve into the discussion in this chapter as I believe this would grant them a deeper understanding of the overall conceptual framework. I explore here the work of two key figures: the logician Kurt Gödel and the philosopher Ludwig Wittgenstein, both were crowned in 2000 by TIME Magazine, as the leading Logician and Philosopher, respectively, of the 20th Century. I review the fascinating logical result of Gödel's Incompleteness Theorem and examine its relevance as setting a theoretical limit to the power of formalization. This amazing logical result - a result that shakes the logical foundations of 20th century thought in as much as the discovery of irrational numbers shook the foundations of the Pythagorean program of the ancient Greeks - bears significantly on the question of action and the blind trust we place in the power of formalization in the form of protocols and rules. It is here that Wittgenstein's philosophy enters in full force. We follow Wittgenstein as he dismantles our conception of rules as if there were "Railroads to Infinite", i.e. as prescribing for us in-advance their proper employments in all possible -/- future eventualities. Instead we propose that the dilemma of action demands of us an extension of rules rather than a mechanical or blind repetition of their literal imperative. In turn, this extension can serve as a new lesson added to the curriculum of school and simulation. The theme of chapter (8), the concluding chapter, is Strategy, Logic, and Ethics. The chapter comes to place the ethical dilemma in the conceptual map we presented in the book. I discuss here the tension between strategy as a process of setting goals and deriving backward as it were the steps that are necessary for achieving these goals, to the inescapable dictation of the ethical imperative. This unavoidable tension is particularly important against the backdrop of contemporary culture that is guided by a vision of personal success and achievement that may threaten our ability to do what is right. Most of all, I am troubled in this chapter, with the role logic may play, first as a liberating force enabling a change that is tuned to the ethical imperative, and second, as a force designed to justify on logical grounds, as it were, the existing power structure. It is in this junction that brave individuals will be called to challenge the governing logic of the zeitgeist - logic that operates now as an oppressive force that serves the vested interest of beneficials of the existing order. When success is favored over doing what is right, as we must admit is the prevailing cultural mood of our times, that the words of Emanuel Kant carry their full weight: "Do the Right thing and leave the Consequences to God". For this we need heroes and heroines that challenge the time by bearing the full weight of responsibility that comes with the doing of what is Right. *** This book was written more than anything from the perspective of the heroes and heroines of action. Sometimes they may be missing the exact words or the full insight into the solid logical complexity that stands between them and the doing of what is right. They feel what is right to do on the battlefield of life, whether in real battle, in political or economic life or whether in the life of creativity and the quest of the intellect. They do need, in analogy, proper logical and intellectual artillery. I hope they will find the logical cannons they require as they travel through the pages of this book. The rest is in their hands at the Moment of Truth. -/- Doron Avital, Tel Aviv 2011 -/- . (shrink)

A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this (...) property until now. We also prove that, over RCA0, INDEC is implied by [Formula: see text] and implies ACA0, but of course, neither ACA0, nor ACA 0+ imply it. We introduce five other statements of hyperarithmetic analysis and study the relations among them. Four of them are related to finitely-terminating games. The fifth one, related to iterations of the Turing jump, is strictly weaker than all the other statements that we study in this paper, as we prove using Steel's method of forcing with tagged trees. (shrink)

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 examine the influence of word choices on mathematical practice, i.e. in developing definitions, theorems, and proofs. As a case study, we consider Euclid’s and Euler’s word choices in their influential developments of geometry and, in particular, their use of the term ‘polyhedron’. Then, jumping to the twentieth century, we look at word choices surrounding the use of the term ‘polyhedron’ in the work of Coxeter and of Grünbaum. We also consider a recent and explicit conflict of approach between Grünbaum (...) and Shephard on the one hand and that of Hilton and Pedersen on the other, elucidating that the conflict was engendered by disagreement over the proper conceptualization, and so also the appropriate word choices, in the study of polyhedra. (shrink)

The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . In this article we examine the effective (...) content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)

Demuth tests generalize Martin-Löf tests in that one can exchange the m-th component a computably bounded number of times. A set fails a Demuth test if Z is in infinitely many final versions of the Gm. If we only allow Demuth tests such that GmGm+1 for each m, we have weak Demuth randomness.We show that a weakly Demuth random set can be high and , yet not superhigh. Next, any c.e. set Turing below a Demuth random set is strongly (...) class='Hi'>jump-traceable.We also prove a basis theorem for non-empty classes P. It extends the Jockusch–Soare basis theorem that some member of P is computably dominated. We use the result to show that some weakly 2-random set does not compute a 2-fixed point free function. (shrink)

The main results of the present paper are the following theorems: 1. There is no e ∈ ω such that for any A, B ⊆ ω, SA = Wmath image is simple in A, and if A′ [TRIPLE BOND]TB′, then SA =* SB. 2 There is an e ∈ ω such that for any A, B ⊆ ω, MA = We is incomplete maximal in A, and if A =* B, then MA [TRIPLE BOND]TMB.

We investigate the modal logic of stepwise removal of objects, both for its intrinsic interest as a logic of quantification without replacement, and as a pilot study to better understand the complexity jumps between dynamic epistemic logics of model transformations and logics of freely chosen graph changes that get registered in a growing memory. After introducing this logic (MLSR) and its corresponding removal modality, we analyze its expressive power and prove a bisimulation characterization theorem. We then provide a complete (...) Hillbert-style axiomatization for the logic of stepwise removal in a hybrid language enriched with nominals and public announcement operators. Next, we show that model-checking for MLSR is PSPACE-complete, while its satisfiability problem is undecidable. Lastly, we consider an issue of fine-structure: the expressive power gained by adding the stepwise removal modality to fragments of first-order logic. (shrink)

Formal aspects of various ways of description of Jan Łukasiewicz’s four-valued modal logic £ are discussed. The original Łukasiewicz’s description by means of the accepted and rejected theorems, together with the four-valued matrix, is presented. Then the improved E.J. Lemmon’s description based upon three specific axioms, together with the relational semantics, is presented as well. It is proved that Lemmon’s axiomatic is not independent: one axiom is derivable on the base of the remanent two. Several axiomatizations, based on three, two (...) or one single axiom are provided and discussed, including S. Kripke’s axiomatics. It is claimed that (a) all substitutions of classical theorems, (b) the rule of modus ponens, (c) the definition of “◊” and (d) the single specific axiom schema: ⬜A ∧ B → A ∧ ⬜B, called the jumping necessity axiom, constitute an elegant axiomatics of the system £. (shrink)

We show that every MALL proof-structure [9] satisfies the property of softness, originally a categorical notion introduced by Joyal. Furthermore, we show that the notion of hereditary softness precisely captures Girard’s algebraic restriction of the technical condition on proof-structures. Relying on this characterization, we prove a MALL+Mix sequentialization theorem by a proof-theoretical method, using Girard’s notion of jump. Our MALL+Mix correctness criterion subsumes the Danos/Fleury-Retoré criterion [6] for MLL+Mix.

We reformulate slightly Russell's notion of typicality, so as to eliminate its circularity and make it applicable to elements of any first‐order structure. We argue that the notion parallels Martin‐Löf (ML) randomness, in the sense that it uses definable sets in place of computable ones and sets of “small” cardinality (i.e., strictly smaller than that of the structure domain) in place of measure zero sets. It is shown that if the domain M satisfies, then there exist typical elements and only (...) non‐typical ones. In particular this is true for the standard model of second‐order arithmetic. By allowing parameters in the defining formulas, we are led to relative typicality, which satisfies most of van Lambalgen's axioms for relative randomness. However van Lambalgen's theorem is false for relative typicality. The class of typical reals is incomparable (with respect to ⊆) with the classes of ML‐random, Schnorr random and computably random reals. Also the class of typical reals is closed under Turing degrees and under the jump operation (both ways). (shrink)

Let I be a countable jump ideal in $\mathscr{D} = \langle \text{The Turing degrees}, \leq\rangle$ . The central theorem of this paper is: a is a uniform upper bound on I iff a computes the join of an I-exact pair whose double jump a (1) computes. We may replace "the join of an I-exact pair" in the above theorem by "a weak uniform upper bound on I". We also answer two minimality questions: the class of uniform (...) upper bounds on I never has a minimal member; if ∪ I = L α [ A] ∩ ω ω for α admissible or a limit of admissibles, the same holds for nice uniform upper bounds. The central technique used in proving these theorems consists in this: by trial and error construct a generic sequence approximating the desired object; simultaneously settle definitely on finite pieces of that object; make sure that the guessing settles down to the object determined by the limit of these finite pieces. (shrink)

Contents: Recursive Enumerability and the Jump Operator; On the Degrees Less Than 0'; A Simple Set Which Is Not Effectively Simple; The Recursively Enumerable Degrees Are Dense; Metarecursive Sets (with G Kreisel); Post's Problem, Admissible Ordinals and Regularity; On a Theorem of Lachlan and Marlin; A Minimal Hyperdegree (with R O Gandy); Measure-Theoretic Uniformity in Recursion Theory and Set Theory; Forcing with Perfect Closed Sets; Recursion in Objects of Finite Type; The a-Finite Injury Method (with S G Simpson); (...) Remarks Against Foundational Activity; Countable Admissible Ordinals and Hyperdegrees; The 1-Section of a Type n Object; The k-Section of a Type n Object; Post's Problem, Absoluteness and Recursion in Finite Types; Effective Bounds on Morley Rank; On the Number of Countable Models; Post's Problem in E-Recursion; The Limits of E-Recursive Enumerability; Effective Versus Proper Forcing. (shrink)

The principle of proportionality is seen as the highest peak of structural, logical thinking that enables balancing between constitutional principles and their interferences. So far, Alexy's weight formula has been the most advanced approach in structured balancing of proportionality stricto sensu, while this paper shows it as still too subjective. Despite judicial tests—or different, manifestly inappropriate reasonableness tests—proportionality stricto sensu hides some form of the jumping-to-conclusions bias, because the inference is made through a subjective lens. The paper presents structured legal (...) balancing (and hence reasoning) based on Bayes’ theorem. This paper, based on the connection between probability and hypothetical legal norms, transfers the four-part structure of proportionality into the relevant four-part structure of the Bayes tree. This transfer shows the first as flawed due to its failing to consider means that can have the same effects as the considered ones. Only by inclusion of the latter can the total probability of a considered case be established. Numerical proportionality à la Bayes can be further improved through the use of public-value weights that are obtained from surveys or online communities of people giving weights in the real time (collective wisdom). The Bayesian approach can also be used in adjudication as a control in assessing judicial standards in use. (shrink)

Since then we have been engaged in the development of such results of greater relevance to mathematical practice. In January, 1997 we presented some new results of this kind involving what we call “jump free” classes of finite functions. This Jump Free Theorem is treated in section 2.

We study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive (respectively, n-r-cohesive) if A is almost homogeneous for every computably enumerable (respectively, computable) 2-coloring of the n-element sets of natural numbers. (Thus the 1-cohesive and 1-r-cohesive sets coincide with the cohesive and r-cohesive sets, respectively.) We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we (...) show that for all n ≥ 2, there exists a Δ 0 n+1 n-cohesive set. We improve this result for n = 2 by showing that there is a Π 0 2 2-cohesive set. We show that the n-cohesive and n-r-cohesive degrees together form a linear, non-collapsing hierarchy of degrees for n ≥ 2. In addition, for n ≥ 2 we characterize the jumps of n-cohesive degrees as exactly the degrees ≥ 0 (n+1) and also characterize the jumps of the n-r-cohesive degrees. (shrink)

There is a family of questions in relativized complexity theory--weak analogs of the Friedberg Jump-Inversion Theorem--that are resolved by 1-generic sets but which cannot be resolved by essentially any weaker notion of genericity. This paper defines aw2-generic sets. i.e., sets which meet every dense set of strings that is r.e. in some incomplete r.e. set. Aw2-generic sets are very close to 1-generic sets in strength, but are too weak to resolve these questions. In particular, it is shown that (...) for any set X there is an aw2-generic set G such that $\mathbf{NP}^G \cap co-\mathbf{NP}^G \nsubseteq \mathbf{P}^{G \oplus X}$ . (On the other hand, if G is 1-generic, then $\mathbf{NP}^G \cap co-\mathbf{NP}^G \subseteq \mathbf{P}^{G \oplus \mathrm{SAT}}$ . where SAT is the NP-complete satisfiability problem [6].) This result runs counter to the fact that most finite extension constructions in complexity theory can be made effective. These results imply that any finite extension construction that ensures any of the Friedberg analogs must be noneffective, even relative to an arbitrary incomplete r.e. set. It is then shown that the recursion theoretic properties of aw2-generic sets differ radically from those of 1-generic sets: every degree above O' contains an aw2-generic set: no aw2-generic set exists below any incomplete r.e. set; there is an aw2-generic set which is the join of two Turing equivalent aw2-generic sets. Finally, a result of Shore is presented [30] which states that every degree above 0' is the jump of an aw2-generic degree. (shrink)

Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states (...) that every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.In this thesis, we will introduce a few tools which we use to prove several cases of Martin’s conjecture. It turns out that both these tools and these results on Martin’s conjecture have some interesting consequences both for Martin’s conjecture and for a few related topics.The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin’s conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin’s conjecture: that it holds for regressive functions on the hyperarithmetic degrees, that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.This last result has several interesting consequences for the study of Martin’s conjecture. In particular, it shows that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin’s conjecture, which we will discuss.The basis theorem that we use to prove these results also has some applications outside of Martin’s conjecture. We will use it to prove a few theorems related to Sacks’ question about whether it is provable in $\mathsf {ZFC}$ that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of $\mathsf {ZF}$, this holds for all partial orders of height two, but not for all partial orders of height three. Our proof also yields an analogous result for Borel partial orders and Borel embeddings in $\mathsf {ZF}$, which shows that the Borel version of Sacks’ question has a negative answer.We will end the thesis with a list of open questions related to Martin’s conjecture, which we hope will stimulate further research.prepared by Patrick Lutz.E-mail: [email protected]. (shrink)

Einstein wrote his famous sentence "God does not play dice with the universe" in a letter to Max Born in 1920. All experiments have confirmed that quantum mechanics is neither wrong nor “incomplete”. One can says that God does play dice with the universe. Let quantum mechanics be granted as the rules generalizing all results of playing some imaginary God’s dice. If that is the case, one can ask how God’s dice should look like. God’s dice turns out to be (...) a qubit and thus having the shape of a unit ball. Any item in the universe as well the universe itself is both infinitely many rolls and a single roll of that dice for it has infinitely many “sides”. Thus both the smooth motion of classical physics and the discrete motion introduced in addition by quantum mechanics can be described uniformly correspondingly as an infinite series converges to some limit and as a quantum jump directly into that limit. The second, imaginary dimension of God’s dice corresponds to energy, i.e. to the velocity of information change between two probabilities in both series and jump. (shrink)

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, (...) by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline. (shrink)

Let A and B be subsets of the reals. Say that A κ ≥ B, if there is a real a such that the relation "x ∈ B" is uniformly Δ 1 (a, A) in L[ ω x,a,A 1 , x,a,A]. This reducibility induces an equivalence relation $\equiv_\kappa$ on the sets of reals; the $\equiv_\kappa$ -equivalence class of a set is called its Kleene degree. Let K be the structure that consists of the Kleene degrees and the induced partial order (...) K ≥. A substructure of K that is of interest is P, the Kleene degrees of the Π 1 1 sets of reals. If sharps exist, then there is not much to P, as Steel [9] has shown that the existence of sharps implies that P has only two elements: the degree of the empty set and the degree of the complete Π 1 1 set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in P; in the context of V = L, Hrbacek has shown that P is dense and has no minimal pairs. The Hrbacek results led Simpson [6] to make the following conjecture: if V = L, then p forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Godel's maximal thin Π 1 1 set is the infimum of two strictly larger elements of P. The second main result deals with the notion of jump in K. Let A' be the complete Kleene enumerable set relative to A. Say that A is low-n if A (n) has the same degree as $\varnothing^{(n)}$ , and A is high-n if A (n) has the same degree as $\varnothing^{(n + 1)}$ . Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete Π 1 1 set in L. They have also shown that various other Π 1 1 sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x # does not exist, then there is an element of P that, for all n, is neither low-n nor high-n. In § 2, ZFC is used to show that, for all n, if A is Π 1 1 and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp]. (shrink)