We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, . The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, . Additionally, we resolve an open question in [7] (...) about passive versus active learning. (shrink)

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, < \rbrack$. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, < \rbrack$. Additionally, we resolve an open question (...) in [7] about passive versus active learning. (shrink)

In prior papers the following question was considered: which classes of computable sets can be learned if queries about those sets can be asked by the learner? The answer depended on the query language chosen. In this paper we develop a framework for studying this question. Essentially, once we have a result for queries to [S,<]2, we can obtain the same result for many different languages. We obtain easier proofs of old results and several new results. An earlier result we (...) have an easier proof of: the set of computable sets cannot be learned with queries to the language [+,<] . A new result: the set of computable sets cannot be learned with queries to the language [+,<,POWa] where POWa is the predicate that tests if a number is a power of a. (shrink)

Erdős proved that for every infinite \ there is \ with \, such that all pairs of points from Y have distinct distances, and he gave partial results for general a-ary volume. In this paper, we search for the strongest possible canonization results for a-ary volume, making use of general model-theoretic machinery. The main difficulty is for singular cardinals; to handle this case we prove the following. Suppose T is a stable theory, \ is a finite set of formulas of (...) T, \, and X is an infinite subset of M. Then there is \ with \ and an equivalence relation E on Y with infinitely many classes, each class infinite, such that Y is \\)-indiscernible. We also consider the definable version of these problems, for example we assume \ is perfect and we find some perfect \ with all distances distinct. Finally we show that Erdős’s theorem requires some use of the axiom of choice. (shrink)

A recursive graph is a graph whose vertex and edge sets are recursive. A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the neighbors of a vertex. We show that, if (...) A is r.e. and not recursive, then there exists A-recursive graphs that are 2-colorable but not recursively k-colorable for any k. This is false for highly-recursive graphs but true for recursive graphs. Hence A-recursive graphs are closer in spirit to recursive graphs than to highly recursive graphs. (shrink)

LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK.

Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about (...) when these degrees are trivial, and when the degrees are omniscient. (shrink)

If and the function is partial recursive, it is easily seen that A is recursive. In this paper, we weaken this hypothesis in various ways (and similarly for ``min'' in place of ``max'') and investigate what effect this has on the complexity of A. We discover a sharp contrast between retraceable and co-retraceable sets, and we characterize sets which are the union of a recursive set and a co-r.e., retraceable set. Most of our proofs are noneffective. Several open questions are (...) raised. (shrink)

We prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = 1, (...) we show that the theory of the hpm-degrees is undecidable. We also show that index sets cannot be minimal. Lastly, we examine an alternative definition of honest m-reduction under which recursive minimal sets can be constructed. (shrink)

For a fixed set A, the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: $ODD^A_n = \{(x_1, \dots ,x_n): {\tt\#}^A_n(x_1, \dots, x_n) \text{is odd}\}$ and, for m ≥ 2, $\text{MOD}m^A_n = \{(x_1, \dots ,x_n):{\tt\#}^A_n(x_1, \dots ,x_n) \not\equiv 0 (\text{mod} m)\},$ where ${\tt\#}^A_n(x_1, \dots ,x_n) = A(x_1)+\cdots+A(x_n)$ . (We identify A(x) with χ A (x), where χ A is (...) the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODD A n and $\text{MOD}m^A_n: \bullet\text{ODD}^A_n$ can be decided with n parallel queries to A, but not with n - 1. $\bullet \text{ODD}^A_n$ can be decided with $\lceil log(n + 1)\rceil$ sequential queries to A but not with $\lceil log(n + 1)\rceil - 1. \bullet\text{MOD}m^A_n$ can be decided with $\lceil n/m\rceil + \lfloor n/m\rfloor$ parallel queries to A but not with $\lceil n/m\rceil + \lfloor n/m\rfloor - 1. \bullet\text{MOD}m^A_n$ can be decided with $\lceil log(\lceil n/m\rceil + \lfloor n/m\rfloor + 1)\rceil$ sequential queries to A but not with $\lceil log(\lceil n/m\rceil + \lfloor n/m\rfloor + 1)\rceil - 1$ . The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.) In particular, every nonzero truth-table degree contains a set A such that ODD A n cannot be decided with n - 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODD B n can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, $Q(n,A) = \{S: S \text{can be decided with n sequential queries to} A\},\\Q_\parallel(n, A) = \{S: S \text{can be decided with n parallel queries to} A\}.$ We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: $\bullet Q(0,A) \subset Q(1,A) \subset Q(2,A) \subset\cdots\\ \bullet Q_\parallel(0, A) \subset Q_\parallel(1, A) \subset Q_\parallel(2,A) \subset\cdots$ The same is true if A is a jump. (shrink)

Higman essentially showed that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. Let s1, s2, s3, . . . be the standard lexicographic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: given A(s1), A(s2), A(s3), . . . . learn, in the limit, a DFA for SUBSEQU). We consider this model of learning and the variants of it that are usually (...) studied in Inductive Inference: anomalies, mind-changes, teams, and combinations thereof. This paper is a significant revision and expansion of an earlier conference version [10]. (shrink)

مداخلة مترجمة عن الفرنسية للفيلسوف الفرنسي جيل دولوز.

By the time of his death in 2003, Bernard Williams was one of the greatest philosophers of his generation. Ethics and the Limits of Philosophy is not only widely acknowledged to be his most important book, but also hailed a contemporary classic of moral philosophy. Presenting a sustained critique of moral theory from Kant onwards, Williams reorients ethical theory towards ‘truth, truthfulness and the meaning of an individual life’. He explores and reflects upon the most difficult problems in contemporary philosophy (...) and identifies new ideas about central issues such as relativism, objectivity and the possibility of ethical knowledge. This edition also includes a new commentary on the text by A.W.Moore and a foreword by Jonathan Lear. (shrink)

Noted psychologist and philosopher develops his own brand of pragmatism, based on theories of C. S. Peirce. Emphasis on "radical empiricism," versus the transcendental and rationalist tradition. One of the most important books in American philosophy. Note.

By the time of his death in 2003, Bernard Williams was one of the greatest philosophers of his generation. Ethics and the Limits of Philosophy is not only widely acknowledged to be his most important book, but also hailed a contemporary classic of moral philosophy. Presenting a sustained critique of moral theory from Kant onwards, Williams reorients ethical theory towards ‘truth, truthfulness and the meaning of an individual life’. He explores and reflects upon the most difficult problems in contemporary philosophy (...) and identifies new ideas about central issues such as relativism, objectivity and the possibility of ethical knowledge. (shrink)

This first volume contains discussions of the brain, methods for analyzing behavior, thought, consciousness, attention, association, time, and memory.

With a new foreword by Jonathan Lear 'Remarkably lively and enjoyable…It is a very rich book, containing excellent descriptions of a variety of moral theories, and innumerable and often witty observations on topics encountered on the way.' -_ Times Literary Supplement_ Bernard Williams was one of the greatest philosophers of his generation. Ethics and the Limits of Philosophy is not only widely acknowledged to be his most important book, but also hailed a contemporary classic of moral philosophy. Drawing on the (...) ideas of the Greek philosophers, Williams reorients ethics away from a preoccupation with universal moral theories towards ‘truth, truthfulness and the meaning of an individual life’. He explores and reflects upon the most difficult problems in contemporary philosophy and identifies new ideas about central issues such as relativism, objectivity and the possibility of ethical knowledge. This edition also includes a commentary on the text by A.W.Moore. At the time of his death in 2003, Bernard Williams was hailed by the Times as 'the outstanding moral philosopher of his age.' He taught at the Universities of Cambridge, Berkeley and Oxford and is the author of many influential books, including _Morality; Descartes: The Project of Pure Enquiry_ and _Truth and Truthfulness_. (shrink)

Lycan not only uses the numerous arguments against materialism, and functionalist theories of mind in particular, to gain a more detailed positive view of the ..

Sections include: experiments and generalised causal inference; statistical conclusion validity and internal validity; construct validity and external validity; quasi-experimental designs that either lack a control group or lack pretest observations on the outcome; quasi-experimental designs that use both control groups and pretests; quasi-experiments: interrupted time-series designs; regresssion discontinuity designs; randomised experiments: rationale, designs, and conditions conducive to doing them; practical problems 1: ethics, participation recruitment and random assignment; practical problems 2: treatment implementation and attrition; generalised causal inference: a grounded theory; (...) generalised causal inference: methods for single studies; generalised causal inference: methods for multiple studies; a critical assessment of our assumptions. (shrink)

Liberal thinkers of the eighteenth and nineteenth centuries were alert to the political costs and human cruelties involved in European colonialism, but they also thought that European expansion held out progressive possibilities. In Progress, Pluralism, and Politics David Williams examines the colonial and anti-colonial arguments of Adam Smith, Immanuel Kant, Jeremy Bentham, and L.T. Hobhouse. Williams locates their ambivalent attitude towards European conquest and colonial rule in a set of tensions between the impact of colonialism on European states, the possibilities (...) of progress in distant and diverse places, and the relationship between universalism and cultural pluralism. In so doing he reveals some of the central ambiguities that characterize the ways that liberal thought has dealt with the reality of an illiberal world. Of particular importance are appeals to various forms of universal history, attempts to mediate between the claims of identity and the reality of difference, and the different ways of thinking about the achievement of liberal goods in other places. Pointing to key elements in still ongoing debates within liberal states about how they should relate to illiberal places, Progress, Pluralism, and Politics enriches the discussion on political thought and the relationship between liberalism and colonialism. (shrink)

The Gifford Lectures were established in 1885 at the universities of St Andrews, Glasgow, Aberdeen and Edinburgh to promote the discussion of 'Natural Theology in the widest sense of the term - in other words, the knowledge of God', and some of the world's most influential thinkers have delivered them. The 1901–2 lectures given in Edinburgh by American philosopher William James are considered by many to be the greatest in the series. The lectures were published in book form in (...) 1902 and have been reprinted many times. James, who was educated in the United States and Europe, and spent much of his career teaching philosophy at Harvard, was very influential in the development of modern psychology, and in these twenty lectures he explores the personal experience of religion. Some of the topics include religion and neurology, 'the sick soul', saintliness, and mysticism. (shrink)

A representationalist-friendly introduction to representationalism which covers a number of central problems and objections.

For this 1897 publication, the American philosopher William James brought together ten essays, some of which were originally talks given to Ivy League societies. Accessible to a broader audience, these non-technical essays illustrate the author's pragmatic approach to belief and morality, arguing for faith and action in spite of uncertainty. James thought his audiences suffered 'paralysis of their native capacity for faith' while awaiting scientific grounds for belief. His response consisted in an attitude of 'radical empiricism', which deals practically (...) rather than ideologically with real-world phenomena. When facing a 'momentous' decision about belief, he says, we both can and must choose the best hypothesis. The first four essays apply this principle to religious faith, and the rest explore the pragmatic approach to such topics as determinism, ethics and individual achievement. James developed his ideas further in The Varieties of Religious Experience and Pragmatism, both of which are reissued in this series. (shrink)

In fourteen scholarly yet delightfully readable essays, Ober solves some ancient mysteries and reveals the secret kinks and passions of famous and obscure historical figures.

When "Aristotle on Emotion" was first published it showed how discussion within Plato's Academy led to a better understanding of emotional response, and how that understanding influenced Aristotle's work in rhetoric, poetics, politics and ethics. The subject has been much discussed since then: there are numerous articles, anthologies and large portions of books on emotion and related topics. In a new epilogue to this second edition, W.W. Fortenbaugh takes account of points raised by other scholars and clarifies some of his (...) earlier thoughts, focusing on the central issue: how Aristotle conceived of emotional response. Among other matters, he considers laughter, emotion in relation to belief and appearance, the effect of emotion on judgement, and the involvement of pain and pleasure in emotional response. (shrink)

We tend to suppose that the ancient Greeks had primitive ideas of the self, of responsibility, freedom, and shame, and that now humanity has advanced from these to a more refined moral consciousness. Bernard Williams's original and radical book questions this picture of Western history. While we are in many ways different from the Greeks, Williams claims that the differences are not to be traced to a shift in these basic conceptions of ethical life. We are more like the ancients (...) than we are prepared to acknowledge, and only when this is understood can we properly grasp our most important differences from them, such as our rejection of slavery. The author is a philosopher, but much of his book is directed to writers such as Homer and the tragedians, whom he discusses as poets and not just as materials for philosophy. At the center of his study is the question of how we can understand Greek tragedy at all, when its world is so far from ours. Williams explains how it is that when the ancients speak, they do not merely tell us about themselves, but about ourselves. _Shame and Necessity_ gives a new account of our relations to the Greeks, and helps us to see what ethical ideas we need in order to live in the modern world. (shrink)

The Right and the Good, a classic of twentieth-century philosophy by the great scholar Sir David Ross, is now presented in a new edition with a substantial introduction by Philip Stratton-Lake, a leading expert on Ross. Ross's book is the pinnacle of ethical intuitionism, which was the dominant moral theory in British philosophy for much of the nineteenth and early twentieth century. Intuitionism is now enjoying a considerable revival, and Stratton-Lake provides the context for a proper understanding of Ross's great (...) work today. (shrink)

One of the great American pragmatic philosophers alongside Peirce and Dewey, William James (1842–1910) delivered these eight lectures in Boston and New York in the winter of 1906–7. Though he credits Peirce with coining the term 'pragmatism', James highlights in his subtitle that this 'new name' describes a philosophical temperament as old as Socrates. The pragmatic approach, he says, takes a middle way between rationalism's airy principles and empiricism's hard facts. James' pragmatism is both a method of interpreting ideas (...) by their practical consequences and an epistemology which identifies truths according to their useful outcomes. Furnished with many examples, the lectures illustrate pragmatism's response to classic problems such as the question of free will versus determinism. Published in 1907, this work further develops James's approach to religion and morality, introduced in The Will to Believe (1897) and The Varieties of Religious Experience (1902), both reissued in this series. (shrink)

Former Google advertising strategist, now Oxford-trained philosopher James Williams launches a plea to society and to the tech industry to help ensure that the technology we all carry with us every day does not distract us from pursuing our true goals in life. As information becomes ever more plentiful, the resource that is becoming more scarce is our attention. In this 'attention economy', we need to recognise the fundamental impacts of our new information environment on our lives in order to (...) take back control. Drawing on insights ranging from Diogenes to contemporary tech leaders, Williams's thoughtful and impassioned analysis is sure to provoke discussion and debate. Williams is the inaugural winner of the Nine Dots Prize, a new Prize for creative thinking that tackles contemporary social issues. This title is also available as Open Access. (shrink)

Introduction: Three key principles -- Sense datum theories -- Adverbial theories -- Belief acquisition theories -- Intentional theories -- Disjunctive theories -- Perception and causation -- Perception and the sciences of the mind -- Perception and other sense modalities.

This book argues that a realist analysis of the structures and processes which make up the social world can provide a way out of its present impasse.

Philosophers of mind have long been interested in the relation between two ideas: that causality plays an essential role in our understanding of the mental; and that we can gain an understanding of belief and desire by considering the ascription of attitudes to people on the basis of what they say and do. Many have thought that those ideas are incompatible. William Child argues that there is in fact no tension between them, and that we should accept both. He (...) shows how we can have a causal understanding of the mental without having to see attitudes and experiences as internal, causally interacting entities and he defends this view against influential objections. The book offers detailed discussions of many of Donald Davidson's contributions to the philosophy of mind, and also considers the work of Dennett, Anscombe, McDowell, and Rorty, among others. Issues discussed include: the nature of intentional phenomena; causal explanation; the character of visual experience; psychological explanation; and the causal relevance of mental properties. (shrink)

This massive two-volume reference presents a comprehensive selection of the most important works on the foundations of mathematics. While the volumes include important forerunners like Berkeley, MacLaurin, and D'Alembert, as well as such followers as Hilbert and Bourbaki, their emphasis is on the mathematical and philosophical developments of the nineteenth century. Besides reproducing reliable English translations of classics works by Bolzano, Riemann, Hamilton, Dedekind, and Poincare, William Ewald also includes selections from Gauss, Cantor, Kronecker, and Zermelo, all translated here (...) for the first time. (shrink)