Up to

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

Two mathematical objects a and b are called equal up to an equivalence relation R

Contents

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 toR 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 by a constant" tacitly employs the equivalence relation R between functions, defined by fRg if fg is a constant function, and means that the solution and the function sin(x) are equal up to this R. [2] 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 does". 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

Tetris pieces I, J, L, O, S, T, Z Tetrominoes IJLO STZ Worlds.svg
Tetris pieces I, J, L, O, S, T, 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). 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.

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, but 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", [2] 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

Equivalence relation Mathematical concept for comparing objects

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The relation "is equal to" is the canonical example of an equivalence relation.

Equivalence class

In mathematics, when the elements of some set S have a notion of equivalence defined on them, then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a and b belong to the same equivalence class if, and only if, they are equivalent.

Eight queens puzzle Mathematical problem/puzzle set on a chessboard

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.

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

Isomorphism In mathematics, invertible homomorphism

In mathematics, an isomorphism is a structure-preserving 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 conditions called group axioms are satisfied, namely associativity, identity and invertibility. These conditions are familiar from many mathematical structures, such as number systems: for example, the integers endowed with the addition operation form a group. The formulation of the axioms is, however, detached from the concrete nature of the group and its operation. This allows one to handle entities of very different mathematical origins in a flexible way, while retaining essential structural aspects of many objects in abstract algebra and beyond. The ubiquity of groups in numerous areas—both within and outside mathematics—makes them a central organizing principle of contemporary mathematics.

In mathematics, equality is a relationship between two quantities or, more generally two mathematical expressions, asserting that the quantities have the same value, or that the expressions represent the same mathematical object. The equality between A and B is written A = B, and pronounced A equals B. The symbol "=" is called an "equals sign". Two objects that are not equal are said to be distinct.

In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation

In mathematics and logic, the term "uniqueness" refers to the property of being the one and only object satisfying a certain condition. This sort of quantification is known as uniqueness quantification or unique existential quantification, and is often denoted with the symbols "∃!" or "∃=1". For example, the formal statement

In mathematics, localization of a category consists of adding to a category inverse morphisms for some collection of morphisms, constraining them to become isomorphisms. This is formally similar to the process of localization of a ring; it in general makes objects isomorphic that were not so before. In homotopy theory, for example, there are many examples of mappings that are invertible up to homotopy; and so large classes of homotopy equivalent spaces. Calculus of fractions is another name for working in a localized category.

In mathematics, the term modulo is often used to assert that two distinct mathematical objects can be regarded as equivalent—if their difference is accounted for by an additional factor. It was initially introduced into mathematics in the context of modular arithmetic by Carl Friedrich Gauss in 1801. Since then, the term has gained many meanings—some exact and some imprecise. For the most part, the term often occurs in statements of the form:

Orientation (vector space) Choice of reference for distinguishing an object and its mirror image

In mathematics, orientation is a geometric notion that in two dimensions allows one to say when a cycle goes around clockwise or counterclockwise, and in three dimensions when a figure is left-handed or right-handed. In linear algebra, the notion of orientation makes sense in arbitrary finite dimension. In this setting, the orientation of an ordered basis is a kind of asymmetry that makes a reflection impossible to replicate by means of a simple rotation. Thus, in three dimensions, it is impossible to make the left hand of a human figure into the right hand of the figure by applying a rotation alone, but it is possible to do so by reflecting the figure in a mirror. As a result, in the three-dimensional Euclidean space, the two possible basis orientations are called right-handed and left-handed.

In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum. Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolean algebra A has an essentially unique completion, which is a complete Boolean algebra containing A such that every element is the supremum of some subset of A. As a partially ordered set, this completion of A is the Dedekind–MacNeille completion.

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.

Mathematics of Sudoku Mathematical investigation of Sudoku

Sudoku puzzles can be studied mathematically to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

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, a canonical map, also called a natural map, is a map or morphism between objects that arises naturally from the definition or the construction of the objects. In general, it is the map which preserves the widest amount of structure, and it tends to be unique. In the rare cases where latitude in choices remains, the map is either conventionally agreed upon to be the most useful for further analysis, or sometimes the most elegant map known up to date.

In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that either of the orders can be obtained from the other just by renaming of elements. Two strictly weaker notions that relate to order isomorphisms are order embeddings and Galois connections.

In mathematics, equivalent definitions are used in two somewhat different ways. First, within a particular mathematical theory, a notion may have more than one definition. These definitions are equivalent in the context of a given mathematical structure. Second, a mathematical structure may have more than one definition.

References

  1. Nekovář, Jan (2011). "Mathematical English (a brief summary)" (PDF). Institut de mathématiques de Jussieu – Paris Rive Gauche. Retrieved 2019-11-21.
  2. 1 2 "The Definitive Glossary of Higher Mathematical Jargon — Up to". Math Vault. 2019-08-01. 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. 32nd ICALP, Lecture Notes in Computer Science, vol. 3580, Springer Verlag (2005), pp. 730–741

Further reading