Joseph Y. Halpern

In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as illustrations of what he called the empirical law of epistemology, which asserts that the mathematical formulation of the laws of nature is both appropriate and accurate, and that mathematics is actually the correct language for formulating the laws of nature. At the same time, Wigner pointed out that the reasons for the success of mathematics in the natural sciences are not completely understood; in fact, he went as far as asserting that “… the enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and there is no rational explanation for it.”

An agent often has a number of hypotheses, and must choose among them based on observations, or outcomes of experiments. Each of these observations can be viewed as providing evidence for or against various hypotheses. All the attempts to formalize this intuition up to now have assumed that associated with each hypothesis h there is a likelihood function  μ h , which is a probability measure that intuitively describes how likely each observation is, conditional on h being the correct hypothesis. We consider an extension of this framework where there is uncertainty as to which of a number of likelihood functions is appropriate, and discuss how one formal approach to defining evidence, which views evidence as a function from priors to posteriors, can be generalized to accommodate this uncertainty.

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1,..., N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kii [24], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'kii also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable

We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker’s beliefs are represented by plausibility measures and the decision maker’s tastes are represented by general (i.e., not necessarily real-valued) utility functions. We show that every agent, “rational” or not, can be modeled as a GEU maximizer. We then show that we can customize GEU by selectively imposing just the constraints we want. In particular, we show how each of Savage’s postulates corresponds to constraints on GEU.

We show that a 0–1 law holds for propositional modal logic, both for structure validity and frame validity. In the case of structure validity, the result follows easily from the well-known 0–1 law for first-order logic. However, our proof gives considerably more information. It leads to an elegant axiomatization for almost-sure structure validity and to sharper complexity bounds. Since frame validity can be reduced to a Π11 formula, the 0–1 law for frame validity helps delineate when 0–1 laws exist for second-order logics

The question of whether knowledge is definable in terms of belief, which has played an important role in epistemology for the last 50 years, is studied here in the framework of epistemic and doxastic logics. Three notions of definability are considered: explicit definability, implicit definability, and reducibility, where explicit definability is equivalent to the combination of implicit definability and reducibility. It is shown that if knowledge satisfies any set of axioms contained in S5, then it cannot be explicitly defined in terms of belief. S5 knowledge can be implicitly defined by belief, but not reduced to it. On the other hand, S4.4 knowledge and weaker notions of knowledge cannot be implicitly defined by belief, but can be reduced to it by defining knowledge as true belief. It is also shown that S5 knowledge cannot be reduced to belief and justification, provided that there are no axioms that involve both belief and justification

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference $(\sigma \vdash_\mathrm{v} \varphi$ if for every substitution $\tau$, the validity of $\tau \lbrack\sigma\rbrack$ entails the validity of $\tau\lbrack\varphi\rbrack)$, and truth inference $(\sigma \vdash_\mathrm{t} \varphi$ if for every substitution $\tau$, the truth of $\tau\lbrack\sigma\rbrack$ entails the truth of $\tau\lbrack\varphi\rbrack)$. In this paper we introduce a general semantic framework that allows us to investigate the notion of inference more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic

A teacher announced to his pupils that on exactly one of the days of the following school week (Monday through Friday) he would give them a test. But it would be a surprise test; on the evening before the test they would not know that the test would take place the next day. One of the brighter students in the class then argued that the teacher could never give them the test. "It can't be Friday," she said, "since in that case we'll expect it on Thurday evening. But then it can't be Thursday, since having already eliminated Friday we'll know Wednesday evening that it has to be Thursday. And by similar reasoning we can also eliminate Wednesday, Tuesday, and Monday. So there can't be a test!" The students were somewhat baffled by the situation. The teacher was well-known to be truthful, so if he said there would be a test, then it was safe to assume that there would be one. On the other hand, he also said that the test would be a surprise. But it seemed that whenever he gave the test, it wouldn't be a surprise. Well, the teacher gave the test on Tuesday, and, sure enough, the students were surprised.

This collection of essays is a Festschrift for Ernest W. Adams, and is based on a symposium that was held in his honor in 1993. As the title suggests, most of the essays focus on probability and the logic of conditionals, and the relationship between them; they draw their inspiration from Adams’s seminal work on the subject. As a computer scientist, I was struck by just how much the topics discussed play a major role in much recent work in computer science, and how relevant much recent work in computer science is to some of the issues discussed here.

Galles & Pearl (l998) claimed that s [possible-worlds] framework.s framework. Recursive models are shown to correspond precisely to a subclass of (possible-world) counterfactual structures. On the other hand, a slight generalization of recursive models, models where all equations have unique solutions, is shown to be incomparable in expressive power to counterfactual structures, despite the fact that the Galles and Pearl arguments should apply to them as well. The problem with the Galles and Pearl argument is identified: an axiom that they viewed as irrelevant, because it involved disjunction (which was not in their language), is not irrelevant at all