Post has attachment

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. (Some authors use the term "antichain" to mean strong antichain, a subset such that there is no element of the poset smaller than two distinct elements of the antichain.)

Let S be a partially ordered set. We say two elements a and b of a partially ordered set are comparable if a ≤ b or b ≤ a. If two elements are not comparable, we say they are incomparable; that is, x and y are incomparable if neither x ≤ y nor y ≤ x.

A chain in S is a subset C of S in which each pair of elements is comparable; that is, C is totally ordered. An antichain in S is a subset A of S in which each pair of different elements is incomparable; that is, there is no order relation between any two different elements in A.

Height and width
A maximal antichain is an antichain that is not a proper subset of any other antichain. A maximum antichain is an antichain that has cardinality at least as large as every other antichain. The width of a partially ordered set is the cardinality of a maximum antichain. Any antichain can intersect any chain in at most one element, so, if we can partition the elements of an order into k chains then the width of the order must be at most k (if the antichain has more than "k" elements, by the Pigeonhole Principle, there would be 2 of its elements belonging to the same chain, contradiction). Dilworth's theorem states that this bound can always be reached: there always exists an antichain, and a partition of the elements into chains, such that the number of chains equals the number of elements in the antichain, which must therefore also equal the width. Similarly, we can define the height of a partial order to be the maximum cardinality of a chain. Mirsky's theorem states similarly that in any partial order of finite height, the height equals the smallest number of antichains into which the order may be partitioned.

Post has attachment

Post has attachment

Post has attachment
This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

completeness properties of partial orders
distributivity laws of order theory
preservation properties of functions between posets.

In the following, partial orders will usually just be denoted by their carrier sets. As long as the intended meaning is clear from the context, ≤ will suffice to denote the corresponding relational symbol, even without prior introduction. Furthermore, < will denote the strict order induced by ≤.

Post has attachment
Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = A × A. More generally, a binary relation between two sets A and B is a subset of A × B. The terms correspondence, dyadic relation and 2-place relation are synonyms for binary relation.

An example is the "divides" relation between the set of prime numbers P and the set of integers Z, in which every prime p is associated with every integer z that is a multiple of p (but with no integer that is not a multiple of p). In this relation, for instance, the prime 2 is associated with numbers that include −4, 0, 6, 10, but not 1 or 9; and the prime 3 is associated with numbers that include 0, 6, and 9, but not 4 or 13.

Binary relations are used in many branches of mathematics to model concepts like "is greater than", "is equal to", and "divides" in arithmetic, "is congruent to" in geometry, "is adjacent to" in graph theory, "is orthogonal to" in linear algebra and many more. The concept of function is defined as a special kind of binary relation. Binary relations are also heavily used in computer science.

A binary relation is the special case n = 2 of an n-ary relation R ⊆ A1 × … × An, that is, a set of n-tuples where the jth component of each n-tuple is taken from the jth domain Aj of the relation. An example for a ternary relation on Z×Z×Z is " ... lies between ... and ...", containing e.g. the triples (5,2,8), (5,8,2), and (−4,9,−7).

In some systems of axiomatic set theory, relations are extended to classes, which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as Russell's paradox.

Post has attachment

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. Weak orders are a generalization of totally ordered sets (rankings without ties) and are in turn generalized by partially ordered sets and preorders.[1]

There are several common ways of formalizing weak orderings, that are different from each other but cryptomorphic (interconvertable with no loss of information): they may be axiomatized as strict weak orderings (partially ordered sets in which incomparability is a transitive relation), as total preorders (transitive binary relations in which at least one of the two possible relations exists between every pair of elements), or as ordered partitions (partitions of the elements into disjoint subsets, together with a total order on the subsets). In many cases another representation called a preferential arrangement based on a utility function is also possible.

Weak orderings are counted by the ordered Bell numbers. They are used in computer science as part of partition refinement algorithms, and in the C++ Standard Library.[2]

Post has attachment

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity.

A locally finite poset is one in which every closed interval

[a, b] = {x : a ≤ x ≤ b}
is finite.

The members of the incidence algebra are the functions f assigning to each nonempty interval [a, b] a scalar f(a, b), which is taken from the ring of scalars, a commutative ring with unity. On this underlying set one defines addition and scalar multiplication pointwise, and "multiplication" in the incidence algebra is a convolution defined by

{\displaystyle (f*g)(a,b)=\sum _{a\leq x\leq b}f(a,x)g(x,b).} (f*g)(a,b)=\sum _{{a\leq x\leq b}}f(a,x)g(x,b).
An incidence algebra is finite-dimensional if and only if the underlying poset is finite.

Related concepts[edit]
An incidence algebra is analogous to a group algebra; indeed, both the group algebra and the incidence algebra are special cases of a category algebra, defined analogously; groups and posets being special kinds of categories.

Post has attachment
Wait while more posts are being loaded