Extensionality
Encyclopedia
In logic
, extensionality, or extensional equality refers to principles that judge objects to be equal if they have the same external properties. It is the opposite concept of intensionality, which is concerned with whether two descriptions are intended to be the same or not.
s to the natural numbers defined as follows:
These functions are extensionally equal; given the same input, both functions always produce the same value. But the definitions of the functions are not equal, and in that intensional sense the functions are not the same.
Similarly, in natural language there are many predicates (relations) that are intensionally different but are extensionally identical. For example, suppose that a town has one person named Joe, who is also the oldest person in the town. Then "Joe" and "oldest person in the town" are extensionally equal, but intensionally distinct.
, in which case two functions must not only agree on all values, but must also have the same codomain, in order to be equal.
A similar extensional definition is usually employed for relations: two relations are said to be equal if they have the same extensions
.
In set theory, the axiom of extensionality
states that two sets are equal if and only if they contain the same elements. In mathematics formalized in set theory, it is common to identify relations—and, most importantly, functions
—with their extension as stated above, so that it is impossible for two relations or functions with the same extension to be distinguished.
Other mathematical objects are also constructed in such a way that the intuitive notion of "equality" agrees with set-level extensional equality; thus, equal ordered pair
s have equal elements, and elements of a set which are related by an equivalence relation
belong to the same equivalence class.
Type-theoretical
foundations of mathematics are generally not extensional in this sense, and setoid
s are commonly used to maintain a difference between intensional equality and a more general equivalence relation (which generally has poor constructibility
or decidability properties).
In lambda calculus
, extensionality is expressed by the eta-conversion rule, which allows conversion between any two expressions that denote the same function.
, two related approaches to type resolution in computer programming
which apply extensionality as a means of determining the effective type of a variable.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, extensionality, or extensional equality refers to principles that judge objects to be equal if they have the same external properties. It is the opposite concept of intensionality, which is concerned with whether two descriptions are intended to be the same or not.
Example
Consider the functions f and g from the natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s to the natural numbers defined as follows:
- To find f(n), first add 5 to n, then multiply by 2.
- To find g(n), first multiply n by 2, then add 10.
These functions are extensionally equal; given the same input, both functions always produce the same value. But the definitions of the functions are not equal, and in that intensional sense the functions are not the same.
Similarly, in natural language there are many predicates (relations) that are intensionally different but are extensionally identical. For example, suppose that a town has one person named Joe, who is also the oldest person in the town. Then "Joe" and "oldest person in the town" are extensionally equal, but intensionally distinct.
In mathematics
The extensional definition of function equality, discussed above, is commonly used in mathematics. Sometimes additional information is attached to a function, such as an explicit codomainCodomain
In mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...
, in which case two functions must not only agree on all values, but must also have the same codomain, in order to be equal.
A similar extensional definition is usually employed for relations: two relations are said to be equal if they have the same extensions
Extension (predicate logic)
The extension of a predicatea truth-valued functionis the set of tuples of values that, used as arguments, satisfy the predicate. Such a set of tuples is a relation.For example the statement "d2 is the weekday following d1"...
.
In set theory, the axiom of extensionality
Axiom of extensionality
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo-Fraenkel set theory.- Formal statement :...
states that two sets are equal if and only if they contain the same elements. In mathematics formalized in set theory, it is common to identify relations—and, most importantly, functions
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
—with their extension as stated above, so that it is impossible for two relations or functions with the same extension to be distinguished.
Other mathematical objects are also constructed in such a way that the intuitive notion of "equality" agrees with set-level extensional equality; thus, equal ordered pair
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
s have equal elements, and elements of a set which are related by an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
belong to the same equivalence class.
Type-theoretical
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
foundations of mathematics are generally not extensional in this sense, and setoid
Setoid
In mathematics, a setoid is a set equipped with an equivalence relation.Setoids are studied especially in proof theory and in type-theoretic foundations of mathematics. Often in mathematics, when one defines an equivalence relation on a set, one immediately forms the quotient set...
s are commonly used to maintain a difference between intensional equality and a more general equivalence relation (which generally has poor constructibility
Constructivism (mathematics)
In the philosophy of mathematics, constructivism asserts that it is necessary to find a mathematical object to prove that it exists. When one assumes that an object does not exist and derives a contradiction from that assumption, one still has not found the object and therefore not proved its...
or decidability properties).
In lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, extensionality is expressed by the eta-conversion rule, which allows conversion between any two expressions that denote the same function.
See also
Structural typing and duck typingDuck typing
In computer programming with object-oriented programming languages, duck typing is a style of dynamic typing in which an object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface...
, two related approaches to type resolution in computer programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
which apply extensionality as a means of determining the effective type of a variable.