ALASDAIR IAN FENTON URQUHART
Professor of Philosophy
University of Toronto
Date of latest revision: April 1998

A. Biographical Information

Personal
Date of Birth: 20 December, 1945

Citizenship: British (Landed Immigrant 1970)

Home address: 54 Boustead Avenue, Toronto, Ontario, M6R 1Y9

Home phone: 767-5240 (unlisted)

University address: Department of Philosophy, University of Toronto,

215 Huron Street, Toronto, Ontario M5S 1A1

Office phone: 978-6789

Degrees

M.A. Hons., University of Edinburgh, 1967

M.A. University of Pittsburgh, 1969

Ph.D. University of Pittsburgh, 1973

Title of Ph.D.Thesis: "The Semantics of Entailment"

Supervisors: Profs. Nuel D. Belnap Jr. and Alan Ross Anderson

Employment

Present Appointment

Professor, University of Toronto, 1986 -

Associate Professor, University of Toronto, Erindale College, 1975-86

Date of appointment to Graduate School, 1973

Date of tenure award, Spring, 1975

Assistant Professor, University of Toronto, Erindale College, 1973-75

Lecturer, University of Toronto, Erindale College, 1970-73

Teaching Fellow, University of Pittsburgh, 1967-70

Professional Affiliations and Activities

Consulting editor Journal of Symbolic Logic 1983-89

Former editor of Canadian Philosophical Monographs

Associate of the Institute for the History and Philosophy of Science and Technology

Referee for Canada Council, NSERC, NSF etc.

Referee for JSL, JPL, Studia Logica etc. etc.

Member, Executive Committee, Association for Symbolic Logic 1987-90 Member, Advisory Editorial board, Studia Logica 1991- Member, ASL committee on meetings in N. America 1992- Member, ASL nominating committee, 1993 -

Programme comittee, joint meeting of ASL and SEP, York University May 1993.

Board of consultant editors, Russell. Editor, Lecture Notes in Logic (Springer Verlag), 1994-

Editor, Trends in Logic, 1994-

Consulting editor, Studia Logica.

Member of editorial board, International Studies in the Philosophy of Science.

Editor for non-classical logics, Stanford On-Line Encyclopedia.

B. Academic History

a. Research Endeavours

Non-classical logics, lattice theory, philosophy of logic, foundations of mathematics, history of logic, theory of computation, computational complexity theory.

b. Research Awards

Canada Council Leave Fellowship 1976-77 (one-year) - $9,200.
SSHRC Leave Fellowship 1983-84 $11,500.
SSHRC Research Grant 1984-85. Project: ``Investigations in logic" $6,920.
SSHRC Research Grant 1986-87. Project: "Studies in Complexity Theory", $10,185.
SSHRC Research Grant 1986-87. Project: "Editing Volume 4 of Bertrand Russell's Papers", $45,615.
SSHRC Research Grant 1989-91. Project: "Editing Volume 4 of The Collected Papers of Bertrand Russell", $124,700.
SSHRC Research Grant 1991-2. Project: "Editing Volume 4 of the Collected Papers of Bertrand Russell." $46,490.
SSHRC Research Grant 1992-3. Project: "Editing Volume 4 of the Collected Papers of Bertrand Russell." $10,400.
NSERC Operating Grant 1991-4. $24,000 p.a.
NSERC Operating Grant 1994-8. $27,000 p.a.

C. Scholarly and Professional Work

Refereed Publications

a. Articles in refereed journals

``Semantics for relevant logics", Journal of Symbolic Logic, Vol. 37, No. 1, March 1972.
``Completeness of weak implication", Theoria Vol. 37 (1971).
``A semantical theory of analytic implication", Journal of Philosophical Logic, Vol. 2, April, 1973.
``An interpretation of many-valued logic", Zeitschrift fur mathematische logik und grundlagen der Mathematik, Vol. 19, pp. 111-114.
``Free distributive pseudocomplemented lattices", Algebra Universalis, Vol. 3, pp. 13-15.
``Free Heyting algebras", Algebra Universalis, Vol. 3, pp. 94-97.
``Implicational formulas in intuitionistic logic", Journal of Symbolic Logic, Vol. 39, No. 4, December, 1974.
``Popper's logical conceptions", Communication and Cognition, Vol. 8 (1975), 237-242.
``Proofs, snakes and ladders", Dialogue, Vol. 13, pp. 723-731 (1974).
Critical notice of Richard Montague's Formal Philosophy, Canadian Journal of Philosophy, Vol. 4, pp. 573-578 (1975).
Critical notice of Entailment, Vol. 1, by Anderson and Belnap. Canadian Journal of Philosophy, Vol. 7, 405-411.
``A Finite Matrix Whose Consequence Relation is not Finitely Axiomatizable", Reports on Mathematical Logic, Vol. 9 (1977), 71-73.
Review of Meaning and Modality by Casimir Lewy, Journal of Philosophy, Vol. 75 (1978).
``A topological representation theory for lattices", Algebra Universalis, Vol. 8 (1978), 45-58.
``Distributive lattices with a dual homomorphic operation', Studia Logica, Vol. 38 (1979), 201-209.
``Equational classes of distributive double p-algebras", Algebra Universalis, Vol. l4 (l982), 235-243.
``Distributive lattices with a dual homomorphic operation II", Studia Logica, Vol. XL, 1981-4, 391-404.
``The undecidability of entailment and relevant implication", Journal of Symbolic Logic, Vol. 49 (1984), 1059-1073.
``Relevant implication and projective geometry", Logique et Analyse, special issue on Canadian logic, Vol. 103-104, September 1983, pp. 345-357.
Critical notice of Handbook of Mathematical Logic (ed. Barwise) Canadian Journal of Philosophy, Vol. XIV, December 1984, 675-682.
Critical notice of Beyond Analytic Philosophy by Hao Wang, Canadian Journal of Philosophy, Vol. 17, 477-482 (June 1987).
``A Contractionless Semilattice Semantics", (with S. Giambrone & Meyer), Journal of Symbolic Logic, Vol. 52 526-529 (June 1987).
``Proof Theories for Semilattice Logics" (with S. Giambrone), Zeitschrift fur Math. Logik und Grundlagen der Mathematik, Vol. 33, 433-9 (1987).
``Hard examples for resolution", Journal of the Association for Computing Machinery, Vol. 34, 209-219, (1987).
``Further Results on Proof Theories for Semilattice Logics" (co-authors Meyer, Giambrone, Martin), Zeitschrift fur Math. Logik u. Grundlagenforschung, Vol. 34, 1988, 301-4.
``The Complexity of Gentzen Systems for Propositional Logic", Theoretical Computer Science, Vol. 66, 1989, 87-97.
``What is relevant implication?" in: Directions in Relevant Logic ed. by Norman and Sylvan (Kluwer 1989), 167-74.
``Functional Interpretations of Feasibly Constructive Arithmetic" (extended abstract co-authored with S.A. Cook), 21st Annual ACM Symposium on theory of computing May 1989.
``The Logic of Physical Theory", in: Physicalism in Mathematics, ed. A.D. Irvine, Kluwer 1990, 145-154.
``The complexity of decision problems in relevance logic", in Truth and Consequences ed. by Dunn and Gupta, Kluwer 1990, 61-76.
``Complexity of proofs in classical propositional logic", in Logic from Computer Science ed. Y.N. Moschovakis, Springer-Verlag 1992, 597-608.
Review of papers by Arnon Avron, J. Symbolic Logic, Vol. 57 (1992), 1481-2.
``Approximations and small-depth Frege proofs" (co-authors Stephen Bellantoni and Toni Pitassi), extended abstract in conference proceedings Structures in Complexity Theory 1991, Springer Lecture Notes in Computer Science 1991.
``The relative complexity of resolution and cut-free Gentzen systems", Annals of Mathematics and Artificial Intelligence, 6 (1992), 157-68.
``Approximations and small-depth Frege proofs" (co-authors Stephen Bellantoni and Toni Pitassi), SIAM J. of Computing, Vol. 21 (1992), 1161-79.
``The Complexity of the Hajos calculus" (co-author Toniann Pitassi), Proceedings of Symposium on the Theory of Computing, Pittsburgh 1992. See below for published complete version.
``Failure of interpolation in relevant logics", J. of Philosophical Logic, Vol. 22 (1993), 449-479.
``Functional interpretations of feasibly constructive arithmetic" (co-author S.A. Cook), Annals of Pure and Applied Logic, Vol. 63 (1993), 103-200.
``Russellian Propositions" (co-author J. Pelham), Proceedings of the conference on Logic, Methodology and Philosophy of Science, Uppsala 1991, 307-326.
``Upper and lower bounds for tree-like cutting-plane proofs," (co-authors Russell Impagliazzo and Toni Ann Pitassi), Ninth I.E.E.E. Symposium on Logic in Computer Science (1994), pp. 220-228.
``Decision problems for distributive lattice-ordered semigroups", Algebra Universalis, Vol. 33 (1995), 399-418.
``The Complexity of the Hajos calculus" (co-author Toniann Pitassi). SIAM J. of Discrete Mathematics, Vol. 8 (1995), 464-483.
``Duality for algebras of relevant logics", Studia Logica, Vol. 56 (1996), 263-276.
``G.F. Stout and the theory of descriptions," Russell Vol. 14, 163-171.
``The complexity of propositional proofs," Bulletin of Symbolic Logic, Vol. 1 (1995), 425-467.
``Simplified lower bounds for propositional proofs," (co-author Xudong Fu), Notre Dame J. of Formal Logic, Vol. 37 (1996), 523-544.
``The number of lines in Frege proofs with substitution," Archive for Mathematical Logic, (1997), Vol. 37, 15-19.
``Beth's definability theorem in relevant logics," forthcoming in Festschrift for Helena Rasiowa.

b. Books and Chapters in books

Temporal Logic (joint author with Nicholas Rescher), Springer Verlag New York and Vienna 1971.
Section on Many Valued Logic in Gabbay and Guenthner (eds.), Handbook of Philosophical Logic, Vol. III. Reidel l984.
Sections 47 and 65 of Entailment, Vol. 2, by Anderson, Belnap and Dunn. Princeton University Press 1992.
The Collected Papers of Bertrand Russell, Volume 4 : Foundations of Logic 1903-05 (Editor).
``Zeit und Zeitlogik" (co-author Nicholas Rescher), in Zustand und Ereignis, ed. by Bertram Kienzle, Suhrkamp 1994 (partial translation of Temporal Logic).

Non-refereed Publications

a. Articles

About 100 short reviews on papers in logic and mathematics Mathematical Reviews, 1973-85.
Review of The Paradox of the Liar, ed. by Robert Martin, Dialogue, Vol. 10, (1971), pp. 823-825.
Review of The Development of Mathematical logic, by R.L. Goodstein, Historia Mathematica, Vol. 11, pp. 212-214.
Review of Distributive Lattices, by Balbes and Dwinger, Journal of Symbolic logic, 40 (1975).
Review of Classical Propositional Operators, by Krister Segerberg, Canadian Philosophical Review, Vol. III, No. 6.
``Intensional Languages via Nominalisation", Pacific Journal of Philosophy, 1981.
Review of Mathematics in Philosophy, by Charles Parsons, History and Philosophy of Logic, (1985).
Review of two papers on symbolic logic, JSL 1985.
Review of Routley et al. "Relevant Logics and their Rivals I" Studia Logica (1988).
Review of Rachel Garden "Modern Logic and quantum mechanics", Journal of Symbolic Logic, Vol. 53, 648.
Review of J.M. Dunn, J. of Symbolic Logic, Vol. 54 (1989), pp. 615-16.
``Russell's zigzag path to the ramified theory of types", Russell, N.S. Vol. 8 (1988), pp. 82-91.
Review of Troelstra and van Dalen "Constructivism in Mathematics Volume 1", Studia Logica 1989.
Review of Troelstra and van Dalen "Constructivism in Mathematics" Volume 2, Studia Logica, June 1991.
Review of Per Martin-Lof "Intuitionistic Type Theory", Studia Logica 1990.
Review of Stephen Read "Relevant Logic", History and Philosophy of Logic, Vol. 11 98-99.
Review of Jon Barwise "The situation in logic", Can. Phil. Rev., Vol. X, 96-8.
Review of Stuart Shapiro "Intensional Mathematics", Studia Logica, April 1990.
Review of paper by D. Deutsch, J. Symbolic Logic, Vol. 55, 1309-10.
``Functional interpretations of feasibly constructive arithmetic" (extended abstract) in Feasible Mathematics,ed. Buss and Scott, Birkhauser 1990, 97-8.
Review of Hermes No. 7 , in Russell, Vol. 11 (1991), 103-5.
Review of M. Detlefsen, "Proof and Knowledge in Mathematics", Canadian Phil. Reviews, Vol. 12 (1992), 237-8.
Review of Rodriguez-Consuegra, "The Mathematical Philosophy of Bertrand Russell", Philosophia Mathematica Vol. 1 (1993), 90-93.
Review of Hartry Field "Realism, mathematics and modality", History and Philosophy of Logic, Vol. 14 (1993), 117-119.
Review of "Lectures on Linear Logic" by Anne Troelstra, Can. Phil. Reviews, Vol. 13, 126-128.
Review of "Russell's Idealist Apprenticeship" by Nicholas Griffin, Russell, Vol. 13, 104-108.
Review of "Substructural Logics", History and Philosophy of Logic, Vol. 16 (1995), 138-9.
Review of G. Malinowski, "Many-valued logics", Notre Dame Journal of Formal Logic, Vol. 35, 469-70.
Review of "Russell and Analytic Philosophy," J. Symbolic Logic, Vol. 61, 1391-2.
Review of "Feasible Mathematics II," J. of the I.G.P.L. Vol. 5, 301-2.
Review of Jagdish Mehra, "The Beat of a Different Drummer," International Studies in the Philosophy of Science, Vol. 11 (1997), 311-313.

Manuscripts in preparation and submitted

``Weakly additive operators in distributive lattices", in preparation.
``The symmetry rule in propositional logic," submitted.
``The graph constructions of Hajós and Ore," submitted.

Papers presented at Meetings and Symposia

``A general theory of implication", Association for Symbolic Logic Annual Meeting, December 1971, New York.
``Free Heyting Algebras", Association for Symbolic Logic Annual Meeting, Dallas, January 1973.
``Implicational formulas in intuitionistic logic", Association of Symbolic Logic Annual Meeting, Atlanta, December 1973.
``Elementary classes in infinitary logic", Association for Symbolic Logic, Spring Meeting, Chicago, April 1975.
``A representation theory for lattices", Universal Algebra Conference, Oberwolfach, West Germany, August l976.
``Congruence latices and Heyting algebras", Universal Algebra Conference, Esztergom, Hungary, July 1977.
``Ockham lattices", Canadian Mathematical Society Annual Meeting, Calgary, December 1977.
``Equational classes of distributive double p-algebras", read to American Mathematical Society special session on Varieties, Claremont, California, October 1978.
``Projective distributive p-lattices", American Mathematical Society session on Universal Algebra, Boulder, Colorado, March 1979.
``Word problems for distributive lattice-ordered semigroups" Charleston Conference on Universal Algebra, July 1984.
Talks to graduate forum (Philosophy) Fall 1982 and Fall 1983 on logic.
``How do we know mathematical proofs are correct?", talk to IHPST October 31, 1985.
``The complexity of decision procedures in relevant logic", presented at meeting of the Association for Symbolic Logic, Los Angeles, January 1989.
``Are there absolutely undecidable mathematical propositions?" Talk to graduate forum, October 19 1989.

Invited Lectures

``What is Relevant Implication?", International Conference on Relevance Logics, St. Louis, September 1974.
``How to put Routley and Meyer into a Comer", University of Waterloo Conference on the Foundations of Logic, April 1982.
``Undecidability of Relevant Implication", Wollongong, Australia, July 1982.
``Does Many-valued Logic make Sense?", University of Melbourne, July 1982.
``The Undecidability of Entailment and Relevant implication", University of Western Ontario, November 1982, also University of Buffalo, February, 1983, University of Alberta, February 1984.
``Russell's Zig-Zag Path to the Ramified Theory of Types", Conference on Russell's Early Philosophy, University of Toronto, Summer 1984.
``Intensional Languages via Nominalization", Society for Exact Philosophy, Halifax 1980.
``The Algebra of Entailment", Asilomar conference on algebra and logic, July 1987.
``The Geometry of Entailment", Indiana University, 12 November 1987.
``Complexity of Proofs in Propositional Logic", Indiana University, 13 November 1987.
``Functional Interpretations of Feasible Arithmetic", U. Pennsylvania, Mathematics Department, 7 December, 1987
``Functional Interpretations of Fesibly Constructive Arithmetic", Conference on Feasible Mathematics, Cornell, June, 1989.
``Translation Problems in Modal Logic", Society for Exact Philosophy, Edmonton, Alberta, August 1989.
``The complexity of propositional proof systems", Berkeley conference on Logic from Computer Science, MSRI, November 1989.
``Failure of interpolation in relevant logics", Kleene '90, Chaika, Bulgaria, July 1990.
``Complexity of proofs in classical propositional calculus", Department of Mathematics, University of Waterloo, October 30 1990.
``Recent results in propositional complexity", Dept. of Mathematics, McMaster University March 25 1991.
``Why are some tautologies harder to prove than others?" Society for Exact Philosophy, Victoria B.C. May 1991.
``Russellian Propositions" (co-author Judy Pelham), Conference on Logic, Methodology and Philosophy of Science, Uppsala, Sweden, August 1991.
``Russellian Propositions" (co-author Judy Pelham), U. of Buffalo Logic Colloquium October 1991.
"Propositional Complexity", Talk to Mathematics Seminar, U. of Buffalo, October 1991.
"Complexity of decision procedures in relevant logic", McGill University Mathematics Seminar November 1991.
"The complexity of the Hajos calculus", "Mathematische Logik", Mathematisches Forschungsinstitut Oberwolfach April 14 1992.
"Complexity of the Hajos construction", logic workshop, U. of Victoria, B.C. July 3 1992.
"Recent results and open problems in classical propositional logic", Association for Symbolic Logic Annual Meeting March 13 1993, Notre Dame, Indiana.
"Recent work in complexity theory", talk to Logic and Philosophy of Science group, Toronto February 1994.
"Recent results in classical propositional logic", talk to Toronto Set Theory seminar, April 6 1994.
"Complexity of propositional proofs", invited lecture, Conference on Computational Logic, Indianapolis, October 14 1994.
``Russell and the Foundations of Logic 1903-05," invited lecture, Annual Meeting, Association for Symbolic Logic, Irvine, California April 2 1995.
Lectures on propositional proof complexity, DIMACS Workshop on Feasible Mathematics and Proof complexity, Rutgers University, Center for Discrete Mathematics and Theoretical Computer Science, August 21-25 1995.
``The symmetry rule in propositional logic," conference on the satisfiability problem, Siena, Italy, April 29 - May 3 1996.
``The graph constructions of Hajós and Ore," talk to the University of Toronto combinatorics seminar October 12 1996.
``Complexity of Propositional Proofs," talk to Philosophy Department Carnegie Mellon University, April 12 1997.
``Solution of a 2000-year-old logic problem," Philosophy Department, University of Waterloo, November 14 1997.
``Is Gödel's Theorem a red herring?" Talk to the University of Toronto Cognitive Science and Artificial Intelligence Students' Association, January 15 1998.

D. List of courses (in preceding 5 years)

a. Undergraduate courses taught

PHL 245: Modern Symbolic Logic

PHL 246: Probability and inductive logic PHL 345: Intermediate Logic PHL 346: Philosophy of Logic and Mathemataics

PHL 349: Set Theory PHL 342: Minds and Machines PHL 350: Philosophy of Language PHL 231: Existence and Reality PHL 344: Metalogic

b. Graduate courses taught

PHL 2121: Modern Logic PHL 2124: Seminar in Logic (theory of entailment) PHL 2124: Seminar in Logic (algebraic logic) PHL 2087: Russell PHL 2126: Foundations of Mathematics

PHL 2122: Advanced Logic (Seminar on Russellian propositions) PHL 2192: Frege

c. Theses Supervised

Masters Student:
Giovanni Panti (Mathematics) 1990.
David McClurkin (Computer Science) 1991.
Oliver Schulte (Computer Science).
Francois Pitt (Computer Science).
Doctoral Students:
Gerald Charlwood. Thesis topic: Relevance Logic. Period of supervision: 1974-78. Thesis completed 1978. Primary supervisor
Pamela Ely. Thesis topic: Medieval Logic. Period of supervision: 1975-80. Thesis completed 1980. Secondary supervisor.
Merrie Bergmann. Thesis topic: Metaphysics. Period of supervision: 1975-77. Secondary supervisor.
Ben Russell. Thesis topic: Wittgenstein's Philosophy. Period of supervision: 1978-80. Completion date: 1980. Secondary supervisor.
Mark Vorobej. Thesis topic: Deontic Logic. Period of supervision: 1979-83. Primary supervisor.
Alejandro Garciadiego. Thesis topic: History of Foundations of Mathematics. Period of supervision: 1978-1980. Secondary supervisor.
Peter Turney. Thesis topic: Inductive Inference and Stability. Thesis completed 1988. Primary supervisor.
Arnold Silverberg. Thesis topic: Anti-Realism in Semantics and Logic. Thesis completed 1988. Primary supervisor.
Andre Vellino. Thesis topic: The complexity of automated reasoning. Thesis completed 1989. Primary supervisor.
Judith Pelham. Thesis topic: Russell on propositions and objects. Thesis completed September 1993. Primary supervisor.
Kent Peacock. Thesis topic: Space-time view of non-locality. Secondarysupervision.
Andrew Malton (Computer Science Dept). Thesis topic: Functional Interpretation of Programming Methods. Secondary supervision.
Arvind Gupta (Computer Science Dept). Thesis topic: Constructivity in Tree Minors. Secondary supervision.
Frederic Portoraro. Thesis Topic: Automated theorem proving. Primary supervisor.
Xudong Fu (Computer Science). Thesis topic: Complexity of propositional proofs. Secondary supervision. Thesis completed February 1996.
Jeffrey Denson (Philosophy). Thesis topic: Objectivity in Frege. Primary supervisor. Withdrew from doctoral program 1995.
Arnold Rosenbloom (Computer Science). Secondary supervisor.
Achille Varzi (Philosophy). Secondary supervision. Thesis topic: General semantics. Thesis completed: October 1994.
Francois Pitt (Computer Science). Secondary supervision. Thesis topic: "Bounded arithmetic."
Anthony Jenkins. "The Nature of Logical Inquiry." Primary supervision.
C.K. Poon (Computer Science). Thesis topic: "The Complexityof the st-connectivity problem." PhD completed August 1995.
David Mitchell (Computer Science). Thesis topic: "Propositional Satisfiability Testing." Secondary supervision.
Tomoyuki Yamakami (Computer Science). Thesis topic: "Structure of average case hierarchies." Secondary supervision. PhD completed February 1997.
David Hyder (Philosophy). Thesis topic: "Helmholtz and Wittgenstein." PhD completed December 1996. Secondary supervision.

Administrative Positions

1970-72 Scholarships and Awards Committee, Erindale College

1973-74, 1974-75 Search Committee

1974-75, 1977-80 Personnel Committee 1978-79 Discipline Representative, Erindale College

1980-83 UTFA Representative

1979 Tenure Committee 1980 Promotion Committee

Served on thesis committee, James Hoover, Department of Computer Science.

Wrote internal appraisal for Tom Archibald (IHPST, May 1987) Ph.D. Thesis.

Martha Lile Love Award Committee 1992.

Promotion Committee, J.R. Brown 1991.

Search Committee, 1991-2.

Co-ordinator, Logic and Philosophy of Science group 1994 - Member, Mathematical Sciences Review Panel, 1994.

Member, committee for Connaught awards, 1994-7; chair 1995-6

Member, reading committee, P. Apostoli tenure decision, 1996-7.