 | This articlemay beconfusing or unclear to readers. In particular, all this article confuses "invariance" (a property) and "an invariant" (a mathematical object that is left invariant under agroup action). Please helpclarify the article. There might be a discussion about this onthe talk page.(January 2024) (Learn how and when to remove this message) |
 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(April 2015) (Learn how and when to remove this message) |
Inmathematics, aninvariant is a property of amathematical object (or aclass of mathematical objects) which remains unchanged afteroperations ortransformations of a certain type are applied to the objects.[1][2] The particular class of objects and type of transformations are usually indicated by the context in which the term is used. For example, thearea of atriangle is an invariant with respect toisometries of theEuclidean plane. The phrases "invariant under" and "invariant to" a transformation are both used. More generally, an invariant with respect to anequivalence relation is a property that is constant on eachequivalence class.[3]
Invariants are used in diverse areas of mathematics such asgeometry,topology,algebra anddiscrete mathematics. Some important classes of transformations are defined by an invariant they leave unchanged. For example,conformal maps are defined as transformations of the plane that preserveangles. The discovery of invariants is an important step in the process of classifying mathematical objects.[2][3]
A simple example of invariance is expressed in our ability tocount. For afinite set of objects of any kind, there is a number to which we always arrive, regardless of theorder in which we count the objects in theset. The quantity—acardinal number—is associated with the set, and is invariant under the process of counting.
Anidentity is an equation that remains true for all values of its variables. There are alsoinequalities that remain true when the values of their variables change.
Thedistance between two points on anumber line is not changed byadding the same quantity to both numbers. On the other hand,multiplication does not have this same property, as distance is not invariant under multiplication.
Angles andratios of distances are invariant underscalings,rotations,translations andreflections. These transformations producesimilar shapes, which is the basis oftrigonometry. In contrast, angles and ratios are not invariant under non-uniform scaling (such as stretching). The sum of a triangle's interior angles (180°) is invariant under all the above operations. As another example, allcircles are similar: they can be transformed into each other and the ratio of thecircumference to thediameter is invariant (denoted by the Greek letter π (pi)).
Some more complicated examples:
TheMU puzzle[7] is a good example of a logical problem where determining an invariant is of use for animpossibility proof. The puzzle asks one to start with the word MI and transform it into the word MU, using in each step one of the following transformation rules:
An example derivation (with superscripts indicating the applied rules) is
In light of this, one might wonder whether it is possible to convert MI into MU, using only these four transformation rules. One could spend many hours applying these transformation rules to strings. However, it might be quicker to find aproperty that is invariant to all rules (that is, not changed by any of them), and that demonstrates that getting to MU is impossible. By looking at the puzzle from a logical standpoint, one might realize that the only way to get rid of any I's is to have three consecutive I's in the string. This makes the following invariant interesting to consider:
This is an invariant to the problem, if for each of the transformation rules the following holds: if the invariant held before applying the rule, it will also hold after applying it. Looking at the net effect of applying the rules on the number of I's and U's, one can see this actually is the case for all rules:
| Rule | #I's | #U's | Effect on invariant |
|---|---|---|---|
| 1 | +0 | +1 | Number of I's is unchanged. If the invariant held, it still does. |
| 2 | ×2 | ×2 | Ifn is not a multiple of 3, then 2×n is not either. The invariant still holds. |
| 3 | −3 | +1 | Ifn is not a multiple of 3,n−3 is not either. The invariant still holds. |
| 4 | +0 | −2 | Number of I's is unchanged. If the invariant held, it still does. |
The table above shows clearly that the invariant holds for each of the possible transformation rules, which means that whichever rule one picks, at whatever state, if the number of I's was not a multiple of three before applying the rule, then it will not be afterwards either.
Given that there is a single I in the starting string MI, and one is not a multiple of three, one can then conclude that it is impossible to go from MI to MU (as the number of I's will never be a multiple of three).
AsubsetS of the domainU of a mappingT:U →U is aninvariant set under the mapping when Theelements ofS are not necessarilyfixed, even though the setS is fixed in thepower set ofU. (Some authors use the terminologysetwise invariant,[8] vs.pointwise invariant,[9] to distinguish between these cases.)For example, a circle is an invariant subset of the plane under arotation about the circle's center. Further, aconical surface is invariant as a set under ahomothety of space.
An invariant set of an operationT is also said to bestable underT. For example, thenormal subgroups that are so important ingroup theory are thosesubgroups that are stable under theinner automorphisms of the ambientgroup.[10][11][12]Inlinear algebra, if alinear transformationT has aneigenvectorv, then the line through0 andv is an invariant set underT, in which case the eigenvectors span aninvariant subspace which is stable underT.
WhenT is ascrew displacement, thescrew axis is an invariant line, though if thepitch is non-zero,T has no fixed points.
Inprobability theory andergodic theory, invariant sets are usually defined via the stronger property[13][14][15] When the map is measurable, invariant sets form asigma-algebra, theinvariant sigma-algebra.
 | This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(February 2010) (Learn how and when to remove this message) |
The notion of invariance is formalized in three different ways in mathematics: viagroup actions, presentations, and deformation.
Firstly, if one has agroupGacting on a mathematical object (or set of objects)X, then one may ask which pointsx are unchanged, "invariant" under the group action, or under an elementg of the group.
Frequently one will have a group acting on a setX, which leaves one to determine which objects in anassociated setF(X) are invariant. For example, rotation in the plane about a point leaves the point about which it rotates invariant, while translation in the plane does not leave any points invariant, but does leave all lines parallel to the direction of translation invariant as lines. Formally, define the set of lines in the planeP asL(P); then arigid motion of the plane takes lines to lines – the group of rigid motions acts on the set of lines – and one may ask which lines are unchanged by an action.
More importantly, one may define afunction on a set, such as "radius of a circle in the plane", and then ask if this function is invariant under a group action, such as rigid motions.
Dual to the notion of invariants arecoinvariants, also known asorbits, which formalizes the notion ofcongruence: objects which can be taken to each other by a group action. For example, under the group of rigid motions of the plane, theperimeter of a triangle is an invariant, while the set of triangles congruent to a given triangle is a coinvariant.
These are connected as follows: invariants are constant on coinvariants (for example, congruent triangles have the same perimeter), while two objects which agree in the value of one invariant may or may not be congruent (for example, two triangles with the same perimeter need not be congruent). Inclassification problems, one might seek to find acomplete set of invariants, such that if two objects have the same values for this set of invariants, then they are congruent.
For example, triangles such that all three sides are equal are congruent under rigid motions, viaSSS congruence, and thus the lengths of all three sides form a complete set of invariants for triangles. The three angle measures of a triangle are also invariant under rigid motions, but do not form a complete set as incongruent triangles can share the same angle measures. However, if one allows scaling in addition to rigid motions, then theAAA similarity criterion shows that this is a complete set of invariants.
Secondly, a function may be defined in terms of some presentation or decomposition of a mathematical object; for instance, theEuler characteristic of acell complex is defined as the alternating sum of the number of cells in each dimension. One may forget the cell complex structure and look only at the underlyingtopological space (themanifold) – as different cell complexes give the same underlying manifold, one may ask if the function isindependent of choice ofpresentation, in which case it is anintrinsically defined invariant. This is the case for the Euler characteristic, and a general method for defining and computing invariants is to define them for a given presentation, and then show that they are independent of the choice of presentation. Note that there is no notion of a group action in this sense.
The most common examples are:
Thirdly, if one is studying an object which varies in a family, as is common inalgebraic geometry anddifferential geometry, one may ask if the property is unchanged under perturbation (for example, if an object is constant on families or invariant under change of metric).
Incomputer science, an invariant is alogical assertion that is always held to be true during a certain phase of execution of acomputer program. For example, aloop invariant is a condition that is true at the beginning and the end of every iteration of a loop.
Invariants are especially useful when reasoning about thecorrectness of a computer program. The theory ofoptimizing compilers, the methodology ofdesign by contract, andformal methods for determiningprogram correctness, all rely heavily on invariants.
Programmers often useassertions in their code to make invariants explicit. Someobject orientedprogramming languages have a special syntax for specifyingclass invariants.
Abstract interpretation tools can compute simple invariants of given imperative computer programs. The kind of properties that can be found depend on theabstract domains used. Typical example properties are single integer variable ranges like0<=x<1024, relations between several variables like0<=i-j<2*n-1, and modulus information likey%4==0. Academic research prototypes also consider simple properties of pointer structures.[16]
More sophisticated invariants generally have to be provided manually.In particular, when verifying an imperative program usingthe Hoare calculus,[17] a loop invariant has to be provided manually for each loop in the program, which is one of the reasons that this approach is generally impractical for most programs.
In the context of the aboveMU puzzle example, there is currently no general automated tool that can detect that a derivation from MI to MU is impossible using only the rules 1–4. However, once the abstraction from the string to the number of its "I"s has been made by hand, leading, for example, to the following C program, an abstract interpretation tool will be able to detect thatICount%3 cannot be 0, and hence the "while"-loop will never terminate.
voidMUPuzzle(void){volatileintRandomRule;intICount=1,UCount=0;while(ICount%3!=0)// non-terminating loopswitch(RandomRule){case1:UCount+=1;break;case2:ICount*=2;UCount*=2;break;case3:ICount-=3;UCount+=1;break;case4:UCount-=2;break;}// computed invariant: ICount % 3 == 1 || ICount % 3 == 2}
{{citation}}:ISBN / Date incompatibility (help)