Affine logic is a
substructural logic whose proof theory rejects the
structural rule
In proof theory, a structural rule is an inference rule that does not refer to any logical connective, but instead operates on the judgment or sequents directly. Structural rules often mimic intended meta-theoretic properties of the logic. Logics ...
of
contraction
Contraction may refer to:
Linguistics
* Contraction (grammar), a shortened word
* Poetic contraction, omission of letters for poetic reasons
* Elision, omission of sounds
** Syncope (phonology), omission of sounds in a word
* Synalepha, merged ...
. It can also be characterized as
linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also ...
with
weakening.
The name "affine logic" is associated with
linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also ...
, to which it differs by allowing the weakening rule.
Jean-Yves Girard
Jean-Yves Girard (; born 1947) is a French logician working in proof theory. He is the research director (emeritus) at the mathematical institute of the University of Aix-Marseille, at Luminy.
Biography
Jean-Yves Girard is an alumnus of the ...
introduced the name as part of the
geometry of interaction semantics of linear logic, which characterizes linear logic in terms of
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrice ...
; here he alludes to
affine transformation
In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.
More generall ...
s on
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s.
Affine logic predated linear logic. V. N. Grishin used this logic in 1974, after observing that
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains ...
cannot be derived in a
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
without contraction, even with an
unbounded comprehension axiom.
[Cf. ]Frederic Fitch
Frederic Brenton Fitch (September 9, 1908, Greenwich, Connecticut – September 18, 1987, New Haven, Connecticut) was an American logician, a Sterling Professor at Yale University.
Education and career
At Yale, Fitch earned his B.A in 1931 and ...
's demonstrably consistent set theory Likewise, the logic formed the basis of a
decidable sub-theory of
predicate logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
, called 'Direct logic' (Ketonen & Wehrauch, 1984; Ketonen & Bellin, 1989).
Affine logic can be embedded into linear logic by rewriting the affine arrow
as the linear arrow
.
Whereas full linear logic (i.e. propositional linear logic with multiplicatives, additives, and exponentials) is undecidable, full affine logic is decidable.
Affine logic forms the foundation of
ludics.
Notes
References
* V.N. Grishin, 1974. “A nonstandard logic and its application to set theory,” (Russian). Studies in Formalized Languages and Nonclassical Logics (Russian), 135–171. Izdat, “Nauka,” Moscow.
* V.N. Grishin, 1981. “Predicate and set-theoretic calculi based on logic without contraction rules,” (Russian). Izvestiya Akademii Nauk SSSR Seriya Matematicheskaya 45(1):47-68. 239. Math. USSR Izv., 18, no.1, Moscow.
* J. Ketonen and R. Weyhrauch, 1984, A decidable fragment of predicate calculus.
Theoretical Computer Science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
32:297-307.
* J. Ketonen and G. Bellin, 1989. A decision procedure revisited: notes on Direct Logic. In ''Linear Logic and its Implementation''.
See also
*
Strict logic
In mathematical writing, the term strict refers to the property of excluding equality and equivalence and often occurs in the context of inequality and monotonic functions. It is often attached to a technical term to indicate that the exclusiv ...
and
relevant logic
*
Affine type system, a
substructural type system
Substructural logic
{{logic-stub