|
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). Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ...
Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ...
In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...
Modular arithmetic
The prototypical example is modular arithmetic: for n a positive integer, two integers a and b are called congruent modulo n if a − b is divisible by n (or an equivalent condition is that they give the same remainder when divided by n). Modular arithmetic (sometimes called modulo arithmetic) 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, …), their negatives (−1, −2, −3, ...) and the number zero. ...
For example, 5 and 11 are congruent modulo 3:
- 11 ≡ 5 (mod 3)
because 11 − 5 gives 6, which is divisible by 3. Or, equally, both numbers give the same remainder when divided by 3: - 11 = 3×3 + 2
- 5 = 1×3 + 2
If  and  , then  and  . This turns the congruence (mod n) into an equivalence on the ring of all integers. In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ...
The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...
Linear algebra Two real matrices A and B are called congruent if there is an invertible real matrix P such that In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...
In mathematics, two matrices A and B with real entries are called congruent if there exists an invertible matrix P with real entries such that PTAP = B where T denotes the matrix transpose. ...
In linear algebra, an n-by-n (square) matrix is called invertible, non-singular, or regular if there exists an n-by-n matrix such that where denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. ...
 A symmetric matrix has real eigenvalues. The inertia of a symmetric matrix is a triple consisting of the number of positive eigenvalues, the number of zero eigenvalues, and the number of negative eigenvalues. Sylvester's law of inertia states that two symmetric real matrices are congruent if and only if they have the same inertia. So, congruence transformations may change the eigenvalues of a matrix but they cannot change the signs of the eigenvalues. In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...
In linear algebra, Sylvesters law of inertia states that the inertia of a matrix A is invariant under congruence transformations. ...
For complex matrices, we have to distinguish between Tcongruency (A and B are Tcongruent if there is an invertible matrix P such that PTAP = B) and *congruency (A and B are *congruent if there is an invertible matrix P such that P*AP = B).
Universal algebra The idea is generalized in universal algebra: A congruence relation on an algebra A is a subset of the direct product A × A that is both an equivalence relation on A and a subalgebra of A × A. Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ...
A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ...
In mathematics, one can often define a direct product of objects already known, giving a new one. ...
In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...
In universal algebra, a subalgebra of an algebra A is a subset S of A that also has the structure of an algebra of the same type when the algebraic operations are restricted to A. Since the axioms of algebraic structures in universal algebra are described by equational laws, the...
Congruences typically arise as kernels of homomorphisms, and in fact every congruence is the kernel of some homomorphism: For a given congruence ~ on A, the set A/~ of equivalence classes can be given the structure of an algebra in a natural fashion, the quotient algebra. Furthermore, the function that maps every element of A to its equivalence class is a homomorphism, and the kernel of this homomorphism is ~. 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. ...
In abstract algebra, a homomorphism is a structure-preserving map. ...
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 ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...
(See also Algebraic lattice.) In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any directed set that does not already contain members above the compact element. ...
Group theory In the particular case of groups, congruence relations can be described in elementary terms as follows: If G is a group (with identity element e) and ~ is a binary relation on G, then ~ is a congruence whenever: In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ...
In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...
In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ...
- Given any element a of G, a ~ a (reflexivity);
- Given any elements a and b of G, if a ~ b, then b ~ a (symmetry);
- Given any elements a, b, and c of G, if a ~ b and b ~ c, then a ~ c (transitivity);
- Given any elements a and a' of G, if a ~ a' , then a−1 ~ a' −1 (this can actually be proven from the other four, so is strictly redundant);
- Given any elements a, a' , b, and b' of G, if a ~ a' and b ~ b' , then a * b ~ a' * b' .
Notice that ~ is trivially an equivalence relation by 1, 2 and 3. In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ...
In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ...
In logical calculus of mathematics, the logical conditional (also known as the material implication, sometimes material conditional) is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ...
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. ...
AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ...
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, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...
Also notice that such a congruence ~ is determined entirely by the set {a ∈ G : a ~ e} of those elements of G that are congruent to the identity element, and this set is a normal subgroup. Specifically, a ~ b if and only if b−1 * a ~ e. So instead of talking about congruences on groups, people usually speak in terms of normal subgroups of them; in fact, every congruence corresponds uniquely to some normal subgroup of G. This is what makes it possible to speak of kernels in group theory as subgroups, while in more general universal algebra, kernels are congruences. 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...
Ring theory A similar trick allows one to speak of kernels in ring theory as ideals instead of congruence relations, and in module theory as submodules instead of congruence relations. In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ...
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. ...
In abstract algebra, the notion of a module over a ring is the common generalizations of two of the most important notions in algebra, vector space (where we take the ring to be a particular field), and abelian group (where we take the ring to be the ring of integers). ...
In abstract algebra, a module is a generalization of a vector space. ...
General case of kernels The most general situation where this trick is possible is in ideal-supporting algebras. But this cannot be done with, for example, monoids, so the study of congruence relations plays a more central role in monoid theory. In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...
See also Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...
The word modulo is the Latin ablative of modulus. ...
References - Horn and Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2. (Section 4.5 discusses congruency of matrices.)
|
Feeds |
Contact