FACTOID # 4: Just 1% of the houses in Nevada were built before 1939.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Equivalence relation

In mathematics, an equivalence relation is a binary relation between two elements of a set which groups them together as being "equivalent" in some way. Let a, b, and c be arbitrary elements of some set X. Then "a ~ b" or "ab" denotes that a is equivalent to b. For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...


An equivalence relation "~" is reflexive, symmetric, and transitive. In other words, the following must hold for "~" to be an equivalence relation on X: In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... Symmetry is a characteristic of geometrical shapes, equations and other objects; we say that such an object is symmetric with respect to a given operation if this operation, when applied to the object, does not appear to change it. ... In grammar, a verb is transitive if it takes an object. ...

An equivalence relation partitions a set into several disjoint subsets, called equivalence classes. All the elements in a given equivalence class are equivalent among themselves, and no element is equivalent with any element from a different class.
An equivalence relation partitions a set into several disjoint subsets, called equivalence classes. All the elements in a given equivalence class are equivalent among themselves, and no element is equivalent with any element from a different class.

The equivalence class a under "~", denoted [a], is the subset of X whose elements b are such that a~b. X together with "~" is called a setoid. Image File history File links Set_partition. ... Image File history File links Set_partition. ... A partition of U into 6 blocks: an Euler diagram representation. ... In mathematics, two sets are said to be disjoint if they have no element in common. ... In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

Contents

Examples of equivalence relations

A ubiquitous equivalence relation is the equality ("=") relation between elements of any set. Other examples include: In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ...

This article is about the mathematical topic. ... For alternate meanings, such as the musical instrument, see triangle (disambiguation). ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ... In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... In mathematics, the domain of a function is the set of all input values to the function. ... In logic, statements p and q are logically equivalent if they have the same logical content. ... Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... Look up similarity in Wiktionary, the free dictionary. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out... In set theory, ordinal, ordinal number, and transfinite ordinal number refer to a type of number introduced by Georg Cantor in 1897, to accommodate infinite sequences and to classify sets with certain kinds of order structures on them. ... This article or section is in need of attention from an expert on the subject. ... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ... In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. ... Two sets A and B are said to be equinumerous if they have the same cardinality, i. ... For other uses, see Universe (disambiguation). ... In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... Infinity is a word carrying a number of different meanings in mathematics, philosophy, theology and everyday life. ... Alternative meaning: number of pitch classes in a set. ... In mathematics, an ordered pair is a collection of two not necessarily distinct objects, one of which is distinguished as the first coordinate (or first entry or left projection) and the other as the second coordinate (second entry, right projection). ... The integers are commonly denoted by the above symbol. ... In mathematics, a rational number is a number which can be expressed as a ratio of two integers. ... The plot of a Cauchy sequence shown in blue, as versus If the space containing the sequence is complete, the ultimate destination of this sequence, that is, the limit, exists. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, Greens relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... Parallel may refer to: Parallel (geometry) Parallel (latitude), an imaginary east-west line circling a globe Parallelism (grammar), a balance of two or more similar words, phrases, or clauses Parallel (manga), a shōnen manga by Toshihiko Kobayashi Parallel (video), a video album by R.E.M. The Parallel, an... In mathematics, an affine space is an abstract structure that generalises the affine-geometric properties of Euclidean space. ...

Examples of relations that are not equivalences

  • The relation "≥" between real numbers is reflexive and transitive, but not symmetric. For example, 7 ≥ 5 does not imply that 5 ≥ 7. It is, however, a partial order.
  • The relation "has a common factor greater than 1 with" between natural numbers greater than 1, is reflexive and symmetric, but not transitive. (The natural numbers 2 and 6 have a common factor greater than 1, and 6 and 3 have a common factor greater than 1, but 2 and 3 do not have a common factor greater than 1).
  • The empty relation R on a non-empty set X (i.e. aRb is never true) is vacuously symmetric and transitive, but not reflexive. (If X is also empty then R is reflexive.)
  • The relation "is approximately equal to" between real numbers or other things, even if more precisely defined, is not an equivalence relation, because although reflexive and symmetric, it is not transitive, since multiple small changes can accumulate to become a big change.
  • The relation "is a sibling of" on the set of all human beings is not an equivalence relation. Although siblinghood is symmetric (if A is a sibling of B, then B is a sibling of A) it is neither reflexive (no one is a sibling of himself), nor transitive (since if A is a sibling of B, then B is a sibling of A, but A is not a sibling of A). Instead of being transitive, siblinghood is "almost transitive", meaning that if A ~ B, and B ~ C, and AC, then A ~ C.

In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In set theory, a set is called non-empty (or nonempty) if it contains at least one element, and is therefore not the empty set. ... Informally, a logical statement is vacuously true if it is true but doesnt say anything; examples are statements of the form everything with property A also has property B, where there is nothing with property A. It is tempting to dismiss this concept as vacuous or silly. ...

Connection to other relations

A congruence relation is an equivalence relation whose domain X is also the underlying set for an algebraic structure, and which respects the additional structure. In general, congruence relations play the role of kernels of homomorphisms, and the quotient of a structure by a congruence relation can be formed. In many important cases congruence relations have an alternative representation as substructures of the structure on which they are defined. E.g. the congruence relations on groups correspond to the normal subgroups. In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... The word kernel has several meanings in mathematics, some related to each other and some not. ... In mathematics, a normal subgroup N of a group G is a subgroup invariant under conjugation; that is, for each element n in N and each g in G, the element g−1ng is still in N. The statement N is a normal subgroup of G is written: . There are...


Order and equivalence relations are both transitive, but only equivalence relations are symmetric as well. If symmetry is weakened to antisymmetry, the result is a partial order. Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In grammar, a verb is transitive if it takes an object. ... Sphere symmetry group o. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...


A partial equivalence relation is transitive and symmetric, but not reflexive. In mathematics, a partial equivalence relation (often abbreviated as PER) R on a set X is a relation which is symmetric and transitive. ...

  • Transitive and symmetric imply reflexive iff for all a,bX, a~b is always defined.

A dependency relation is reflexive and symmetric, but not transitive.
A preorder is reflexive and transitive, but neither symmetric nor antisymmetric.
A strict partial order is transitive alone. IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation... In mathematics and computer science, a dependency relation is a binary relation that is finite, symmetric, and reflexive. ... In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered sets. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ...


Equivalence relations can thus be seen as the culmination of a hierarchy of order relations.


Equivalence class, quotient set, partition

Let X be a nonempty set with typical elements a and b. Some definitions:

  • The set of all a and b for which a ~ b holds make up an equivalence class of X by ~. Let [a ] =: {xX : x ~ a} denote the equivalence class to which a belongs. Then all elements of X equivalent to each other are also elements of the same equivalence class: ∀a, bX (a ~ b ↔ [a ] = [b ]).
  • The set of all possible equivalence classes of X by ~, denoted X/~ =: {[x] : xX}, is the quotient set of X by ~. If X is a topological space, there is a natural way of transforming X/~ into a topological space; see quotient space for the details.
  • The projection of ~ is the function π : XX/~, defined by π(x) = [x ], mapping elements of X into their respective equivalence classes by ~.
Theorem on projections (Birkhoff and Mac Lane 1999: 35, Th. 19): Let the function f: XB be such that a ~ bf(a) = f(b). Then there is a unique function g : X/~B, such that f = g π. If f is a surjection and a ~ bf(a) = f(b), then g is a bijection.
  • The equivalence kernel of a function f is the equivalence relation, denoted Ef, such that xEfyf(x) = f(y). The equivalence kernel of an injection is the identity relation.
  • A partition of X is a set P of subsets of X, such that every element of X is an element of a single element of P. Each element of P is a cell of the partition. Moreover, the elements of P are pairwise disjoint and their union is X.

Theorem ("Fundamental Theorem of Equivalence Relations": Wallace 1998: 31, Th. 8; Dummit and Foote 2004: 3, Prop. 2): In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x in X | x ~ a } The notion of equivalence classes is useful for constructing sets... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... In topology and related areas of mathematics, a quotient space (also called an identification space) is, intuitively speaking, the result of identifying or gluing together certain points of a given space. ... The word projection can mean more than one thing. ... The word projection can mean more than one thing. ... A surjective function. ... A bijective function. ... Injection has multiple meanings: In mathematics, the term injection refers to an injective function. ... A partition of U into 6 blocks: an Euler diagram representation. ...

  • An equivalence relation ~ partitions X.
  • Conversely, corresponding to any partition of X, there exists an equivalence relation ~ on X.

In both cases, the cells of the partition of X are the equivalence classes of X by ~. Since each element of X belongs to a unique cell of any partition of X, and since each cell of the partition is identical to an equivalence class of X by ~, each element of X belongs to a unique equivalence class of X by ~. Thus there is a natural bijection from the set of all possible equivalence relations on X and the set of all partitions of X. A partition of U into 6 blocks: an Euler diagram representation. ... A partition of U into 6 blocks: an Euler diagram representation. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out... A bijective function. ...


Counting possible partitions. Let X be a finite set with n elements. Since every equivalence relation over X corresponds to a partition of X, and vice versa, the number of possible equivalence relations on X equals the number of distinct partitions of X, which is the nth Bell number Bn: The Bell numbers, named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus (sequence A000110 in OEIS): In general, Bn is the number of partitions of a set of size n. ...

B_n = sum_{k=0}^infty frac{k^n}{ek!}.

Generating equivalence relations

  • An equivalence relation ~ on X is the equivalence kernel of its surjective projection π : XX/~. (Birkhoff and Mac Lane 1999: 33 Th. 18). Conversely, any surjection between sets determines a partition on its domain, the set of preimages of singletons in the codomain. Thus an equivalence relation over X, a partition of X, and a projection whose domain is X, are three equivalent ways of specifying the same thing.
  • The intersection of any two equivalence relations over X (viewed as a subset of X × X) is also an equivalence relation. This yields a convenient way of generating an equivalence relation: given any binary relation R on X, the equivalence relation generated by R is the smallest equivalence relation containing R. Concretely, R generates the equivalence relation if:
a ~ b if and only if there exist elements x1, x2, ..., xn in X such that x1 = a, xn = b, and such that (xi , xi + 1) or (xi + 1, xi ) is in R for every i = 1, ..., n − 1.
Note that the generated equivalence relation generated in this manner can be trivial. For instance, the equivalence relation ~ generated by:
  • The binary relation has exactly one equivalence class, X itself, because x ~ y for all x and y;
  • An antisymmetric relation has equivalence classes that are the singletons of X.
  • Let r be any sort of relation on X. Then rr −1 is a symmetric relation. The transitive closure s of rr −1 assures that s is transitive and reflexive. Moreover, s is the "smallest" equivalence relation containing r, and r/s partially orders X/s.
  • Equivalence relations can construct new spaces by "gluing things together." Let X be the unit Cartesian square [0,1] × [0,1], and let ~ be the equivalence relation on X defined by ∀a, b ∈ [0,1] ((a, 0) ~ (a, 1) ∧ (0, b) ~ (1, b)). Then the quotient space X/~ can be naturally identified with a torus: take a square piece of paper, bend and glue together the upper and lower edge to form a cylinder, then bend the resulting cylinder so as to glue together its two open ends, resulting in a torus.
  • Let G be a group and H a subgroup of G. Define an equivalence relation ~ on G such that a ~ b ↔ (ab−1H ). The equivalence classes of ~—also called the orbits of the action of H on G—are the right cosets of H in G. Interchanging a and b yields the left cosets.

In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ... The word projection can mean more than one thing. ... A surjective function. ... In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two... In mathematics, the image of an element x in a set X under the function f : X &#8594; Y, denoted by f(x), is the unique y in Y that is associated with x. ... Generally, a singleton is something which exists alone in some way. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ... “Superset” redirects here. ... In set theory, the adjective antisymmetric usually refers to an antisymmetric relation. ... Generally, a singleton is something which exists alone in some way. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, the Cartesian product (or direct product) of two sets X and Y, denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y. X × Y = { (x, y) | x ∈ X and y... In topology and related areas of mathematics, a quotient space (also called an identification space) is, intuitively speaking, the result of identifying or gluing together certain points of a given space. ... In geometry, a torus (pl. ... In geometry, a torus (pl. ... This picture illustrates how the hours on a clock form a group under modular addition. ... In group theory, given a group G under a binary operation *, we say that some subset H of G is a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H is a group... In mathematics, a symmetry group describes all symmetries of objects. ... In mathematics, if G is a group, H a subgroup of G, and g an element of G, then gH = { gh : h an element of H } is a left coset of H in G, and Hg = { hg : h an element of H } is a right coset of H in G...

Algebraic characterizations

The possible equivalence relations on any set X, when ordered by set inclusion, form a modular lattice, called Con X by convention. The canonical map ker: XXCon X, relates the monoid X^X of all functions on X and Con X. ker is surjective but not injective. Less formally, the equivalence relation on X, ker, takes each function f: XX to its kernel, ker f. Likewise, ker(ker) is an equivalence relation on X^X. Superset redirects here. ... See lattice for other mathematical as well as non-mathematical meanings of the term. ... In mathematics and related technical fields, the term map or mapping is often a synonym for function. ... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ... In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ... In the various branches of mathematics that fall under the heading of abstract algebra, the kernel of a homomorphism measures the degree to which the homomorphism fails to be injective. ...


The set of all possible functions on the set X gives rise to another equivalence relation. Two functions, both XX, are deemed equivalent when their respective sets of fixpoints have the same cardinality, corresponding to cycles of length one in a permutation. Functions equivalent in this manner form an equivalence class on X^X, and these equivalence classes partition X^X. In mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ...


Transformation groups

It is very well known that lattice theory captures the mathematical structure of order relations. It is less known that transformation groups (some authors prefer permutation groups) and their orbits shed light on the mathematical structure of equivalence relations. Just as order relations are grounded in ordered sets, sets closed under pairwise supremum and infimum, equivalence relations are grounded in partitioned sets, sets closed under bijections preserving partition structure. Since all such bijections map an equivalence class onto itself, such bijections are also known as permutations. The name lattice is suggested by the form of the Hasse diagram depicting it. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, a symmetry group describes all symmetries of objects. ... In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). ... In mathematics, a symmetry group describes all symmetries of objects. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... ... In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ... In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is less than or equal to all other elements of the subset. ... A partition of U into 6 blocks: an Euler diagram representation. ... A bijective function. ... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ...


Let '~' denote an equivalence relation over some nonempty set A, called the universe or underlying set. Let G denote the set of bijective functions over A that preserve the partition structure of A: ∀xAgG (g(x) ∈ [x ]). Then the following three connected theorems hold (Van Fraassen 1989: §10.3): In mathematics, and particularly in applications to set theory and the foundations of mathematics, a universe or universal class (or if a set, universal set) is, roughly speaking, a class that is large enough to contain (in some sense) all of the sets that one may wish to use. ...

  • ~ partitions A into equivalence classes. (This is the Fundamental Theorem of Equivalence Relations, mentioned above);
  • Given a partition of A, G is a transformation group under composition, whose orbits are the cells of the partition‡;
  • Given a transformation group G over A, there exists an equivalence relation ~ over A, whose equivalence classes are the orbits of G. (Wallace 1998: 202, Th. 6; Dummit and Foote 2004: 114, Prop. 2).

In sum, given an equivalence relation ~ over A, there exists a transformation group G over A whose orbits are the equivalence classes of A under ~. A partition of U into 6 blocks: an Euler diagram representation. ... A partition of U into 6 blocks: an Euler diagram representation. ... In mathematics, a symmetry group describes all symmetries of objects. ... In mathematics, a symmetry group describes all symmetries of objects. ... A partition of U into 6 blocks: a Venn diagram representation. ... In mathematics, a symmetry group describes all symmetries of objects. ... In mathematics, a symmetry group describes all symmetries of objects. ... The symmetry group of a geometric figure is the group of congruencies under which it is invariant, with composition as the operation. ... In mathematics, a symmetry group describes all symmetries of objects. ...


This transformation group characterisation of equivalence relations differs fundamentally from the way lattices characterize order relations. The arguments of the lattice theory operations meet and join are elements of some universe A. Meanwhile, the arguments of the transformation group operations composition and inverse are elements of a set of bijections, AA. The name lattice is suggested by the form of the Hasse diagram depicting it. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... See lattice for other mathematical as well as non-mathematical meanings of the term. ... Look up join in Wiktionary, the free dictionary. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ... A bijective function. ...


On group theory and equivalence relations, also see Lucas (1973: §31).


Proof (adapted from Van Fraassen 1989: 246). Let function composition interpret group multiplication, and function inverse interpret group inverse. Then G is a group under composition, meaning that ∀xAgG ([g(x)] = [x]), because G satisfies the following four conditions: In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ...

Let f and g be any two elements of G. By virtue of the definition of G, [g(f(x))] = [f(x)] and [f(x)] = [x], so that [g(f(x))] = [x]. Hence G is also a transformation group (and an automorphism group) because function composition preserves the partitioning of A. square In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... Look up domain in Wiktionary, the free dictionary. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ... For other uses, see identity (disambiguation). ... An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... In mathematics, associativity is a property that a binary operation can have. ... In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ...


Category theory

The composition of morphisms central to category theory, denoted here by concatenation, generalizes the composition of functions central to transformation groups. The axioms of category theory assert that the composition of morphisms associates, and that the left and right identity morphisms exist. If all morphisms in a category were to have "inverses," the category would resemble a transformation group, whose close relation to equivalence relations has just been explained. A morphism f can be said to have an inverse when f is an automorphism, i.e., the domain and codomain of f are identical, and there exists a morphism g such that fg = gf = identity morphism. Hence the category-theoretic concept nearest to an equivalence relation is a category whose morphisms are all automorphisms. In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In mathematics, a morphism is an abstraction of a function or mapping between two spaces. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes that preserve structure. ... The symmetry group of a geometric figure is the group of congruencies under which it is invariant, with composition as the operation. ... In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ... Look up domain in Wiktionary, the free dictionary. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ...


Equivalence relations and mathematical logic

An implication of model theory is that the properties defining a relation can be proved independent of each other (and hence necessary parts of the definition) if and only if, for each property, examples can be found of relations not satisfying the given property while satisfying all the other properties. Hence the three defining properties of equivalence relations can be proved mutually independent by the following three examples: In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ...

  • Reflexive and transitive: The relation ≤ on N;
  • Symmetric and transitive: The relation R on N, defined as aRbab ≠ 0;
  • Reflexive and symmetric: The relation R on Z, defined as aRb ↔ "ab is divisible by at least one of 2 or 3." More generally, any dependency relation will do.

Properties definable in first-order logic that an equivalence relation may or may not possess include: In mathematics and computer science, a dependency relation is a binary relation that is finite, symmetric, and reflexive. ... First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ...

  • The number of equivalence classes is finite or infinite;
  • The number of equivalence classes equals the (finite) natural number n;
  • All equivalence classes have infinite cardinality;
  • The number of elements in each equivalence class is the natural number n.

An equivalence relation with exactly two infinite equivalence classes is an easy example of a theory which is ω-categorical, but not categorical for any larger cardinal number. In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x in X | x ~ a } The notion of equivalence classes is useful for constructing sets... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ... The categorical imperative is the philosophical concept central to the moral philosophy of Immanuel Kant and to modern deontological ethics. ... Aleph-0, the smallest infinite cardinal In mathematics, cardinal numbers, or cardinals for short, are a generalized kind of number used to denote the size of a set, known as its cardinality. ...


Equivalence relations are not all that difficult or interesting, but can be a source of easy examples or counterexamples.


Euclid anticipated equivalence

Euclid's The Elements includes the following "Common Notion 1": For other uses, see Euclid (disambiguation). ... The frontispiece of Sir Henry Billingsleys first English version of Euclids Elements, 1570 Euclids Elements (Greek: ) is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria circa 300 BC. It comprises a collection of definitions, postulates (axioms), propositions (theorems...

Things which equal the same thing also equal one another.

Nowadays, the property described by Common Notion 1 is called Euclidean (replacing "equal" by "are in relation with"). The following theorem connects Euclidian relations and equivalence relations: This article does not cite any references or sources. ...


Theorem. If a relation is Euclidian and reflexive, it is also symmetric and transitive.


Proof:

  • (aRcbRc) → aRb [a/c] = (aRabRa) → aRb [reflexive; erase T∧] = bRaaRb. Hence R is symmetric.
  • (aRcbRc) → aRb [symmetry] = (aRccRb) → aRb. Hence R is transitive.square

Hence an equivalence relation is a relation that is Euclidean and reflexive. The Elements mentions neither symmetry nor reflexivity, and Euclid probably would have deemed the reflexivity of equality too obvious to warrant explicit mention. If this (and considering "equality" as an abstract relation) is granted, a charitable reading of Common Notion 1 would credit Euclid with being the first to conceive of equivalence relations and their importance in deductive systems.


See also

In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ... In mathematics, a directed set is a set A together with a binary relation &#8804; having the following properties: a &#8804; a for all a in A (reflexivity) if a &#8804; b and b &#8804; c, then a &#8804; c (transitivity) for any two a and b in A, there... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out... In mathematics, a partial equivalence relation (often abbreviated as PER) R on a set X is a relation which is symmetric and transitive. ... In mathematics and set theory, a total order, linear order, simple order, or (non-strict) ordering is a binary relation (here denoted by infix ≤) on some set X. The relation is transitive, antisymmetric, and total. ... Look up Up to on Wiktionary, the free dictionary In mathematics, the phrase up to xxxx indicates that members of an equivalence class are to be regarded as a single entity for some purpose. ...

References

  • Garrett Birkhoff and Saunders Mac Lane, 1999 (1967). Algebra, 3rd ed. Chelsea.
  • Castellani, E., 2003, "Symmetry and equivalence" in Katherine Brading and E. Castellani (eds.), Symmetries in Physics: Philosophical Reflections. Cambridge University Press: 422-433.
  • Robert Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice Hall. Chpt. 12 discusses how equivalence relations arise in lattice theory.
  • Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. John Wiley & Sons.
  • John Randolph Lucas, 1973. A Treatise on Time and Space. London: Methuen. Section 31.
  • Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press.
  • Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag.

Garrett Birkhoff (January 19, 1911, Princeton, New Jersey, USA - November 22, 1996, Water Mill, New York, USA) was an American mathematician. ... Saunders Mac Lane (4 August 1909, Taftville, Connecticut - 14 April 2005, San Francisco) was an American mathematician who cofounded category theory with Samuel Eilenberg. ... Robert Palmer Dilworth (December 2, 1914 – October 29, 1993) was an American mathematician. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ... John Randolph Lucas (born 18 June 1929) is a British philosopher. ... Bastiaan Cornelis van Fraassen (born Goes, the Netherlands, 5 April 1941) is a member of the Princeton University Philosophy department, currently entering phased retirement. ...

External links

  • Equivalence relations

  Results from FactBites:
 
Equivalence Relation (2634 words)
Equivalence relation, a mathematical concept, is a type of relation on a given set that provides a way for elements of that set to be identified with (meaning considered equivalent to for some present purpose) other elements of that set.
Equivalence relation is defined in a branch of mathematics called set theory, a vital branch underpinning all branches of mathematics and those fields that use mathematics.
Equivalence relations are so ubiquitous in mathematics and other fields that use mathematics because they enable the user to partition a set in a particular way of the user’s design.
Equivalence relation - Wikipedia, the free encyclopedia (2425 words)
The equivalence kernel of a bijection is the identity relation.
Green's relations are five equivalence relations on the elements of a semigroup.
Hence an equivalence relation is a relation that is Euclidean and reflexive.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m