Driven by the question, 'What is the computational content of a (formal) proof?', this book studies fundamental interactions between proof theory and computability. It provides a unique self-contained text for advanced students and researchers in mathematical logic and computer science. Part I covers basic proof theory, computability and Gödel's theorems. Part II studies and classifies provable recursion in classical systems, from fragments of Peano arithmetic up to Π11-CA0. Ordinal analysis and the (Schwichtenberg-Wainer) subrecursive hierarchies play a central role and (...) are used in proving the 'modified finite Ramsey' and 'extended Kruskal' independence results for PA and Π11-CA0. Part III develops the theoretical underpinnings of the first author's proof assistant MINLOG. Three chapters cover higher-type computability via information systems, a constructive theory TCF of computable functionals, realizability, Dialectica interpretation, computationally significant quantifiers and connectives and polytime complexity in a two-sorted, higher-type arithmetic with linear logic. (shrink)

An English language translation accompanies the original Greek text of Aristotle's book about the nature of the state, constitutions, revolutions, democracy, and oligarchy.

Let A be a formula without implications, and Γ consist of formulas containing disjunction and falsity only negatively and implication only positively. Orevkov and Nadathur proved that classical derivability of A from Γ implies intuitionistic derivability, by a transformation of derivations in sequent calculi. We give a new proof of this result , where the input data are natural deduction proofs in long normal form involving stability axioms for relations; the proof gives a quadratic algorithm to remove the stability axioms. (...) This can be of interest for computational uses of classical proofs. (shrink)

"Using hundreds of examples from newsrooms large and small, author Ron F. Smith challenges readers to determine how they would face moral dilemmas on the job. Chapters evaluate the search for principles, accountability, truth and objectivity, errors and corrections, diversity, "faking" the news, reporters and their sources, privacy, the government watch, deception, compassion, the business of news, journalists and their communities, and financial concerns. New to this edition: a chapter on improving coverage of minorities, expanded discussion of broadcast journalism and (...) reporting on the Internet, and stories from recent front pages and TV news programs."--BOOK JACKET.Title Summary field provided by Blackwell North America, Inc. All Rights Reserved. (shrink)

The paper presents a refined method of extracting reasonable and sometimes unexpected programs from classical proofs of formulas of the form ∀x∃yB . We also generalize previously known results, since B no longer needs to be quantifier-free, but only has to belong to a strictly larger class of so-called “goal formulas”. Furthermore we allow unproven lemmas D in the proof of ∀x∃yB , where D is a so-called “definite” formula.

This article aims to read feminist new materialisms (Barad), together with ‘postulated’ linguistic or cultural primacy of Queer Theory (Butler), to show how both are engaged in similar critical-ethical endeavours. The central argument is that the criticism of Barad and new materialisms misses Butler’s materialistic insights due to a narrow interpretation of Butler's alleged social-constructivist position. There is, therefore, a specific focus on where they both make similar ethical appeals. Moreover, the article relies on Adorno's negative dialectic to highlight an (...) interpretation of Barad and Butler as being part of the same dialectical movement, in which materialism and idealism fluctuate in their mutual criticisms, thus continuing the procession towards 'new knowledge' and emancipation, or freedom, through their motions back and forth. (shrink)

The book challenges the values of much of contemporary bioethics and health care policy by confronting their failure to secure the moral norms they seek to apply.

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

Provability, Computability and Reflection.

From a classical proof that the gcd of natural numbers a1 and a2 is a linear combination of the two, we extract by Gödel's Dialectica interpretation an algorithm computing the coefficients. The proof uses the minimum principle. We show generally how well-founded recursion can be used to Dialectica interpret well-founded induction, which is needed in the proof of the minimum principle. In the special case of the example above it turns out that we obtain a reasonable extracted term, representing an (...) algorithm close to Euclid's. (shrink)

Proceedings of the NATO Advanced Study Institute on Proof and Computation, held in Marktoberdorf, Germany, July 20 - August 1, 1993.

This is a tutorial for the Minlog Proof Assistant, version 5.0.

Buchholz presented a method to build notation systems for infinite sequent-style derivations, analogous to well-known systems of notation for ordinals. The essential feature is that from a notation one can read off by a primitive recursive function its n th predecessor and, e.g. the last rule applied. Here we extend the method to the more general setting of infinite terms, in order to make it applicable in other proof-theoretic contexts as well as in recursion theory. As examples, we use the (...) method to 1. give a new proof of a well-known trade-off theorem , which says that detours through higher types can be eliminated by the use of transfinite recursion along higher ordinals, and 2. construct a continuous normalization operator with an explicit modulus of continuity. (shrink)

This paper argues that proper functions are proximal functions. In other words, it rejects the notion that there are distal biological functions – strictly speaking, distal functions are not functions at all, but simply beneficial effects normally associated with a trait performing its function. Once we rule out distal functions, two further positions become available: dysfunctions are simply failures of proper function, and pathological conditions are dysfunctions. Although elegant and seemingly intuitive, this simple view has had surprisingly little uptake in (...) the literature. Indeed, our position departs from that of almost every theorist who has engaged with the issue at any depth. We start by presenting three arguments for the position that proper functions are proximal: one from the specificity of functions, one from their relation to intervention, and one from their relation to pathology. We then consider two case studies evidencing the trouble that accepting distal functions causes for philosophical reflection on the nature of pathological conditions. Finally, we anticipate and respond to three objections: that there can be failure of function without dysfunction; that our account is unacceptably revisionary in respect of normal function-talk; and that our thesis over-generalises from a narrow set of cases. (shrink)

This is the first complete, one-volume English translation of the ancient Chinese text Xunzi, one of the most extensive, sophisticated, and elegant works in the tradition of Confucian thought. Through essays, poetry, dialogues, and anecdotes, the Xunzi articulates a Confucian perspective on ethics, politics, warfare, language, psychology, human nature, ritual, and music, among other topics. Aimed at general readers and students of Chinese thought, Eric Hutton’s translation makes the full text of this important work more accessible in English than ever (...) before. Named for its purported author, the Xunzi has long been neglected compared to works such as the Analects of Confucius and the Mencius. Yet interest in the Xunzi has grown in recent decades, and the text presents a much more systematic vision of the Confucian ideal than the fragmented sayings of Confucius and Mencius. In one famous, explicit contrast to them, the Xunzi argues that human nature is bad. However, it also allows that people can become good through rituals and institutions established by earlier sages. Indeed, the main purpose of the Xunzi is to urge people to become as good as possible, both for their own sakes and for the sake of peace and order in the world. In this edition, key terms are consistently translated to aid understanding and line numbers are provided for easy reference. Other features include a concise introduction, a timeline of early Chinese history, a list of important names and terms, cross-references, brief explanatory notes, a bibliography, and an index. (shrink)

Several properties of monotone functionals (MF) and monotone majorizable functionals (MMF) used in the earlier work by the author and van de Pol are proved. It turns out that the terms of the simply typed lambda-calculus define MF, but adding primitive recursion, and even monotonic primitive recursion changes the situation: already Z.Z(1 — sg) is not MMF. It is proved that extensionality is not Dialectica-realizable by MMF, and a simple example of a MF which is not hereditarily majorizable is given.

The development of transplantation technology increasingly places before society a multitude of diverse, complex ethical and legal problems. The subject is the more complex because of the various divergent interests involved. There are the interests of the donor of organs, who has a right to protection of his legal position, and those of the patient in need of an often lifesaving organ. There are also the interests of the donor’s relatives, after his death, and those of the transplantation surgeons. The (...) international dimension of transplantation technology makes the picture even more complicated. Though this article is devoted to the European situation, the problems are similar all over the world. (shrink)

The development of transplantation technology increasingly places before society a multitude of diverse, complex ethical and legal problems. The subject is the more complex because of the various divergent interests involved. There are the interests of the donor of organs, who has a right to protection of his legal position, and those of the patient in need of an often lifesaving organ. There are also the interests of the donor’s relatives, after his death, and those of the transplantation surgeons. The (...) international dimension of transplantation technology makes the picture even more complicated. Though this article is devoted to the European situation, the problems are similar all over the world. (shrink)