Up to

Last updated
In a hexagon vertex set there are 20 partitions which have one three-element subset and three single-element subsets (uncolored) (top figure). Of these, there are four partitions up to rotation, and three partitions up to rotation and reflection. Partitions of 6-set with 3 singletons.svg
In a hexagon vertex set there are 20 partitions which have one three-element subset and three single-element subsets (uncolored) (top figure). Of these, there are four partitions up to rotation, and three partitions up to rotation and reflection.

In mathematics, the phrase up to is used to convey the idea that some objects in the same class — while distinct — may be considered to be equivalent under some condition or transformation. [1] It often appears in discussions about the elements of a set, and the conditions under which some of those elements may be considered to be equivalent. More specifically, given two elements , " and are equivalent up to " means that and are equivalent, if criterion , such as rotation or permutation, is ignored. In which case, the elements of can be arranged in subsets known as "equivalence classes", sets whose elements are equivalent to each other up to . In some cases, this might mean that and can be transformed into one another—if a transformation corresponding to (e.g., rotation, permutation) is applied.

Contents

If is some property or process, then the phrase "up to " can be taken to mean "disregarding a possible difference in ". For instance, the statement "an integer's prime factorization is unique up to ordering" means that the prime factorization is unique—when we disregard the order of the factors. [2] One might also say "the solution to an indefinite integral is , up to addition by a constant ", meaning that the focus is on the solution rather than the added constant, and that the addition of a constant is to be regarded as a background information. 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

Tetris pieces O, I, L, J, T, S, Z Tetrominoes IJLO STZ Worlds.svg
Tetris pieces O, I, L, J, T, S, Z

A simple example is "there are seven reflecting 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). This could also be written as "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 notation is likely to seem more natural.

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 reflecting tetrominoes (= 19 total [3] ) up to rotations". Here, Tetris provides an excellent example, as one might simply count 7 pieces × 4 rotations as 28, where some pieces (such as the 2×2 O) obviously have fewer than four rotation states.

Eight queens

A solution of the eight queens problem Skak 8dronning.png
A solution of the eight queens problem

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 identical, and one usually says "there are 92 () unique solutions up to permutations of the queens", or that "there are 92 solutions mod 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 given n, is unique up to similarity. In other words, if all similar n-gons are considered instances of the same n-gon, then there is only one regular n-gon.

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", [1] 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. [4]

See also

Related Research Articles

Eight queens puzzle mathematical chess problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3.

In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two groups, then the groups are called isomorphic. From the standpoint of group theory, isomorphic groups have the same properties and need not be distinguished.

Group action Operation of the elements of a group as transformations or automorphisms (mathematics)

In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism group of the structure. It is said that the group acts on the space or structure. If a group acts on a structure, it also acts on everything that is built on the structure. For example, the group of Euclidean isometries acts on Euclidean space and also on the figures drawn in it. In particular, it acts on the set of all triangles. Similarly, the group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron.

Isomorphism In mathematics, invertible homomorphism

In mathematics, an isomorphism is a mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσος isos "equal", and μορφή morphe "form" or "shape".

Group (mathematics) Algebraic structure with one binary operation

In mathematics, a group is a set equipped with a binary operation that combines any two elements to form a third element in such a way that four conditions called group axioms are satisfied, namely closure, associativity, identity and invertibility. One of the most familiar examples of a group is the set of integers together with the addition operation, but groups are encountered in numerous areas within and outside mathematics, and help focusing on essential structural aspects, by detaching them from the concrete nature of the subject of the study.

Modular arithmetic Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

Pentomino a polygon in the plane made of 5 equal-sized squares connected edge-to-edge

A pentomino is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there are 12 different free pentominoes. When reflections are considered distinct, there are 18 one-sided pentominoes. When rotations are also considered distinct, there are 63 fixed pentominoes.

Permutation group Group whose operation is composition of permutations

In mathematics, a permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of permutations in G. The group of all permutations of a set M is the symmetric group of M, often written as Sym(M). The term permutation group thus means a subgroup of the symmetric group. If M = {1,2,...,n} then, Sym(M), the symmetric group on n letters is usually denoted by Sn.

Symmetric group automorphism group of a set; the group of bijections on a set, whose group operation is function composition

In 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 Sn defined over a finite set of n symbols consists of the permutation operations that can be performed on the n symbols. Since there are n! such permutation operations, the order of the symmetric group Sn is n!.

Tetromino type of polyomino; corresponding tetracube (type of polycube); geometric shape composed of four squares, connected orthogonally

A tetromino is a geometric shape composed of four squares, connected orthogonally. This, like dominoes and pentominoes, is a particular type of polyomino. The corresponding polycube, called a tetracube, is a geometric shape composed of four cubes connected orthogonally.

Group theory branch of mathematics that studies the algebraic properties of groups

In mathematics and abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen as groups endowed with additional operations and axioms. Groups recur throughout mathematics, and the methods of group theory have influenced many parts of algebra. Linear algebraic groups and Lie groups are two branches of group theory that have experienced advances and have become subject areas in their own right.

Klein four-group

In mathematics, the Klein four-group is a group with four elements, in which each element is self-inverse (composing it with itself produces the identity) and in which composing any two of the three non-identity elements produces the third one. It can be described as the symmetry group of a non-square rectangle (with the three non-identity elements being horizontal and vertical reflection and 180-degree rotation), as the group of bitwise exclusive or operations on two-bit binary values, or more abstractly as Z2 × Z2, the direct product of two copies of the cyclic group of order 2. It was named Vierergruppe (meaning four-group) by Felix Klein in 1884. It is also called the Klein group, and is often symbolized by the letter V or as K4.

Permutation Change of ordering in a (mathematical) set

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.

Imaginary unit Principal square root of −1

The imaginary unit or unit imaginary number is a solution to the quadratic equation x2 + 1 = 0. Although there is no real number with this property, i can be used to extend the real numbers to what are called complex numbers, using addition and multiplication. A simple example of the use of i in a complex number is 2 + 3i.

Galois theory Mathematical connection between field theory and group theory

In mathematics, Galois theory provides a connection between field theory and group theory. Using Galois theory, certain problems in field theory can be reduced to group theory, which is in some sense simpler and better understood. It has been used to solve classic problems including showing that two problems of antiquity cannot be solved as they were stated ; showing that there is no quintic formula; and showing which polygons are constructible.

In the mathematics of the real numbers, the logarithm logba is a number x such that bx = a, for given numbers a and b. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logba is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) for rxa (mod m) if r is a primitive root of m and gcd(a,m) = 1.

Dihedral group of order 6 Non-commutative group with 6 elements

In mathematics, D3 (sometimes alternatively denoted by D6) is the dihedral group of degree 3, or, in other words, the dihedral group of order 6. It is isomorphic to the symmetric group S3 of degree 3. It is also the smallest possible non-abelian group.

Symmetry in mathematics symmetry in mathematics

Symmetry occurs not only in geometry, but also in other branches of mathematics. Symmetry is a type of invariance: the property that a mathematical object remains unchanged under a set of operations or transformations.

In mathematics, the term essentially unique is used to describe a weaker form of uniqueness, where an object satisfying a property is "unique" only in the sense that all objects satisfying the property are equivalent to each other. The notion of essential uniqueness presupposes some form of "sameness", which is often formalized using an equivalence relation.

In mathematics, particularly in the area of number theory, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as

References

  1. 1 2 "The Definitive Glossary of Higher Mathematical Jargon — Up to". Math Vault. 2019-08-01. Retrieved 2019-11-21.
  2. Nekovář, Jan (2011). "Mathematical English (a brief summary)" (PDF). Institut de mathématiques de Jussieu – Paris Rive Gauche. Retrieved 2019-11-21.
  3. Weisstein, Eric W. "Tetromino". mathworld.wolfram.com. Retrieved 2019-11-21.
  4. Damien Pous, Up-to techniques for weak bisimulation, Proc. 32th ICALP, Lecture Notes in Computer Science, vol. 3580, Springer Verlag (2005), pp. 730–741

Further reading