Logic from A to Z

The Routledge Encyclopedia of Philosophy Glossary of Logical and Mathematical Terms

John B. Bacon, Michael Detlefsen, David Charles McCarty

• Publisher: Routledge
• Year: 2013
• eBook ISBN:
  9781134971046
• Subtopic: Logic in Mathematics

First published in the most ambitious international philosophy project for a generation; the Routledge Encyclopedia of Philosophy.
Logic from A to Z is a unique glossary of terms used in formal logic and the philosophy of mathematics.
Over 500 entries include key terms found in the study of:
* Logic: Argument, Turing Machine, Variable
* Set and model theory: Isomorphism, Function
* Computability theory: Algorithm, Turing Machine
* Plus a table of logical symbols.
Extensively cross-referenced to help comprehension and add detail, Logic from A to Z provides an indispensable reference source for students of all branches of logic.

C

Calculus See Formal system.

Calemes See Mood (of a categorical syllogism).

Calemop See Mood (of a categorical syllogism).

Calemos See Mood (of a categorical syllogism).

Camene See Mood (of a categorical syllogism).

Camenes See Mood (of a categorical syllogism).

Camenop See Mood (of a categorical syllogism).

Camestres See Mood (of a categorical syllogism).

Camestrop See Mood (of a categorical syllogism).

Cantor’s paradox See Paradox, Cantor’s.

Cantor’s theorem Basic result in set theory, proved by Cantor in 1892. It states that the power set ℘ (A) of a set A is always of greater size or cardinality than A. Indeed, if A has cardinality α, then ℘ (A) has cardinality 2^α.

See Axiom of power set; Cardinality; Power set.

Cardinal (number) See Cardinality; Large cardinal.

Cardinality Concept of set theory. Two sets A and B have the same cardinality (or power) if and only if there is a bijection from A to B. When sets are of the same cardinality they are often treated as having the same size. Cardinal numbers measure cardinality. Hence, two sets have the same cardinal number just in case they have the same cardinality. Example: Cantor showed that the sets of natural numbers and integers have the same cardinal number, ℵ₀ (‘aleph-nought’).

See Alephs; Beths; Equinumerosity/equipollence; Large cardinal; Transfinite cardinal.

Cartesian product Term of set theory. Also called the ‘cross product’ or ‘direct product’. The Cartesian product A₁ × … × A_n of a family of sets A₁,…,A_n is the class of those ordered n-tuples

a₁,…,a_n

such that a_i ∈ A_i for 1 ≤ i ≤ n.

Categoremata Term of traditional logic. Signifies a term which can serve as a subject or predicate of a categorical proposition. Contrasted with syncategoremata. Examples: ‘horse’, ‘red’, ‘Greek’.

See Syncategoremata.

Categorical in power κ Important model-theoretic property of formal theories. When κ is a cardinal number, a theory is categorical in power κ whenever it has a model whose domain has cardinality κ and all of its models with domains of that cardinality are isomorphic. Equivalently, a theory is categorical in power κ if it has, up to isomorphism, a unique model of cardinality κ. Example: the theory of dense, total orders without endpoints is categorical in power ℵ₀.

See Cardinality; Structure.

Categorical proposition Basic notion of traditional logic. A categorical proposition is a subject-predicate sentence consisting of a quantifier, two terms (the minor or subject term and the major or predicate term) and a copula (negated or not). (The name comes from the Greek ‘katēgoreīn’, ‘to predicate’.) Two possible quantifiers and two copulas yield four categorical forms, universal (‘all’, ‘every’) or particular (‘some’) in quantity, affirmative (‘are’) or negative (‘are not’) in quality (sign of the copula). In the Middle Ages these came to be called by the first four vowels:

A All A are B (universal affirmative);

E No A are B (universal negative);

I Some A are B (particular affirmative);

O Some A are not B (particular negative).

In De interpretatione Aristotle recognizes also ‘indefinite’ categorical propositions, which lack a quantifier. Their precise interpretation remains a matter of dispute.

See Mood (of a categorical syllogism); Opposition; Syllogism, categorical.

Categorical syllogism See Syllogism, categorical.

Categorical theory Important model-theoretic property of formal theories. A theory is categorical (or has the categoricity property) whenever it has a model and all of its models are isomorphic. Equivalently, a theory is categorical if it has, up to isomorphism, a unique model. Example: second-order Peano arithmetic is categorical.

See Structure.

Celantes See Mood (of a categorical syllogism).

Celantop See Mood (of a categorical syllogism).

Celantos See Mood (of a categorical syllogism).

Celarent See Mood (of a categorical syllogism).

Celaro See Mood (of a categorical syllogism).

Celaront See Mood (of a categorical syllogism).

Cesare See Mood (of a categorical syllogism).

Cesaro See Mood (of a categorical syllogism).

Characteristic function Term of set theory and mathematics generally. The characteristic function of a set is the function which maps the members of the set to 1 and all other elements to 0.

See Recursive set; Recursively enumerable set.

Choice, axiom of See Axiom of choice.

Choice sequence Concept introduced into the intuitionistic theory of real numbers by Brouwer (inspired by ideas of du Bois-Reymond and Borel) around 1914. In intuitionistic mathematics, a choice sequence is a mapping from the natural numbers into a collection (usually the natural numbers or the rational numbers) and is considered an ‘incomplete entity’ in that values which the sequence will attain may not be conceived as fully determined in advance by either logic, explicit rule or stipulation. Brouwer discovered proofs of his famous continuity theorem – that all total real-valued functions over the unit interval are uniformly continuous – from reflection upon his conception of choice sequence.

Choice set/function Sets or functions, respectively, which are guaranteed to exist by the axiom of choice. Let A be a collection of non-empty sets x. A choice set for A is a set containing precisely one element from each x. A choice function for A is a function which takes each x in A to an element of itself: for each x in A, f (x) ∈ x.

See Axiom of choice.

Church’s theorem A major result in the metamathematics of first-order logic, proved by Church in 1936. Church’s theorem asserts that validity in full first-order logic is undecidable; equivalently, that there is no decision procedure for determining whether or not an arbitrary formula in full first-order predicate logic is a theorem. In fact, it is possible to show that validity is undecidable for any first-order language containing at least one binary predicate symbol. Church’s theorem yields a definitive negative solution to Hilbert’s Entscheidungsproblem (decision problem) for elementary logic.

See Decidability; Decision procedure; Solvable problem; Validity.

Church’s thesis A claim which is foundational for abstract computability and recursion theory, first put forward by Church. Also known as the Church–Turing thesis. Church’s thesis maintains that a mathematical function is computable mechanically by intuitive algorithm just in case it is Turing computable or, equivalently, is recursive. Church’s thesis is widely thought not to admit of definitive proof, although certain forms of evidence for it can be adduced.

See Algorithm; Recursive function; Turing computable function.

Church–Turing thesis See Church’s thesis.

Circular reasoning, fallacy of Term of logic; an informal fallacy or class of informal fallacies, also known as arguing in a circle, begging the question and petitio principii. An argument exhibits circular reasoning when, explicitly or implicitly, it assumes its conclusion, or a claim tantamount to the conclusion, among its premises. To accept the premises of a circular argument, one must already have accepted its conclusion.

Class Basic concept of set and class theory. Generally, a class is the extension of a property. Certain abstract set theories – for example, von Neumann–Bernays–Gödel – distinguish between sets and classes, taking classes to be arbitrary collections of sets, some of which may well be sets themselves. Those classes which are not sets, such as the class of all sets and the class of all ordinals, are called proper classes.

See Axiom of comprehension; Paradox, Burali-Forti’s; Von Neumann–Bernays–Gödel set theory.

Class/set distinction See Von Neumann–Bernays–Gödel set theory.

Closed term/formula Notion of predicate logic. Signifies a term or formula that contains no free occurrence of a bindable variable.

See Variable.

Closure (deductive, logical) Term of metalogic. A set A of sentences of a language L is deductively closed just in case every sentence of L that is deducible from A is an element of A. The deductive closure of a set A is the set of all sentences deducible from A. Dedu...

Table of contents

• Cover
• Halftitle
• Title
• Copyright
• Contents
• Introduction
• A
• B
• C
• D
• E
• F
• G
• H
• I
• J
• K
• L
• M
• N
• O
• P
• Q
• R
• S
• T
• U
• V
• W
• Z
• Table of logical symbols