LOGICAL AND MATHEMATICAL TERMS, GLOSSARY OF

*Algorithm*.  Basic concept in mathematics and, especially,
computability theory.  Generally, an algorithm is a calculatory
procedure given by a finite set of instructions for computing
solutions to a class of mathematical problems.  In computability
theory, algorithms, also called 'effective procedures', are finitary
rules for computing functions, to be executed mechanically on relevant
inputs.  In this sense, algorithmic calculation cannot rely upon any
special mathematical insight (for example, constructing proofs for
unsolved mathematical problems) or upon the outcomes of random
processes (for example, rolls of a die).  Example: the rules, learned
in primary school, for finding sums of columns of figures represent an
algorithm, in either sense, for number addition.

*Analytic (judgment or proposition)*.  Notion of modern logic.  A
judgment or proposition of subject-predicate form is analytic if the
predicate (concept) is 'contained in' the subject (concept).  Kant's
way of putting this was to say that in an analytic judgment the
predicate is *thought* in (the very act of) *thinking* the subject.
Analytic judgments are opposed to *synthetic* judgments, which are
defined as judgments in which thinking the subject does not entail
thinking the predicate (though the two may legitimately be associated
by other means).  In more recent philosophy the term 'analytic' is
generally applied to propositions that are true by dint of their forms
or the meanings of their constituent terms.

*Argument*.  Basic notion of logic.  The simplest argument is a set of
propositions divided into two parts: (1) a set of propositions
referred to collectively as the *premises*, and (2) a single
proposition referred to as the *conclusion*.  Complex arguments are
built up by suitably arranging a number of simple arguments or steps.
The premises, taken together, are supposed to provide a reason for
believing the conclusion in this sense: their joint truth is supposed
either to guarantee (in the case of deductive, non-ampliative or
demonstrative arguments) or to support to some lesser extent (in the
case of inductive, ampliative or non-demonstrative arguments) the
truth of the conclusion.

*Axiom*.  Term of traditional and modern logic.  An axiom is a
proposition of a theory that is treated as fundamental or not
admitting of proof.  Traditionally, axioms were also treated as
epistemically basic in various senses (for example, as being
self-evident or as not requiring proof for their acceptance).  In
modern axiomatic systems, *logical* axioms are the propositions that
are fundamental in presenting the underlying logic of the theory (for
example, the law of the excluded middle), and *proper* axioms are the
propositions that are fundamental in presenting the non-logical or
substantive truths of the theory (for example, in usual
axiomatizations of the arithmetic of the natural numbers, the law that
0 has no predecessor).

*Axiom of choice*.  Controversial principle of set theory used
implicitly in the nineteenth century and formulated explicitly by
Zermelo in 1904 for use in his proof of the well-ordering theorem.
Also known as the multiplicative axiom.  There are different versions
of the axiom of choice in modern set theory.  In its most familiar
statement, it is understood to guarantee, for every set A of non-empty
sets, a choice set, which is a set containing exactly one member from
each x in A.  It is essential to proofs of standard mathematical
results concerning the transfinite.  It is also equivalent to other
noteworthy principles, among them Zorn's lemma.  Thanks to celebrated
theorems of Goedel and of Paul Cohen, we know that it is neither
refutable nor provable from standard axioms for sets, such as those of
Zermelo-Fraenkel set theory, provided that they are consistent.  See
*AXIOM OF CHOICE*; *Zorn's lemma*.

*Axiom of infinity*.  Principle of set or type theory, variously
formulated, requiring the existence of an infinite number of objects
of the theory.  In the type theory of *Principia Mathematica* (1910),
Whitehead and Russell introduced an axiom of infinity to guarantee
infinitely many individuals; items of lowest type.  In set theories,
axioms of infinity assert the existence of infinite collections.
Zermelo included one formulation among his 1908 axioms for Cantor's
set theory.  In Zermelo's version the axiom states that there is a set
Z of which O (the empty set) is an element and which contains, for
each of its elements e, the further element {e}.

*Axiom of separation*.  Principle of set theory included by Zermelo in
his 1908 axioms for set theory, later reformulated by Skolem.  It
permits one to separate off those elements of a given set which
satisfy a given property.  Stated more formally, it says that whenever
A is a set and P is a well-defined property of A, the collection of
precisely those members of A possessing P is also a set.

*Axiom schema*.  Term of modern logic.  An axiom schema is an
expression which employs schematic 'letters' (metalinguistic
variables) and which determines an infinity of particular axioms, one
for each substitution of a definite expression of the appropriate sort
for the schematic letters.  A classic example is the axiom schema of
induction in first-order arithmetic.  It is formulated as

       (PHI(0) & .ALL. x (PHI x -> PHI x')) -> .ALL. x PHI x ,

where PHI is schematic for well-formed formulas of the language.  When
such an expression is substituted for PHI, we get an axiom of
first-order arithmetic.

*Axiomatic theory*.  Basic concept of modern logic.  A theory T
(conceived of as a set of sentences) is said to be *axiomatized* by a
set of sentences A (its axioms) when the sentences making up T are
precisely the sentences provable from A (that is, the sentences making
up T are the deductive closure of A).  It is said to be
*axiomatizable* just in case it is the deductive closure of some
subset of its theorems.  It is said to be *recursively axiomatizable*
just in case it is the deductive closure of some recursive subset of
its theorems.  It is said to be *finitely axiomatizable* just in case
it is the deductive closure of some finite subset of its theorems.

*Biconditional*.  Term of propositional logic.  A biconditional is a
sentence-forming operator which, given two sentences, produces a
sentence that is true just in case the given sentences have the same
truth-value.  The word can also refer to the compound sentence formed
using a biconditional operator.  The typical example in English is the
operator 'if and only if'.

*Bijection*.  Term of set theory and mathematics generally.  A
function is said to be a bijection when it is both one-one and onto
(in other words, when it is both an injection and a surjection).  If
f: A -> B is a bijection then for any b in B there is exactly one a in
A such that f(a) = b.

*Bound (occurrence of a) variable*.  See *Variable*.

*Cantor's theorem*.  Basic result in set theory, proved by Cantor in
1892.  It states that the power set p(A) of a set A (that is, the set
of all subsets of A) is always of greater size or cardinality than A.
Indeed, if A has cardinality a, then p(A) has cardinality 2^a.  See
*CANTOR'S THEOREM*.

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

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

A      All A are B (universal affirmative);
E      No A are B (universal negative);
I      Some A are B (particular affirmative);
O      Some A are not B (particular negative).

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

*Categorical syllogism*.  See *Syllogism, categorical*.

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

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

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

*Closure (deductive, logical)*.  Term of metalogic.  A set A of
sentences of a language L is deductively closed just in case every
sentence of L that is deducible from A is an element of A.  The
deductive closure of a set A is the set of all sentences deducible
from A.  Deductive closure is a syntactic notion.  Logical closure is
a semantic notion which obtains when a set A of sentences of L
contains every sentence of L that follows validly from A.

*Compactness*.  Semantic property of formal systems in modern logic
and a leading idea in model theory.  A formal system is compact just
in case the semantic consistency or satisfiability of every set of
formulas is finitely determined; that is, a set is satisfiable
whenever all its finite subsets are.  Equivalently, a system is
compact if whenever a sentence S is a logical consequence of a set of
sentences T, S is a logical consequence of some finite subset of T.
Classical propositional logic and first-order logic are both compact
(as proved by Gödel and Maltsev), the latter fact being of crucial
import in the model theory of first-order languages.  Classical
second-order logic, however, is not compact.  See *Satisfaction*.

*Completeness (of a logical calculus)*.  Term of metalogic.  A logical
calculus is weakly complete if every logical truth is a logical
theorem.  If one is interested in formalizing the more general notion
of logical consequence, then one will require that the calculus is
also strongly complete, that is, whenever a sentence S is a logical
consequence of a set of premises Y, there is a derivation of S from Y.
The name 'completeness theorem' is used for the theorem, first proved
by Gödel in 1930, that every consistent set of sentences of a
first-order calculus has a model.  From this it follows that the
calculus is both weakly and strongly complete.  See *Soundness (of a
logical calculus)*.

*Completeness (of a theory)*.  Notion of metamathematics.  A theory T
is said to be complete with respect to a given semantical property P
(for example, classical validity, classical truth) when all sentences
of the language of T that have P are theorems of T.  Thus, if P is the
classical truth (viz. a notion of truth according to which every
sentence is either true or false), T is complete if, for every
sentence A of the language of T, either A or the denial of A is a
theorem of T.  (This completeness property is sometimes referred to as
'negation completeness'.) Examples: the formal system known as
first-order Peano arithmetic (PA) is incomplete; full second-order
Peano arithmetic (that is, the full set of second-order logical
consequences of the second-order Peano axioms), however, is complete
with respect to classical truth.  See *Theory*.

*Computable function*.  Essential notion in abstract computability
theory.  A mathematical function f is computable whenever there is an
algorithm or finitary mechanical procedure which will accept any X for
which f is defined and, after a finite series of steps, produce the
appropriate value f(x) of the function on x.  Computable functions are
also called 'effectively computable', 'effectively calculable' or
'algorithmic' functions.  Since the early 1930s, a variety of
mathematically rigorous explications of computable function have been
offered, among them Turing computable function and recursive function.

*Conditional, counterfactual*.  Term of philosophical logic.  Also
known as 'contrary to fact conditionals' or 'subjunctive
conditionals', these are any of a variety of conditional or
"If... then..."  statements in which the 'if' clause or *antecedent*
states a condition which the speaker assumes to be unsatisfied.
Example: 'If Oswald hadn't killed Kennedy, someone else would have'.
(Contrast 'If Oswald didn't kill Kennedy, someone else did'.)
Counterfactual conditionals are neither truth-functional nor strict
conditionals and the issue of proper logical rules and semantics to
govern them continues to spark debate in philosophical logic.

*Conditional, material*.  Term of logic.  Sometimes also known as the
Philonian conditional.  It is a statement which places a condition
(called the *antecedent*) on the obtaining of another statement
(called the *consequent*).  A material conditional is false when the
antecedent is true and the consequent false.  Otherwise, it is true.
'If ..., then ___','___ if ...' and '... only if ___' are expressions
in English that are often used to express material conditionals.  In
each of these, the antecedent is the sentence that goes in the place
of '...', and the consequent the sentence that goes in the place of
'___'.

*Conditional proof*.  Term of logic and mathematics.  It signifies a
type of proof in which one deduces a conclusion C from a list of
assumed premises P_1,...,P_n and asserts on the basis of this the
conditional proposition 'If P_1 and P_2 and... and P_n, then C'

*Connective*.  See *Propositional operator / connective*.

*Conservative extension*.  Notion of metalogic.  A theory U is a
conservative extension of theory T whenever every theorem of U which
is statable in the vocabulary of T is also a theorem of T.  Example:
first-order arithmetic with addition and multiplication is a
conservative extension of first-order arithmetic with addition only.
See *Theory*.

*Consistency*.  Basic notion of metalogic.  In the syntactic sense, a
set GAMMA of sentences or propositions is said to be consistent
(satisfiable) just in case there is no sentence S such that both S and
not-S are derivable from GAMMA.  In the *semantic* sense, GAMMA is
consistent just in case there is no proposition S such that both S and
not-S are logically implied by GAMMA.

*Constant*.  In mathematics and science generally, a quantity or
linguistic expression having, in the context, a fixed, determinate
value, such as n or the acceleration of gravity, g.  In logic,
constants represent, syntactically, those places and patterns in a
formal expression not open to government by a quantifier or other
binding operator.  Semantically, contants are those elements of an
expression which do not range over various values after an
interpretation of the language has been fixed.  Logical constants are
those formal items which never permit re-interpretation; standardly,
these include connectives and quantifiers.  Predicate and individual
constants are those which, under a given interpretation, are assigned
fixed subsets of or elements from the domain of interpretation.

*Continuum hypothesis*.  Problem of set theory first raised by Cantor
in 1878. The smallest infinite class is that of the natural numbers
0,1,2,..., whose size is denoted by ALEPH_0.  The continuum (the class
of real numbers) is isomorphic to the power set of the natural numbers
so, by Cantor's theorem, the continuum is larger than the class of
natural numbers.  The continuum problem is the problem of determining
whether the continuum is the very next largest size (cardinality) of
infinite class after that of the natural numbers or whether there are
infinite classes of intermediate size. Cantor conjectured that there
are not.  This conjecture has come to be known as the continuum
hypothesis (in symbols, ALEPH_1 = 2^ALEPH_0).  The generalized
continuum hypothesis is the conjecture that this same structure holds
for the entire increasing series of infinite class sizes: that is, for
every size of infinite class ALEPH_a, one obtains the next largest
cardinal ALEPH_a+1 by forming the power set of a set of cardinality
ALEPH_a.  See *Cantor's theorem*; *CONTINUUM HYPOTHESIS*.

*Contraction*.  Term of modern logic.  A type of structural rule in
sequent systems.  Roughly it signifies a modification of a valid
argument or inference in which repetition of premises is eliminated or
diminished.

*Contradiction*.  Basic notion of logic.  A proposition is said to be
a contradiction when it is logically impossible that it be true or,
equivalently, when it is logically necessary that it be false.
Example: any proposition of the form 'p and not p' is a contradiction.

*Contraposition*.  Basic notion of logic.  In sentential logic,
turning a sentence 'If p then q' around to 'If not-q then not-p'
(called the contrapositive of the original sentence) is
contraposition.  This is valid in most logics of conditionals.  In
Aristotelian logic, contraposition refers to the valid immediate
inference forms 'All A are B; therefore all non-B are non-A' and 'Some
A are not B; therefore some non-B are non-A' and their converses.

*Converse (of a relation)*.  Term of logic and set theory.  The
converse (also called the inverse) of a relation R is the relation R%
such that Rxy if and only if R%yx.

*Countable*.  Term of set theory.  A set is countable (or denumerable)
when it is either empty or can be exhaustively listed using the
natural numbers.  Equivalently, a set is countable when it is either
finite or in one-one correspondence with the set of natural numbers.
Any set which is not countable is uncountable.

*Counterfactual (conditional)*.  See *Conditional, counterfactual*.

*Cut-elimination theorems*.  A class of crucial results in the proof
theory of formal logics, the first theorem of which was stated and
proved in 1934 by Gerhard Gentzen (though anticipated by Jacques
Herbrand).  Gentzen's cut-elimination theorem is also known as the
'Hauptsatz' (main theorem).  When formulated as a sequent calculus
(that is, as a system representing logical consequence immediately)
first-order predicate logic naturally contains a 'cut rule' for
eliminating extra hypotheses.  In a simple case, such a rule states,
'If A derives B or C, while A and C derives D, then A derives B or D',
hence cutting the extra hypothesis C.  Gentzen showed how to convert
every proof in his system into a (possibly much longer) cut-free
proof.  Cut-elimination theorems have been formulated and proved for a
wide variety of formal systems, including arithmetic and predicative
analysis, and shed considerable light on issues of provability and
consistency.

*De Morgan's laws*.  Theorems of propositional logic and Boolean
algebra known, in effect, to medieval logicians but named for De
Morgan (1806-71) who stated them as laws for class operations. In
propositional logic, De Morgan's laws assert that not-(A and B) is
equivalent to (not-A or not-B) and that not-(A or B) is equivalent to
(not-A and not-B) for statements A and B.

*De re / de dicto*.  Important distinction in modal and intensional
logics.  An epistemic or modal expression such as 'possibly' or 'it is
known that' is used de dicto just in case it is taken as modifying an
entire sentence or proposition (dictum).  It is used de re when it is
understood as attributing an epistemic or modal characteristic to some
particular items or features (res) mentioned in the sentence.  The
distinction, which played an implicit role in Greek logic and an
explicit role in medieval logic, has received various formulations
over the centuries.  Examples: when we construe 'It is possible that
everyone is married' as putting forward the statement that everyone is
married as possibly true, 'it is possible' is used de dicto.  If we
understand 'It is possible that everyone is married' to mean, of each
individual person, that they are possibly married, then that
possibility is ascribed de re.  See *DE RE / DE DICTO*.

*Decidability*.  Basic notion of computability theory and
metamathematics.  A set (for example, of numbers or of formulas in
some formal language) is decidable if there is a decision procedure
for membership in it, that is, an algorithm which determines for any
suitable item (number, formula and so on) whether it is a member of
the set.  A set is said to be semi-decidable if there is a procedure
which reliably confirms when presented with a member of the set that
it is a member, but which need not produce an answer at all when
presented with a non-member.  A property is said to be decidable or
semi-decidable if the set of items having the property is.  A sentence
S is decidable by or in a theory T just in case either S or not-S is
provable in T.  Examples: the truth-table method provides a decision
procedure for classical propositional logic and shows that the set of
propositional tautologies is decidable.  The set of valid sentences of
predicate logic, on the other hand, is only semi-decidable.  See
*Algorithm*.

*Deducibility*.  In a formal system F consisting of a language L,
axioms and/or rules of inference, a formula phi of L is said to be
deducible from a set of formulas A of L just in case there is a finite
sequence of formulas PHI_1,...,PHI_n of L such that PHI_n is PHI and
each PHI_i, i < n, is either an element of A, an axiom of F or follows
from preceding elements of PHI_1,...,PHI_n by a rule of inference of
F.  In an informal sense, a sentence is said to be deducible from a
set of sentences just in case it follows from them by deductive means
of reasoning.

*Deduction theorem*.  A theorem apparently first proved by Tarski in
1921 and first published by Herbrand in 1930.  It states that if a
formula B can be derived from a set of formulas T and a single formula
A (that is, if T, A |- B), then the sentence A —> B can be derived
from T (that is, T |- A -> B).

*Derivation*.  Notion of metalogic.  A derivation (or deduction) is a
syntactic entity which corresponds to an argument, proof or inference
in a given formal system of inference or proof.  Typically, it is a
finite sequence of sentences of a formal language in which the first
is an axiom or assumption of some sort and each succeeding element is
either an axiom or assumption or follows from previous elements via
the rules of inference of the system.  The conclusion of the
derivation is the last element of the sequence.  In such a system, a
sentence S is said to be derivable if there is a derivation whose last
element is S.

*Distributed term (of a syllogism)*.  Notion of traditional logic
which signifies the way in which a term is used in a categorical
proposition.  Historically, a distributed term is one that refers to
or stands for all members of its extension.  One common rule for
distribution is that universal (that is, A and E) propositions
distribute their subject terms and negative (that is, E and O)
propositions distribute their predicate terms.  Another common rule,
however, teaches that universal propositions distribute their subjects
and that particular propositions distribute their predicates.  This
illustrates the lack of clarity of the central notion of the
traditional characterization; namely, that of a terms 'referring to'
the elements of its extension.

*Duality*.  Important property of equational laws in Boolean algebra
and logical equivalences in classical logic.  In Boolean algebra, the
duality theorem asserts that an equation expresses a law of Boolean
algebra just in case its dual also does.  Here, the dual of a Boolean
equation results from interchanging the symbol for meet (intersection)
with that of join (union), and 0 with 1 throughout the equation.  In a
language for propositional logic in which disjunction, conjunction and
negation are primitives, the dual of a formula is obtained by
replacing disjunction by conjunction and conversely.  In this case,
whenever two formulas are logically equivalent, so are their duals.
The concept was also prominent in early nineteenth-century geometry,
where it was noticed that many theorems in plane geometry had duals
obtainable by interchanging the term 'line' with the term 'point'.

*Effective procedure*.  See *Algorithm*.

*Enthymeme*. Term of logic.  In modern logic, it signifies any
argument which, taken literally, is invalid, but which becomes valid
when certain propositions thought too obvious or apparent to require
explicit statement are taken as implicit premises.  In traditional
logic it referred broadly to a syllogism having a missing premise that
the reader was supposed to supply.

*Entscheidungsproblem*.  Problems highly influential in the
development of metamathematics and computability theory, first set by
David Hilbert.  To construct a positive solution to the
Entscheidungsproblem or decision problem for a formal system is to
describe a decision procedure or algorithm for determining the
provability or unprovability of arbitrary statements in the system.
The work of Church and Turing in 1935 and 1936 showed definitively
that there can be no such procedures for full first-order logic and
for elementary arithmetic.  See *Church's theorem*.

*Equinumerosity / equipollence*.  Term of set theory.  Sets are said
to be equipollent, or equinumerous, whenever they have the same number
of members.  More precisely, sets are equipollent whenever there is a
bijection between them.  Equipollence is a foundational notion for
Cantor's treatment of transfinite cardinal numbers.  See *Cardinality
(cardinal number)*.

*Equivalence relation*.  Term of mathematics.  A binary relation is an
equivalence relation if it is reflexive, symmetric and transitive in
its field.  Example: being parallel.  See *Relations (properties of)*.

*Existential generalization*.  Rule governing the logic of the
existential quantifier.  It permits one to conclude that there is
something that has the property P from a premise which asserts of some
particular thing that it has the property P.

*Existential instantiation*.  Rule governing the logic of the
existential quantifier.  It permits one to conclude a proposition of
the form 'o has P', where 'o' is the name of an object, from the
premise that 'There is at least one thing that has P'.  In using this
inference in a proof, however, one cannot choose 'o' to be the name of
any object about which one has additional information.  Hence, the
inference is tantamount to giving a mere name (that is, a tag which
carries no descriptive information with it) to that which is said to
exist.

*Existential quantifier*.  See *Quantifier*.

*Fallacy*.  Term of logic.  A fallacy is an (often unnoticed) error or
flaw in an argument which prevents it from fulfilling its task of
rational persuasion; also an argument featuring such an error.  A
fallacy is formal when its invalidity is discernible from the
argument's structure alone.  Otherwise, the fallacy counts as
informal.  See *FALLACIES*.

*Figure (of a categorical syllogism)*.  Term of traditional logic.
Signifies the relationship in which the middle term of a syllogism
stands to its major and minor terms.  Aristotle gave three figures
(also called schemata).  In the first, the middle term is the
predicate of one of the premises and the subject of the other.  In the
second it is the predicate of both premises.  In the third it is the
subject of both.  Some medievals and most moderns divided the first
figure into two to get four rather than three figures.  The first of
these is one in which the middle term is the predicate of the minor
term in one of the premises and the subject of the major term in the
other.  In the other, the middle term is the subject of the minor term
in one of the premises and the predicate of the major term in the
other.

*First-order / higher-order*. Notions of metalogic.  A first-order
variable ranges over individuals (that is, the elements of the domain
of an interpreting structure).  A second-order variable ranges over
sets of (or properties of or relations between) individuals, and a
third-order variable ranges over sets of sets of (or properties of
properties of, ...) individuals, and so on.  Logic of order n is the
logic of systems whose variables are of order at most n.  See
*Variable*.

*Forcing*.  Semantic method for extending models of set theory.
Forcing was first introduced in 1963 by Paul Cohen in his celebrated
proofs of the independence from Zermelo-Fraenkel set theory of the
axiom of choice and Cantor's continuum hypothesis.  Since Cohen's
initial results, elaborations and simplifications of forcing have been
applied to obtain consistency and independence results in many
branches of higher mathematics, including topology and algebra.  See
*FORCING*.

*Formal language*.  Basic notion of metalogic.  A formal language is
constituted by a finite vocabulary of symbols, together with formation
rules for determining which strings of symbols are grammatically well
formed (in particular, which are sentences).  The crucial requirement
is that it be effectively decidable whether a string of symbols is a
well formed expression or not.  See *FORMAL LANGUAGES AND SYSTEMS*.

*Formal proof (derivation)*.  See *Formal system*.

*Formal system*.  Basic notion of metalogic.  Also known as a logistic
system or calculus.  It is a system of proof based on a formal
language.  The distinction between the finite sequences of words of
the language that are proofs or derivations and those that are not is
effectively decidable.  No appeal to the meaning of any symbol is thus
required in order to determine of a finite sequence of words whether
or not it is a derivation.  It is purely a mechanical decision based
upon the forms or shapes of the symbols involved and the orders of
their combinations.  The theorems of a formal system are those words
for which there is a derivation.  Because the derivations form an
effectively decidable set, the theorems form an effectively enumerable
or (assuming Church's Thesis) recursively enumerable set.  See *Formal
language*.

*Free (occurrence of a) variable*.  See *Variable*.

*Function*.  Term of set theory and mathematics generally.  Also
called a mapping.  A function is an operation which takes elements
from one set and produces elements of another (or the same) set.  If f
is a function from A to B (in symbols, f : A —> B), A is called the
domain of f and B the range or codomain.  The elements a of A are
called the arguments or inputs of f, and the element f(a) of B
produced by applying f to a is called the value or output or image of
f at a.  A total function from A to B is a function which is defined
for every element of A.  Otherwise it is a partial function.  In
set-theoretic terms, a function signifies a many-one relation (that
is, a relation that associates with each appropriate sequence of
elements of its field a unique single element of its field).  An n-ary
function f is an n+1-ary relation R_f such that for all
a_1,...,a_n,c,d in the field of R_f, if R_f(a_1,...,a_n,c) (that is,
f(a_1,...,a_n) = c) and R_f(a_1,..,a_n,d), then c = d.

*Halting problem*.  Basic undecidability result in computability
theory.  It is provable that the halting problem does not admit of
general solution.  To solve the halting problem would be to construct
a general computer program (more precisely, a Turing machine or
register machine) which will correctly determine, of an arbitrary
program or machine P in the same language and an arbitrary potential
input n, whether P's computation will ever halt once n is actually
input to P.  Part of the import of the halting problem lies in the
fact that there are many natural, mathematical problems which can be
shown unsolvable by comparison with it.

*Homomorphism*.  Term of algebra and model theory.  In mathematics
generally, a homomorphism is (1) a function from the domain or
universe of a structure A into the domain of a structure B of the same
type or signature which (2) preserves structural features relevant to
the signature.  More specifically, a homomorphism maps the
distinguished elements, relations and operations of A into
corresponding elements, relations and operations of B.  In formal
logic, a homomorphism is a structure-preserving function between
similar models.

*Identity of indiscernibles*.  Principle enunciated by Leibniz
(Discourse on Metaphysics, §9).  It states that two substances may not
be exactly alike in all qualitative respects and differ only
numerically.  Stated contrapositively and in more modern terms, it
says that for all individuals x and y, if, for every property P, x has
P if and only if y has P, then x is identical to y.

*Impredicative definition*.  Term of metalogic.  An impredicative
definition of an object or class is any definition that refers to a
collection of which that object or class is an element.  The use of
impredicative definitions in mathematics was forsworn by Russell in
his vicious-circle principle.  The enforcement of this principle was
the primary motive of his theory of types.

*Incompleteness theorems*.  Common name for two theorems first
published by Gödel in 1931.  The first of these says (roughly) that,
if T is a consistent, recursively axiomatizable theory that includes
an elementary fragment of arithmetic, then there is a sentence G of
the language of T such that neither G nor not-G is provable in T.  The
second says (roughly) that, if T is a consistent, recursively
axiomatizable theory that includes an elementary fragment of
arithmetic, then there is a formula Con_T of the language of T which
expresses the idea that T is consistent and which is not provable in
T.  *See GÖDEL'S THEOREMS*.

*Independence*.  Basic notion of logic and axiomatics.  Typically, a
proposition p is said to be independent of a set of propositions A
just in case p is not logically implied by A.  A set of sentences may
then be said to be independent (or its elements mutually independent)
if none of its elements is logically implied by the remaining
elements.  Independence in this sense has commonly been identified as
a virtue of an axiomatic system by modern foundational thinkers.  In
another sense of independence, a proposition p is said to be
independent of a set of propositions A just in case neither p nor
not-p is logically implied by A.

*Indirect proof*.  See *Reductio ad absurdum*.

*Indiscernibility of identicals*.  Converse of Leibniz's principle of
the identity of indiscernibles formulated in such famous texts of
modern logic as Frege's Begriffsschrift (1879).  It states that for
all individuals x and y, if x and y are identical, then, for every
property P, x has P if and only if vy has P.  A first-order version
not quantifying over properties can be written in symbolic notation as
.ALL. x .ALL. y (x =y —> (Px <-> Py)).

*Induction, mathematical*.  Fundamental principle or form of
mathematical reasoning for the natural numbers, variants of which
apply to other well-ordered or recursively defined collections.  For
the natural numbers, induction allows one to conclude that every
number has a property P from the premises that 0 has P and that,
whenever a number has P, so does its successor.  A variant, known as
'complete induction' or 'course-of-values' or strong induction, allows
one to conclude that every number has a property P from the premise
that any number is such that it has P whenever all its predecessors
do.  See *Axiom schema*; *Transfinite induction*.

*Injection*. See *One-one correspondence*.

*Interpretation*.  Term of mathematical logic and linguistics.
Logicians use the term 'interpretation' for a variety of distinct
conceptions.  First, in semantics, an interpretation of a formal
language is a function (or other mathematical setting) sufficient to
determine meanings or denotations for all grammatically correct
expressions of the language.  For formal prepositional logic, a
semantic interpretation is an assignment of truth-values to atomic
formulas extendible recursively to all formulas in accordance with the
truth tables for the connectives.  In quantifier logics,
interpretations in this sense are functions assigning denotations to
each of the nonlogical symbols of the language.  Alternatively,
'interpretation' sometimes refers to assignments of truth-conditions
to all formulas of a language.  It is also sometimes used in a
syntactic sense to describe mappings of one formal language (or of one
formal theory) into another that preserve certain of their important
characteristics.

*Isomorphism*.  Term of set theory, model theory and mathematics
generally.  An isomorphism between two structures A and B of the same
type or signature is a bijection f : A —> B from the domain (or
universe) of A to the domain of B which preserves structure.  If R_A
xy for elements x, y of A, then R_B f(x)f(y), where R_B is the
relation in B which corresponds to the relation R_A in A and f(x) and
f(y) the elements of B which correspond to x and y.  And if g_A : A —>
A and g_B : B —> B are corresponding functions defined on A and B,
respectively, then f(g_A(a)) = g_B(f(a)) for all a in A.  In formal
logic, an isomorphism is such a correspondence between similar models.
Example: the function 'multiplication by 2' is an isomorphism between
the structure of the natural numbers {0,1,2,...} together with the
operation of addition, and the set {0,2,4,...} with the same
operation.  This function is one-one because every number in the set
{0,2,4,...} corresponds to a unique natural number (found by dividing
by 2).  It is onto because every number in the set {0,2,4,...} is the
image of some natural number.  And it is structure-preserving because
it maps the zero element of the natural numbers to the zero element of
the set {0,2,4,...} and for all natural numbers n, m, 2(n + m) = 2n +
2m.

*Laws of thought*.  Term of traditional logic used to refer to a family
of principles that were taken to be laws according to which valid
inference proceeds regardless of the subject matter involved.  The
three principles most commonly identified as belonging to this family
are: the law of identity (taken as stating (1) that every thing is
identical to itself or (2) that every proposition implies itself), the
law of contradiction (taken as stating (1) that nothing both has and
lacks a given attribute or (2) that no proposition is both true and
false), and the law of the excluded middle (taken as stating (1) that
every thing either has or lacks a given property or (2) that every
proposition is either true or false).

*Liar paradox*.  Attributed to Eubulides (4th century BC).  A man
says, 'What I am saying is false'.  If what he says is true then it is
false, and if it is false then it is true.  Assuming that it is either
true or false, it follows that it must be both, which is absurd.  The
strengthened liar is a variant designed to rule out the alternative
that what he says is meaningless, by having him say 'What I am saying
is either false or meaningless'.  See *Paradoxes of set and property*.

*Logical implication*.  Basic term of logic.  A set of propositions A
is said to logically imply a proposition p just in case it is
impossible that all the elements of A be true and p be false.

*Logistic system*.  See *Formal system*.

*Löwenheim-Skolem theorem(s)*.  Basic theorem proved by Löwenheim in
1915 and Skolem in 1919, showing that any theory in first-order logic
(with identity) that has a model has a countable model.  Tarski (1928)
later showed that every such theory that has an infinite model has a
model of every infinite cardinality.  The original theorem shows that
some theories (for example, set theory and the theory of real numbers)
have unexpectedly small models and is therefore sometimes referred to
as the downward Lowenheim-Skolem theorem.  The theorem proved by
Tarski indicates that theories with infinite models have unexpectedly
large models and is sometimes called the upward Löwenheim-Skolem
theorem.

*Major term (of a syllogism)*.  Term of traditional logic.  The
predicate term of the conclusion of a categorical syllogism.  See
*Syllogism, categorical*.

*Mapping*.  See *Function*.

*Maximal consistent set*.  Notion of metalogic.  If A is a set of
sentences of a language L, A is said to be maximal consistent just in
case (1) A is consistent, and (2) no further sentence of L can be
added to A to form a consistent set.

*Middle term (of a syllogism)*.  Term of traditional logic.  The term
that appears in each of the premises but not in the conclusion of a
categorical syllogism.  See *Syllogism, categorical*.

*Minor term (of a syllogism)*.  Term of traditional logic. The subject
term of the conclusion of a categorical syllogism.  See *Syllogism,
categorical*.

*Mnemonics, syllogistic*.  The mnemonic names for the syllogistic
moods (valid forms of syllogism) were established by the early
thirteenth century.  An early fairly complete list is given by Peter
of Spain (Summulae logicales 4.17).  The names encode the way to
reduce the syllogisms to the first figure.  The significant letters in
the mnemonics are the initial consonant, the first three vowels and
's', 'p', 'm' and 'c'.  Syllogisms whose names begin with 'B' reduce
to Barbara; with 'C to Celarent; with 'D' to Darii; and with 'F' to
Ferio.  The vowels 'a', 'e', 'i' and 'o' denote the four forms of
categorical proposition.  The consonant 's' after a vowel indicates a
simple conversion of the corresponding first-figure proposition; 'p'
indicates conversion per accidens, which presupposes existential
import; 'm' indicates mutatio praemissarum, that is, interchange of
the premises; and 'c' indicates indirect proof, per contradictionem.
(Subalternation, a mode of immediate inference recognized by Aristotle
that also presupposes existential import, is not indicated, for the
so-called subaltern moods were codified only later.)  Example: to
reduce a second-figure syllogism in the mood Camestrop to the
first-figure mood Celarent, we interchange the premises (m), convert
the E-premise simply (s), and convert the E-conclusion per accidens
(p) to the desired O-conclusion.  See *Categorical proposition*;
*Figure (of a categorical syllogism)*; *Mood (of a categorical
syllogism)*.

*Model*.  See *Structure*.

*Modus ponens*.  Term of traditional logic and modern logic (in full,
modus ponendo ponens).  Traditionally, modus ponens is one of the
basic forms or moods of the mixed hypothetical syllogism; namely, that
in which the minor premise is the antecedent of the major premise and
the conclusion its consequent.  In other words, it is the following
argument form: 'If p then q. p .'. q'.  It is also used as the name
for the rule of inference which allows one to infer 'q' from the two
propositions 'If p then q' and 'p'.

*Modus tollens*.  Term of traditional logic (in full, modus tollendo
tollens).  Modus tollens signifies the basic form or mood of the mixed
hypothetical syllogism in which the minor premise is the denial of the
consequent of the major premise and whose conclusion is the denial of
its antecedent.  In other words, it is the following argument form:
'If p then q. Not q .'. not p'.  It is also used as the name for the
rule of inference which allows one to infer 'not p' from the two
propositions 'If p then q' and 'Not q'.

*Mood (of a categorical syllogism)*.  Term of traditional logic.  The
moods are the different valid syllogistic forms that are available
within a given figure through variation of the quantities (universal
or particular) and qualities (affirmative or negative) of the premises
and conclusion.  As an example, consider the figure 'A is B, C is A
.'. C is B' (where B is the major, C the minor and A the middle term).
It has the following moods: (1) 'Every A is B, every C is A .'. every
C is B', (2) 'No A is B, every C is A .'. no C is B', (3) 'Every A is
B, some C is A .'. some C is B' and (4) 'No A is B, some C is A
.'. some C is not B'.  In the first figure, then, (1) is in the mood
AAA (Barbara), (2) in the mood EAE (Celarent), (3) in the mood AII
(Darii) and (4) in the mood EIO (Ferio).  See *Categorical
proposition*; *Figure (of a categorical syllogism)*; *Mnemonics,
syllogistic*.

*Normal form (conjunctive)*.  Notion of metalogic.  A formula is in
conjunctive normal form if it is a conjunction of disjunctions of
atomic formulas and negations of atomic formulas.  In classical
propositional logic, every formula is logically equivalent to one in
conjunctive normal form.

*Normal form (disjunctive)*.  Notion of metalogic.  A formula is in
disjunctive normal form if it is a disjunction of conjunctions of
atomic formulas and negations of atomic formulas.  In classical
propositional logic, every formula is logically equivalent to one in
disjunctive normal form.

*Normal form (prenex)*.  Notion of metalogic.  A formula is said to be
in prenex normal form if it consists of a (possibly empty) string of
quantifiers (called its quantifier prefix) followed by a formula
(called its matrix) that contains no quantifiers.  Every formula of a
first-order language is logically equivalent to a first-order formula
in prenex normal form.

*Omega-completeness*.  Notion of metamathematics.  A theory T in an
arithmetic language L is said to be omega-complete (usually written
'OMEGA-complete') just in case for every formula PHIx of L, if every formula
of the form PHIn (where 'n' is a numeral) is provable in T, then so is
the formula .ALL. x PHIx.

*Omega-consistency*.  Notion of metamathematics.  A theory T in an
arithmetic language L is said to be omega-consistent (usually written
'OMEGA-consistent') if there is no formula PHIx of L such that each
formula of the form PHIn (where 'n' is a numeral) is provable in T and
T also proves not .ALL. x PHIx.  Gödel used OMEGA-consistency as a
condition on the theories for which he proved his incompleteness
theorems.  Rosser later showed how to prove the first incompleteness
theorem using just consistency (a weaker condition than
omega-consistency).  See *Consistency*.

*One-one correspondence*.  Term of set theory and mathematics
generally.  Also called a one-to-one correspondence and an
injection. A one-one (or 1-1) correspondence between two sets A and B
is a function f : A —> B which maps every element of A to an element
of B and never maps distinct elements of A into the same element of B:
for all x, y in A, if f(x) = f(y), then x = y.

*Onto function*.  Term of set theory and mathematics generally.  Also
called a surjection.  A function f : A —> B is said to be onto B when
every element of B is the value of f for some element of A: for all b
in B, b = f(a) for some a in A.

*Opposition*.  Term of traditional logic.  Aristotle used 'opposition'
as a general term for the different ways in which categorical
propositions could be at odds with one another.  He delineated three
species of opposition: contradictories, contraries and subcontraries.
Contradictories cannot both be true and cannot both be false.
Contraries cannot both be true but can both be false.  Subcontraries
cannot both be false but can both be true.  These relations were
captured in the famous square of opposition, a post-Aristotelian
device which arranged the A, E, I and O propositions as follows.  The
proposition-types in the top row (that is, A and E) are contraries,
the proposition-types of the bottom row (that is, I and O)
subcontraries, and the diagonal pairs (that is, A and O, and E and I)
are contradictories.

Universal affirmative (A)      Universal negative (E)
All A are B.                   No A are B.

Particular affirmative (I)     Particular negative (O) 
Some A are B.                  Some A are not B.

*Ordering*.  Term of set theory and mathematics generally.  An
ordering (or order) is a relation defined on a set which allows at
least certain elements of that set to be arranged in order.  A
relation R defined on a set A yields a *partial* ordering if it is
reflexive, antisymmetric and transitive on A.  R is said to be a
*total* ordering, a *linear* ordering or simply an ordering of A if it
is connected, irreflexive and transitive in A.  Example: the 'subset
of' relation gives a partial order on the power set of a set. The
'less than' relation is a total order of the natural numbers.  See
*Relations (properties of)*.

*Ordinal (number)*.  Term of set theory and mathematics generally.  The
cardinal number of a collection is concerned only with its 'size', but
the ordinal is concerned also with the relationship of its
elements.  The ordinal numbers are generally defined as the order types
of the well-ordered sets, two orders having the same order type if
there is an isomorphism between them.  Intuitively, ordinals measure
the size of a collection by determining how far into a given
'indexing' set one has to go in order to count its members.  Cantor
pointed out that the differences between these two ways of measuring
class size become significant when one is dealing with infinite or
transfinite sets.  See *SET THEORY*.

*Peano postulates (Peano arithmetic)*.  System of axioms for the
arithmetic of the natural numbers.  Dedekind introduced an equivalent
system in 1888, but it was Peano's system introduced a year later that
became widely used.  In its early form, the system comprises five
postulates:

(1)  0 is a natural number.
(2)  Any successor of a natural number is a natural number.
(3)  0 is not the successor of any natural number.
(4)  If two successors are identical, then the numbers of which they
     are successors are identical.
(5)  For any property P, if (a) 0 has P and (b) for any natural number
     x, if x has P, then so does the successor of x, then (c) every
     natural number has P.

Formulated in this way, with a quantifier over properties in axiom (5)
(the induction postulate), Peano arithmetic is a second-order
system.  A first-order system is obtained by treating induction not as
an axiom but as an axiom schema.

*Power set*.  Term of set theory.  The power set p(A) of a set A is the
set of all subsets of A.

*Proposition*.  From the Middle Ages to the nineteenth century, a
proposition was understood as (1) a declarative sentence considered
together with its meaning or content; or as the one or the other in
particular contexts.  In the early twentieth century, 'proposition'
came to be used in two overlapping senses: (2) the intension or
meaning of a (possible) sentence; and (3) the fully determinate
circumstance or content capable of being asserted or expressed by a
particular utterance of a sentence.  A proposition in sense (3) is the
sort of thing that can be an object of belief.  Sense (2) is often
explicated, following Carnap, as a set of 'indices' (or a function
from indices to truth-values), where an index is a possible world, a
state description, a context of use, or the like.  But it is not clear
that this explication is adequate for all the uses to which (2) is
put, for example, as what synonymous sentences have in common.  See
*Categorical proposition*; *Singular proposition*.

*Propositional operator / connective*.  Basic notion of propositional
logic.  In its most general sense, a propositional operator /
connective is any operator or expression of a language that forms
sentences from sentences (for example, 'and', 'or', 'It is not the
case that', 'Wilbur believes that').  Some of these operators are
truth-functional in character; that is, sentences formed using them
are such that their truth-values are uniquely determined by the
truth-values of the component sentences.  In most of their usages, the
first three English operators named above are truth-functional; the
fourth is not.

*Quantifier*.  Basic notion of logic.  Classically, it referred to
those syncategorematic expressions in categorical propositions (for
example, 'all', 'some', 'none') that indicate the quantity of the
proposition.  In modern logic, it refers to any of a variety of
operators that are capable of binding occurrences of variables so as
to turn term-like expressions into terms, or propositional functions
into propositions.  A universal quantifier attached to a proposition
'A are B' asserts that every element of A (or everything having the
property A) is an element of (or has the property) B.  An existential
quantifier attached to a proposition 'A are B' asserts that there is
at least one element of A (or at least one object having the property
A) that is an element of (or has the property) B.  See *Categorical
proposition*; *QUANTIFIERS*; *Variable*.

*Recursive function*.  Term of computability theory.  A function on
the natural numbers is recursive if it is one of the following:

(1)  the identity function, a constant function, the successor
     function or a projection function;
(2)  definable by composition of recursive functions;
(3)  definable from recursive functions by recursion;
(4)  definable in terms of a given recursive function PHI as the least
     natural number such that PHI takes the value zero.

A function is *primitive recursive* if it is definable using only
(1)-(3).  A primitive recursive function must be total, that is,
defined for every natural number (or n-tuple, for appropriate n) as
input.  Moreover, the function which gives the number of steps
required to calculate the value for any input is computable as a
function of the input.  A recursive funtion need not be total since
the recursive function in terms of which it is defined in (4) above
might never take the value zero.  It is not in general decidable
whether a given recursive function is total; even if it is total,
there need not be any computable bound to the number of steps required
to calculate its value.  The recursive functions can be proved to
coincide with the Turing computable functions, and with those
computable by register machines.  Church's thesis is the claim that
these classes of functions coincide with those which are computable
algorithmically.  See *Computability theory*.

*Recursive set*.  Term of computability theory.  A set of natural
numbers is said to be recursive if the characteristic function of the
set, that is, the function which maps the members of the set to 1 and
all other numbers to 0, is total recursive.  Church's thesis claims
that the recursive sets are just the decidable ones.  See
*Decidability*; *Recursive function*.

*Recursively enumerable set*.  Term of computability theory.  A set of
natural numbers is recursively enumerable if it is the range (or
codomain) of a recursive function or, equivalently, if it is the
domain of a partial recursive function.  If Church's thesis holds, the
recursively enumerable sets are just the semi-decidable ones.  See
*Decidability*; *Recursive function*.

*Reductio ad absurdum*.  Term of logic.  This is the rule, valid in
most systems of logic, that if you can deduce a contradictory pair of
sentences q, not-q from an assumption p, then p must be false and
not-p (the contradictory of p) follows.  When p is itself negative,
the rule is also called indirect proof.  Reductio ad absurdum (or
reductio ad impossibile) was a mode of immediate inference in
Aristotle's syllogistic.

*Register machine*.  Concept of computability theory.  A register
machine is a type of automaton or idealized computing device
characterizing computable functions, closely related to the notion of
an abacus machine.  It consists of an infinite array of abstract
memory locations or registers and a Finite set of simple instructions
for the stepwise manipulation of data stored in these registers.  A
numerical function is register computable just in case there is a
register program which computes its outputs correctly from its inputs
using the set of registers.  It is provable that a function is
register computable precisely when it is Turing computable or,
equivalently, recursive.

*Relation*.  Notion of logic and set theory.  In the first systematic
treatment, De Morgan defined a proposition to be the presentation of
two names under a relation, and took its general form to be 's is in
relation R to p', with R acting as a copula between the subject s and
the predicate p.  He treated relational expressions as having both
intensions and extensions.  He also saw a general theory of relations
as having to allow for relational expressions with any finite number
of terms or arguments.  Modern logic takes the extension of an
n-termed relational expression to be a set of n-tuples of elements of
a the set on which the relation is defined, known as the field of the
relation.  See *LOGIC IN THE 19TH CENTURY*.

*Relations (properties of)*.  Let R be a relation on a set A. Then 

R is *connected (or complete)* in A iff any two distinct elements of A
are R-related: for any x,y in A, then Rxy (read: 'x bears R to y') or
Ryx or x = y.

R is *dense* iff whenever R relates two elements of A there is a third
which relates to both of them as follows: if Rxy, there is a z in A
such that Rxz and Rzy.

R is *reflexive* iff R relates every element of A to itself: Rxx for
every x in A.

R is *irreflexive* iff no element of A is R-related to itself: if Rxy
then x not= y.

R is *symmetric* iff R and its converse coincide: for all x, y in A,
if Rxy, then Ryx.

R is *anti-symmetric* iff no two distinct elements of A are in both R
and its converse: if Rxy and Ryx then x = y.

R is *transitive* iff whenever R relates x to y and y to z, then it
relates x directly to z: if Rxy and Ryz, then Rxz.

R is *linear* (or *simple* or *total*) in A iff R is antisymmetric,
connected, reflexive and transitive in A.

R is *well-founded* iff every non-empty subset of A has a least
element under R or there are no infinite descending chains of
R-related elements.

See *Converse (of a relation)*; *Ordering*; *Well-ordering*.

*Russell's paradox*.  The most celebrated of the set-theoretic
paradoxes.  Let A be the set of all sets which do not belong to
themselves.  If A belongs to itself, it must satisfy the condition for
membership of A, that is, it must not belong to itself.  This is
absurd.  So A does not belong to itself, in which case it satisfies
the condition for membership of itself, which is also absurd.  We have
therefore to conclude that A does not exist.  (Note that the
derivation of the absurdity makes no use of the law of the excluded
middle.)  See *PARADOXES OF SET AND PROPERTY*.

*Satisfaction*.  Basic concept of model theory and formal semantics,
introduced by Tarski in order to define truth for languages with
quantifiers.  It signifies a three-place relation between (a) formulae
of a formal language L, (b) interpretations or structures M for L, and
(c) sequences of items from the domain of M.  Intuitively, a sequence
satisfies a formula under an interpretation just in case the formula,
so interpreted, holds of the items of the sequence taken in the order
in which the sequence arranges them.  Thus, for example, if m_1 and
m_2 are elements of the domain of M and 'Rxy' is a formula of L, the
sequence (m_1, m_2) satisfies 'Rxy' under M just in case (m_1, m_2) is
in the extension (i.e. the set of ordered pairs of elements of the
domain of M) assigned to 'Rxy' by M.  Sentences (i.e. formulas
containing no occurrences of free variables) turn out to be satisfied
by all sequences under M if they are satisfied by any.  A sentence
that is satisfied by all (some) sequences under M is said to be
true-in-M.  A set S of sentences of L is said to be satisfiable (or
simultaneously satisfiable) just in case there is at least one
structure M for L that makes all the sentences in S true.  See
*Interpretation*; *MODEL THEORY*; *Structure*.

*Sentence*.  Term of logic. In a formal language, a formula is said to
be a sentence if it contains no free occurrences of variables.  See
*Variable*.

*Signature*.  Notion of model theory.  The signature of a structure or
model M is specified by giving (1) the set of individual constants to
which M assigns elements of its domain, (2) for each n > 0, the set of
n-ary relation symbols to which M assigns sets of n-tuples of elements
of its domain as extensions, and (3) for each n > 0, the set of n-ary
function symbols to which M assigns sets of n + 1-tuples of elements
of its domain as extensions.  'Signature' is another term for what
model theorists often refer to as a 'language', by which they mean not
a whole formal language (complete with logical symbols, such devices
as parentheses and a grammar), but rather those elements of a formal
language whose different interpretation serves to differentiate models
or structures that have the same domain.

*Singular proposition*.  Term of logic.  Traditionally, a singular
proposition is a categorical proposition with a proper name as subject
term.  No express quantifier is present, but William of Ockham
construed the proper name as a universally quantified term of unit
extension, thereby rendering singular propositions tractable in
syllogistic.  In modern logic a singular proposition is a simple
sentence consisting of nothing but a predicate and the appropriate
number of singular terms, as 'Fa' or 'Rxy'.

*Sophism*. Term used by Aristotle (Topics, 162a14) to describe an
argument that is not valid but may misleadingly appear to be so.

*Sorites paradox*.  Term of logic and linguistics.  Also known as the
'paradox of the heap', soros being Greek for heap.  This refers to any
of a number of paradoxical arguments related to gradual or continuous
change.  The most famous such argument concludes that no amount of
sand constitutes a heap.  This is because (1) a single grain of sand
does not constitute a heap and (2) if n grains of sand do not make a
heap, then n + 1 grains do not make a heap.  By mathematical
induction, no number of grains of sand yields a heap.  Typically,
sorites paradoxes are thought symptomatic of the vagueness of such
predicates as 'heap', 'bald' and 'red'.  See *FUZZY LOGIC*;
*VAGUENESS*.

*Soundness (of a logical calculus)*.  Term of metalogic.  A logical
calculus is *weakly* sound if every one of its theorems is a logical
truth.  If one is interested in formalizing the more general notion of
logical consequence, then one may require that the calculus is also
*strongly* sound, that is, whenever a sentence S can be derived from a
set of premises T, S is a logical consequence of T.  See *Completeness
(of a logical calculus)*.

*Soundness (of a theory)*.  Term of metamathematics.  A theory is
sound if each of its theorems is true in the intended structure.
Example: every theorem of first-order Peano arithmetic is true in the
intended structure of the natural numbers.  See *Theory*.

*Soundness (of an argument)*.  Term of basic logic.  An argument is
said to be sound when it is valid and all its premises are true.

*Square of opposition*.  See *Opposition*.

*Structure*.  Central notion of model theory.  A structure M for a
language (or signature) L is a pair (D, I), where D is a set referred
to as the domain of M (sometimes also called the universe of discourse
of M or the carrier of M) and I (called the interpretation function of
M) is a function which maps each individual constant of L to an
element of D, each n-ary relation symbol of L to a set of n-tuples of
elements of D, and each m-ary function of L to a mapping of the
m-tuples of elements of D to the elements of D.  A structure is a
*model* of a theory (that is, a set of sentences) T when it makes
every element of T true.  Classically, D is required to be non-empty,
though this requirement is no longer enforced as a general requirement
in model-theoretic work.  See *Interpretation*; *MODEL THEORY*;
*Satisfaction*.

*Surjection*.  See *Onto function*.

*Syllogism, categorical*.  A valid form of argument in the oldest
known system of formal logic in the West, presented by Aristotle at
the beginning of his Prior Analytics.  A syllogistic argument has a
major premise, a minor premise and a conclusion, all of them
categorical propositions.  (Hence the name 'categorical syllogism';
hypothetical syllogisms consist of compound propositions.)  See
*Categorical proposition*.

*Syllogism, disjunctive*.  Originally, this referred to either of the
two valid argument forms 'p or q; p; therefore not q' (the 'fourth
indemonstrable' of Stoic logic) or 'p or q; not p; therefore q' (the
'fifth indemonstrable'), or the same but with the major premise
commuted.  The 'or' here was exclusive.  The disjunctive syllogism was
considered a species of hypothetical syllogism.  Now 'disjunctive
syllogism' is used only for the second form (corresponding to the
fifth indemonstrable), but with 'or' taken inclusively.  It fails in
certain relevance logics.

*Syllogism, hypothetical*.  Originally, this referred to a valid
two-premise argument from conditionals; later, involving various
connectives.  Aristotle's syllogisms consist of categorical
propositions but he also spoke of 'syllogisms from hypotheses'.
Theophrastus was credited with formulating hypothetical syllogisms,
particularly 'thoroughly hypothetical syllogisms', such as 'If A then
B; if B then C; so if A then C'.  This is what is called 'hypothetical
syllogism' today.  (By the time of Boethius, the term had been
extended to Stoic two-premise arguments in general.)

*Syllogism, modal*.  A two-premise argument made up of modalized and
unmodalized categorical propositions.  For Aristotle the modalization
typically affected the predicate term: for example, 'All A are
necessarily-B'.  Thus the modality was *de re*.  He recognized both
one-sided possibility ('not impossible') and two-sided possibility
(contingency).  His most curious form of modalized categorical
proposition was 'All possibly-A are possibly-B', and similarly for
other quantities and qualities (two-sided possibility).  Theophrastus
interpreted the modalities de dicto, which gave much clearer results.
Ultimately, the two systems complement each other.  Example: 'All men
are necessarily animals; all Greeks are men; so all Greeks are
necessarily animals'.  See *Categorical proposition*.

*Symbols*  See table on pages 796-797.

*Tautology, tautological implication*.  Basic notions of logic.  A
proposition is said to be a tautology when its truth is logically
necessary or, equivalently, when its negation is a contradiction.  A
sentence built up by means of truth-functional operators is a
tautology if it is true under every assignment of truth-values to the
atomic sentences.  A set of premises tautologically imply a conclusion
if every assignment of truth-values to the atomic sentences that make
all the premises true also makes the conclusion true.  Examples: 'p or
not-p' is a tautology; 'p' and 'p —> q' tautologically imply 'q'.

*Theory*. bTerm of metamathematics.  A (formal) theory is a set T of
sentences (or formulas) of a formal language that is closed under
logical consequence, that is, T is such that everything that follows
from members of T is also in T.  The elements of T are its theorems.
Examples: a set of axioms together with all their consequences is a
theory.  The set of all the sentences true in a structure M is a
theory.

*Transfinite induction*.  Concept of set theory.  Transfinite
induction, a generalization of ordinary, finite mathematical
induction, is one or another principle of inductive proof as applied
to an ordinal number or well-ordered set which is larger than that of
the natural numbers.  Generally, transfinite induction on a
well-ordered set A shows that every element of A has a property P by
proving that, whenever all the order predecessors of an element x in A
have P, then so does x.  See *Induction, mathematical*.

*Truth table*.  Basic notion of propositional logic.  A truth table is
a diagram displaying, for a propositional formula or argument, the
truth-values of the whole formula or argument as determined by each
possible combination of the truth-values of its ultimate constituents
(frequently referred to as 'base components' or 'atomic sentences').
In a logic with k different basic truth-values, a proposition made up
of n atomic sentences, or an n-ary truth-function, is given by a truth
table that has n input columns and one output column, each of k^n
rows. Example:

   A  B  | A and B
   -------------- 
   T  T  |   T 
   T  F  |   F 
   F  T  |   F 
   F  F  |   F 

See *Many-valued logics*; *Truth-value*.

*Truth-function*.  Term of formal propositional logic.  A
truth-function takes (lists of) truth-values into truth-values.  In
classical, two-valued logic, a truth-function takes n-tuples of
elements of the set {T, F} to the set {T, F}.  In many-valued logics,
truth-functions take their arguments and values from larger sets.
Generally speaking, if there are k different basic truth-values, there
are k^k^n-ary truth-functions.  See *MANY-VALUED LOGICS*;
*Truth-value*.

*Truth-value*.  Term of formal propositional logic.  In classical,
two-valued logic, the members of the set {T,F}, 'true' and 'false',
are conventionally adopted as truth-values, that is, objects over
which propositional formulas are interpreted.  For nonclassical and
many-valued logics, other sets of truth-values provide objects for
interpretation.  Sometimes, elements of Boolean algebras or open sets
from topological spaces serve as useful sets of truth-values.

*Tuple*.  Term of set theory denoting a sequence or ordered set.  An
n-tuple is an ordered set of n elements.

*Turing machine*.  Notion fundamental to computability theory.
Devised by Turing as a characterization of the notion of computable
function or mechanical calculation, a Turing machine is an abstract
automaton or idealized computing device which consists of a program -
a finite set of simple instructions - to be carried out on a
one-dimensional recording tape by a reading-writing device with a
memory restricted in capacity.  A numerical function f is said to be
computed by a Turing machine or to be Turing computable just in case
there is a program which, when implemented, mimics on its tape the
input-output behaviour of f.  Turing computability can be proved to be
equivalent to register computability and to a function's being
recursive.  See *Turing machines*.

*Universal generalization*.  Rule governing the logic of the universal
quantifier.  It permits one to conclude that everything has the
property P from a premise to the effect that an arbitrarily selected
object o has P.  In saying that o is arbitrarily selected, we mean
that one has no information about it that could serve to distinguish
it from any other object.  It thus functions as a kind of generic
object.

*Universal instantiation*.  Rule governing the logic of the universal
quantifier.  It permits one to conclude of any object o that it has
the property P from the premise that everything has P.

*Universal quantifier*.  See *Quantifier*.

*Validity*.  Basic notion of logic.  In modern usage, it is applied
both to arguments or inferences and to individual propositions.  It is
also traditionally divided into two types, *deductive* and
*inductive*, although some would reserve it for the deductive case
alone.  In the deductive case, an argument is valid if it is
impossible that all the premises be true and the conclusion false; a
*proposition* is valid if it is impossible that the proposition be
false.  In the inductive case, an argument is valid if the premises'
being true makes it likely (to some implied degree) that the
conclusion is true.

*Valuation*.  Term of mathematical logic and formal semantics.
Generally, a valuation for a formal language, given a semantic domain
D, is any function which assigns appropriate semantic values over D to
chosen expressions of the language.  In predicate logic, 'valuation'
often refers to functions (also called 'assignments') from the set of
variables of a language into the universe of a structure D.
Occasionally, 'valuation' is used as a synonym for 'interpretation'.
See *Interpretation*.

*Variable*.  Term of logic.  A variable is a linguistic expression,
typically a letter of the alphabet, having, in the context, no fixed,
determined value but capable of adopting any of a range of values.
Variables are often said to 'range over' items in those domains in
which they are assigned values.  In many formalisms, not all
appearances of variables in a well-formed expression need be attached
to a binding operator (for example, a quantifier); those which are are
called 'bound' (Russell: 'apparent'), and those which are not are
called 'free' (Russell: 'real').  Types in a hierarchy of systems or
languages are often distinguished by the order of the variables
available.  See *First-order / higher-order*; *Sentence*.

*Well-ordering*.  Term of set theory and mathematics generally.  A set
A is well-ordered by a relation R (equivalently, R is a well-ordering
of A) just in case R is an ordering of A and every non-empty subset of
A has an R-least element.  See *Ordering*; *Relations (properties
of)*.

*Zorn's lemma*.  A noted maximality principle of set theory first
introduced by Hausdorff in 1909; rediscovered by Zorn in 1933.  Zorn's
lemma asserts that a non-empty partially ordered set has a maximal
element provided that each totally ordered subcollection of its
members is bounded above.  Zorn's lemma is provably equivalent to the
axiom of choice in standard set theories and is extremely useful in a
wide variety of formal contexts, among them proofs for completeness.
See *Axiom of choice*; *Ordering*.

MICHAEL DETLEFSEN
DAVID CHARLES McCARTY
JOHN B. BACON