Table of Contents
82 relations: Abstract rewriting system, Alexandrov topology, Antisymmetric relation, Asymmetric relation, Big O notation, Bijection, Binary relation, Category (mathematics), Category of preordered sets, Class (set theory), Commutative ring, Complement (set theory), Composition of relations, Connected relation, Consistency, Converse relation, Cycle (graph theory), Directed acyclic graph, Directed graph, Directed set, Division (mathematics), Embedding, Encompassment ordering, Enriched category, Equivalence class, Equivalence relation, Finite topological space, Forcing (mathematics), Graph minor, Greatest common divisor, Independence (mathematical logic), Injective function, Interior algebra, Interval (mathematics), Kripke semantics, Least common multiple, Lindenbaum–Tarski algebra, Logical conjunction, Logical equivalence, Many-one reduction, Mathematics, Modal logic, Modus ponens, Morphism, Neighbourhood (mathematics), Net (mathematics), Order theory, Partially ordered set, Path (graph theory), Permutation, ... Expand index (32 more) »
- Properties of binary relations
Abstract rewriting system
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a formalism that captures the quintessential notion and properties of rewriting systems.
See Preorder and Abstract rewriting system
Alexandrov topology
In topology, an Alexandrov topology is a topology in which the intersection of every family of open sets is open. Preorder and Alexandrov topology are order theory.
See Preorder and Alexandrov topology
Antisymmetric relation
In mathematics, a binary relation R on a set X is antisymmetric if there is no pair of distinct elements of X each of which is related by R to the other. Preorder and antisymmetric relation are properties of binary relations.
See Preorder and Antisymmetric relation
Asymmetric relation
In mathematics, an asymmetric relation is a binary relation R on a set X where for all a, b \in X, if a is related to b then b is not related to a. Preorder and asymmetric relation are properties of binary relations.
See Preorder and Asymmetric relation
Big O notation
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
See Preorder and Big O notation
Bijection
A bijection, bijective function, or one-to-one correspondence between two mathematical sets is a function such that each element of the first set (the domain) is mapped to exactly one element of the second set (the codomain).
Binary relation
In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain.
See Preorder and Binary relation
Category (mathematics)
In mathematics, a category (sometimes called an abstract category to distinguish it from a concrete category) is a collection of "objects" that are linked by "arrows".
See Preorder and Category (mathematics)
Category of preordered sets
In mathematics, the category Ord has preordered sets as objects and order-preserving functions as morphisms.
See Preorder and Category of preordered sets
Class (set theory)
In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share.
See Preorder and Class (set theory)
Commutative ring
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative.
See Preorder and Commutative ring
Complement (set theory)
In set theory, the complement of a set, often denoted by A^\complement, is the set of elements not in.
See Preorder and Complement (set theory)
Composition of relations
In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations R and S. In the calculus of relations, the composition of relations is called relative multiplication, and its result is called a relative product.
See Preorder and Composition of relations
Connected relation
In mathematics, a relation on a set is called connected or complete or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements. Preorder and connected relation are properties of binary relations.
See Preorder and Connected relation
Consistency
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction.
Converse relation
In mathematics, the converse of a binary relation is the relation that occurs when the order of the elements is switched in the relation.
See Preorder and Converse relation
Cycle (graph theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal.
See Preorder and Cycle (graph theory)
Directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles.
See Preorder and Directed acyclic graph
Directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
See Preorder and Directed graph
Directed set
In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has an upper bound. Preorder and directed set are order theory.
Division (mathematics)
Division is one of the four basic operations of arithmetic.
See Preorder and Division (mathematics)
Embedding
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. Preorder and embedding are order theory.
Encompassment ordering
In theoretical computer science, in particular in automated theorem proving and term rewriting, the containment, or encompassment, preorder (≤) on the set of terms, is defined by It is used e.g. in the Knuth–Bendix completion algorithm. Preorder and encompassment ordering are order theory.
See Preorder and Encompassment ordering
Enriched category
In category theory, a branch of mathematics, an enriched category generalizes the idea of a category by replacing hom-sets with objects from a general monoidal category.
See Preorder and Enriched category
Equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes.
See Preorder and Equivalence class
Equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive.
See Preorder and Equivalence relation
Finite topological space
In mathematics, a finite topological space is a topological space for which the underlying point set is finite.
See Preorder and Finite topological space
Forcing (mathematics)
In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results.
See Preorder and Forcing (mathematics)
Graph minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges, vertices and by contracting edges.
Greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
See Preorder and Greatest common divisor
Independence (mathematical logic)
In mathematical logic, independence is the unprovability of a sentence from other sentences.
See Preorder and Independence (mathematical logic)
Injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies.
See Preorder and Injective function
Interior algebra
In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set.
See Preorder and Interior algebra
Interval (mathematics)
In mathematics, a (real) interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Preorder and interval (mathematics) are order theory.
See Preorder and Interval (mathematics)
Kripke semantics
Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke and André Joyal.
See Preorder and Kripke semantics
Least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by, is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.
See Preorder and Least common multiple
Lindenbaum–Tarski algebra
In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a logical theory T consists of the equivalence classes of sentences of the theory (i.e., the quotient, under the equivalence relation ~ defined such that p ~ q exactly when p and q are provably equivalent in T).
See Preorder and Lindenbaum–Tarski algebra
Logical conjunction
In logic, mathematics and linguistics, and (\wedge) is the truth-functional operator of conjunction or logical conjunction.
See Preorder and Logical conjunction
Logical equivalence
In logic and mathematics, statements p and q are said to be logically equivalent if they have the same truth value in every model.
See Preorder and Logical equivalence
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether an instance is in L_2) using a computable function.
See Preorder and Many-one reduction
Mathematics
Mathematics is a field of study that discovers and organizes abstract objects, methods, theories and theorems that are developed and proved for the needs of empirical sciences and mathematics itself.
Modal logic
Modal logic is a kind of logic used to represent statements about necessity and possibility.
Modus ponens
In propositional logic, modus ponens (MP), also known as modus ponendo ponens, implication elimination, or affirming the antecedent, is a deductive argument form and rule of inference.
Morphism
In mathematics, a morphism is a concept of category theory that generalizes structure-preserving maps such as homomorphism between algebraic structures, functions from a set to another set, and continuous functions between topological spaces.
Neighbourhood (mathematics)
In topology and related areas of mathematics, a neighbourhood (or neighborhood) is one of the basic concepts in a topological space.
See Preorder and Neighbourhood (mathematics)
Net (mathematics)
In mathematics, more specifically in general topology and related branches, a net or Moore–Smith sequence is a function whose domain is a directed set.
See Preorder and Net (mathematics)
Order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations.
Partially ordered set
In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. Preorder and Partially ordered set are order theory.
See Preorder and Partially ordered set
Path (graph theory)
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges).
See Preorder and Path (graph theory)
Permutation
In mathematics, a permutation of a set can mean one of two different things.
Polynomial
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer powers, and has a finite number of terms.
Polynomial-time reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another.
See Preorder and Polynomial-time reduction
Posetal category
In mathematics, specifically category theory, a posetal category, or thin category, is a category whose homsets each contain at most one morphism.
See Preorder and Posetal category
Preference
In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between alternatives.
Preordered class
In mathematics, a preordered class is a class equipped with a preorder. Preorder and preordered class are order theory.
See Preorder and Preordered class
Prewellordering
In set theory, a prewellordering on a set X is a preorder \leq on X (a transitive and reflexive relation on X) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation x defined by x \leq y \text y \nleq x is a well-founded relation. Preorder and prewellordering are order theory.
See Preorder and Prewellordering
Propositional calculus
The propositional calculus is a branch of logic.
See Preorder and Propositional calculus
Reachability
In graph theory, reachability refers to the ability to get from one vertex to another within a graph.
Reflexive closure
In mathematics, the reflexive closure of a binary relation R on a set X is the smallest reflexive relation on X that contains R. A relation is called if it relates every element of X to itself.
See Preorder and Reflexive closure
Reflexive relation
In mathematics, a binary relation R on a set X is reflexive if it relates every element of X to itself. Preorder and reflexive relation are properties of binary relations.
See Preorder and Reflexive relation
Ring homomorphism
In mathematics, a ring homomorphism is a structure-preserving function between two rings.
See Preorder and Ring homomorphism
Sentence (mathematical logic)
In mathematical logic, a sentence (or closed formula) of a predicate logic is a Boolean-valued well-formed formula with no free variables.
See Preorder and Sentence (mathematical logic)
Set (mathematics)
In mathematics, a set is a collection of different things; these things are called elements or members of the set and are typically mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets.
See Preorder and Set (mathematics)
Set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects.
Simulation (computer science)
In theoretical computer science a simulation is a relation between state transition systems associating systems that behave in the same way in the sense that one system simulates the other.
See Preorder and Simulation (computer science)
Specialization (pre)order
In the branch of mathematics known as topology, the specialization (or canonical) preorder is a natural preorder on the set of the points of a topological space. Preorder and specialization (pre)order are order theory.
See Preorder and Specialization (pre)order
Substitution (logic)
A substitution is a syntactic transformation on formal expressions.
See Preorder and Substitution (logic)
Subtyping
In programming language theory, subtyping (also called subtype polymorphism or inclusion polymorphism) is a form of type polymorphism.
Surjective function
In mathematics, a surjective function (also known as surjection, or onto function) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that.
See Preorder and Surjective function
Symmetric relation
A symmetric relation is a type of binary relation. Preorder and symmetric relation are properties of binary relations.
See Preorder and Symmetric relation
Term (logic)
In mathematical logic, a term denotes a mathematical object while a formula denotes a mathematical fact.
Theory (mathematical logic)
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language.
See Preorder and Theory (mathematical logic)
Theta-subsumption
Theta-subsumption (θ-subsumption, or just subsumption) is a decidable relation between two first-order clauses that guarantees that one clause logically entails the other.
See Preorder and Theta-subsumption
Topology
Topology (from the Greek words, and) is the branch of mathematics concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing holes, opening holes, tearing, gluing, or passing through itself.
Total order
In mathematics, a total order or linear order is a partial order in which any two elements are comparable. Preorder and total order are order theory and properties of binary relations.
Transitive closure
In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive.
See Preorder and Transitive closure
Transitive relation
In mathematics, a binary relation on a set is transitive if, for all elements,, in, whenever relates to and to, then also relates to.
See Preorder and Transitive relation
Turing reduction
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987).
See Preorder and Turing reduction
Upper and lower bounds
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of. Preorder and upper and lower bounds are order theory.
See Preorder and Upper and lower bounds
Weak ordering
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Preorder and weak ordering are order theory and properties of binary relations.
See Preorder and Weak ordering
Well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set X is a quasi-ordering of X for which every infinite sequence of elements x_0, x_1, x_2, \ldots from X contains an increasing pair x_i \leq x_j with i. Preorder and well-quasi-ordering are order theory.
See Preorder and Well-quasi-ordering
Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox.
See Preorder and Zermelo–Fraenkel set theory
See also
Properties of binary relations
- Antisymmetric relation
- Asymmetric relation
- Connected relation
- Dense order
- Dependency relation
- Euclidean relation
- Homogeneous relation
- Idempotent relation
- Intransitivity
- Law of trichotomy
- Partial function
- Preorder
- Quasitransitive relation
- Reflexive relation
- Semiorder
- Serial relation
- Series-parallel partial order
- Symmetric relation
- Total order
- Total relation
- Weak ordering
- Wellfoundedness
References
Also known as Precongruence, Preorder (mathematics), Preordered set, Quasi order, Quasi-order, Quasi-ordering, Quasiorder, Strict preorder.