ABSTRACT Quine insisted that the satisfaction of an open modalised formula by an object depends on how that object is described. Kripke's ‘objectual’ interpretation of quantified modal logic, whereby variables are rigid, is commonly thought to avoid these Quinean worries. Yet there remain residual Quinean worries for epistemic modality. Theorists have recently been toying with assignment-shifting treatments of epistemic contexts. On such views an epistemic operator ends up binding all the variables in its scope. One might worry that (...) this yields the undesirable result that any attempt to ‘quantify in’ to an epistemic environment is blocked. If quantifying into the relevant constructions is vacuous, then such views would seem hopelessly misguided and empirically inadequate. But a famous alternative to Kripke's semantics, namely Lewis' counterpart semantics, also faces this worry since it also treats the boxes and diamonds as assignment-shifting devices. As I'll demonstrate, the mere fact that a variable is bound is no obstacle to binding it. This provides a helpful lesson for those modelling de re epistemic contexts with assignment sensitivity, and perhaps leads the way toward the proper treatment of binding in both metaphysical and epistemic contexts: Kripke for metaphysical modality, Lewis for epistemic modality. (shrink)

The paper purports to show, against Quine, that one can construct a language , which results from the extension of the theory of truth functions by introducing sentence letter quantification. Next a semantics is provided for this language. It is argued that the quantification is neither substitutional nor requires one to consider the sentence letters as taking entities as values.

Potts et seq. presents an analysis of gap-containing supplements where the gap is modelled as a variable over the semantic type of the constituent that the as-clause adjoins to. This much allows the meaning of the gap to be resolved purely compositionally, by defining as as a function that allows the anchor to bind the gap variable. This article presents a class of as-clauses where Potts’s analysis seems to break down, in that the gap cannot be modelled as a variable (...) over the semantic type of the anchor. I propose that these cases can be unified with those in Potts’s work, as well as a larger class of ellipsis phenomena, by assuming that, under certain conditions, surface gaps are composite entities, containing a bound variable and a free variable that are resolved independently of each other. The bound variable is bound by the anchor, and the free variable is resolved by anaphora to a salient discourse object. (shrink)

Consider the bounded variable logics $L^k_{\infty\omega}$ (with k variable symbols), and $C^k_{\infty\omega}$ (with k variables in the presence of counting quantifiers $\exists^{\geq m}$ ). These fragments of infinitary logic $L_{\infty\omega}$ are well known to provide an adequate logical framework for some important issues in finite model theory. This paper deals with a translation that associates equivalence of structures in the k-variable fragments with bisimulation equivalence between derived structures. Apart from a uniform and intuitively appealing treatment of these equivalences, this (...) approach relates some interesting issues for the case of an arbitrary number of variables to the case of just three variables. Invertibility of the invariants for $\equiv_{C^3}$ , in particular, would imply a positive answer to the tempting conjecture that fixed-point logic with counting captures $\bigcup_k$ Ptime $\cap C^k_{\infty\omega}$. (shrink)

The core question behind this Frontiers research topic is whether explaining linguistic phenomena requires appeal to properties of human cognition that are specialized to language. We argue here that investigating this issue requires taking linguistic research results seriously, and evaluating these for domain-specificity. We present a particular empirical phenomenon, bound variable interpretations of pronouns dependent on a quantifier phrase, and argue for a particular theory of this empirical domain that is couched at a level of theoretical depth which allows (...) its principles to be evaluated for domain-specialization. We argue that the relevant principles are specialized when they apply in the domain of language, even if analogs of them are plausibly at work elsewhere in cognition or the natural world more generally. So certain principles may be specialized to language, though not, ultimately, unique to it. Such specialization is underpinned by ultimately biological factors, hence part of UG. (shrink)

We consider a one-dimensional translation invariant point process of density one with uniformly bounded variance of the number NI of particles in any interval I. Despite this suppression of fluctuations we obtain a large deviation principle with rate function F(ρ) −L−1 log Prob(ρ) for observing a macroscopic density profile ρ(x), x ∈ [0, 1], corresponding to the coarse-grained and rescaled density of the points of the original process in an interval of length L in the limit L → ∞. F(ρ) (...) is not convex and is discontinuous at ρ ≡ 1, the typical profile. (shrink)

The presence of contrastive focus on pronouns interpreted as bound variables is puzzling. Bound variables do not refer, and it is therefore unclear how two of them can be made to contrast with each other. It is argued that this is a problem for both alternative-based accounts such as Rooth’s (Nat Lang Semantics 1:75–116, 1992) and givenness-based ones such as Schwarzschild’s (Nat Lang Semantics 7:141–177, 1999). The present paper shows that previous approaches to this puzzle face (...) an empirical problem, namely the co-occurrence of additive too and focus on bound pronouns. Our account is based on the idea that the alternatives introduced by focused bound pronouns denote individuals. Putting forward the novel concept of compositional reconstruction, we show that a suitably modified Roothian analysis of focus licensing allows us to get bound pronouns to contrast with other bound pronouns. The reason for this is that the number of potential alternatives increases. We also suggest a modification of Rooth’s ~-operator: contrastiveness becomes a requirement of the operator, which is modelled as a definedness condition. It is argued that in the case of focused bound pronouns a ~-operator is necessarily inserted in the scope of the quantifier. If this is on the right track, it follows that the phenomenon of focused bound pronouns warrants both an operator interpreting focus as well as a semantic value for the contribution of focus. Any givenness-based analysis must include these two ingredients as well; we suggest a way in which this can be implemented more or less straightforwardly. (shrink)

(Though it is now known that many pronouns once lumped under ”bound variables” are in fact referential indefinites or other phenomena better accounted for in a DRT-like view of referents, there remain many true instances of sentenceinternally bound anaphora: this talk concerns only the latter.) Almost all versions of categorial grammar (CG) are differentiated from other syntactic theories in treating a multi-argument verb as an Ò-place predicate phrase (PrdP) that combines with a NP or other argument to (...) yield a (Ò-1)-place PrdP (which, if (n–1) 1, then combines with another argument to yield a ´Ò ¾µ-place PrdP, until a sentence (0-place PrdP) results) – a ”curried function” account of argument structure. (In CG, Ú ÔÜ ÒÔ · ÒÔ Üµ. A number of CG analyses of Ú Ô bound anaphora (Bach & Partee 1980, Chierchia 1988, Szabolcsi 1992, Jacobson 1991, Dowty 1993, Jacobson 1999), though otherwise diverse, have in common that they treat anaphoric binding as a process that affects (only) a predicate phrase (PrdP) — usually (finite or non-finite) Ú Ô, else ÚÔ ÒÔ — by binding an internal pronoun, i.e. ”binding at the VP level”; semantically, this is usually indicated ´Üµ . The result of this binding is that the next argument the.. (shrink)

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects (...) in the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as "mapping functions." The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as "capturing," "bottom," or "continuity." Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are. (shrink)

In a homogeneous jury, the votes are exchangeable correlated Bernoulli random variables. We derive the bounds on a homogeneous jury’s competence as the minimum and maximum probability of the jury being correct, which arise due to unknown correlations among the votes. The lower bound delineates the downside risk associated with entrusting decisions to the jury. In large and not-too-competent juries the lower bound may fall below the success probability of a fair coin flip—one half, while the upper (...) bound may not reach a certainty. We also derive the bounds on the voting power of an individual juror as the minimum and maximum probability of her/his casting a decisive vote. The maximum is less than one, while the minimum of zero can be attained for infinitely many combinations of distribution moments. (shrink)

MILLIANISM and DESCRIPTIVISM are without question the two most prominent views with respect to the semantics of proper names. However, debates between MILLIANS and DESCRIPTIVISTS have tended to focus on a fairly narrow set of linguistic data and an equally narrow set of problems, mainly how to solve with Frege's puzzle and how to guarantee rigidity. In this article, the author focuses on a set of data that has been given less attention in these debates—namely, so-called predicative uses, bound (...) uses, and shifted uses of names. The author first shows that these data points seem to favor a DESCRIPTIVIST view over a MILLIAN view, but the author then introduces an alternative view of names that not only provides a simple and elegant way of dealing with the data, but also retains rigidity without becoming subject to the problems raised by Frege's puzzle. This is the view that names are variables, also called VARIABILISM. (shrink)

Model RB is a model of random constraint satisfaction problems, which exhibits exact satisfiability phase transition and many hard instances, both experimentally and theoretically. Benchmarks based on Model RB have been successfully used by various international algorithm competitions and many research papers. In a previous work, Xu and Li defined two notions called i-constraint assignment tuple and flawed i-constraint assignment tuple to show an exponential resolution complexity of Model RB. These two notions are similar to some kind of consistency in (...) constraint satisfaction problems, but seem different from all kinds of consistency so far known in literatures. In this paper, we explicitly define this kind of consistency, called variable-centered consistency, and show an upper bound on a parameter in Model RB, such that up to this bound the typical instances of Model RB are variable-centered consistent. (shrink)

Certain anaphoric forms are widely supposed to give rise to ‘de se’ interpretations. Castanteda (1966a/b, 1967) argues that intensive reflexive anaphors such as ‘he himself’ and ‘she herself’ act as devices for the indirect report of essentially ‘first person’ contents when they occur with singular antecedents. In this paper, I argue that first and third person pronouns that occur as anaphors on c-commanding quantified antecedents (so-called ‘bound variable pronouns’) also give rise to de se interpretations. I draw out a (...) problem that this observation raises for a well-accepted account according to which bound pronouns occur as featureless variables. I argue that the best way to account for de se interpretations of bound first and third person pronouns is to abandon the view that pronouns lack features when bound. I offer a new account of bound pronominal anaphora which assigns the features of pronouns a crucial role in deriving bound readings. (shrink)

If quantum mechanics is correct and there is a finite upper bound for the speed of causal influences (e.g., the speed of light), then quantum mechanics is complete (i.e., it does not admit a more detailed description in terms of hidden variables). Here I show that the conclusion holds if we replace the assumption of bounded velocity by the assumption that there is a finite upper bound to the memory a finite physical system can store (e.g., the (...) Holevo bound). On the way to this conclusion I first show that, although the quantum violation of an inequality valid for any non-contextual model can be explained with a classical contextual model, the inequality can be promoted to a Bell inequality in which, if the model is contextual, then it must be also non-local. This suggests that there is something non-classical in any contextual explanation of the individual systems, and leads us to the question of which are the minimum resources (and specifically memory) any contextual explanation should consume. (shrink)

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results support (...) this claim.) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

Extropy, as a complementary dual of entropy, has been discussed in many works of literature, where it is declared for other measures as an extension of extropy. In this article, we obtain the extropy of generalized order statistics via its dual and give some examples from well-known distributions. Furthermore, we study the residual and past extropy for such models. On the other hand, based on Farlie–Gumbel–Morgenstern distribution, we consider the residual extropy of concomitants of m-generalized order statistics and present this (...) measure with some additional features. In addition, we provide the upper bound and stochastic orders of it. Finally, nonparametric estimation of the residual extropy of concomitants of m-generalized order statistics is included using simulated and real data connected with COVID-19 virus. (shrink)

In the present paper we give a precise definition of a hidden-variable theory for quantum mechanics, whereby we adopt the weakest possible definition of a hidden-variable theory, which is compatible with the assumption that the bounded observables of a quantum mechanical system are represented by the elements of the real part Ar of a W*-algebra A (of the most general type) and the states are represented by the “normal states” (in the mathematical sense) of A. We then go on to (...) show that an example put forward by Bell in 1966 satisfies our definition (Sec. 2). Finally we make use of Bell's famous theorem to show that for a sufficiently non-commutative W*-algebra A no hidden-variable theory in our sense exists (Theorem 3.3 and its corollaries). (shrink)

When real-valued utilities for outcomes are bounded, or when all variables are simple, it is consistent with expected utility to have preferences defined over probability distributions or lotteries. That is, under such circumstances two variables with a common probability distribution over outcomes – equivalent variables – occupy the same place in a preference ordering. However, if strict preference respects uniform, strict dominance in outcomes between variables, and if indifference between two variables entails indifference between their (...) difference and the status quo, then preferences over rich sets of unbounded variables, such as variables used in the St. Petersburg paradox, cannot preserve indifference between all pairs of equivalent variables. In such circumstances, preference is not a function only of probability and utility for outcomes. Then the preference ordering is not defined in terms of lotteries. (shrink)

-/- A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. -/- Kalish-Montague proposed using vbtos to formalize definite descriptions, set abstracts {x: F}, minimalization in recursive function theory, etc. However, they gave no sematics for vbtos. Hatcher gave a semantics but one that has flaws. We give a (...) correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture was later proved independently by the authors and by Newton da Costa. -/- The expression (vy:F) is called a variable bound term (vbt). In case F has only y free, (vy:F) has the syntactic propreties of an individual constant; and under a suitable interpretation of the language vy:F) denotes an individual. By a semantic analysis of vbtos we mean a proposal for amending the standard notions of (1) "an interpretation o f a first -order language" and (2) " the denotation of a term under an interpretation and an assignment", such that (1') an interpretation o f a first -order language associates a set-theoretic structure with each vbto and (2') under any interpretation and assignment each vb t denotes an individual. (shrink)

As a result of these restrictions, an implementation of L [subscript lambda] does not need to implement full higher-order unification. Instead, an extension to first-order unification that respects bound variable names and scopes is all that is required. Such unification problems are shown to be decidable and to possess most general unifiers when unifiers exist. A unification algorithm and logic programming interpreter are described and proved correct. Several examples of using L[subscript lambda] as a meta-programming language are presented.

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order (...) logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

We are used to the idea that computers operate on numbers, yet another kind of data is equally important: the syntax of formal languages, with variables, binding, and alpha-equivalence. The original application of nominal techniques, and the one with greatest prominence in this paper, is to reasoning on formal syntax with variables and binding. Variables can be modelled in many ways: for instance as numbers (since we usually take countably many of them); as links (since they may (...) `point' to a binding site in the term, where they are bound); or as functions (since they often, though not always, represent `an unknown'). None of these models is perfect. In every case for the models above, problems arise when trying to use them as a basis for a fully formal mechanical treatment of formal language. The problems are practical—but their underlying cause may be mathematical. The issue is not whether formal syntax exists, since clearly it does, so much as what kind of mathematical structure it is. To illustrate this point by a parody, logical derivations can be modelled using a Gödel encoding (i.e., injected into the natural numbers). It would be false to conclude from this that proof-theory is a branch of number theory and can be understood in terms of, say, Peano's axioms. Similarly, as it turns out, it is false to conclude from the fact that variables can be encoded e.g., as numbers, that the theory of syntax-with-binding can be understood in terms of the theory of syntax-without-binding, plus the theory of numbers (or, taking this to a logical extreme, purely in terms of the theory of numbers). It cannot; something else is going on. What that something else is, has not yet been fully understood. In nominal techniques, variables are an instance of names, and names are data. We model names using urelemente with properties that, pleasingly enough, turn out to have been investigated by Fraenkel and Mostowski in the first half of the 20th century for a completely different purpose than modelling formal language. What makes this model really interesting is that it gives names distinctive properties which can be related to useful logic and programming principles for formal syntax. Since the initial publications, advances in the mathematics and presentation have been introduced piecemeal in the literature. This paper provides in a single accessible document an updated development of the foundations of nominal techniques. This gives the reader easy access to updated results and new proofs which they would otherwise have to search across two or more papers to find, and full proofs that in other publications may have been elided. We also include some new material not appearing elsewhere. (shrink)

We prove an exponential lower bound on the size of proofs in the proof system operating with ordered binary decision diagrams introduced by Atserias, Kolaitis and Vardi [2]. In fact, the lower bound applies to semantic derivations operating with sets defined by OBDDs. We do not assume any particular format of proofs or ordering of variables, the hard formulas are in CNF. We utilize (somewhat indirectly) feasible interpolation. We define a proof system combining resolution and the OBDD (...) proof system. (shrink)

We obtain a nonasymptotic lower time bound for deciding sentences of bounded second-order arithmetic with respect to a form of the random access machine with stored programs. More precisely, let P be an arbitrary program for the model under consideration which recognized true formulas with a given range of parameters. Let p be the length of P and let N be an arbitrary natural number. We show how to construct a formula G with one free variable with length not (...) more than 400 symbols and a value f of x such that the time required by P to decide the truth of G is at least N+1 steps. Furthermore, the G constructed does not depend on P and the length of f is less than p+400. (shrink)

We introduce frame-equivalence games tailored for reasoning about the size, modal depth, number of occurrences of symbols and number of different propositional variables of modal formulae defining a given frame property. Using these games, we prove lower bounds on the above measures for a number of well-known modal axioms; what is more, for some of the axioms, we show that they are optimal among the formulae defining the respective class of frames.

Extremist views on normative rationality fail to address differences in responding owing to intellectual ability or epistemic self-regulation. Individual difference research thus raises serious questions concerning the scientific utility of universal rationality and universal irrationality theories. However, recent data indicate that computational capacity theories do not account adequately for within-subject variability in normative responding, memory-reasoning independence, and instances of ability-normative reasoning independence.

Progress in neuroscience – notably, on the dynamic functions of neural networks – has deepened our understanding of decision‐making, acquisition of character and temperament, and the development of moral dispositions. The evolution of our cerebral architecture is both genetic and epigenetic: the nervous system develops in continuous interaction with the immediate physical and socio‐cultural environments. Each individual has a unique cerebral identity even in the relative absence of genetic distinction, and the development of this identity is strongly influenced by social (...) and cultural environments leaving major traces in the connectivity of the brain. This interaction introduces important elements of variability and plasticity. Synaptic epigenetic theories of cultural and social imprinting on our brain architecture suggest the possibility that we can be “epigenetically proactive” and adapt our social structures, in both the short and the long term, to benefit and constructively interact with the ever‐developing neuronal architecture of our brains. Epigenetic proaction can be described as a way to socially steer evolution by influencing the cultural imprints to be stored in our brains. The purpose of this article is to present, in a historical and ideological light, the idea that we may culturally shape the developing brain, and discuss some key risks and benefits of this endeavour. The article is a contribution to neuroethics. (shrink)

By combining experimental interventions with search procedures for graphical causal models we show that under familiar assumptions, with perfect data, N - 1 experiments suffice to determine the causal relations among N > 2 variables when each experiment randomizes at most one variable. We show the same bound holds for adaptive learners, but does not hold for N > 4 when each experiment can simultaneously randomize more than one variable. This bound provides a type of ideal for (...) the measure of success of heuristic approached in active learning methods of casual discovery, which currently use less informative measures. (shrink)

Combinatory logic (Curry and Feys 1958) is a “variable-free” alternative to the lambda calculus. The two have the same expressive power but build their expressions differently. “Variable-free” semantics is, more precisely, “free of variable binding”: it has no operation like abstraction that turns a free variable into a bound one; it uses combinators—operations on functions—instead. For the general linguistic motivation of this approach, see the works of Steedman, Szabolcsi, and Jacobson, among others. The standard view in linguistics is that (...) reflexive and personal pronouns are free variables that get bound by an antecedent through some coindexing mechanism. In variable free semantics the same task is performed by some combinator that identifies two arguments of the function it operates on (a duplicator). This combinator may be built into the lexical semantics of the pronoun, into that of the antecedent, or it may be a free-floating operation applicable to predicates or larger chunks of texts, i.e. a typeshifter. This note is concerned with the case of cross-sentential anaphora. It adopts Hepple’s and Jacobson’s interpretation of pronouns as identity maps and asks how this can be extended to the cross-sentential case, assuming the dynamic semantic view of anaphora. It first outlines the possibility of interpreting indefinites that antecede non-ccommanded pronouns as existential quantifiers enriched with a duplicator. Then it argues that it is preferable to use the duplicator as a type-shifter that applies “on the fly”. The proposal has consequences for two central ingredients of the classical dynamic semantic treatment: it does away with abstraction over assignments and with treating indefinites as inherently existentially quantified. However, cross-sentential anaphora remains a matter of binding, and the idea of propositions as context change potentials is retained. (shrink)

Local hidden-variable model of singlet-state correlations discussed in Czachor (Acta Phys Polon A 139:70, 2021a) is shown to be a particular case of an infinite hierarchy of local hidden-variable models based on an infinite hierarchy of calculi. Violation of Bell-type inequalities can be interpreted as a ‘confusion of languages’ problem, a result of mixing different but neighboring levels of the hierarchy. Mixing of non-neighboring levels results in violations beyond the Tsirelson bounds.

We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a (...) finite model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

Expressions such as English himself are interpreted as locally bound anaphors in certain syntactic environments and are exempt from the binding conditions in others. This article provides a unified semantics for himself in both of these uses. Their difference is reduced to the interaction with the syntactic environment. The semantics is based on an extension of the treatment of pronominals in variable-free semantics. The adoption of variable free semantics is inspired by the existence of proxy-readings, which motivate an analysis (...) based on Skolem functions. It is explained why certain anaphor types allow proxy-readings whereas others do not. (shrink)

Contemporary versions of Bell’s argument against local hidden variable (LHV) theories are based on the Clauser Horne Shimony and Holt (CHSH) inequality, and various attempts to generalize it. The amount of violation of these inequalities cannot exceed the bound set by the Grothendieck constants. However, if we go back to the original derivation by Bell, and use the perfect anticorrelation embodied in the singlet spin state, we can go beyond these bounds. In this paper we derive two-particle Bell inequalities (...) for traceless two-outcome observables, whose violation in the singlet spin state go beyond the Grothendieck constant both for the two and three dimensional cases. Moreover, creating a higher dimensional analog of perfect correlations, and applying a recent result of Alon and his associates (Invent. Math. 163 499 (2006)) we prove that there are two-particle Bell inequalities for traceless two-outcome observables whose violation increases to in…nity as the dimension and number of measurements grow. Technically these result are possible because perfect correlations (or anti-correlations) allow us to transport the indices of the inequality from the edges of a bipartite graph to those of the complete graph. Finally, it is shown how to apply these results to mixed Werner states, provided that the noise does not exceed 20%. (shrink)

Instrumental variables allow for quantification of cause and effect relationships even in the absence of interventions. To achieve this, a number of causal assumptions must be met, the most important of which is the independence assumption, which states that the instrument and any confounding factor must be independent. However, if this independence condition is not met, can we still work with imperfect instrumental variables? Imperfect instruments can manifest themselves by violations of the instrumental inequalities that constrain the set (...) of correlations in the scenario. In this article, we establish a quantitative relationship between such violations of instrumental inequalities and the minimal amount of measurement dependence required to explain them for the case of discrete observed variables. As a result, we provide adapted inequalities that are valid in the presence of a relaxed measurement dependence assumption in the instrumental scenario. This allows for the adaptation of existing and new lower bounds on the average causal effect for instrumental scenarios with binary outcomes. Finally, we discuss our findings in the context of quantum mechanics. (shrink)

We extend a result of Dubins [3] from bounded to unbounded random variables. Dubins [3] showed that a finitely additive expectation over the collection of bounded random variables can be written as an integral of conditional expectations (disintegrability) if and only if the marginal expectation is always within the smallest closed interval containing the conditional expectations (conglomerability). We give a sufficient condition to extend this result to the collection Z of all random variables that have finite expected (...) value and whose conditional expectations are finite and have finite expected value. The sufficient condition also allows the result to extend some, but not all, subcollections of Z. We give an example where the equivalence of disintegrability and conglomerability fails for a subcollection of Z that still contains all bounded random variables. (shrink)

We extend de Finetti’s (1974) theory of coherence to apply also to unbounded random variables. We show that for random variables with mandated infinite prevision, such as for the St. Petersburg gamble, coherence precludes indifference between equivalent random quantities. That is, we demonstrate when the prevision of the difference between two such equivalent random variables must be positive. This result conflicts with the usual approach to theories of Subjective Expected Utility, where preference is defined over lotteries. In (...) addition, we explore similar results for unbounded variables when their previsions, though finite, exceed their expected values, as is permitted within de Finetti’s theory. In such cases, the decision maker’s coherent preferences over random quantities is not even a function of probability and utility. One upshot of these findings is to explain further the differences between Savage’s theory (1954), which requires bounded utility for non-simple acts, and de Finetti’s theory, which does not. And it raises a question whether there is a theory that fits between these two. (shrink)

In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$ -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$ s representing clauses of the initial formula. All $\text {OBDD}$ s in such proofs have the same order of variables. We initiate the study of $\text {OBDD}$ based proof systems that additionally contain a rule that allows changing the order in $\text {OBDD}$ s. At first we consider a (...) proof system $\text {OBDD}$ that uses the conjunction rule and the rule that allows changing the order. We exponentially separate this proof system from $\text {OBDD}$ proof system that uses only the conjunction rule. We prove exponential lower bounds on the size of $\text {OBDD}$ refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for $\text {OBDD}$ proofs and the second one extends the result of Tveretina et al. from $\text {OBDD}$ to $\text {OBDD}$.In 2001 Aguirre and Vardi proposed an approach to the propositional satisfiability problem based on $\text {OBDD}$ s and symbolic quantifier elimination $ algorithms). We augment these algorithms with the operation of reordering of variables and call the new scheme $\text {OBDD}$ algorithms. We notice that there exists an $\text {OBDD}$ algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time, but we show that there are formulas representing systems of linear equations over $\mathbb {F}_2$ that are hard for $\text {OBDD}$ algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over $\mathbb {F}_2$ that correspond to checksum matrices of error correcting codes. (shrink)

We study first-order logic with two variables FO² and establish a small substructure property. Similar to the small model property for FO² we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse the satisfiability problem for FO² under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO² has the finite model property and is complete (...) for non-deterministic exponential time, just as for plain FO² With two equivalence relations, FO² does not have the finite model property, but is shown to be decidable via a construction of regular models that admit finite descriptions even though they may necessarily be infinite. For three or more equivalence relations, FO² is undecidable. (shrink)