A general algorithm is given for determining whether or not a given set of pair distributions allows for the construction of all the members of a specified set of higher-order distributions which return the given pair distributions as marginals. This mathematical question underlies studies of quantum correlation experiments such as those of Bell or of Clauser and Horne, or their higher-spin generalizations. The algorithm permits the analysis of rather intricate versions of such problems, in a form readily adaptable to the (...) computer. The general procedure is illustrated by simple derivations of the results of Mermin and Schwarz for the symmetric spin-1 and spin-3/2 Einstein-Podolsky-Rosen problems. It is also used to extend those results to the spin-2 and spin-5/2 cases, providing further evidence that the range of strange quantum theoretic correlations does not diminish with increasing s. The algorithm is also illustrated by giving an alternative derivation of some recent results on the necessity and sufficiency of the Clauser-Horne conditions. The mathematical formulation of the algorithm is given in general terms without specific reference to the quantum theoretic applications. (shrink)

PA is Peano Arithmetic. Pr(x) is the usual Σ1-formula representing provability in PA. A strong provability predicate is a formula which has the same properties as Pr(·) but is not Σ1. An example: Q is ω-provable if PA + ¬ Q is ω-inconsistent (Boolos [4]). In [5] Dzhaparidze introduced a joint provability logic for iterated ω-provability and obtained its arithmetical completeness. In this paper we prove some further modal properties of Dzhaparidze's logic, e.g., the fixed point property and the Craig (...) interpolation lemma. We also consider other examples of the strong provability predicates and their applications. (shrink)

Donald Davidson infamously claims that belief is in its nature veridical, and that skepticism is for this reason fundamentally incoherent. To those who take the issue of external world skepticism seriously, Davidson's arguments may seem to involve a conjuring trick. In particular, his invocation of an ‘omniscient interpreter’, whose intelligibility supposedly ensures that our beliefs must be largely true, has the air of incense and lantern-rubbing about it. Davidson's claim has received considerable critical response in the literature, almost all of (...) it negative. In my view, some commentators have indeed lit on a critical and controversial lemma in Davidson's argument, but this basic result has been obscured by being presented amidst an array of other criticisms that simply make no sense from a Davidsonian point of view. The aim of this paper is to clear away some of the confusion that stands in the way of a more productive evaluation of Davidson's important claim. (shrink)

Virtue ethics proposes a set of seven—four pagan virtues and three Christian—as a roughly adequate philosophical psychology. Hobbes tried to get along with one virtue, prudence, to which Rawls added a veiled virtue of justice. Nussbaum’s Frontiers of Justice adds the virtue of love. But in criticizing Rawls, she enunciates a “Nussbaum Lemma,” that is, a good society is unlikely to arise from over-simple models of ethical life. Since virtuous, flourishing societies are what we wish, we had better insert (...) the virtues, as she puts it, “from the start.” James Buchanan's constitutionalism, for example, solves moral hazards in a Nussbaumian world, but leaves hanging the ethical start. To start a project ending in constitutional citizenship—or human capabilities, or justice as fairness, or a Leviathan state, or the categorical imperative, or the greatest happiness of the greatest number—we need already an ethical actor, embodying the seven principal virtues. (shrink)

In this study, we investigate the effectiveness of a robust sampled-data H ∞ load frequency control scheme for power systems with randomly occurring time-varying delays. By using the input-delay technique, the sampled-data LFC model is reformulated as a continuous time-delay representation. Then, Bernoulli-distributed white noise sequences are used to describe randomly occurring time-varying delays in the sampled-data LFC model. Some less conservative conditions are achieved by utilizing the Lyapunov–Krasovskii functional and employing Jensen inequality and reciprocal convex combination lemma to (...) ensure the considered power system has mean-square asymptotic stability under the designed control scheme. The derived results are based on linear matrix inequalities that can readily be solved using the MATLAB LMI toolbox. The criteria obtained are used to analyze the upper bounds for time delays, and a comparison study to validate the efficacy of the presented method is presented. (shrink)

In this paper we propose to present from a new perspective some loci comunes of traditional logic. More exactly, we intend to show that some hypothetico-disjunctive inferences (i.e. the complex constructive dilemma, the complex destructive dilemma, the simple constructive dilemma, the simple destructive dilemma) and two hypothetico-categorical inferences (namely modus ponendo-ponens and modus tollendo-tollens) particularize two more abstract inferential structures: the constructive n-lemma and the destructive nlemma.

We show that there is a limit lemma for enumeration reducibility to 0 e ', analogous to the Shoenfield Limit Lemma in the Turing degrees, which relativises for total enumeration degrees. Using this and `good approximations' we prove a jump inversion result: for any set W with a good approximation and any set X< e W such that W≤ e X' there is a set A such that X≤ e A< e W and A'=W'. (All jumps are enumeration (...) degree jumps.) The degrees of sets with good approximations include the Σ0 2 degrees and the n-CEA degrees. (shrink)

In this article, we develop and clarify some of the basic combinatorial properties of the new notion of n-dependence recently introduced by Shelah. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, n-dependence corresponds to the inability to encode a random -partite -hypergraph with a definable edge relation. We characterize n-dependence by counting φ-types over finite sets, and in terms of the collapse of random ordered -hypergraph (...) indiscernibles down to order-indiscernibles. (shrink)

Rauszer and Sabalski proved in [2] that distributivity with respect to infi- nite joins and meets is a sucient and necessary condition making the RasiowaSikorski Lemma valid in distributive lattices. The main part of their proof is a direct construction of a required filter under distributivity. In this note we show that a generalization of the result can be obtained from the Rasiowa-Sikorski Lemma for Boolean algebras by using Gornemann’s result in [1] instead of a direct con- ¨ (...) struction. Suppose A is a distributive lattice and Q; R 2 A f;g. We call A complete if 8M 2 Q9 M 2 A and 8N 2 R9 F N 2 A. M 2 Q is -dis if 9 M 2 A and 8a 2 A a t M = m2M. N 2 R is F -dis if 9 F N 2 A and 8a 2 A a u F N = F n2N. is called distributive if every M 2 Q is -dis and every N 2 R is F -dis. Suppose A is complete and C; D A. By rC we mean the filter in A generated by C, in particular, let r; = ; = ;. is called complete if and , where 8M 2 Q 9m 2 MrC \ D[fmg = ;) 8N 2 R 9n 2 NrC[fng \ D = ;). (shrink)

We’ve now proved our key version of the First Theorem, Theorem 42. If T is the right kind of ω-consistent theory including enough arithmetic, then there will be an arithmetic sentence GT such that T ￿ GT and T ￿ ¬GT. Moreover, GT is constructed so that it is true if and only if unprovable-in T (so it is true). Now recall that, for a p.r. axiomatized theory T , Prf T(m, n) is the relation which holds just if m (...) is the super g.n. of a sequence of wffs that is a T proof of a sentence with g.n. n. This relation is p.r. decidable (see §25.4). Assuming T extends Q, it can capture any p.r. decidable relation, including Prf T (§22). So we can define.. (shrink)

The seminal Satisfiability Coding Lemma of Paturi, Pudlák, and Zane is a coding scheme for satisfying assignments of k-CNF formulas. We generalize it to give a coding scheme for implicants and use this generalized scheme to establish new structural and algorithmic properties of prime implicants of k-CNF formulas. Our first application is a near-optimal bound of n⋅ 3^{n(1-Ω(1/k))} on the number of prime implicants of any n-variable k-CNF formula. This resolves an open problem from the Ph.D. thesis of Talebanfard, (...) who proved such a bound for the special case of constant-read k-CNF formulas. Our proof is algorithmic in nature, yielding an algorithm for computing the set of all prime implicants - the Blake Canonical Form - of a given k-CNF formula. The problem of computing the Blake Canonical Form of a given function is a classic one, dating back to Quine, and our work gives the first non-trivial algorithm for k-CNF formulas. (shrink)

The focus of this paper is the incomputability of some topological functions using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝn, like closure, border, intersection, and derivative, and we prove for such functions results of Σ02-completeness and Σ03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for generic metric spaces (...) . Both lemmas define Σ02-computable functions which in some cases are even Σ02-complete. (shrink)

IΣ n andBΣ n are well known fragments of first-order arithmetic with induction and collection forΣ n formulas respectively;IΣ n 0 andBΣ n 0 are their second-order counterparts. RCA0 is the well known fragment of second-order arithmetic with recursive comprehension;WKL 0 isRCA 0 plus weak König's lemma. We first strengthen Harrington's conservation result by showing thatWKL 0 +BΣ n 0 is Π 1 1 -conservative overRCA 0 +BΣ n 0 . Then we develop some model theory inWKL 0 and (...) illustrate the use of formalized model theory by giving a relatively simple proof of the fact thatIΣ 1 provesBΣ n+1 to be Π n+2-conservative overIΣ n . Finally, we present a proof-theoretic proof of the stronger fact that theΠ n+2 conservation result is provable already inIΔ 0 + superexp. ThusIΣ n+1 proves 1-Con (BΣ n+1) andIΔ 0 +superexp proves Con (IΣ n )↔Con(BΣ n+1). (shrink)

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

In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems ${\cal T}^{\omega} :={\rm G}_n{\rm A}^{\omega} +{\rm AC}$ -qf $+\Delta$ , where (G $_n$ A $^{\omega})_{n \in {\Bbb N}}$ is a hierarchy of (weak) subsystems (...) of arithmetic in all finite types (introduced in [14]), AC-qf is the schema of quantifier-free choice in all types and $\Delta$ is a set of certain analytical principles which e.g. includes the binary König's lemma. We apply this method to show that the arithmetical closures of single instances of $\Pi^0_1$ -comprehension and -choice contribute to the growth of extractable bounds from proofs relative to ${\cal T}^\omega$ only by a primitive recursive functional in the sense of Kleene. In subsequent papers these results are widely generalized and the method is used to determine the arithmetical content of single sequences of instances of the Bolzano-Weierstraß principle for bounded sequences in ${\Bbb R}^d$ , the Ascoli-lemma and others. (shrink)

Within the technical frame supplied by the algebraic variety of diagonalizable algebras, defined by R. Magari in [2], we prove the following: Let T be any first-order theory with a predicate Pr satisfying the canonical derivability conditions, including Löb's property. Then any formula in T built up from the propositional variables $q,p_{1},...,p_{n}$ , using logical connectives and the predicate Pr, has the same "fixed-points" relative to q (that is, formulas $\psi (p_{1},...,p_{n})$ for which for all $p_{1},...,p_{n}\vdash _{T}\phi (\psi (p_{1},...,p_{n}),p_{1},...,p_{n})\leftrightarrow \psi (...) (p_{1},...,p_{n})$ ) of a formula $\phi ^{\ast}$ of the same kind, obtained from φ in an effective way. Moreover, such $\phi ^{\ast}$ is provably equivalent to the formula obtained from φ substituting with $\phi ^{\ast}$ itself all the occurrences of q which are under Pr. In the particular case where q is always under Pr in φ, $\phi ^{\ast}$ is the unique (up to provable equivalence) "fixed-point" of φ. Since this result is proved only assuming Pr to be canonical, it can be deduced that Löb's property is, in a sense, equivalent to Gödel's diagonalization lemma. All the results are proved more generally in the intuitionistic case. (shrink)

We prove several results giving lower bounds for the large cardinal strength of a failure of the singular cardinal hypothesis. The main result is the following theorem: Theorem. Suppose κ is a singular strong limit cardinal and 2κ λ where λ is not the successor of a cardinal of cofinality at most κ. If cf > ω then it follows that o λ, and if cf = ωthen either o λ or {α: K o α+n} is confinal in κ for (...) each n ε ω.We also prove several results which extend or are related to this result, notably Theorem. If 2ω ω1 then there is a sharp for a model with a strong cardinal.In order to prove these theorems we give a detailed analysis of the sequences of indiscernibles which come from applying the covering lemma to nonoverlapping sequences of extenders. (shrink)

This expository paper presents an application, to the modal logic S4, of the valuation semantics technique proposed by Loparić for the basic normal modal logic K. In previous works we presented a valuation semantics for the minimal temporal logic Kt and several other systems modal and temporal logic. How to deal with S4, however, was left as an open problem—although we arrived at a working definition of \(A_1,\ldots,A_n\) -valuations, we were not able to prove an important lemma for correctness. (...) In this paper we solve this, presenting valuations for S4. (shrink)

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ (...) ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}. (shrink)

Given a family${\cal C}$of infinite subsets of${\Bbb N}$, we study when there is a Borel function$S:2^{\Bbb N} \to 2^{\Bbb N} $such that for every infinite$x \in 2^{\Bbb N} $,$S\left \in {\Cal C}$and$S\left \subseteq x$. We show that the family of homogeneous sets as given by the Nash-Williams’ theorem admits such a Borel selector. However, we also show that the analogous result for Galvin’s lemma is not true by proving that there is an$F_\sigma $tall ideal on${\Bbb N}$without a Borel selector. (...) The proof is not constructive since it is based on complexity considerations. We construct a${\bf{\Pi }}_2^1 $tall ideal on${\Bbb N}$without a tall closed subset. (shrink)

The first aim of this paper is to prove a topological completeness theorem for a weak version of Stalnaker’s logic KB of knowledge and belief. The weak version of KB is characterized by the assumption that the axioms and rules of KB have to be satisfied with the exception of the axiom (NI) of negative introspection. The proof of a topological completeness theorem for weak KB is based on the fact that nuclei (as defined in the framework of point-free topology) (...) give rise to a profusion of topological belief operators that are compatible with the familiar topological knowledge operator Int. Thereby a canonical topological model for weak KB can be constructed. For this canonical model a truth lemma for the modal operators K and B holds such that a completeness theorem for weak KB can be proved in the familiar way. The second aim of this paper is to show that the topological interpretation of knowledge Int comes along with a complete Heyting algebra of belief operators N° that all fit the knowledge operator Int in the sense that the pairs (Int, N°) satisfy all axioms of weak KB. This amounts to a pluralistic relation between knowledge and belief: Knowledge does not fully determine belief, rather it designs a conceptual space for belief operators where different (competing) belief operators coexist that can be compared with each other. (shrink)

The characteristic sequence of hypergraphs Pn:n<ω associated to a formula φ, introduced in Malliaris [5], is defined by Pn=i≤nφ. We continue the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemerédi’s celebrated regularity lemma, can be naturally applied to the study of model-theoretic complexity via the characteristic sequence. Specifically, we relate classification-theoretic properties of φ and of the Pn to density between components in Szemerédi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemerédi regularity to (...) calibrate model-theoretic notions of independence by describing the depth of independence of a constellation of sets and showing that certain failures of depth imply Shelah’s strong order property SOP3; this sheds light on the interplay of independence and order in unstable theories. (shrink)

We study the formalization within sybsystems of second-order arithmetic of theorems concerning periodic points in dynamical systems on the real line. We show that Sharkovsky's theorem is provable in WKL0. We show that, with an additional assumption, Sharkovsky's theorem is provable in RCA0. We show that the existence for all n of n-fold iterates of continuous mappings of the closed unit interval into itself is equivalent to the disjunction of Σ02 induction and weak König's lemma.

Let f be a function from N to N that can not be computed in polynomial time, and let a be an element of a differential field K of characteristic 0. The problem of large powers is the set of tuples x̄ = (x 1 ,..., x n ) of K so that x 1 = a f(n) , and the problem of large roots is the set of tuples x̄ of K so that x f(n) 1 = a. These (...) are two examples of problems that the use of derivation does not allow to solve quicker. We show that the problem of large roots is not polynomial for the differential field K, even if we use a polynomial number of parameters, and that the problem of large powers is not polynomial for the differential field K, even for non-uniform complexity. The proofs use the polynomial stability (i.e., the elimination of parameters) of field of characteristic 0, shown by L. Blum. F. Cucker. M. Shub and S. Smale, and the reduction lemma, that transforms a differential polynomial in variables x̄ into a polynomial in variables x̄. and their derivatives. (shrink)

We develop a series of small infinitary epistemic logics to study deductive inference involving intra-/interpersonal beliefs/knowledge such as common knowledge, common beliefs, and infinite regress of beliefs. Specifically, propositional epistemic logics GL are presented for ordinal α up to a given αo so that GL is finitary KDn with n agents and GL allows conjunctions of certain countably infinite formulae. GL is small in that the language is countable and can be constructive. The set of formulae Lα is increasing up (...) to α = ω but stops at ω We present Kripke-completeness for GL for each α ≤ ω, which is proved using the Rasiowa–Sikorski lemma and Tanaka–Ono lemma. GL has a sufficient expressive power to discuss intra-/interpersonal beliefs with infinite lengths. As applications, we discuss the explicit definability of Axioms T, 4, 5, and of common knowledge in GL Also, we discuss the rationalizability concept in game theory in our framework. We evaluate where these discussions are done in the series GL, α ≤ ω. (shrink)

We examine the reverse mathematical strength of a variation of Hindman’s Theorem (HT) constructed by essentially combining HT with the Thin Set Theorem to obtain a principle that we call thin-HT. This principle states that every coloring c:N→N has an infinite set S⊆N whose finite sums are thin for c, meaning that there is an i with c(s)≠i for all nonempty sums s of finitely many distinct elements of S. We show that there is a computable instance of thin-HT such (...) that every solution computes ∅′, as is the case with HT, as shown by Blass, Hirst, and Simpson (1987). In analyzing this proof, we deduce that thin-HT implies ACA0 over RCA0+IΣ20. On the other hand, using Rumyantsev and Shen’s computable version of the Lovász Local Lemma, we show that there is a computable instance of the restriction of thin-HT to sums of exactly 2 elements such that any solution has diagonally noncomputable degree relative to ∅′. Hence there is a computable instance of this restriction of thin-HT with no Σ20 solution. (shrink)

By an unfounded chain for a function f:X→X we mean a sequence nω of elements of X s.t. fxn+1=xn for every n. Unfounded chains can be regarded as a generalization of fixed points, but on the other hand are linked with concepts concerning non-well-founded situations, as ungrounded sentences and the hypergame. In this paper, among other things, we prove a lemma in general topology, we exhibit an extensional recursive function from the set of sentences of PA into itself without (...) an unfounded chain, and we prove that every term in a Magari algebra has an unfounded chain. (shrink)

Anlambilimsel bileşimsellik ilkesi, herhangi bir ifadenin anlamının o ifadenin parçalarının anlamlarının bir fonksiyonu olduğunu bildirmektedir. İlke Gottlob Frege’nin dilsel anlamı fonksiyon argüman uygulaması olarak ele alan çalışmalarına dayanmaktadır. Bileşimselliğin, Richard Montague ile birlikte biçimsel anlambilim içerisinde merkezi bir rol aldığı görülmektedir. Bileşimsellik ilkesi, dilsel yapı ve anlamsal yapı arasında homomorfik bir ilişki bulunduğunu bildirmektedir. İlkenin savunucuları bileşimselliğin dilin sistematik ve üretken yapısına önemli katkılar sağladığını iddia etmektedirler. Wlodek Zadrozny, bu görüşe karşı olarak, bileşimselliğin dilin sistematik yapısına herhangi bir katkı sağlamadığını (...) iddia etmektedir. Zadrozny, iddiasını temellendirmek için, herhangi bir anlambilimsel yapının bileşimsel olarak kodlanabileceğini gösteren bir ispat ortaya atmıştır. Zadrozny herhangi bir anlambilimsel yapı için böyle bir anlam fonksiyonunun var olduğunu ise Peter Aczel’in iyi-yapılanmamış kümeler kuramına dayandırmaktadır. Çözüm Lemması bize böyle bir anlam fonksiyonunun var olduğunu bildirmektedir. Zadrozny’nin iddiasına karşı önemli bir itiraz bulunmaktadır. Elde edilen anlamsal yapının asıl anlamsal yapıyı kodlamak için yeterli olmadığı iddia edilmektedir. Bu iddianın temelinde eş anlamlılık olgusu bulunmaktadır. Eş anlamlı ifadelerin yer değiştirme ilkesine uymadığı, bileşimsel olmayan anlambilimsel yapıların elde edilen bileşimsel yapılar tarafından temsil edilemeyeceği iddia edilmektedir. Bu çalışmada, Zadrozny’nin ispatı incelenerek, eş anlamlılık üzerinden yapılan itiraz cevaplandırılmaktadır. İtirazın konusu olan eş anlamlılığın, anlambilimsel olarak korunması gereken bir özellik olmadığı iddia edilmektedir. (shrink)

We study the first-order consequences of Ramsey’s Theorem fork-colourings ofn-tuples, for fixed$n, k \ge 2$, over the relatively weak second-order arithmetic theory$\mathrm {RCA}^*_0$. Using the Chong–Mourad coding lemma, we show that in a model of$\mathrm {RCA}^*_0$that does not satisfy$\Sigma ^0_1$induction,$\mathrm {RT}^n_k$is equivalent to its relativization to any proper$\Sigma ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.We give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$for$n (...) \ge 3$. We show that they form a non-finitely axiomatizable subtheory of$\mathrm {PA}$whose$\Pi _3$fragment coincides with$\mathrm {B} \Sigma _1 + \exp $and whose$\Pi _{\ell +3}$fragment for$\ell \ge 1$lies between$\mathrm {I} \Sigma _\ell \Rightarrow \mathrm {B} \Sigma _{\ell +1}$and$\mathrm {B} \Sigma _{\ell +1}$. We also give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^2_k + \neg \mathrm {I} \Sigma _1$. In general, we show that the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^2_k$form a subtheory of$\mathrm {I} \Sigma _2$whose$\Pi _3$fragment coincides with$\mathrm {B} \Sigma _1 + \exp $and whose$\Pi _4$fragment is strictly weaker than$\mathrm {B} \Sigma _2$but not contained in$\mathrm {I} \Sigma _1$.Additionally, we consider a principle$\Delta ^0_2$-$\mathrm {RT}^2_2$which is defined like$\mathrm {RT}^2_2$but with both the$2$-colourings and the solutions allowed to be$\Delta ^0_2$-sets rather than just sets. We show that the behaviour of$\Delta ^0_2$-$\mathrm {RT}^2_2$over$\mathrm {RCA}_0 + \mathrm {B}\Sigma ^0_2$is in many ways analogous to that of$\mathrm {RT}^2_2$over$\mathrm {RCA}^*_0$, and that$\mathrm {RCA}_0 + \mathrm {B} \Sigma ^0_2 + \Delta ^0_2$-$\mathrm {RT}^2_2$is$\Pi _4$- but not$\Pi _5$-conservative over$\mathrm {B} \Sigma _2$. However, the statement we use to witness failure of$\Pi _5$-conservativity is not provable in$\mathrm {RCA}_0 +\mathrm {RT}^2_2$. (shrink)

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...) main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Löf random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n−g. Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic.Turning our attention to KL-stochasticity, we construct a non-empty class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree.Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α<1. This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively. (shrink)

Ifκis a measurable cardinal, let us say that a measure onκis aκ-complete nonprincipal ultrafilter onκ. IfUis a measure onκ, letjUbe the canonical elementary embedding ofVinto its Ultrapower UltU. Ifxis a set, say thatUmovesxwhenjU≠x; say thatκmovesxwhen some measure onκmovesx. Recall Kunen's lemma : “Every ordinal is moved only by finitely many measurable cardinals.” Kunen's proof and Fleissner's proof are essentially nonconstructive.The following proposition can be proved by using elementary facts about iterated ultrapowers.Proposition.Let ‹Un: n ∈ ω› be a sequence of (...) measures on a strictly increasing sequence ‹κn: n ∈ ω› of measurable cardinals. Let U = ‹ Wα: α < ω2›, where Wωm + n= Um. Then, for each θ inUltU,if E is the support of θ inUltU,then, for all m ∈ ω, Ummoves θ iff E ∩ [ωm, ω)≠ ∅. (shrink)

Let φ be a monadic second order sentence about a finite structure from a class K which is closed under disjoint unions and has components. Compton has conjectured that if the number of n element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities ν(φ) (μ(φ) respectively) for φ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the (...) number of single component K-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates. (shrink)

We present here an approach to the fine structure of L based solely on elementary model theoretic ideas, and illustrate its use in a proof of Global Square in L. We thereby avoid the Lévy hierarchy of formulas and the subtleties of master codes and projecta, introduced by Jensen [3] in the original form of the theory. Our theory could appropriately be called ”Hyperfine Structure Theory”, as we make use of a hierarchy of structures and hull operations which refines the (...) traditional Lα -or Jα-sequences with their Σn-hull operations.§1. Introduction. In 1938, K. Gödel defined the model L of set theory to show the relative consistency of Cantor's Continuum Hypothesis. L is defined as a unionof initial segments which satisfy: L0 = ∅, Lλ = ∪α<λLα for limit ordinals λ, and, crucially, Lα + 1 = the collection of 1st order definable subsets of Lα. Since every transitive model of set theory must be closed under 1st order definability, L turns out to be the smallest inner model of set theory. Thus it occupies the central place in the set theoretic spectrum of models.The proof of the continuum hypothesis in L is based on the very uniform hierarchical definition of the L-hierarchy. The Condensation Lemma states that if π : M → Lα is an elementary embedding, M transitive, then some ; the lemma can be proved by induction on α. If a real, i.e., a subset of ω, is definable over some Lα,then by a Löwenheim-Skolem argument it is definable over some countable M as above, and hence over some, < ω1. This allows one to list the reals in L in length ω1 and therefore proves the Continuum Hypothesis in L. (shrink)

Propositional dynamic logic is complete but not compact. As a consequence, strong completeness requires an infinitary proof system. In this paper, we present a short proof for strong completeness of $$\mathsf{PDL}$$ relative to an infinitary proof system containing the rule from [α; β n ]φ for all $$n \in {\mathbb{N}}$$, conclude $$[\alpha;\beta^*] \varphi$$. The proof uses a universal canonical model, and it is generalized to other modal logics with infinitary proof rules, such as epistemic knowledge with common knowledge. Also, we (...) show that the universal canonical model of $$\mathsf{PDL}$$ lacks the property of modal harmony, the analogue of the Truth lemma for modal operators. (shrink)

Community-based healthcare organisations manage competing, and often conflicting, priorities. These conflicts can arise from the multiple roles these organisations take up, and from the diverse range of stakeholders to whom they must be responsive. Often such conflicts may be titled conflicts of interest; however, what precisely constitutes such conflicts and what should be done about them is not always clear. Clarity about the duties owed by organisations and the roles they assume can help identify and manage some of these conflicts. (...) Taking divisions of general practice in Australia as an example, this paper sets out to distinguish two main types of conflicts of interest, so that they may be more clearly identified and more effectively managed. (shrink)

Purpose. This article is devoted to the case study of relevant linguacultural stereotypes of the particular organization’s managerial culture and based on corresponding results the inquiry of the discourses formation features associated with the lexico-semantic meanings dispersion of (Foucault). -/- Methods and Procedure of Research. Top managers of a large Ukrainian enterprise (67 respondents) were asked to arbitrarily describe the following concepts – “manager”, “subordinate”, “managerial style”. Each concept was differentiated according to the principle of the lexico-semantic opposition (“productive – (...) counterproductive”). The obtained set of texts was lemmatized and a frequency analysis of the lemmas was carried out as well. Collocations were also evaluated, in particular, repeated n-grams were identified. In the further analysis were used all detected n-grams and those lemmas, the observed frequencies of which statistically significantly exceeded the expected ones. -/- Results. Discourse formation features are determined by the paradigmatic relations of lexico-semantic units (words) and their semantic linear compatibility. The paradigmatic dispersion of a discourse is represented by the quality of connections between lemmas according to the criterion of the paradigm types to be found. Also informative is the assessment of the lemmas number (granularity of the discourse) and the spectrum diversity of paradigmatic relations in the discourse. These parameters reflect the properties of homogeneity/complexity of discourse meanings dispersion. The syntagmatic dissemination of discourse is manifested by the features of the words semantic linear interrelationship in each n-gram. This parameter reflects the quality of rationalizations (verbal-logical chains) associated with the corresponding discourses. The length of n-grams (the number of words) is also indicative – the higher n, the more differentiated the discourse is and vice versa. Matching the words semantics in n-grams with lemmas allows one to draw a conclusion regarding the internal consistency (integration) of the discourse. -/- Conclusions. Psycholinguistic tools can be effectively used in an organizational phenomena study. In particular, the frequency analysis of lemmas, their lexico-semantic evaluation, as well as the qualitative analysis of n-grams in the problem-targeted texts of respondents allows one to solve applied research issues related to the assessment of current linguacultural trends in an organization and understanding their possible causes. Managerial culture, as a linguacultural phenomenon, is represented by a set of stably reproduced discourses in the process of the organization’s functioning. At the same time, discourses are constituted by the dispersion of meanings (words), which is being realized in two linguistic dimensions – paradigmatic and syntagmatic ones. (shrink)

This note explores the common core of constructive, intuitionistic, recursive and classical analysis from an axiomatic standpoint. In addition to clarifying the relation between Kleene’s and Troelstra’s minimal formal theories of numbers and number-theoretic sequences, we propose some modified choice principles and other function existence axioms which may be of use in reverse constructive analysis. Specifically, we consider the function comprehension principles assumed by the two minimal theories EL and M, introduce an axiom schema CFd asserting that every decidable property (...) of numbers has a characteristic function, and use it to describe a precise relationship between the minimal theories. We show that the axiom schema AC00 of countable choice can be decomposed into a monotone choice schema AC00m (which guarantees that every Cauchy sequence has a modulus) and a bounded choice schema BC00. We relate various (classically correct) axiom schemas of continuous choice to versions of the bar and fan theorems, suggest a constructive choice schema AC1/2,0 (which incidentally guarantees that every continuous function has a modulus of continuity), and observe a constructive equivalence between restricted versions of the fan theorem and correspondingly restricted bounding axioms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${AB_{1/2,0}^{2^{\mathbb{n}}}}$$\end{document}. We also introduce a version WKL!! of Weak König’s Lemma with uniqueness which is intermediate in strength between WKL and the decidable fan theorem FTd. (shrink)