Equivalence relationIn mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other if and only if they belong to the same equivalence class.
Equivalence classIn mathematics, when the elements of some set have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set into equivalence classes. These equivalence classes are constructed so that elements and belong to the same equivalence class if, and only if, they are equivalent. Formally, given a set and an equivalence relation on the of an element in denoted by is the set of elements which are equivalent to It may be proven, from the defining properties of equivalence relations, that the equivalence classes form a partition of This partition—the set of equivalence classes—is sometimes called the quotient set or the quotient space of by and is denoted by .
Transitive relationIn mathematics, a relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive. A homogeneous relation R on the set X is a transitive relation if, for all a, b, c ∈ X, if a R b and b R c, then a R c. Or in terms of first-order logic: where a R b is the infix notation for (a, b) ∈ R. As a non-mathematical example, the relation "is an ancestor of" is transitive.
Reflexive relationIn mathematics, a binary relation R on a set X is reflexive if it relates every element of X to itself. An example of a reflexive relation is the relation "is equal to" on the set of real numbers, since every real number is equal to itself. A reflexive relation is said to have the reflexive property or is said to possess reflexivity. Along with symmetry and transitivity, reflexivity is one of three properties defining equivalence relations.
Symmetric polynomialIn mathematics, a symmetric polynomial is a polynomial P(X1, X2, ..., Xn) in n variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, P is a symmetric polynomial if for any permutation σ of the subscripts 1, 2, ..., n one has P(Xσ(1), Xσ(2), ..., Xσ(n)) = P(X1, X2, ..., Xn). Symmetric polynomials arise naturally in the study of the relation between the roots of a polynomial in one variable and its coefficients, since the coefficients can be given by polynomial expressions in the roots, and all roots play a similar role in this setting.
Ring of symmetric functionsIn algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in n indeterminates, as n goes to infinity. This ring serves as universal structure in which relations between symmetric polynomials can be expressed in a way independent of the number n of indeterminates (but its elements are neither polynomials nor functions). Among other things, this ring plays an important role in the representation theory of the symmetric group.
Closure (mathematics)In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but not under subtraction: 1 − 2 is not a natural number, although both 1 and 2 are. Similarly, a subset is said to be closed under a collection of operations if it is closed under each of the operations individually. The closure of a subset is the result of a closure operator applied to the subset.
IntransitivityIn mathematics, intransitivity (sometimes called nontransitivity) is a property of binary relations that are not transitive relations. This may include any relation that is not transitive, or the stronger property of antitransitivity, which describes a relation that is never transitive. A relation is transitive if, whenever it relates some A to some B, and that B to some C, it also relates that A to that C.
Partial equivalence relationIn mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) is a homogeneous binary relation that is symmetric and transitive. If the relation is also reflexive, then the relation is an equivalence relation. Formally, a relation on a set is a PER if it holds for all that: if , then (symmetry) if and , then (transitivity) Another more intuitive definition is that on a set is a PER if there is some subset of such that and is an equivalence relation on .
Transitive reductionIn the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D.
Relation (mathematics)In mathematics, a binary relation on a set may, or may not, hold between two given set members. For example, "is less than" is a relation on the set of natural numbers; it holds e.g. between 1 and 3 (denoted as 1
Elementary symmetric polynomialIn mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary symmetric polynomials. That is, any symmetric polynomial P is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials.
Binary relationIn mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain. A binary relation over sets X and Y is a new set of ordered pairs (x, y) consisting of elements x in X and y in Y. It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation.
Homogeneous relationIn mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.
Complete homogeneous symmetric polynomialIn mathematics, specifically in algebraic combinatorics and commutative algebra, the complete homogeneous symmetric polynomials are a specific kind of symmetric polynomials. Every symmetric polynomial can be expressed as a polynomial expression in complete homogeneous symmetric polynomials. The complete homogeneous symmetric polynomial of degree k in n variables X1, ..., Xn, written hk for k = 0, 1, 2, ..., is the sum of all monomials of total degree k in the variables.
Symmetric relationA symmetric relation is a type of binary relation. An example is the relation "is equal to", because if a = b is true then b = a is also true. Formally, a binary relation R over a set X is symmetric if: where the notation means that . If RT represents the converse of R, then R is symmetric if and only if R = RT. Symmetry, along with reflexivity and transitivity, are the three defining properties of an equivalence relation. "is equal to" (equality) (whereas "is less than" is not symmetric) "is comparable to", for elements of a partially ordered set ".
Reflexive closureIn mathematics, the reflexive closure of a binary relation on a set is the smallest reflexive relation on that contains A relation is called if it relates every element of to itself. For example, if is a set of distinct numbers and means " is less than ", then the reflexive closure of is the relation " is less than or equal to ". The reflexive closure of a relation on a set is given by In plain English, the reflexive closure of is the union of with the identity relation on As an example, if then the relation is already reflexive by itself, so it does not differ from its reflexive closure.
Tolerance relationIn universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption of transitivity is dropped. On a set, an algebraic structure with empty family of operations, tolerance relations are simply reflexive symmetric relations. A set that possesses a tolerance relation can be described as a tolerance space.
Representation theory of the symmetric groupIn mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from symmetric function theory to quantum chemistry studies of atoms, molecules and solids. The symmetric group Sn has order n!. Its conjugacy classes are labeled by partitions of n.
Symmetric groupIn abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are ( factorial) such permutation operations, the order (number of elements) of the symmetric group is .
