|
Preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive relation, reflexive and Transitive relation, transitive. The name is meant to suggest that preorders are ''almost'' partial orders, but not quite, as they are not necessarily Antisymmetric relation, antisymmetric. A natural example of a preorder is the Divisor#Definition, divides relation "x divides y" between integers, polynomials, or elements of a commutative ring. For example, the divides relation is reflexive as every integer divides itself. But the divides relation is not antisymmetric, because 1 divides -1 and -1 divides 1. It is to this preorder that "greatest" and "lowest" refer in the phrases "greatest common divisor" and "lowest common multiple" (except that, for integers, the greatest common divisor is also the greatest for the natural order of the integers). Preorders are closely related to equivalence relations and (non-strict) partial orders. Both of th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Directed Set
In mathematics, a directed set (or a directed preorder or a filtered set) is a preordered set in which every finite subset has an upper bound. In other words, it is a non-empty preordered set A such that for any a and b in A there exists c in A with a \leq c and b \leq c. A directed set's preorder is called a direction. The notion defined above is sometimes called an . A is defined symmetrically, meaning that every finite subset has a lower bound. Some authors (and this article) assume that a directed set is directed upward, unless otherwise stated. Other authors call a set directed if and only if it is directed both upward and downward. Directed sets are a generalization of nonempty totally ordered sets. That is, all totally ordered sets are directed sets (contrast Partially ordered sets, ordered sets, which need not be directed). Join-semilattices (which are partially ordered sets) are directed sets as well, but not conversely. Likewise, Lattice (order), lattices are directed s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Transitive Relation
In mathematics, a binary relation on a set (mathematics), set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Every partial order and every equivalence relation is transitive. For example, less than and equality (mathematics), equality among real numbers are both transitive: If and then ; and if and then . Definition A homogeneous relation on the set is a ''transitive relation'' if, :for all , if and , then . Or in terms of first-order logic: :\forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc, where is the infix notation for . Examples As a non-mathematical example, the relation "is an ancestor of" is transitive. For example, if Amy is an ancestor of Becky, and Becky is an ancestor of Carrie, then Amy is also an ancestor of Carrie. On the other hand, "is the birth mother of" is not a transitive relation, because if Alice is the birth mother of Brenda, and Brenda is the birth mother of Claire, then it does ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Order Theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary. Background and motivation Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.g. "2 is less than 3", "10 is greater than 5", or "Does Tom have fewer cookies than Sally?". This intuitive concept can be extended to orders on other sets of numbers, such as the integers and the reals. The idea of being greater than or less than another number is one of the basic intuitions of number systems in general (although one usually is also interested in the actual difference of two numbers, which is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Binary Relation
In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs (x, y), where x is an element of X and y is an element of Y. It encodes the common concept of relation: an element x is ''related'' to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. An example of a binary relation is the "divides" relation over the set of prime numbers \mathbb and the set of integers \mathbb, in which each prime p is related to each integer z that is a Divisibility, multiple of p, but not to an integer that is not a Multiple (mathematics), multiple of p. In this relation, for instance, the prime number 2 is related to numbers such as -4, 0, 6, 10, but not to 1 or 9, just as the prime number 3 is related to 0, 6, and 9, but not to 4 or 13. Binary relations ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Partial Order
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. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable. Formally, a partial order is a homogeneous binary relation that is reflexive, antisymmetric, and transitive. A partially ordered set (poset for short) is an ordered pair P=(X,\leq) consisting of a set X (called the ''ground set'' of P) and a partial order \leq on X. When the meaning is clear from context and there is no ambiguity about the partial order, the set X itself is sometimes called a poset. Partial order relations The term ''partial order'' usually refers to the reflexive partial order relations, referred to in this article as ''non-strict'' partial orders. However som ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Equivalence Relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number a is equal to itself (reflexive). If a = b, then b = a (symmetric). If a = b and b = c, then a = c (transitive). Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other if and only if they belong to the same equivalence class. Notation Various notations are used in the literature to denote that two elements a and b of a set are equivalent with respect to an equivalence relation R; the most common are "a \sim b" and "", which are used when R is implicit, and variations of "a \sim_R b", "", or "" to specify R explicitly. Non-equivalence may be written "" or "a \not\equiv b". Definitions A binary relation \,\si ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if X and Y are sets and L \subseteq X \times Y is a relation from X to Y, then L^ is the relation defined so that yL^x if and only if xLy. In set-builder notation, :L^ = \. Since a relation may be represented by a logical matrix, and the logical matrix of the converse relation is the transpose of the original, the converse relation is also called the transpose relation. It has also been called the opposite or dual of the original relation, the inverse of the original relation,Gerard O'Regan (2016): ''Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications'' or the reciprocal L^ of the relation L. Other notations for the converse relation include L^, L^, \breve, L^, or L^. The notati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greatest Common Divisor
In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest common divisor of and is denoted \gcd (x,y). For example, the GCD of 8 and 12 is 4, that is, . In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include highest common factor, etc. Historically, other names for the same concept have included greatest common measure. This notion can be extended to polynomials (see ''Polynomial greatest common divisor'') and other commutative rings (see ' below). Overview Definition The ''greatest common divisor'' (GCD) of integers and , at least one of which is nonzero, is the greatest positive integer such that is a divisor of both and ; that is, there are integers and such that ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
One-to-one Correspondence
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivalently, a bijection is a relation between two sets such that each element of either set is paired with exactly one element of the other set. A function is bijective if it is invertible; that is, a function f:X\to Y is bijective if and only if there is a function g:Y\to X, the ''inverse'' of , such that each of the two ways for composing the two functions produces an identity function: g(f(x)) = x for each x in X and f(g(y)) = y for each y in Y. For example, the ''multiplication by two'' defines a bijection from the integers to the even numbers, which has the ''division by two'' as its inverse function. A function is bijective if and only if it is both injective (or ''one-to-one'')—meaning that each element in the codomain is mapped f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theory (mathematical Logic)
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduction rules. An element \phi\in T of a deductively closed theory T is then called a theorem of the theory. In many deductive systems there is usually a subset \Sigma \subseteq T that is called "the set of axioms" of the theory T, in which case the deductive system is also called an " axiomatic system". By definition, every axiom is automatically a theorem. A first-order theory is a set of first-order sentences (theorems) recursively obtained by the inference rules of the system applied to the set of axioms. General theories (as expressed in formal language) When defining theories for foundational purposes, additional care must be taken, as normal set-theoretic language may not be appropriate. The construction of a theory begins ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sentence (mathematical Logic)
In mathematical logic, a sentence (or closed formula)Edgar Morscher, "Logical Truth and Logical Form", ''Grazer Philosophische Studien'' 82(1), pp. 77–90. of a predicate logic is a Boolean-valued well-formed formula with no free variables. A sentence can be viewed as expressing a proposition, something that ''must'' be true or false. The restriction of having no free variables is needed to make sure that sentences can have concrete, fixed truth values: as the free variables of a (general) formula can range over several values, the truth value of such a formula may vary. Sentences without any logical connectives or quantifiers in them are known as atomic sentences; by analogy to atomic formula. Sentences are then built up out of atomic sentences by applying connectives and quantifiers. A set of sentences is called a theory; thus, individual sentences may be called theorems. To properly evaluate the truth (or falsehood) of a sentence, one must make reference to an interpr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
