Up to
Two mathematical objects a and b are called equal up to an equivalence relation R
- if a and b are related by R, that is,
- if aRb holds, that is,
- if the equivalence classes of a and b with respect to R are equal.
This figure of speech is mostly used in connection with expressions derived from equality, such as uniqueness or count. For example, x is unique up to R means that all objects x under consideration are in the same equivalence class with respect to the relation R.
Moreover, the equivalence relation R is often designated rather implicitly by a generating condition or transformation. For example, the statement "an integer's prime factorization is unique up to ordering" is a concise way to say that any two lists of prime factors of a given integer are equivalent with respect to the relation R that relates two lists if one can be obtained by reordering (permutation) from the other.[1] As another example, the statement "the solution to an indefinite integral is sin(x), up to addition of a constant" tacitly employs the equivalence relation R between functions, defined by fRg if the difference f−g is a constant function, and means that the solution and the function sin(x) are equal up to this R. In the picture, "there are 4 partitions up to rotation" means that the set P has 4 equivalence classes with respect to R defined by aRb if b can be obtained from a by rotation; one representative from each class is shown in the bottom left picture part.
Equivalence relations are often used to disregard possible differences of objects, so "up to R" can be understood informally as "ignoring the same subtleties as R ignores". In the factorization example, "up to ordering" means "ignoring the particular ordering".
Further examples include "up to isomorphism", "up to permutations", and "up to rotations", which are described in the Examples section.
In informal contexts, mathematicians often use the word modulo (or simply "mod") for similar purposes, as in "modulo isomorphism".
Examples
Tetris
A simple example is "there are seven tetrominoes, up to rotations", which makes reference to the seven possible contiguous arrangements of tetrominoes (collections of four unit squares arranged to connect on at least one side) and which are frequently thought of as the seven Tetris pieces (O, I, L, J, T, S, Z). One could also say "there are five tetrominoes, up to reflections and rotations", which would then take into account the perspective that L and J (as well as S and Z) can be thought of as the same piece when reflected. The Tetris game does not allow reflections, so the former statement is likely to seem more relevant than the latter.
To add in the exhaustive count, there is no formal notation for the number of pieces of tetrominoes. However, it is common to write that "there are seven tetrominoes (= 19 total[2]) up to rotations". Here, Tetris provides an excellent example, as one might simply count 7 pieces × 4 rotations as 28, but some pieces (such as the 2×2 O) obviously have fewer than four rotation states.
Eight queens
In the eight queens puzzle, if the eight queens are considered to be distinct, then there are 3709440 distinct solutions. Normally, however, the queens are considered to be equal, and one usually says "there are 3,709,440 / 8! = 92 unique solutions up to permutations of the queens", or that "there are 92 solutions modulo the names of the queens", signifying that two different arrangements of the queens are considered equivalent if the queens have been permuted, but the same squares on the chessboard are occupied by them.
If, in addition to treating the queens as identical, rotations and reflections of the board were allowed, we would have only 12 distinct solutions up to symmetry and the naming of the queens, signifying that two arrangements that are symmetrical to each other are considered equivalent (for more, see Eight queens puzzle § Solutions).
Polygons
The regular n-gon, for a fixed n, is unique up to similarity. In other words, by scaling, translation, and rotation, as necessary, any n-gon can be transformed to any other n-gon (with the same n).
Group theory
In group theory, one may have a group G acting on a set X, in which case, one might say that two elements of X are equivalent "up to the group action"—if they lie in the same orbit.
Another typical example is the statement that "there are two different groups of order 4 up to isomorphism", or "modulo isomorphism, there are two groups of order 4". This means that there are two equivalence classes of groups of order 4—assuming that one considers groups to be equivalent if they are isomorphic.
Nonstandard analysis
A hyperreal x and its standard part st(x) are equal up to an infinitesimal difference.
Computer science
In computer science, the term up-to techniques is a precisely defined notion that refers to certain proof techniques for (weak) bisimulation, and to relate processes that only behave similarly up to unobservable steps.[3]
See also
References
- Nekovář, Jan (2011). "Mathematical English (a brief summary)" (PDF). Institut de mathématiques de Jussieu – Paris Rive Gauche. Retrieved 2019-11-21.
- Weisstein, Eric W. "Tetromino". mathworld.wolfram.com. Retrieved 2019-11-21.
- Damien Pous, Up-to techniques for weak bisimulation, Proc. 32nd ICALP, Lecture Notes in Computer Science, vol. 3580, Springer Verlag (2005), pp. 730–741