LOGICAL TERMS, GLOSSARY OF

This glossary is confined, with few exceptions, to terms used in formal logic, set theory, and related areas. No attempt has been made to cover what is often called "inductive logic," although several terms in this field have been included for the convenience of the reader.

It should be noted that many topics dealt with very briefly here are treated in full in various other entries in this encyclopedia. Cross references to these will be enclosed in quotation marks; cross references to other glossary entries will be indicated by boldface italics (e.g., "see relation ").

abduction

(1) A syllogism whose major premise is known to be true but whose minor premise is merely probable. (2) C. S. Peirce's name for the type of reasoning that yields from a given set of facts an explanatory hypothesis for them.

abstraction

(1) In traditional logic, the process of deriving a universal from particulars. (2) In set theory, the process of defining a set as the set of all objects that have a particular property.

abstraction, axiom of (axiom of comprehension)

An axiom in set theory stating that for any predicate P, there exists a set of all and only those objects that satisfy P. It was the unrestricted use of this axiom that led to the paradoxes of set theory.

abstract term

In traditional logic, a term that is a name of the common nature of many individuals, considered apart from them or from what distinguishes them from one another. A common example of an abstract term is "humanity."

accident

See predicables.

actual infinite

The infinite regarded as a completed whole.

a fortiori

A nonsyllogistic mediate inference of the form "B is greater than C; A is greater than B ; hence, A is greater than C. " It is clear that the validity of this argument follows from the transitivity of the relation "greater than," and therefore some authors extend the term to cover all relational syllogisms whose validity depends on the transitivity of the relation involved. See relation.

aggregate

A collection of objects satisfying a given condition.

alephs

The symbols, introduced by Georg Cantor, that designate the cardinality of infinite sets (see entry "Set Theory"). Aleph-null (ℵ₀) designates the cardinality of the smallest infinite set, aleph-one (ℵ₁) the cardinality of the next largest infinite set, etc. See continuum hypothesis ; entry "Set Theory."

algebra of logic

A system in which algebraic formulas are used to express logical relations. In such a system many familiar algebraic laws that hold for numbers are not retained. The work of George Boole contains the first important example of an algebra of logic.

algorithm

A mechanical procedure for carrying out, in a finite number of steps, a computation that leads from certain types of data to certain types of results. See decision problem; effectiveness.

alternation

See disjunction, exclusive.

alternative denial

See Sheffer stroke function.

ambiguity

Capability of being understood in two or more ways. The term is strictly applied only in cases where the possibility of different interpretation is due not to the expression itself but to some feature of the particular use of the expression; when this possibility is due to the expression itself the expression is called equivocal. Many authors, however, do not make this distinction.

amphiboly

An equivocation that arises not out of an equivocation in a word or phrase but because the grammatical structure of the sentence or clause leaves the place of the phrase in the whole not entirely determinate. An example is "The shooting of the hunters was finished quickly."

ampliation

In medieval logic, the extension of a common term from a narrow supposition to a wider one.

analogy

A comparison between two or more objects that indicates one or more respects in which they are similar. An argument from analogy is an inference from some points of resemblance between two or more objects to other such points. The method of refutation by logical analogy is a method for showing that an argument is fallacious by giving an example of another argument of the same form whose invalidity is immediately apparent.

analysis, mathematical

The theory of real and complex numbers and their functions.

analytic

Used of a proposition whose denial is self-contradictory. Such a proposition is true either by virtue of its logical form alone (in which case it is called a logical truth, or logically necessary ) or by virtue of both its logical form and the meaning of its constituent terms. An instance of a logical truth is "It is raining or it is not raining"; an example of an analytic truth that is not a logical truth is "All bachelors are unmarried." Analytic propositions cannot be false and are therefore said to be necessary truths. Whether there are necessary truths that are not also analytic truths is a matter of much dispute. See entry "Analytic and Synthetic Statements."

ancestral relation

For a given relation R, the relation R * that exists between two objects x and y if and only if y has every R -hereditary property that x has. A property is said to be R-hereditary when, if it is correctly predicated of b and if aRb, then it is also correctly predicated of a. For example, let R be the property "is the successor of." Then "is a natural number" (where this property also applies to 0) is R -hereditary, since if b is a natural number and a is the successor of b, then a is also a natural number. Given this fact, we can define the property "is a natural number" as the property of all objects that bear the ancestral relation to 0 for the relation "is the successor of"—that is, as the property of all objects that have every "is the successor of"-hereditary property that 0 has. One of these properties is "is a natural number," and therefore only the natural numbers can meet this definition.

It should be noted that the above definition is an example of an impredicative definition, since "is a natural number" is defined in terms of the class of "is the successor of"-hereditary properties, a class of which it is a member.

antecedent

The part of a hypothetical proposition that precedes the implication sign.

antilogism

A triad of propositions such that the joint truth of any two of the propositions implies the falsity of the third. Christine Ladd-Franklin's principle of the syllogism states that a valid syllogism is one whose premises taken with the contradictory of the conclusion constitute an antilogism. Thus, the syllogism whose premises are "All men are mortal" and "Socrates is a man" and whose conclusion is "Socrates is mortal" is a valid syllogism, for the joint assertion of any two of the three propositions that constitute the premises and the contradictory of the conclusion implies the falsity of the third proposition.

antinomy

See paradox.

apodictic (apodeictic) proposition

See modality.

appellation

In medieval logic a term is said to have appellation if it is applicable to some existing thing. Thus, "the present queen of England" has appellation, but "the present queen of the United States" does not.

A-proposition

In traditional logic, a universal affirmative categorical proposition. An example is "All men are mortal."

Archimedean property

The property of a system of numbers whereby for any two numbers a and b, if a is less than b, then there is a number c such that a multiplied by c is greater than b.

argument of a function

A member of the domain of a given function.

arithmetical predicate

A predicate that can be explicitly expressed in terms of the truth-functional connectives of propositional calculus, the universal and existential quantifiers, constant and variable natural numbers, and the addition and multiplication functions.

arithmetization of mathematics (arithmetization of analysis)

The definition, which was developed by Karl Weierstrass, Richard Dedekind, and Georg Cantor, of the nonnatural numbers as certain objects construed out of the natural numbers and set-theoretic objects and the corresponding reduction of the properties of the former to the properties of the latter.

arithmetization of syntax

The process of correlating the objects of a formal system with some or all of the natural numbers and then studying the relations and properties of the correlated numbers so as to gain information about the syntax of the formal system. This was done systematically by Kurt Gödel in the researches that led to his incompleteness theorems. See entry "Gödel's Theorem."

ars combinatoria

A technique of deriving complex concepts by the combination of relatively few simple ones, which are taken as primitive. This technique was proposed by Gottfried Wilhelm Leibniz as a valuable aid for the study of all subjects. He proposed the development of a universal language (characteristica universalis ) containing a few primitive symbols in terms of which all other symbols would be defined. A universal mathematics (mathesis universalis )—that is, a universal system of reasoning—would then be added, and all subjects could be studied in this language. Leibniz program is often viewed as an early forerunner of the formalization of various disciplines.

assertion sign

The sign ├, introduced by Gottlob Frege to indicate in the object language that a proposition is being judged as true and is not merely being named. Some authors now use this sign in the metalanguage to express that the formula to which it is prefixed is a theorem in the object language.

assertoric proposition

See modality.

associativity

The property of a relation R that consists in the identity of "aR (bRc )" and "(aRb )Rc," where a, b, and c are any elements of the field of R. Addition has this property, since "a + (b + c )" is the same as "(a + b ) + c. "

attribute

Although it is now often used synonymously with "property," this term was traditionally confined to the essential characteristics of a being.

Aussonderungsaxiom

An axiom in set theory, first introduced by Ernst Zermelo, which states that for any set a and any predicate P, there exists a set containing all and only those members of a that satisfy the predicate P.

axiom

A basic proposition in a formal system that is asserted without proof and from which, together with the other such propositions, all other theorems are derived according to the rules of inference of the system. See postulate.

axiomatic method

The method of studying a subject by beginning with a list of undefined terms and a list of axioms and then deriving the truths of the subject from these postulates by the methods of formal logic.

axiom schema

A representation of an infinite number of axioms by means of an expression containing syntactical variables and having well-formed formulas as values. Every value of the expression is to be taken as an axiom.

axiom schema of separation

See Aussonderungsaxiom.

Barbara

See mnemonic terms.

Baroco

See mnemonic terms.

biconditional

A binary propositional connective (↔, ≡), usually read "if and only if" (often abbreviated "iff"), whose truth table is such that "A if and only if B " is true when A and B are either both true or both false and is false when one is true and the other false. "A if and only if B " is equivalent to "if A then B, and if B then A. "

binary connective

See connective.

Bocardo

See mnemonic terms.

Boolean algebra

The first algebra of logic. It was invented by George Boole and given its definitive form by Ernst Schröder.

Boolean functions

Functions that occur in Boolean algebra. The more important ones are the class-union function, the class-intersection function, and the class-complement function.

bound occurrence of a variable

An occurrence of a variable a in a well-formed part of a formula A either of the form "for all a, B " or of the form "there is an a such that B. "

bound of a set

For a given relation R, a lower bound (or first element) of a set a is any member of a that bears the relation R to all members of a ; an upper bound of a is any member of a to which all members of a bear the relation R. A greatest lower bound of a set a (or infimum of a ) is a lower bound of a to which all lower bounds of a bear the relation R ; a least upper bound of a (or supremum of a ) is an upper bound of a that bears the relation R to all upper bounds of a.

bound variable

A bound variable of a formula A is a variable that has a bound occurrence in A.

Bramantip

See mnemonic terms.

Burali-Forti's paradox

See paradox.

calculus

Any logistic system. The two most important types of logical calculi are propositional (or sentential) calculi and functional (or predicate) calculi. A propositional calculus is a system containing propositional variables and connectives (some also contain propositional constants) but not individual or functional variables or constants. In the extended propositional calculus, quantifiers whose operator variables are propositional variables are added. Among the partial propositional calculi, in which not all the theorems of the standard propositional calculus are obtainable, the most important are David Hilbert's positive propositional calculus (this contains all those parts of the standard propositional calculus that are independent of negation) and the intuitionistic propositional calculus (in this system axioms about negation acceptable from the intuitionistic point of view are added to the positive propositional calculus). A functional calculus is a system containing, in addition to the symbols of propositional calculus, individual and functional variables and/or constants, as well as quantifiers that take some of these variables and constants as their operator variables. In a first-order functional calculus (or first-order logic ) the quantifiers have as their operator variables only individual variables, and the functions have as their arguments only individual variables and/or constants. In a second-order functional calculus (or second-order logic) the operator variables of the quantifiers can be functional variables. After that, each odd order adds functional variables and/or constants some of whose arguments are of the type introduced two orders below, and each even order allows the use of the variables introduced one order below as operator variables for the quantifiers. When there are no individual or functional constants present the functional calculus is called pure ; when either is present it is called applied.

Camenes

See mnemonic terms.

Camestres

See mnemonic terms.

Cantor's paradox

See paradox.

Cantor's theorem

The theorem stating that for any given set a, the power set of a has a greater cardinality than a has.

cardinality (power)

For a given set, the cardinal number associated with it.

cardinal number

An object a that is associated with all and only the members of a set of equipollent sets. Various authors disagree on what this object is. The Frege-Russell definition of cardinal number is simply the identification of a with the set of equipollent sets.

Cartesian product

For a given set a, the set whose members are all and only the sets that contain one member from each member of a.

categorematic

In traditional logic, used of a word that can be a term in a categorical proposition. In contemporary logic, used of any symbol that has independent meaning. An example of a categorematic word is "men." Cf. syncategorematic.

categorical proposition

See proposition.

category

A general or fundamental class of objects or concepts about whose members assertions can significantly be made which differ from those that can significantly be made about nonmembers of this class. The two most famous lists of categories are those of Aristotle and Immanuel Kant. Aristotle's list comprises substance, quantity, quality, relation, activity, passivity, place, time, situation, and state. Kant's comprises unity, plurality, and universality (categories of quantity); reality, negation, and limitation (categories of quality); substantiality, causality, and reciprocity (categories of relation); and possibility, actuality, and necessity (categories of modality).

Celarent

See mnemonic terms.

Cesare

See mnemonic terms.

choice, axiom of (multiplicative axiom)

An axiom in set theory stating that if a is a disjoint set which does not have the null set as one of its members, then the Cartesian product of a is different from the null set. It can be proved that this axiom is equivalent to the well-ordering theorem.

choice function

A function R whose domain includes (or, according to some authors, is identified with the set of) all the nonempty subsets of a given set a and whose value is a member of any such subset.

Church's theorem

The theorem, stated and proved by Alonzo Church, that there is no decision procedure for determining whether or not an arbitrary well-formed formula of the first-order functional calculus is a theorem of that system.

Church's thesis

The thesis that every effectively calculable function (effectively decidable predicate) is general recursive.

circular reasoning

See fallacy.

class

(1) An aggregate. (2) In Gödel–von Neumann–Bernays set theory, where a distinction is made between sets and classes, a class is an object that can contain members but cannot be a member of any object. See set.

classification

Two of the issues of concern to traditional logicians were the nature of the process of grouping individuals into classes of individuals (species ), these classes into further classes, and so on (the process of classification), and the nature of the reverse process (the process of division )—breaking a class down into its subclasses, these into their subclasses, and so on, until the simplest classes are broken down into the individuals that are their members.

In the process of classification one begins with a group of individuals and arranges them into classes, called infimae species, none of which can be broken down into species but only into individuals. One then groups the infimae species into other classes, of which the infimae species are subclasses. (For any species the class of which it is a subclass is called the proximum genus. ) The grouping continues until one reaches the class of which all the original individuals are members. This is the summum genus, and when one reaches it the process of classification is finished. (All the classes between the infimae species and the summum genus are called the subaltern genera. )

In the process of division one begins with the summum genus and breaks it down into its subclasses, continuing until one reaches the infimae species. Finally, these are broken down into the individuals that are their members.

Several rules were set up for classification and division: (1) at each step only one principle may be used for breaking down the classes or grouping them together; (2) no group may be omitted at any step; (3) no intermediate step may be omitted. When applied to division this last rule is known as the rule of division non faciat saltum.

A dichotomy is a form of division (or of classification) in which at each stage the genus is divided into species according to whether or not the objects possess a certain set of differentiae. The two species formed (proxima genera ) are therefore mutually exclusive and jointly exhaustive.

closed sentence (closed schema)

A sentence (or schema) that has no free variables.

closed with respect to (closed under) a relation

A set is closed under a relation R if and only if for all a, if aRb and if a is a member of the set, then b is a member of the set.

closure of a formula

A formula formed by placing before an original formula A quantifiers binding all variables that occur freely in A. A universal closure is the formula formed when only universal quantifiers are used, and an existential closure is the formula formed when only existential quantifiers are used.

collective term

In traditional logic, a term that denotes a collection of objects regarded as a unity. An example is "the Rockies."

combinatory logic

A branch of mathematical logic where variables are entirely eliminated, their place being taken by certain types of functions that are unique to this branch of logic.

commutativity

The property of a relation R that consists in the equivalence of aRb and bRa, where a and b are any elements of the field of R.

comparability, law of (law of trichotomy)

The principle in set theory that the cardinality of two sets is always comparable; that is, for any two sets a and b, a is greater than b or equal to b or less than b.

complement of a set (negate of a set)

The set of all and only those objects that are not members of a given set a.

completeness

The word completeness is used in varying senses. In the strongest sense (E. L. Post) a logistic system is said to be complete if and only if for any well-formed formula A, either A is a theorem of the system or the system would become inconsistent upon the addition of A as an axiom (without any other changes); in this sense propositional calculus, but not pure first-order functional calculus, is complete. In a second, weaker sense (Kurt Gödel) a logistic system is said to be complete if and only if all valid well-formed formulas are theorems of the system; in this sense both propositional calculus and pure first-order functional calculus are also complete. In a third, and still weaker, sense of completeness (Leon Henkin) a logistic system is said to be complete if and only if all secondarily valid well-formed formulas are theorems of the system; in this sense the pure second-order functional calculus and functional calculi of higher order are complete.

complete set

A set all of whose members are subsets of it.

composition, fallacy of

See fallacy.

comprehension, axiom of

See abstraction, axiom of.

computable function

See Turing-computable.

conclusion

That which is inferred from the premises of a given argument.

concrete term

In traditional logic, a term that is the name of an individual or individuals. An example of such a term is "Socrates."

condition

A necessary condition is a circumstance in whose absence a given event could not occur or a given thing could not exist. A sufficient condition is a circumstance such that whenever it exists a given event occurs or a given thing exists. A necessary and sufficient condition for the occurrence of a given event or the existence of a given thing is therefore a circumstance in whose absence the event could not occur or the thing could not exist and which is also such that whenever it exists the event occurs or the thing exists.

This terminology is sometimes extended to the formal relations that exist between propositions. Thus, the truth of a proposition A is said to be a necessary condition for the truth of another proposition B if B implies A, and the truth of A is said to be a sufficient condition for the truth of B if A implies B.

conditional

See implication.

conditional proof

A proof that begins by making certain assumptions, A ₁, A ₂, · · ·, A_n, deducing B from them, and then asserting on the basis of this the truth of the hypothetical proposition "if A ₁, then if A ₂, then if …, then if A_n, then B. " The rule of conditionalization is the rule that allows one to make this last step on the basis of the preceding ones.

conjunction

A binary propositional connective (&,.), usually read "and," whose truth table is such that "A and B " is false when A or B or both are false and is true when both are true.

connective

A symbol that is used with one or more constants or forms to produce a new constant or form. When the constants or forms are propositional ones the connective is known as a propositional connective (or sentential connective ). The most common propositional connectives are negation, conjunction, disjunction, implication, and biconditional. They are classified as singulary, binary, etc., according to the number of propositional constants or forms with which they combine.

connotation

See meaning, Frege's theory of.

consequence

Any proposition that can be deduced from a given set of propositions. Thus, given the set of propositions {A, if A then B }, the proposition B is a consequence of the set, since it can be deduced from the members of the set by one application of modus ponens.

consequent

The part of a hypothetical proposition that follows the implication sign or the "then."

consequentia

The name given by medieval logicians to a true hypothetical proposition. Formal consequentiae (those which hold for all substitutions of the categorematic terms) were distinguished from material consequentiae (those holding only for particular categorematic terms).

consistency

A set of propositions has consistency (or is consistent) when no contradiction can be derived from the joint assertion of the propositions in the set. A logistic system has consistency when no contradiction can be derived in it. Two syntactical definitions of the consistency of a logistic system are Alfred Tarski's, that a system is consistent if not every well-formed formula is a theorem, and E. L. Post's, that a system is consistent if no well-formed formula consisting of only a propositional variable is a theorem. There is, in addition, a semantical definition of consistency, according to which a set of propositions (or a logistic system) is consistent if there is a model for that set of propositions (or for the set of all the theorems of the system). It must not be assumed that any of these definitions are equivalent; in any case where it is claimed that they are, a proof is required.

constant

A symbol that, under the principal interpretation, is a name for something definite, be it an individual, a property, a relation, etc.

constructive existence proof

A proof of the existence of a mathematical object having a property P that gives an example of such an object or at least a method by which one could find such an example.

contingent

Logically possible. See logical possibility.

continuity

An ordered dense class all of whose nonempty subsets which have an upper bound have a least upper bound has continuity (or is continuous). See entry "Continuity."

continuum hypothesis

The hypothesis, proposed by Georg Cantor, that the cardinality of the power set of a set whose cardinality is aleph-null (ℵ₀) is aleph-one (ℵ₁)—that is, that there is no set whose cardinality is greater than aleph-null but less than the cardinality of the power set of a set whose cardinality is aleph-null. The generalized continuum hypothesis is the hypothesis that for the cardinality of any infinite set, the next highest cardinality is the cardinality of its power set.

contradiction

The joint assertion of a proposition and its denial.

contradiction, law of

See laws of thought.

contradictory

Two propositions are contradictory if and only if their joint assertion would be a contradiction. "All men are mortal" and "Some men are not mortal," for example, are contradictory propositions. Two terms are contradictory when they jointly exhaust a universe of discourse and are mutually exclusive. In the domain of natural numbers other than 0, for example, "odd" and "even" are contradictory terms. See contrary.

contraposition

In traditional logic, a type of immediate inference in which from a given proposition another proposition is inferred that has as its subject the contradictory of the original predicate. (It should be noted that a change of quality is involved in some cases.) Partial contraposition results in a new proposition that is the same as the subject of the original proposition; full contraposition results in a predicate of the new proposition that is the contradictory of the subject of the original proposition. The process of contraposition (whether partial or full) yields an equivalent proposition only when the original proposition is an A- or O-proposition; when it is an E-proposition traditional logicians allowed for contraposition per accidens (or by limitation)—that is, contraposition plus a change in the quantity of the proposition from universal to particular—claiming that the proposition formed is equivalent to the original proposition. The process of contraposition yields no equivalent proposition when the original proposition is an I-proposition. See entry "Logic, Traditional."

contrary

Applied to two propositions that cannot both be true but can both be false. "All men are mortal" and "No men are mortal," for example, are contrary propositions. Also applied to two terms that are mutually exclusive, but need not be jointly exhaustive, in a universe of discourse. In the domain of natural numbers, for instance, "less than 7" and "more than 19" are contrary terms. See contradictory.

contrary-to-fact (counterfactual) conditional

A conditional proposition whose antecedent is known to be false.

converse domain of a relation (range of a relation)

For any relation R, the set of all objects a such that there exists an object b such that bRa.

converse of a relation (inverse of a relation)

For any relation R, the relation R * such that aR *b if and only if bRa.

conversion

In traditional logic, a type of immediate inference in which from a given proposition another proposition is inferred that has as its subject the predicate of the original proposition and as its predicate the subject of the original proposition (the quality of the proposition being retained). The process of conversion yields an equivalent proposition only when the original proposition is an E- or I-proposition; when it is an A-proposition traditional logicians allowed for conversion per accidens (or by limitation)—that is, conversion plus a change in the quantity of the proposition from universal to particular. Thus, the E-proposition "No men are immortal" yields "No immortals are men," but the A-proposition "All men are mortal" can be converted only by limitation, yielding "Some mortals are men." The process of conversion yields no equivalent proposition if the original proposition is an O-proposition. See entry "Logic, Traditional."

copula

In traditional logic, the term that connects the subject and predicate in a categorical proposition. It is always a form of the verb "to be."

corollary

A proposition that follows so obviously from a theorem that it requires little or no demonstration.

counterfactual conditional

See contrary-to-fact conditional.

course-of-values induction

An argument from mathematical induction such that in the induction step one proves that "if the property P holds for all numbers before a, it holds for a as well," where a is any number.

Darapti

See mnemonic terms.

Darii

See mnemonic terms.

Datisi

See mnemonic terms.

decision problem

The problem of finding an algorithm (a decision procedure ) that enables one to arrive, in a finite number of steps, at an answer to any question belonging to a given class of questions. For a logistic system in particular, this is the problem of finding a decision procedure for determining, for any arbitrary well-formed formula of the system, whether or not it is a theorem of the system.

A positive solution to a decision problem consists of a proof that a decision procedure exists. A negative solution to a decision problem consists of a proof that no such procedure is possible. An example of a positive solution is the proof that the truth tables provide a decision procedure for the propositional calculus; an example of a negative proof is Church's theorem.

decision procedure

See decision problem.

Dedekind finite

See finite set.

Dedekind infinite

See finite set.

deducible

A set of propositions is said to be deducible from another set of propositions if and only if there is a valid deductive inference which has the latter set as its premises and the former set as its conclusion.

deduction

A form of inference such that in a valid deductive argument the joint assertion of the premises and the denial of the conclusion is a contradiction.

deduction theorem

For a given logistic system, the metatheorem that states that if there is a proof in the system of A _{n + 1} from the assumptions A ₁, A ₂, · · ·, A_n, then there is also a proof in the system of the proposition "if A_n, then A _{n + 1}" from the assumptions A ₁, · · ·, A _{n − 1}.

definiendum

That which is defined in a definition.

definiens

That which, in a definition, defines the definiendum.

definite descriptions, theory of

A definite description is a description which, by virtue of the meanings of the words in it, can apply to only one object. A standard example of a definite description is "the author of Waverley. " The theory of definite descriptions, introduced by Bertrand Russell, aims at eliminating definite descriptions. Unlike most other eliminative theories, Russell's does not attempt to offer a way of explicitly defining definite descriptions. Instead, it shows how in any given context the description together with the context can be eliminated in such a way that the resulting linguistic expression is equivalent to the original one. It is for this reason that Russell's theory is said to offer a way of contextually defining definite descriptions.

If we symbolize the definite description as "(x )P " ("the unique x such that P," where P is any well-formed expression), Russell's theory can be stated as follows (unless otherwise indicated, it will be supposed that the scope of the occurrence of a definite description is the smallest well-formed part of the formula that contains that occurrence of the definite description): Let us symbolize the scope of the definite description as M and the whole formula as A. M is replaced by the expression "(∃y )(z )[(Pz ≡ z = y ). M ′]," where y and z are the first two variables not occurring in A and M ′ is the result of substituting y for every occurrence of "(℩x )P " in M. The resulting formula, A ′, is equivalent to A but lacks the definite description that we set out to eliminate.

The motivation for this theory is to be found in certain difficulties that arose for Russell's theory of meaning, the theory that the meaning of a term is its reference. It has been suggested, primarily by W. V. Quine, that since similar difficulties can arise for names in general, this theory should be extended to all names. Russell, however, thought that there was a class of names, logically proper names, for which these difficulties could not arise; he therefore favored retaining names of this class. See entry "Proper Names and Descriptions."

definition

The description or explanation of the meaning of a word or phrase. Various types of definitions have been distinguished by logicians. To begin with, there is the distinction between a lexical definition (a report of a meaning the word already has) and a stipulative definition (a proposal to assign a meaning to a word). One must also distinguish, with traditional logicians, the following techniques for defining: (1) dictionary definition, giving a word or phrase that is synonymous with the definiendum; (2) ostensive definition, giving examples of objects to which the word or phrase is properly applied; and (3) definition per genus et differentiam, giving the genus of the objects to which a word or phrase is properly applied and the differentiae that distinguish these objects from the other members of the genus. See predicables.

Some new types of definition that have been discussed by contemporary logicians include (4) definition by abstraction, defining a class term by specifying the properties that an object must have in order to be a member of the class, and (5) recursive (inductive ) definition, defining a number-theoretic function or predicate term by giving the value or values of the function or predicate when 0 is the argument and then giving the value or values when the successor of any number a is the argument in terms of a and the value when a is the argument (cf. recursive function ). Finally, one must distinguish (6) contextual definitions, which give meaning to the definiendum only in particular contexts, not in isolation.

definition, Aristotelian theory of

See predicables.

demonstration (derivation)

A deductive proof offered for a given set of propositions.

De Morgan's laws

The theorems of propositional calculus that assert the material equivalence of "not (A or B )" with "not-A and not-B " and "not (A and B )" with "not-A or not-B. " De Morgan, in his book Formal Logic, did not actually state these laws; he gave, instead, the corresponding laws for the logic of classes. It should be noted that some of the medieval logicians stated these theorems for the logic of propositions.

denotation

See meaning, Frege's theory of.

dense

Used of an ordered set such that between any two elements of the set there is another element of the set.

denumerable set

A set whose cardinality is aleph-null (ℵ₀). Some authors extend "denumerable" so as to make it synonymous with "enumerable."

derivable

See deducible.

derivation

See demonstration.

derived rule of inference

A metalinguistic theorem asserting that under certain conditions there is a proof in the object language for a certain type of well-formed formula. The point of such theorems is that they enable us to state that certain well-formed formulas are theorems of the object language without having to find a proof in the object language for these formulas.

descending induction

An argument that shows that a certain property holds for no number by demonstrating that if it held for any number, it must hold for a lesser number.

diagonal proof

The proof, given by Georg Cantor, that there are infinite sets that cannot be enumerated.

dichotomy

See classification.

dictum de omni et nullo

The principle of syllogistic reasoning that asserts that whatever is distributively predicated (whether affirmatively or negatively) of any class must be predicated of anything belonging to that class.

difference of sets

For any two sets a and b, the set of all and only those objects that are members of a but not of b.

differentia

See predicables.

dilemma

An argument whose major premise is the conjunctive assertion of two hypothetical propositions and whose minor premise is a disjunctive proposition. If the minor premise alternatively affirms the antecedents of the major premise, the dilemma is said to be constructive ; if the minor premise alternatively denies the consequents of the major premise, the dilemma is said to be destructive. Constructive dilemmas are divided into simple constructive dilemmas (the antecedents of the major premise are different and the consequents are the same) and complex constructive dilemmas (both the antecedents and the consequents of the major premise are different). Destructive dilemmas are divided into simple destructive dilemmas (the consequents of the major premise are different and the antecedents are the same) and complex destructive dilemmas (both the consequents and the antecedents of the major premise are different).

Dimaris

See mnemonic terms.

Disamis

See mnemonic terms.

discreteness

The property possessed by all ordered sets that lack the property of continuity.

disjoint sets

Sets that have no members in common.

disjunction, exclusive (alternation)

A binary propositional connective, one possible interpretation of "or," whose truth table is such that "A or B " is true if and only if one of the two propositions is true and the other false.

disjunction, inclusive

A binary propositional connective (∨), one possible interpretation of "or," whose truth table is such that "A or B " is true in all cases except where both A and B are false.

distributed term

In a categorical proposition the occurrence of a term is distributed if and only if the term as used in that occurrence covers all the members of the class that it denotes. In a universal categorical proposition the subject is distributed; in a negative categorical proposition the predicate is distributed.

distributivity

The relation that exists between two relations R and R * when "aR (bR *c )" is identical with "(aRb )R *(aRc )."

division

See classification.

division non faciat saltum

See classification.

domain of a relation

For any relation R, the set of all objects a such that there exists an object b such that aRb.

domain of individuals

For a given interpretation of a given logistic system, the set of objects that is the range of the individual variables.

duality

The relation that exists between two formulas that are the same except for the interchanging of the universal with the existential quantifier, the symbol for the null class with that for the universal class, sum of sets with product of sets, and conjunction with disjunction (where conjunction, disjunction, and negation are taken as primitive, all other propositional connectives being defined in terms of them). The two formulas are said to be the duals of each other. "A and B" and "A or B," for example, are duals.

dyadic relation

A two-place relation.

effectiveness

A notion is said to be effective if there exists an algorithm for determining, in a finite number of steps, whether or not the notion applies to any given object. For example, in a logistic system the notion of a proof is effective, since there is a mechanical procedure for determining, in a finite number of steps, whether or not in that system a given sequence of well-formed formulas constitutes a proof of another given well-formed formula.

element

A member of a given set.

elementary number theory

The theory of numbers insofar as it does not involve analysis.

empty set

See null set.

entailment

The relation that exists between two propositions one of which is deducible from the other.

enthymeme

A syllogism in which one of the premises or the conclusion is not explicitly stated. An example of an enthymeme is the inference of "Socrates is mortal" from "All men are mortal," the missing premise being "Socrates is a man."

enumerable set

A set that either is finite or has a cardinality of aleph-null (ℵ₀). Cf. denumerable set.

epagoge

In traditional logic, the process of establishing a general proposition by induction.

epicheirema

A syllogism in which one or more of the premises is stated as the conclusion of an enthymematic prosyllogism. See polysyllogism.

episyllogism

See polysyllogism.

E-proposition

In traditional logic, a universal negative categorical proposition. An example is "No men are mortal."

epsilon

In set theory, the name of the symbol (ε) for set-membership.

equality

A relation that exists between two or more sets, equated by some authors with identity and by others with equivalence relation.

equipollent

Used of sets between which there exists a one-to-one correspondence.

equivalence relation

A relation that is reflexive, symmetric, and transitive (see relation ). Identity is a standard example of an equivalence relation.

equivalent

Used of two propositions that are so related that one is true if and only if the other is true. Some authors also use this term, as applied to sets, synonymously with "equipollent."

equivocation

See fallacy.

eristic

The art of fallacious but persuasive reasoning.

essence

See predicables.

Euler's diagrams

The representations, generally attributed to Leonhard Euler, of relations among classes by relations among circles. See entry "Logic Diagrams."

excluded middle, law of

See laws of thought.

existential generalization, rule of

The rule of inference that permits one to infer from a statement of the form "Property P holds for an object a " a statement of the form "There exists an object such that property P holds for it."

existential import

The commitment to the existence of certain objects that is entailed by a given proposition.

existential instantiation, rule of

The rule of inference that permits one to infer from a statement of the form "There exists an object such that property P holds for it" a statement of the form "Property P holds for an object a. " Because this inference is not generally valid, restrictions have to be placed on its use.

existential quantifier

The symbol (E ) or (∃), read "there exists." It is used in combination with a variable and placed before a well-formed formula, as in "(∃a ) ______" ("There exists an object a such that ______").

extension

Although often used synonymously with "denotation," this term is sometimes used to refer to the set of species that are contained within the genus denoted by a given term. In the first sense the extension of "men" is the set of all men; in the second sense it is the set of sets into which humankind can be divided.

extensional

Used of an approach to a problem which in some respect confines attention to truth-values of sentences rather than to their meanings. Thus, a logic in which, for purposes of deductive relations, truth-values may be substituted for sentences is an extensional logic. Cf. intensional.

extensionality, axiom of

An axiom in set theory stating that for any two sets a and b, if for all c, c is a member of a if and only if c is a member of b, then a is identical with b.

fallacy

An argument that seems to be valid but really is not. There are many possible types of fallacy; traditional logicians have discussed the following ones: (1) accentus, a fallacy of ambiguity, where the ambiguity arises from the emphasis (accent) placed on a word or phrase; (2) affirmation of the consequent, an argument from the truth of a hypothetical statement and the truth of the consequent to the truth of the antecedent; (3) ambiguity, an argument in the course of which at least one term is used in different senses; (4) amphiboly, a fallacy of ambiguity where the ambiguity involved is of an amphibolous nature; (5) argumentum ad baculum, an argument that resorts to the threat of force to cause the acceptance of the conclusion; (6) argumentum ad hominem, an argument that attempts to disprove the truth of what is asserted by attacking the asserter or attempts to prove the truth of what is asserted by appealing to the opponent's special circumstances; (7) argumentum ad ignorantiam, an argument that a proposition is true because it has not been shown to be false, or vice versa; (8) argumentum ad misericordiam, an argument that appeals to pity for the sake of getting a conclusion accepted; (9) argumentum ad populum, an argument that appeals to the beliefs of the multitude; (10) argumentum ad verecundiam, an argument in which an authority is appealed to on matters outside his field of authority; (11) begging the question (circular reasoning ), an argument that assumes as part of the premises the conclusion that is supposed to be proved; (12) composition, an argument in which one assumes that a whole has a property solely because its various parts have that property; (13) denial of the antecedent, an argument in which one infers the falsity of the consequent from the truth of a hypothetical proposition and the falsity of its antecedent; (14) division, an argument in which one assumes that various parts have a property solely because the whole has that property; (15) equivocation, an argument in which an equivocal expression is used in one sense in one premise and in a different sense in another premise or in the conclusion; (16) ignoratio elenchi, an argument that is supposed to prove one proposition but succeeds only in proving a different one; (17) illicit process, a syllogistic argument in which a term is distributed in the conclusion but not in the premises; (18) many questions, a demand for a simple answer to a complex question; (19) non causa pro causa, an argument to reject a proposition because of the falsity of some other proposition that seems to be a consequence of the first but really is not; (20) non sequitur, an argument in which the conclusion is not a necessary consequence of the premises; (21) petitio principii, see (11) begging the question ; (22) post hoc, ergo propter hoc, argument from a premise of the form "A preceded B " to a conclusion of the form "A caused B "; (23) quaternio terminorum, an argument of the syllogistic form in which there occur four or more terms; (24) secundum quid, an argument in which a proposition is used as a premise without attention given to some obvious condition that would affect the proposition's application; (25) undistributed middle, a syllogistic argument in which the middle term is not distributed in at least one of the premises. See entry "Fallacies."

Felapton

See mnemonic terms.

Ferio

See mnemonic terms.

Ferison

See mnemonic terms.

Fesapo

See mnemonic terms.

Festino

See mnemonic terms.

field of a relation

The union of the domain and the converse domain of a given relation.

figure

A way of classifying categorical propositions. According to most traditional logicians, since figure depends on the position of the middle term in the premises, there are four possible figures. In the first figure the middle term is the subject of the major premise and the predicate of the minor premise. In the second figure the middle term is the predicate of both premises and in the third figure the subject of both premises. In the fourth figure the middle term is the predicate of the major premise and the subject of the minor premise. Aristotle allowed only three figures and treated as being indirectly in the first figure those syllogisms that later logicians placed in the fourth. See entry "Logic, Traditional."

finitary method

The type of method to which David Hilbert and some of his followers restricted themselves in their metamathematical research. The clearest statement of the restrictions was made by Jacques Herbrand, who insisted that the following conditions be met: (1) One must deal only with a finite and determined number of objects and functions. (2) These are to be so defined that there is a univocal calculation of their values. (3) One should never affirm the existence of an object without indicating how to construct it. (4) One must never deal with the set of all the objects of an infinite totality. (5) That a theorem holds for all of a set of objects means that for every particular object it is possible to repeat the general argument in question, which should then be treated as only a prototype of the resulting particular arguments.

finite set (inductive set)

A set that either is empty or is such that there exists a one-to-one correspondence between its members and the members of the set of all natural numbers less than a specified natural number. A set which is not finite is said to be infinite.

Richard Dedekind introduced a different characterization of finite and infinite sets. A Dedekind finite set is one that has no proper subset such that there exists a one-to-one correspondence between the elements of the set and the elements of that proper subset. A Dedekind infinite set (or reflexive set) is one that is not Dedekind finite. It can be shown that Dedekind's characterization is equivalent to the previous one; the proof, however, involves the axiom of choice.

first element of a set

See bound of a set.

first-order logic

First-order functional calculus. See calculus.

formalism

The doctrine, advanced as a program by David Hilbert and his followers, that the only foundations necessary for mathematics are its formalization and a proof by finitary methods that the system thus produced is consistent. See entry "Mathematics, Foundations of."

formalization

The construction of a logistic system whose intended interpretation is such that under it the truths of a given body of knowledge are the interpreted theorems of the system.

formalized language

A logistic system with an interpretation.

formally imply

A proposition A is said to formally imply a proposition B in a given logistic system if there is, in that system, a valid proof of B from A taken as a hypothesis.

formal system

See logistic system.

formation rules

For a given logistic system, the rules that determine which combinations of symbols are well-formed formulas and which are not.

formula

For a given logistic system, any sequence of primitive symbols.

foundation, axiom of (Axiom der fundierung, axiom of regularity)

An axiom in set theory stating that every nonempty set a contains a member b which has no member in common with a.

free occurrence of a variable

For a given variable a that occurs in a given well-formed formula A, an occurrence of a in no well-formed part of A which is of the form "For all a, B " or of the form "There exists an a, B. "

free variable

A free variable of a formula A is a variable in A that has no bound occurrence in A.

Fresison

See mnemonic terms.

function

A many-one correspondence.

functional calculus

See calculus.

future contingents, problem of

The problem, first discussed by Aristotle, of whether any contingent statement about the future has a truth-value prior to the time it refers to.

Galenian figure

The fourth syllogistic figure, supposedly introduced by Galen.

generalization, rule of

The rule of inference that allows one to infer from every proposition another proposition that is the same as the original one except that it is preceded by a universal quantifier binding any variable.

general term

A term that is predicable, in the same sense, of more than one individual.

Gentzen's consistency proof

The proof, first given by Gerhard Gentzen in 1936, of the consistency of classical pure number theory with the unrestricted-induction postulate. The proof employs transfinite induction up to the ordinal ε₀.

Gentzen system

A system of logic characterized by the introduction into the object language of a new connective (symbolized by →) that has properties analogous to the ordinary metalinguistic idea of "provable in the system." The rules of inference of such a system apply to Sequenzen —that is, to formulas of the form "A ₁, A ₂, · · ·, A_n → B ₁, B ₂, · · ·, B_m," where m and n are equal to or greater than 0, and A ₁, A ₂, · · ·, A_n, B ₁, B ₂, · · ·, B_m are formulas of ordinary logical systems.

genus

See predicables.

Gödel-numbering

The assignment of a natural number to each entity of a formal system. See arithmetization of syntax.

Gödel's completeness theorem

The theorem, first introduced by Kurt Gödel in 1930, that every valid well-formed formula of pure first-order functional calculus is a theorem of that system.

Gödel's incompleteness theorems

Two theorems that were first proved by Kurt Gödel in 1931. One states that any ω -consistent system adequate for elementary number theory is such that there is a valid well-formed formula of the system not provable in the system. J. B. Rosser, in 1936, extended this result to any consistent system. The second theorem states that any consistent system adequate for elementary number theory is such that there can be no proof of the consistency of the system within the system. See entry "Gödel's Theorem."

Gödel–von Neumann–Bernays set theory

The form of axiomatic set theory that avoids the paradoxes of set theory by distinguishing between sets (collections that can also be elements of other collections) and classes (collections that cannot be elements of other collections) and ensuring that all the objects leading to paradoxes (for example, the universal class) are classes and not sets.

Henkin's completeness theorem

The theorem, proved by Leon Henkin in 1947, that every secondarily valid well-formed formula of pure second-order functional calculus is a theorem of that system.

hereditary property

See ancestral relation.

Hilbert program

See formalism.

ideal mathematics

For David Hilbert, the nonfinitary part of mathematics, which, although necessary, was suspect and therefore required a consistency proof. See real mathematics.

idempotency

A binary operation is idempotent if and only if that operation, when performed on any element with itself, results in just that element.

identically false

Used of a well-formed formula of propositional calculus whose truth-value is falsehood for all possible values of its constituent well-formed formulas.

identically true

Used of a well-formed formula of propositional calculus whose truth-value is truth for all possible values of its constituent well-formed formulas.

identity

A relation that holds only between an object and itself.

identity, law of

See laws of thought.

identity of indiscernibles

Gottfried Wilhelm Leibniz's principle that two objects are identical if for every class, one object belongs to the class if and only if the other does. This is not to be confused with what W. V. Quine has called the indiscernibility of identicals, the principle that if two objects are identical, they belong to the same classes.

iff

A common abbreviation for "if and only if." See biconditional.

ignoratio elenchi

See fallacy.

image

The members of the converse domain of a relation that are values of the relation when its argument is a member of a set that is part of its domain.

immediate inference

An inference of a conclusion from a single premise. Traditional logicians discussed two types: (1) opposition of propositions, the inference, from the truth or falsity of one proposition, of the truth or falsity of another proposition having the same subject and predicate (such inferences involve contradictory, contrary, subalternate, and subcontrary propositions), and (2) eductions, the inference, from one proposition, of another differing from it in subject or predicate or in both (these involve obversion, conversion, contraposition, and inversion).

imperfect figures

The second and third syllogistic figures, the valid arguments of which, according to Aristotle, are such that their validity can be known only by their reduction to valid syllogisms in the perfect first figure.

implication (conditional)

A binary propositional connective (→, ⊃), usually read "if-then," of which there are two major interpretations: (1) Material implication. Under this interpretation, "If A then B " is true in all cases except when A is true and B false. (2) Strict implication. Under this interpretation, "If A then B " is true only when B is deducible from A. Philonian implication is the Stoic version of material implication, and Diodorean implication is the Stoic interpretation of "if-then" according to which "If A then B " is true if whenever (in the past, present, or future) A is true, B is also true.

implicit definition

A set of axioms implicitly define the undefined terms in them by, in effect, confining the references of these terms to the intended ones. The axioms do this by stating conditions satisfiable by only one set of objects.

The idea that a set of axioms can implicitly define the undefined terms in them is usually credited to J. D. Gergonne (1819). It was once thought that the basic terms of arithmetic could be implicitly defined by the axioms (namely, Peano's postulates) containing them; however, it is now known that this cannot be done, since Peano's postulates admit of more than one interpretation.

impredicative definition

Definition of an object in terms of a totality of which it is a member. For an example of impredicative definition, see ancestral relation.

inclusion

A relation that holds between two sets when all the members of one are members of the other. The relation of set-inclusion must be distinguished from that of set-membership.

inconsistent

Used of a set of propositions from which, or a logistic system in which, a contradiction can be derived.

indemonstrables

The Stoics' name for the axioms of their propositional logic.

independence

An axiom A of a given logistic system is independent (or has independence) if and only if in the system obtained by omitting A from the axioms of the given system, A is not a theorem. A rule of inference R of a given logistic system is independent if and only if in the system obtained by omitting R from the rules of inference of the given system, R is not a derived rule of inference.

indirect proof (reductio ad absurdum)

An argument that proves a proposition A by showing that the denial of A, together with accepted propositions B ₁, B ₂, · · ·, B_n, leads to a contradiction. Strictly speaking, this fails to prove the truth of A, since one of the previously accepted premises may be false; the force of the argument therefore rests on using premises that are far better established than the denial of A, so that the denial of A will be rejected and A accepted.

individual (particular)

(1) Anything considered as a unit. (2) In the theory of types, any member of the lowest type.

induction

Among acceptable inferences, logicians distinguish those in which the joint assertion of the premises and the denial of the conclusion is a contradiction from those in which that joint assertion is not a contradiction. The former are deductive inferences; inductive inferences are to be found among the latter.

Much has been written about the precise nature of inductive inferences, but few definite results have been obtained. It is likely that there is a wide variety of types of inductive inferences. Two quite different types are the inference from observational data to theoretical conclusions and the inference from the composition of a sample to the composition of a whole population.

induction, mathematical

An inference of the form "0 has the property P ; if any natural number a has the property P, then its successor has the property P ; therefore, every natural number has the property P. " The first step is called the basis, or the zero step, of the induction, and the second is called the induction step.

inductive set

See finite set.

inference

Derivation of a proposition (the conclusion) from a set of other propositions (the premises). When the inference is acceptable the premises afford good reasons to assert, or render certain, the conclusion.

infima species

See classification.

infinite set

See finite set.

infinity, axiom of

An axiom in set theory that guarantees the existence of an infinite number of individuals. This axiom takes various forms, all having in common the property of being valid in at least one infinite domain of individuals while not being valid in any finite domain of individuals.

initial ordinal

An ordinal that is not equipollent with any smaller ordinal.

insolubilia

The medieval name for antinomies. The antinomies that are usually referred to by this name are variants of the Liar paradox.

intension

A term sometimes used by traditional authors as synonymous with "connotation." In contemporary logical works "intension" has come to be synonymous with "sense." See meaning, Frege's theory of.

intensional

(1) Used of an approach which in some respect considers the meaning as well as the truth-value of a formula. A characteristic of such systems is that some propositions in them are referentially opaque. Systems of modal logic are usually intensional systems.

(2) Used of a proposition that contains a referentially opaque part. Cf. extensional.

intention, first (primary)

In medieval logic, signs that signify things and not other signs are said to have first intention. See entry "Logic, Traditional."

intention, second (secondary)

In medieval logic, signs that signify other signs and not things are said to have second intention. See entry "Logic, Traditional."

interpretation

An interpretation of a set A of well-formed formulas consists of a nonempty set (the domain of the interpretation ) and a function which assigns to each individual constant appearing in any of the members of A some fixed element in the domain, to each n -place predicate letter appearing in any of the members of A some n -place relation in the domain, and to each n -place function letter appearing in any member of A some function whose arguments are n -tuples of elements of the domain and whose values are also elements of the domain. The individual variables are thought of as ranging over the elements of the domain, and the connectives are given some meaning. Such an interpretation provides meaning for the members of A.

The principal interpretation is the intended interpretation. The secondary interpretations of a set of well-formed formulas are all the interpretations, other than the principal one, such that under them all the members of the set are true.

intersection of sets (product of sets)

The set of all the objects that are elements of all the sets a ₁, a ₂, · · ·, a_n (symbolized "a ₁ ∩ a ₂ ∩ · · · ∩ a_n ").

intuitionism

The doctrine, advanced by L. E. J. Brouwer and his followers, whose key thesis is that a mathematical entity with a particular property exists only if a constructive existence proof can be given for it. As a result the actual infinite is ruled out of mathematics, and only denumerably infinite sets, viewed as potentially infinite, are allowed. Furthermore, the law of excluded middle is rejected in the sense that when infinite classes are being dealt with, a disproof of a universal statement is not automatically a proof of its denial—that is, an existential statement. See entry "Mathematics, Foundations of."

intuitive set theory

The form of set theory that is based on an unrestricted use of the axiom of abstraction. The paradoxes of set theory were generated within a system of intuitive set theory.

inverse of a relation

See converse of a relation.

inversion

In traditional logic, a type of immediate inference in which from a given proposition another proposition is inferred whose subject is the contradictory of the subject of the original proposition. See entry "Logic, Traditional."

iota operator

The definite description operator, ℩. It is read: "The unique ______ such that ______."

I-proposition

In traditional logic, a particular affirmative categorical proposition. An example is "Some men are mortal."

joint denial

A binary propositional connective (↓) whose truth table is such that "A joint-denial B " is true if and only if both A and B are false. Joint denial and the Sheffer stroke function are the only binary propositional connectives that are adequate for the construction of all truth-functional connectives.

judgment

(1) The affirming or denying of a proposition. (2) The proposition affirmed or denied.

Lambert's diagrams

The representation, introduced by J. H. Lambert, of relations among classes by relations among straight lines.

law of logic

Any general truth of logic.

laws of thought

Three laws of logic that were traditionally treated as basic and fundamental to all thought. They were (1) the law of contradiction, that nothing can be both P and not-P, (2) the law of excluded middle, that anything must be either P or not-P ; and (3) the law of identity, that if anything is P, then it is P.

lekton

The Stoic name for the sense of a formula.

lemma

A theorem proved in the course of, and for the sake of, the proof of a different theorem.

level (order)

In the ramified theory of types, a class of objects that is composed of all and only those objects such that the definition of one of them requires no reference to a totality containing other members of the class. A hierarchy of levels is built up by beginning with the class of those objects that can be defined without reference to any totality and continuing with succeeding levels, members of each of which are defined in terms of totalities of objects of the previous level.

Liar paradox

See paradox, Epimenides' paradox.

limit

For a given sequence of numbers, the number a such that for any arbitrarily small number b greater than 0 there exists a number c such that for any number d larger than c the absolute value of the difference between the d th member of the sequence and a is less than b.

limit number

An ordinal number that is not 0 and is such that if a is a member of it, then the successor of a is also a member of it.

limit ordinal

See limit number.

logic

The study of the validity of different kinds of inference. This term is often used synonymously with deductive logic, the branch of logic concerned with inferences whose premises cannot be true without the conclusion's also being true. The other major branch of logic, inductive logic, is concerned with inferences whose premises can be true even if the conclusion is false.

logical fiction

The apparent denotation of a symbol that really has no denotation. Formulas containing such symbols are translatable into formulas containing no symbol or symbols that even appear to have this denotation.

logical form

It is commonly said that logic is concerned with the form, not the matter, of a proposition or argument. The distinction between form and matter is, however, seldom made precise; it can therefore best be seen by consideration of an example:

If it is raining, people will carry umbrellas.

It is raining.

People will carry umbrellas.

Analysis of this inference shows that it is valid because it is of the form "If A, then B; A ; therefore, B. " The values of the variables make no difference in the validity of the argument. Formal logic is concerned with inferences, like this one, whose validity depends on their form.

As the example shows, the form of a proposition is nothing more than the result of substituting, in the proposition, free variables for the constants, whereas the matter of a proposition is that for which the variables are substituted. The form of an argument is the result of substituting, in all the premises and in the conclusion of the argument, free variables for constants.

In some contemporary works any formula that contains one or more free variables is called a form.

logical implication

The relation that holds between two propositions when one is deducible from the other.

logically necessary

See analytic.

logical possibility (possible truth)

A proposition that is not self-contradictory. Some authors restrict this term to propositions that are also not logically necessary.

logical truth

See analytic.

logic diagram

A diagram used to represent logical relations. See entry "Logic Diagrams."

logicism

The doctrine, advanced by Gottlob Frege and Bertrand Russell, that all the concepts of mathematics can be derived from logical concepts through explicit definitions and all the theorems of mathematics can be derived from logical axioms through purely logical deduction. See entry "Mathematics, Foundations of."

logistic method

The method of studying a subject by formalizing it.

logistic system (formal system)

A system whose primitive basis is explicitly stated in the metalanguage.

Löwenheim's theorem

See Skolem-Löwenheim theorem.

major premise

In a categorical syllogism, the premise that contains the major term.

major term

In a categorical syllogism, the term that is the predicate of the conclusion.

many-one correspondence

A relation R such that for every element a of its domain there is only one member b of its converse domain such that aRb. "Son of" is a many-one correspondence since for every member of its domain (for every son) there is only one member of the converse domain (his father) of which it is true that the member of the domain is the son of the member of the converse domain.

many-valued logic

A system of logic in which each formula has more than two possible truth-values.

map of one set into another

A one-to-one correspondence between two sets whose domain is the first set and whose converse domain is a proper subset of the second set.

map of one set onto another

A one-to-one correspondence between two sets whose domain is the first set and whose converse domain is the second set.

material implication

See implication.

mathematical induction

See induction, mathematical.

matter of a proposition

See logical form.

meaning, Frege's theory of

According to this theory, propounded by Gottlob Frege in 1892, the meaning of a proper name has two aspects, the sense and the reference. The reference of a proper name is that which it is a name of. Thus, the reference of "Sir Walter Scott" is Sir Walter Scott. Frege claimed that there must be, besides the reference, another aspect of the meaning of such a name. "Sir Walter Scott" and "the author of Waverley" have the same reference, but it would be most implausible to say that they have the same meaning. The aspect of meaning that distinguishes "Sir Walter Scott" from "the author of Waverley" is called the sense of the proper name.

It should be noted that this is a theory of the meaning of proper names, not common names. It is for common names that John Stuart Mill first introduced his distinction between denotation (the objects to which the common name is properly applied) and connotation (the characteristic or set of characteristics that determines to which objects the common name properly applies). Unlike Frege, Mill thought that the meaning of a proper name is simply that which it denotes.

mediate inference

An inference in which the conclusion follows from two or more premises.

membership

The relation that exists between a set and its elements. The relation of set-membership must be distinguished from the relation of set-inclusion.

mention of a term

An occurrence of a linguistic expression in quotation marks for the purpose of talking about that linguistic expression. For example, in "'Cicero' has six letters" it is not the orator himself but the word referring to him that is being discussed.

This is to be contrasted with use of a term, the occurrence of a linguistic expression for the purpose of talking about something other than the expression.

metalanguage

A language used to talk about an object language; a meta-metalanguage is a language used to talk about a metalanguage, and so forth. Derivatively, a proposition is said to be in the metalanguage if and only if it is about an expression in the object language.

metamathematics (proof theory)

The study of logistic systems. Some authors restrict this term to investigations employing finitary methods.

metatheorem

A theorem in a metalanguage.

metatheory

The metamathematical investigations relating to a given logistic system.

method of construction

Bertrand Russell's name for the method of introducing new types of numbers by defining them in terms of previously introduced numbers and the usual logical and set-theoretic notation. Opposed to the method of construction is the method of postulation, whereby one introduces new types of numbers as primitive terms with appropriate axioms.

middle term

In a categorical syllogism, the term that occurs in both premises but not in the conclusion.

minor premise

In a categorical syllogism, the premise that contains the minor term.

minor term

In a categorical syllogism, the term that is the subject of the conclusion.

mnemonic terms

The names that the medieval logicians introduced for the valid syllogisms. One such term is "Barbara." The key for these mnemonics is as follows: The three vowels respectively indicate the three constituent propositions of the syllogism as A, E, I, or O. For first-figure syllogisms the initial consonants are arbitrarily the first four consonants; for the other figures the initial consonants indicate to which of the first-figure syllogisms the syllogism in question may be reduced. Other consonants occurring in second-, third-, and fourth-figure mnemonics indicate the operation that must be performed on the proposition indicated by the preceding vowel in order to reduce the syllogism to a first-figure syllogism. The key for this is as follows: "s " indicates simple conversion, "p " indicates conversion per accidens, "m " indicates metathesis (interchanging of the premises), "k " indicates obversion, and "c " indicates convertio syllogism (that is, the syllogism is to be reduced indirectly). In mnemonic terms the only meaningless letters are "r," "t," "l," "n," and noninitial "b " and "d. " More elaborate mnemonics have been devised for syllogisms in which two or more of the premises exhibit modality. See entry "Logic, Traditional."

modality

(1) The characteristic of propositions according to which they can be described as "apodictic," "assertoric," or "problematic." An assertoric proposition asserts that something is the case; an apodictic proposition asserts that something must be the case; a problematic proposition asserts that something may be the case. This type of modality was called by the medieval logicians modality sine dicto (de re ).

(2) The characteristic of propositions according to which they can be described as "necessary," "impossible," "possible," or "not-necessary." Medieval logicians called this type modality cum dicto (de dicto ).

modal logic

The study of inferential relations among propositions which are due to their modality. Most logicians treat systems of modal logic as intensional, basing them upon strict implication. An alternative approach is to treat these systems as extensional, basing them upon a many-valued logic. See entry "Modal Logic."

model

An interpretation of a given set of well-formed formulas according to which all the members of the set are true. The standard model corresponds to the principal interpretation, and a nonstandard model corresponds to a secondary interpretation. See interpretation.

modus ponendo tollens

An inference of the form "Either A or B; A ; therefore, not-B. " This type of inference is valid only if "or" is interpreted as exclusive disjunction.

modus ponens

An argument of the form "If A then B; A ; therefore, B. " Some authors use the term to designate the rule of inference that allows arguments of this form.

modus tollendo ponens

An argument of the form "Either A or B ; not-A ; therefore, B. "

modus tollens

An argument of the form "If A then B ; not-B ; therefore, not-A. " Some authors use the term to designate the rule of inference that allows arguments of this form.

mood

A way of classifying categorical syllogisms according to the quantity and quality of their constituent propositions.

multiplicative axiom

See choice, axiom of.

name

In traditional logic, a word or group of words that can serve as a term in a proposition. A general name is one that can be significantly applied to each member of a set of objects, a singular name is one that can be significantly applied to only one object, and a collective name is one that can be significantly applied to a group of similar things regarded as constituting a single whole.

natural number

A member of a certain subset of the cardinal numbers. There are various ways of defining this subset so that it contains all and only the desired objects (namely 0, 1, 2, 3, · · ·); the most common way is to define it as the set of all objects that belong to all sets containing 0 and closed under the successor relation.

necessary condition

See condition.

necessary truth

See analytic.

negate of a set

See complement of a set.

negation

A singulary propositional connective (¬, ^-, ∼, −), usually read "not," whose truth table is such that "not-A " is true if and only if A is false.

negative name

In traditional logic, a name that implies the absence of one or more properties or that denotes everything with the exception of some particular thing or set of things. An example of such a name is "non-Briton."

non sequitur

See fallacy.

normal system of domains

A system of domains such that the axioms of second-order functional calculus are valid in them and the rules of inference of second-order functional calculus preserve validity in them.

null set (empty set)

A set with no members.

number

See cardinal number; natural number; rational number; real number ; entry "Number."

object language

A language used to talk about things, rather than about other languages. Derivatively, a proposition is said to be in the object language if and only if it is not about any linguistic expression. "Socrates was a philosopher" is therefore in the object language, whereas "'Socrates' has eight letters" is not.

obversion

In traditional logic, a type of immediate inference in which from a given proposition another proposition is inferred whose subject is the same as the original subject, whose predicate is the contradictory of the original predicate, and whose quality is affirmative if the original proposition's quality was negative and vice versa. Obversion of a proposition yields an equivalent proposition when applied to all four types (A, E, I, and O) of propositions that traditional logicians considered. See entry "Logic, Traditional."

omega

The smallest infinite ordinal (denoted by ω ), the order type associated with the set of all natural numbers as ordered in their natural order.

omega-complete

Used of a system which, if it contains the theorems that property P holds of 0, of 1, of 2, and so on, contains the theorem that P holds of all numbers.

omega-consistent

Used of a system which, if it contains the theorems that property P holds of 0, of 1, of 2, and so on, does not contain the theorem that P holds of all numbers.

one-many correspondence

A relation R such that for every member a of its converse domain, there is more than one object b that is a member of its domain such that bRa. "Father of" is an example of a one-many correspondence, since for every member of its converse domain (everyone who has a father) there is only one member of its domain (that person's father) such that the member of the domain is the father of the member of the converse domain.

one-to-one correspondence

A relation R such that for every member a of its converse domain, there is only one object b that is a member of its domain such that bRa. A one-to-one correspondence is said to be order-preserving if both its domain and its converse domain are simply ordered and if, for all c and d that are members of its domain and are such that c precedes d in the ordering of the domain, it is the case that their respective images e and f in the converse domain are such that e precedes f in the ordering of the converse domain.

open schema

A formula containing free individual and functional variables.

open sentence

A formula containing free individual variables.

operator

A symbol or combination of symbols that is syncategorematic under the principal interpretation of the logistic system it occurs in and that may be used with one or more variables and one or more constants or forms or both to produce a new constant or form. Universal and existential quantifiers are the most common examples of operators.

O-proposition

In traditional logic, a particular negative categorical proposition. An example is "Some men are not mortal."

order

See Level.

ordered, partially

A set a is partially ordered if and only if there is a relation R such that for all b, c, and d that are members of a, (1) if bRc and cRd, then bRd, and (2) it is not the case that bRb.

ordered, simply

A set a is simply ordered if and only if there is a relation R such that a is partially ordered by R and for all b and c that are members of a and are not identical, either bRc or cRb.

ordered, well

A set a is well ordered if and only if there is a relation R such that a is simply ordered by R and for every nonempty subset of a, there is a first element of that nonempty subset.

ordered pair

For given objects a and b, the ordered pair (a,b ) is the pair set of which one member is the unit set whose only member is a and the other member is the pair set whose members are a and b.

order-preserving

See one-to-one correspondence.

order type

The set of all sets that are ordinally similar to a given set.

ordinally similar

Two or more sets are ordinally similar if and only if there exists between them a one-to-one order-preserving correspondence.

ordinal number

An order type of a well-ordered set.

pairing axiom

An axiom in set theory stating that for any two objects a and b, there is a set c whose members are a and b only.

pair set

A set that contains exactly two members.

paradox (antinomy)

A statement whose truth leads to a contradiction and the truth of whose denial leads to a contradiction. Since F. P. Ramsey it has been customary to distinguish between logical paradoxes (often called paradoxes of set theory ), which can arise in the object language because they involve only the usual logical and set-theoretic symbols, and semantic paradoxes, which can arise only in the metalanguage because they involve semantic concepts.

The most prominent logical paradoxes are the following: (1) Russell's paradox. Consider the set of all objects that are not members of themselves. Is that set a member of itself? If it is, then it is not. If it is not, then it is. (2) Cantor's paradox. Consider the set of all sets. Is it equal to or greater than its power set? If it is equal, then there is a contradiction, since there is a proof that the power set of any set is greater than the set itself. If it is not, then there is a contradiction, since the power set of any set is a set of sets and must therefore be a subset of the set of all sets, and there is a proof that the subset of a set cannot be greater than the set itself. (3) Burali-Forti's paradox. Consider the set of all ordinals. Does it have an ordinal number? If it does not, there is a contradiction, since by the "less than" relation it is well ordered, and there is a proof that all well-ordered sets have ordinal numbers. If it does, there is a contradiction, since it can be proved that the set's ordinal number must be both equal to and less than its image in the mapping of the set of all ordinals onto the set of all ordinals less than its own ordinal.

The most prominent of the semantic paradoxes are the following: (1) Berry's paradox. Consider the expression "the least natural number not namable in fewer than 22 syllables." Is the number it denotes namable in fewer than 22 syllables? If it is, there is a contradiction, since by definition it cannot be. If it is not, there is a contradiction, since we can produce a way of naming it in 21 syllables—the way we named it in stating this paradox. (2) Epimenides' paradox. Consider the sentence "This sentence is not true." Is it true? If it is, then it is not; if it is not; then it is. (3) Grelling-Nelson paradox of heterologicality. A predicate is heterological if the sentence ascribing the predicate to itself is false. Is the predicate "heterological" itself heterological? If it is, then it is not; if it is not, then it is. (4) Paradox of the Liar. See Epimenides' paradox (although the name is often used to refer to the nearly identical paradox beginning with the sentence "This statement expresses a lie"). (5) Richard's paradox. Consider the set of all real numbers between 0 and 1 that can be characterized in a finite number of English words. This set has only denumerably many members. It can be shown, in a manner very similar to Cantor's diagonal proof, that we can specify in a finite number of English words a number that cannot belong to the set. Does it belong to the set? If it does, there is a contradiction, since it cannot. If it does not, there is a contradiction, since it can be characterized in a finite number of English words, and all such numbers belong to the set. See entry "Logical Paradoxes."

paradoxes of material implication

These so-called paradoxes consist in the fact that if "if ______ then ______" is taken in the sense of material implication, then any proposition of that form is true if the antecedent is false no matter what the consequent is or if the consequent is true no matter what the antecedent is. Thus, "If Eisenhower were premier of France, then the moon would be made of cheese" and "If 2 + 2 = 17, then Johnson is the president of the United States" are both true propositions if "if-then" is interpreted in the sense of material implication.

paralogism

Any fallacious reasoning.

particular

See individual.

Peano's postulates

A system of five postulates from which one can derive the rest of arithmetic. The five postulates are (1) 0 is a number; (2) the successor of any number is a number; (3) there are no two numbers with the same successor; (4) 0 is not the successor of any number; (5) every property of 0 also belonging to the successor of any number that has that property belongs to all numbers.

per accidens

Used of a predication to the subject of one of its accidents.

perfect figure

The first figure of the syllogism. According to Aristotle, this is the only figure to which the dictum de omni et nullo is directly applicable.

per se

Used of a predication to the subject of one of its essential attributes.

petitio principii

See fallacy , (11) begging the question.

polysyllogism

A series of syllogisms so linked that the conclusion of one is a premise of another. In such a series a syllogism is said to be a prosyllogism if its conclusion is a premise of the syllogism with which it is connected and an episyllogism if one of its premises is the conclusion of the syllogism with which it is connected. See sorites.

possible truth

See logical possibility.

post hoc, ergo propter hoc

See fallacy.

postulate

Although often used synonymously with "axiom," this term is sometimes confined to the basic propositions of a particular discipline, with the axioms being the basic propositions common to all disciplines (for example, the laws of logic). The distinction arises only when one is concerned not merely with a formal system but also with its interpretation.

postulation, method of

See method of construction.

potential infinite

The infinite regarded as a limiting concept, as something becoming rather than as something completed.

power

See cardinality.

power set

The set of all subsets of a given set.

power-set axiom

An axiom in set theory stating that for any given set, its power set exists.

pragmatics

See semantics, formal.

predicables

A classification of things and concepts as predicated of subjects, first made by Aristotle. His four predicables were definition, genus (in which he included differentia), proprium, and accident. Medieval logicians, following Porphyry, offered a list of five predicables—species, differentia, genus, proprium, and accident—which was adopted by most traditional logicians.

For Aristotle one defined a term by stating the essence of the object that it names (this statement is called the definition ). The essence of a thing is that property which makes it the type of thing it is and not some other type of thing. The essence has two aspects: the genus is that which is predicable essentially of other kinds of things as well, and the differentia is that which is possessed essentially only by things of one type (members of one species) and not by things of any other type. Thus, in "Man is a rational animal" the genus is "animal," and the differentia is "rational."

Aristotle distinguished between the essence of a thing and other properties which belong only to that type of thing but are not part of its essence; such a property is called a proprium. The precise manner in which he hoped to make this distinction is not very clear. He also recognized that a thing might have a property that it need not have. He called such a property an accident.

predicate

Traditionally, the word or group of words in a categorical proposition that connote the property being attributed to the subject or denote the class which the subject is being included in or excluded from. The term is often extended, in contemporary works, to cover all words or groups of words that connote properties or relations in any type of proposition. Thus, in "All men are mortal" the predicate is "mortal."

predicate calculus

See calculus.

predication

The attributing of a property to a subject.

premise

A member of the set of propositions, assumed for the course of an argument, from which a conclusion is inferred.

primitive basis

The list of primitive symbols, formation rules, axioms, and rules of inference of a given logistic system.

primitive symbols

Those symbols of a given logistic system that are undefined and are not divided into parts in the course of operating within the system. One can, following John von Neumann, divide these symbols into constants, variables, connectives, operators, and bracketlike symbols.

privative name

A name that implies the absence of a property where it has been or where one might expect it to be.

problematic proposition

See modality.

product of sets

See intersection of sets.

proof

For a given well-formed formula A in a given logistic system, a proof of A is a finite sequence of well-formed formulas the last of which is A and each of which is either an axiom of the system or can be inferred from previous members of the sequence according to the rules of inference of the system.

proof from hypothesis

A proof from a given set of hypotheses A ₁, A ₂, · · ·, A_n in a given logistic system is a sequence of well-formed formulas the last of which is the conclusion of the proof and each of which is either an axiom of the system or one of A ₁, A ₂, · · ·, A_n or a formula that can be inferred from previous formulas in the sequence by the rules of inference of the system.

proof theory

See metamathematics.

proper class

An object which contains members but which cannot itself be a member of any object.

proper subset

A subset of a given set that is not identical with the given set.

proposition

There is no uniform use of the word proposition among logicians and philosophers. Many writers distinguish a proposition from a sentence; thus, "Socrates was a philosopher" and "Socrates war ein Philosoph" would be two different sentences that express the same proposition. Other writers use sentence and proposition interchangeably. To avoid some of the associations of the word proposition some contemporary philosophers abandon the term altogether in favor of statement. For a discussion of some of the philosophical controversies arising in this connection, see entry "Propositions." For present purposes it is assumed that the reader has a rough idea of what the term proposition means. This discussion will accordingly confine itself to an account of the different kinds of propositions distinguished by logicians.

Propositions may be classified in many ways. To begin with, one must distinguish simple (or atomic or elementary ) propositions, propositions that do not have other propositions as constituent parts, from compound (or molecular ) propositions, propositions that do have other propositions as constituent parts.

Among simple propositions the more important types are categorical (or subject-predicate ) propositions, which affirm or deny that something has a property or is a member of a class, and relational propositions, which affirm or deny that a relation holds between two or more objects. A categorical proposition is singular when its subject is the name of an individual and general when its subject is the name of a property or class, affirmative when its predicate is affirmed of the subject and negative when its predicate is denied of the subject. A general categorical proposition is universal when it is talking about all the members of the subject class or all the objects that have the subject property and particular when it is talking about only some of the members of the subject class or some of the objects that have the subject property.

Among compound propositions the most important types are alternative (or disjunctive ) propositions, which are of the form "A or B," conditional (or hypothetical ) propositions, of the form "If A then B," conjunctive propositions, of the form "A and B," and negative propositions, of the form "Not-A. " Many propositions that seem to be simple turn out under proper analysis to be compound. Such propositions are known as exponible propositions.

Kant, and many logicians following him, distinguished a class of infinite (or limitative ) propositions, affirmative propositions with a negative term as predicate. This distinction has been challenged by many authors. A more widely accepted addition to our classification is the indefinite proposition, a proposition that is equivocal because no indication is given of whether it is universal or particular. Finally, modality provides still another means of classifying propositions.

propositional calculus

See calculus.

propositional connective

See connective.

propositional function

A function whose range of values consists exclusively of truth-values. Thus, "a is the father of George Washington" is a propositional function, since for any argument for a, the value of the whole unit is truth or falsehood, depending on whether or not the argument is the name of George Washington's father.

proprium

See predicables.

prosyllogism

See polysyllogism.

protothetic

A form of the extended propositional calculus, first introduced by Stanisław Leśniewski, to which have been added variables whose values are truth-functions and a notation for the application of a function to its argument or arguments, and in which the quantifiers are allowed to have variables of any kind as operator variables. In the higher protothetic, variables whose values are propositional functions of truth-functions are added.

proximum genus

See classification.

quality of a proposition

The characteristic that makes a proposition affirmative or negative. Kant, and logicians following him, added a third type, infinite propositions. See proposition.

quantification of the predicate

The prefixing of a sign of quantity, "some" or "all," to the predicate of a proposition in the same way as to the subject, a device introduced by Sir William Hamilton. The claim was that this would make explicit what was implicit in the proposition.

quantifier

An operator of which it is true that both the constant or form it is used with and the constant or form produced are propositions or propositional forms. Thus, an existential quantifier, when joined to a proposition or propositional form A, produces a new proposition or propositional form "(∃a )M. "

quantity of a proposition

The characteristic that makes a proposition universal or particular. Kant and others considered singular propositions as being a third, distinct type of quantity.

Quine's set theories

A group of set theories proposed by W. V. Quine, combining some of the features of type theory with some of the features of the Zermelo-Fraenkel and Gödel–von Neumann–Bernays set theories. As in the set theories, the axiom of abstraction is not retained in its full power, and the formation rules of intuitive set theory are not modified; as in type theory, the notion of stratification is used, since in certain key axioms only stratified formulas generate sets.

range of a relation

See converse domain of a relation.

range of values

The class of those things that are ambiguously named by a given variable.

rational number

A number that can be put into the form a/b, where a is any integer and b any natural number.

real mathematics

For David Hilbert, that part of mathematics that is finitary in character, has therefore a clear and intuitive meaning, and poses no problem about its foundation except for the fact that when ideal mathematics is adjoined to it the possibility of inconsistency arises. See ideal mathematics.

real number

Any number which can be represented by an unending decimal.

recursive function

There are various types of recursive functions. In order to explain them we must first introduce some terminology: a constant function is a function that has the same value for all of its arguments; a successor function has as its value for any given argument the successor of that argument; an identity function is a function of n arguments whose value is always the i th argument. All such functions are known as fundamental functions.

A function of n arguments is defined by composition when, given any set of previously introduced functions of n arguments, the value of the new function is equal to the value of a previously introduced function whose arguments in any particular case are the values of each of the members of the set of functions when their arguments are the arguments of the newly introduced function in that particular case. In symbols, where P is the new function being defined by composition, P (a ₁, a ₂, · · ·, a_n ) = R (S ₁(a ₁, a ₂, · · ·, a_n ), S ₂(a ₁, a ₂, · · ·, a_n ), · · ·, S_m (a ₁, a ₂, · · ·, a_n )), where R and S ₁, S ₂, · · ·, S_m are previously introduced functions.

A function is defined by recursion in the following circumstances: (1) A value is assigned to the function for the case where one of its arguments is 0 in terms of a previously introduced function whose arguments, except for 0, are in any particular case all and only the arguments of the new function in that particular case. In symbols, where P is the new function and R the previously introduced function, P (a ₁, a ₂, · · ·, a_n, 0) = R (a ₁, a ₂, · · ·, a_n ). (2) A value is given to the new function when 0 is not one of its arguments and when one of its arguments is the successor of any number b, in terms of a previously introduced function S, whose arguments, except for the successor of b, are in any particular case all the arguments of the newly introduced function, b itself, and the value of the new function when its arguments are all and only the arguments already given for S. In symbols, P (a ₁, a ₂, · · ·, a_n, b + 1) = S (a ₁, a ₂, · · ·, a_n, b, P (a ₁, a ₂, · · ·, a_n, b )).

Any numerical function that is a fundamental function or can be obtained, by composition or recursion or both, from the fundamental functions by a finite sequence of definitions is a primitive recursive numerical function. A function P is introduced by the least-number operator if its value for a given set of arguments is the least number b such that the value of a previously introduced function R, whose arguments in any particular case are the arguments of P in that case and b, is equal to 0 provided that there is such a b ; if there is no such b, the function is undefined for those arguments. In symbols, P (a ₁, a ₂, · · ·, a_n ) = the least b such that R (a ₁, a ₂, · · ·, a_n, b ) = 0, provided that there is a b such that R (a ₁, a ₂, · · ·, a_n, b ) = 0. Any numerical function that either is a fundamental function or can be obtained from the fundamental functions by a finite sequence of definitions by composition, recursion, and the least-number operator (when this operator is used in defining a general recursive function, it must be the case that for all a ₁, a ₂, · · ·, a_n there is a b such that R (a ₁, a ₂, · · ·, a_n, b ) = 0) is a general recursive numerical function.

recursively enumerable

Used of a set or class that is enumerated (allowing for repetitions) by a general recursive function. That is, there is a general recursive function whose converse domain has the same members as the set when its domain is the set of natural numbers.

recursive number theory

The development of number theory, instituted by Thoralf Skolem, in which no quantifiers are introduced as primitive symbols, in which universality is expressed by the use of free variables, and in which functions are introduced through definitions by recursion.

recursive set

A set that is enumerated (allowing for repetitions) by a general recursive function and whose complement is also enumerated (allowing for repetitions) by a general recursive function.

reducibility, axiom of

An axiom, introduced by Bertrand Russell and A. N. Whitehead in Principia Mathematica, which says that for any propositional function of arbitrary level there exists a formally equivalent propositional function of the first level.

reductio ad absurdum

(1) See indirect proof. (2) The method of proving a proposition by showing that its denial leads to a contradiction. In this sense it is often known as a reductio ad impossibile.

reduction of syllogisms

The process whereby syllogisms in imperfect figures are expressed in the first figure. Reduction is direct when the original conclusion follows from premises in the first figure derived by conversion, obversion, etc., from premises in an imperfect figure. Reduction is indirect when a new syllogism is formed which establishes the validity of the original conclusion by showing the illegitimacy of its contradictory. See entry "Logic, Traditional."

reference

See meaning, Frege's theory of.

referential opacity

An occurrence of a word or sequence of words such that one cannot in general supplant the word or sequence of words with another word or sequence of words that refers to the same thing while preserving the truth-value of the containing sentence. For example, although "9 is necessarily greater than 7" is true, the result of substituting for "9" a sequence of words that refers to the same thing, "the number of planets," is the false proposition "The number of planets is necessarily greater than 7." Therefore, in this occurrence "9" is referentially opaque.

reflexive relation

See relation.

reflexive set

See finite set.

regularity, axiom of

See foundation, axiom of.

relation

This term is not adequately defined in traditional logic. The failure to offer an adequate definition is symptomatic of the lack of serious consideration, on the part of traditional logicians, of the significant differences between categorical and relational propositions. Augustus De Morgan and C. S. Peirce were the first logicians in the contemporary period to study the logic of relational propositions. Since their time this subject has become an important part of logic. In contemporary works, particularly in works on set theory, a relation is defined as a set of ordered pairs.

A relation R is reflexive if "aRa " holds for all a that are members of the field of R, irreflexive if "aRa " holds for no members of the field of R, and nonreflexive if "aRa " holds for some but not all members of the field of R. For example, "is a member of the same family as" is a reflexive relation, "is not a member of the same family as" is an irreflexive relation, and "loves" is a nonreflexive relation.

A relation R is symmetric if for all a and b that are members of the field of R, aRb if and only if bRa, asymmetric if for all a and b that are members of the field of R, aRb if and only if not-bRa, and nonsymmetric when "aRb " and "bRa " hold for some but not all a and b that are members of the field of R. For example, "is a member of the same family as" is a symmetric relation, "is a child of" is an asymmetric relation, and "is a brother of" is a nonsymmetric relation.

A relation R is transitive when for all a, b, and c that are members of the field of R, if aRb and bRc, then aRc, intransitive when for all a, b, and c that are members of the field of R, if aRb and bRc, then not-aRc, and nontransitive when if aRb and bRc, then "aRc " holds for some but not all of the a, b, and c that are members of the field of R. For example, "is a descendant of" is a transitive relation, "is a child of" is an intransitive relation, and "is not a brother of" is a nontransitive relation.

The foregoing classifications are said to apply to a relation in a set if the corresponding properties hold for all members of the field of a relation that are members of the set. A relation is connective in a set if for all distinct a and b that are members of the set, either aRb or bRa.

The study of relational propositions has raised many philosophical issues—and has greatly influenced discussions of older issues—about the nature of relations. On these matters, see entry "Relations, Internal and External."

replacement, axiom of (axiom of substitution)

An axiom in set theory stating that for any set a and any single-valued function R with a free variable b, there exists a set that contains just the members R (b ), with b being a member of a.

representative of a cardinal number

A set that has a given cardinal number as its cardinality.

Richard's paradox

See paradox.

rule of inference (transformation rule)

For a given logistic system, any rule in its metalanguage of the form "From well-formed formulas of the form A ₁, A ₂, · · ·, A_n, it is permissible to infer a well-formed formula of the form B. "

Russell's paradox

See paradox.

Russell's theory of definite descriptions

See definite descriptions, theory of.

Russell's vicious-circle principle

The principle according to which impredicative definitions are not allowed.

satisfiable

A well-formed formula that is satisfiable in some nonempty domain of individuals.

satisfiable in a domain

A well-formed formula is satisfiable in a given domain of individuals if and only if it has the value truth for at least one system of possible values of its free variables.

Schröder-Bernstein theorem

The theorem, first conjectured by Georg Cantor and proved by Felix Bernstein and Ernst Schröder, which states that if a and b are sets such that a is equipollent with a subset of b and b is equipollent with a subset of a, then a and b are equipollent.

scope of a quantifier

For a given occurrence of a quantifier as part of a well-formed part of a well-formed formula, the rest of that well-formed part.

secondarily satisfiable

Used of a well-formed formula that is satisfiable in some normal system of domains.

secondarily valid

Used of a well-formed formula that is valid in every normal system of domains.

second-order logic

Second-order functional calculus. See calculus.

section of a set

See segment of a set.

segment of a set (section of a set)

The subset of a given set ordered by a given relation whose members are those members of the set that precede a given member in the given ordering.

selection set

A set that contains one member from each subset of a given set.

self-contradiction

A proposition that in effect both asserts and denies some other proposition.

semantical rule

Any rule in the metalanguage that concerns the meaning of expressions in the object language.

semantics, formal (semiotics)

The study of linguistic symbols. Following C. W. Morris, it is customary to divide formal semantics into three areas: (1) Syntax, the study of the relations between symbols. The study of the ways in which the symbols of a given language can be combined to form well-formed formulas is one part of syntax. (2) Semantics, the study of the interpretation of symbols. Following W. V. Quine, it is customary to distinguish between the theory of reference, which studies the reference or denotation of symbols, and the theory of meaning, which studies the sense or connotation of symbols. (3) Pragmatics, the study of the relations between symbols, the users of symbols, and the environment of the users. Thus, the study of the conditions in which a speaker uses a given word is part of pragmatics. See entry "Semantics."

sense

See meaning, Frege's theory of.

sentential calculus

See calculus.

sentential connective

See connective.

sequence

A function whose domain is a subset, not necessarily a proper one, of the set of natural numbers. Some authors extend the term to any function whose domain is ordered.

set

(1) An aggregate. (2) In Gödel–von Neumann–Bernays set theory, where a distinction is made between sets and classes, sets are those objects that can both contain members and be members of some other object.

Sheffer stroke function (alternative denial)

A binary propositional connective (|), whose truth table is such that "A stroke-function B " is false if and only if A and B are both true. The Sheffer stroke function and joint denial are the only binary propositional connectives adequate for the construction of all truth-functional connectives.

simultaneously satisfiable

A class of well-formed formulas is said to be simultaneously satisfiable if there is some nonempty domain of individuals such that for all the free variables in all the formulas that are members of the class, there exists at least one system of values in that domain for which every formula in the class has the value truth.

singular term

A term that, in the sense in which it is being used, is predicable of only one individual. For example, any definite description is a singular term.

singulary connective

See connective.

Skolem-Löwenheim theorem

In 1915, Leopold Löwenheim proved that if a well-formed formula is valid in an enumerably infinite domain, it is valid in every nonempty domain. A corollary is that if a well-formed formula is satisfiable in any nonempty domain, it is satisfiable in an enumerably infinite domain. In 1920, Thoralf Skolem generalized this corollary—and thus completed the theorem—by proving that if a class of well-formed formulas is simultaneously satisfiable in any nonempty domain, then it is simultaneously satisfiable in an enumerably infinite domain.

Skolem's paradox

The seemingly paradoxical fact that systems in which Cantor's theorem is provable, and which therefore have nondenumerable sets, must, by virtue of the Skolem-Löwenheim theorem, be satisfiable in an enumerably infinite domain.

sorites

A chain of syllogisms in which the conclusion of each of the prosyllogisms is omitted. If each of the conclusions forms the minor premise of the following episyllogism, the sorites is an Aristotelian sorites; if each of the conclusions forms the major premise of the following episyllogism, it is a Goclenian sorites.

sound

Used of an interpretation of a logistic system such that under the interpretation all the axioms either denote truth or always have the value truth, and all the rules of inference are truth-preserving.

species

See classification.

square of opposition

A diagrammatic representation of that part of the traditional doctrine of immediate inferences between categorical propositions that went under the name of the opposition of propositions. See entry "Logic, Traditional."

stratification

The substitution of numerals for variables in a formula (the same numeral for each occurrence of a single variable) in such a way that the symbol for class-membership is flanked always by variables with consecutive ascending numerals.

subalternation

The relation between a universal and a particular proposition of the same quality. Traditionally this relation has been viewed in such a way that the universal proposition implies the particular proposition. The universal proposition is called the subalternant ; the particular proposition is called the subalternate.

subaltern genera

See classification.

subcontrary propositions

Two propositions that cannot both be false but may both be true. Any I- and O-propositions with the same subject and the same predicate form a pair of subcontrary propositions.

subject

The word or words in a categorical proposition that denote the object to which a property is being attributed or the class which is either included in or excluded from some other class.

subset

Any set b such that all the members of b are members of a given set a.

substitution, axiom of

See replacement, axiom of.

substitution, rule of

A rule of inference that allows one to infer from a given formula A another formula B that is the same as A except for certain specified changes of symbols. The various rules of substitution differ in the types of changes they allow.

successor

For a given number, the number that follows it in the ordinary ordering of the numbers. In Peano's axiomatic treatment of arithmetic "successor" is treated as a primitive term. In the various set-theoretic treatments of arithmetic it is defined differently. For example, "the successor of a " is sometimes defined as the unit set whose only member is a.

sufficient condition

See condition.

summum genus

See classification.

sum of sets

See union of sets.

sum set

For a given set a, the set whose members are all and only those objects which are members of members of a.

sum-set axiom

An axiom in set theory stating that for any set a, its sum set exists.

supposition

Roughly, the property of a term whereby it stands for something; the doctrine of supposition was extensively developed by the medieval logicians. Material supposition is possessed by those terms that stand for an expression, and formal supposition is possessed by those terms that stand for what they signify. Among terms having formal supposition, those that are common terms have common supposition, and those that are properly applicable to only one individual have discrete supposition. When in a given occurrence a common term stands for the universal, it has simple supposition; opposed to this is personal supposition, a property possessed by a common term in those occurrences where it stands for particular instances.

syllogism

A valid deductive argument having two premises and a conclusion. The term is often restricted to the case where both premises and the conclusion are categorical propositions that have between them three, and only three, terms. More careful authors distinguish this case by referring to it as a categorical syllogism. A hypothetical syllogism is one whose premises and conclusions are hypothetical propositions, and a disjunctive syllogism is one whose premises and conclusion are disjunctive propositions. All of these cases, where the three propositions are of the same type, are pure syllogisms. A mixed syllogism is one in which there occur at least two types of propositions.

A strengthened syllogism is one in which the same conclusion could be obtained even if we substitute for one of the premises that is a universal proposition its subalternate. Thus, the syllogism whose premises are "All men are mortal" and "All baseball players are men" and whose conclusion is "Some baseball players are mortal" is a strengthened syllogism, since it would have been sufficient to have as a premise "Some baseball players are men." A weakened syllogism is one whose premises imply a universal proposition but whose conclusion is the subalternate of that universal proposition. The above example is also an example of a weakened syllogism, since the premises, as they stand, imply "All baseball players are mortal."

symbol, improper

A symbol that is syncategorematic under the principal interpretation of the logistic system it occurs in. An example of such a symbol is "and."

symbol, proper

A symbol that is categorematic under the principal interpretation of the logistic system it occurs in. Any individual constant is a proper symbol.

symmetrical relation

See relation.

syncategorematic

In traditional logic, used of a word which cannot be a term in a categorical proposition and which must be used along with a term in order to enter into a categorical proposition. An example of this is "all." In contemporary logic the term refers to any symbol that has no independent meaning and acquires its meaning only when joined to other symbols. Cf. categorematic.

syntactical variable

A variable ranging over the names of symbols and formulas.

syntax

See semantics, formal.

synthetic

Used of a proposition that is neither analytic nor self-contradictory.

systematic ambiguity (typical ambiguity)

A convention, introduced by Bertrand Russell and A. N. Whitehead, whereby one does not specify the type or order to which the variables in a formula belong, thus allowing one formula to represent an infinite number of formulas, namely all those formulas that are exactly like it except for the fact that their variables are assigned orders and types in such a manner that the formula formed is well-formed according to the formation rules of the ramified theory of types.

tautology

A compound proposition that is true no matter what truth-values are assigned to its constituent propositions. Thus, "A or not-A " is a tautology, since if "A " is true, then the whole proposition is true, and if "A " is false, then "not-A " is true, and therefore the whole proposition is still true.

term

Traditionally, the subject or predicate in a categorical proposition. Some authors extend the word term to cover all occurrences of categorematic words or expressions which, although not propositions by themselves, are parts of a proposition.

tertium non datur

The law of excluded middle. See laws of thought.

theorem

Any well-formed formula of a given logistic system for which there is a proof in the system.

theorem schema

A representation of an infinite number of theorems by means of an expression that contains syntactical variables and has well-formed formulas as values. Every value of the expression is to be taken as a theorem.

theory of types

The theory, introduced by Bertrand Russell and A. N. Whitehead in Principia Mathematica, which avoids the paradoxes of set theory by modifying the formation rules of intuitive set theory. In the simple theory of types the only modification is that every variable is assigned a number that signifies its type, and formulas of the form "a is a member of b " are well-formed if and only if a 's type-number is one less than b 's. In ramified type theory each variable is also assigned to a particular level, and certain rules are introduced about the levels of variables; these rules are such as to exclude classes defined by impredicative definitions. See entry "Types, Theory of."

tilde

The name of the symbol for negation (∼).

token

A specified utterance of a given linguistic expression or a written occurrence of it. An expression-type, on the other hand, is an entity abstracted from all actual and potential occurrences of a linguistic expression. In "John loves John," for example, there are three word-tokens but only two word-types.

transfinite cardinals

All cardinal numbers equal to or greater than aleph-null (ℵ₀).

transfinite induction

A proof by course-of-values induction where the numbers involved are the ordinal numbers. This type of proof is important because it can be used to show that a property holds not only for the finite ordinals but for the transfinite ordinals as well.

transfinite ordinal

The order-type of an infinite well-ordered set.

transfinite recursion

A definition of a function by recursion in such a way that a value is assigned not only when the argument is a finite ordinal but also when it is a transfinite ordinal.

transformation rule

See rule of inference.

transitive relation

See relation.

transposition

A rule of inference that permits one to infer from the truth of "A implies B " the truth of "Not-B implies not-A," and conversely.

trichotomy, law of

See comparability, law of.

truth-function

A function whose arguments and values are truth-values. A compound proposition is said to be a truth-functional proposition if the connective that is adjoined to the constituent propositions to form the compound proposition has a truth-function associated with it. In such a case, since the only arguments of the function are truth-values, the truth-value of the compound proposition depends only on the truth-values of its constituent propositions.

truth table

A table that shows the truth-value of a compound proposition for every possible combination of the truth-values of its constituent propositions.

truth-value

One of two abstract entities, truth and falsehood, postulated in Fregean semantics to serve as the reference of true and false sentences. In many-valued logics other truth-values are introduced.

Turing-computable

Used of a function whose value for any given argument a Turing machine can compute. The notion of Turing computability, due to A. M. Turing, is often introduced as a way of making precise the notion of an effectively computable function.

Turing machine

A machine that is capable of being in any one of a finite number of internal states at any particular time. The machine is supplied with a linear tape divided into squares on which symbols (from a fixed finite alphabet) may or may not be printed. It scans one, and only one, square at any given time and can erase a symbol from the scanned square and print some other symbol on it. The machine's behavior (in terms of changing what is on the scanned square, changing its internal state, and moving the tape so as to scan a different square) is governed by a table of instructions that determines what the machine is to do, given any configuration (a combination of the state the machine is in and the symbol on the scanned square) of the machine.

type

(1) See token. (2) In the theory of types, a class of objects all of whose members are such that they can be members of the same object. The lowest type is composed of all individuals, the next type of all sets of individuals, and each succeeding type of sets whose members are objects of the immediately preceding type.

typical ambiguity

See systematic ambiguity.

union of sets (sum of sets)

The set whose members are all and only those objects that are members of at least one of two or more sets.

unit set

A set with only one member.

universal generalization, rule of

The rule of inference that permits one to infer from a formula of the form "Property P holds for an object a " a formula of the form "Property P holds for all objects." Because this inference is not generally valid, restrictions have to be placed on its use.

universal instantiation, rule of

The rule of inference that permits one to infer from a statement of the form "Property P holds for all objects" a statement of the form "Property P holds for an object a. "

universal quantifier

The symbol ( ) or (∀ ), read "for all." It is used in combination with a variable and placed before a well-formed formula, as in "(a ) ______" ("For all a, ______").

universal set

A set such that there is no object a that is not a member of the set.

universe of discourse

Those objects with which a discussion is concerned.

univocal

A linguistic expression is univocal if and only if it is neither ambiguous nor equivocal.

use of a term

See mention of a term.

valid formula

A well-formed formula that is valid in every nonempty domain. A well-formed formula is said to be valid for a given domain of individuals if it is true for all possible values of its free variables.

valid inference

An inference the joint assertion of whose premises and the denial of whose conclusion is a contradiction.

value

A member of the range of values of a given variable.

value of a function

That member of the converse domain of a function with which a given argument is paired under the function.

variable

A symbol that under the principal interpretation is not the name of any particular thing but is rather the ambiguous name of any one of a class of things.

Venn diagram

A modification, first introduced by John Venn, of Euler's diagrams. The key differences between Euler's diagrams and Venn's diagrams stem from the fact that Venn, and many other logicians, wanted to deny the traditional assumption that propositions of the form "All P are Q " or "No P are Q " imply the existence of any P 's. For details, see entry "Logic Diagrams."

vicious-circle principle

See Russell's vicious-circle principle.

well-formed formulas

Those formulas of a given logistic system of which it can sensibly be asked whether or not they are theorems of the system. In any particular system, rules are given that define the class of well-formed formulas and enable one to determine mechanically whether or not a given string of symbols is a well-formed formula of the system.

well-ordering theorem

The theorem stating that for any set there is a relation that well-orders it. See choice, axiom of.

wff

A common abbreviation for "well-formed formula."

Zermelo-Fraenkel set theory

That form of axiomatic set theory that avoids the paradoxes of set theory by dropping the axiom of abstraction and substituting for it a set of axioms about set-existence.

Boruch A. Brody (1967)