Critical pair (order theory)

Critical pair (order theory): In order theory, a discipline within mathematics, a critical pair is a pair of elements in a partially ordered set that are incomparable but that could be made comparable without changing the order relationships of any other pairs of elements.

Formally, let $P = (S, \leq)$ be a partially ordered set. Then a critical pair is an ordered pair $(x, y)$ of elements of $S$ with the following three properties:

$x$ and $y$ are incomparable in $P$ ,

for every $z$ in $S$ , if $z < x$ then $z < y$ , and

for every $z$ in $S$ , if $y < z$ then $x < z$ .

If $(x, y)$ is a critical pair then the binary relation obtained from $P$ by adding the single order relation $x \leq y$ is also a partially ordered set. The required properties of a critical pair ensure that, when the relation $x \leq y$ is added, the addition does not cause any violations of the transitive property.

A set $R$ of linear extensions of $P$ is said to "reverse every critical pair" if, for every critical pair $(x, y)$ of $P$ , there exists a linear extension in $R$ for which $y$ occurs earlier than $x$ . This property may be used to characterize realizers of partial orders: A nonempty set $R$ of linear extensions is a realizer if and only if it reverses every critical pair.

References

Trotter, W. T. (1992), Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins Series in Mathematical Sciences, Baltimore: Johns Hopkins Univ. Press .

Categories:
Order theory

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

Critical pair — A critical pair may refer to: Critical pair (logic), terms resulting from two overlapping rules in a term rewriting system Critical pair (order theory), two incomparable elements in a partial order that have the same order relation to all other… … Wikipedia
Critical thinking — is the process or method of thinking that questions assumptions. It is a way of deciding whether a claim is true, false, or sometimes true and sometimes false, or partly true and partly false. The origins of critical thinking can be traced in… … Wikipedia
Theory (mathematical logic) — This article is about theories in a formal language, as studied in mathematical logic. For other uses, see Theory (disambiguation). In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. Usually… … Wikipedia
Order (mathematics) — Contents 1 In algebra 2 In arithmetic 3 In analysis 4 … Wikipedia
Order dimension — A partial order of dimension 4 (shown as a Hasse diagram) and four total orderings that form a realizer for this partial order. In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the… … Wikipedia
First-order logic — is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic (a less… … Wikipedia
Ordered pair — In mathematics, an ordered pair (a, b) is a pair of mathematical objects. In the ordered pair (a, b), the object a is called the first entry, and the object b the second entry of the pair. Alternatively, the objects are called the first and… … Wikipedia
String theory — This article is about the branch of theoretical physics. For other uses, see String theory (disambiguation). String theory … Wikipedia
Constructive set theory — is an approach to mathematical constructivism following the program of axiomatic set theory. That is, it uses the usual first order language of classical set theory, and although of course the logic is constructive, there is no explicit use of… … Wikipedia
Model theory — This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields,… … Wikipedia

Academic Dictionaries and Encyclopedias

Critical pair (order theory)

References

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Critical pair (order theory)

References

Look at other dictionaries:

Share the article and excerpts

Direct link