well quasi ordering

Let $Q$ be a set and $\\precsim$ a quasi-order on $Q$ . Aninfinite sequence in $Q$ is referred to as bad if forall $i<j\\in{\\mathbf{N}}$ , $a_{i}\ot\\precsim a_{j}$ holds; otherwise it is calledgood. Note that an antichain is obviously a bad sequence.

A quasi-ordering $\\precsim$ on $Q$ is a well-quasi-ordering (wqo) if for every infinite sequence is good. Every well-ordering is a well-quasi-ordering.

The following proposition gives equivalent definitions forwell-quasi-ordering:

Proposition 1.

Given a set $Q$ and a binary relation $\\precsim$ over $Q$ , thefollowing conditions are equivalent:

•
$(Q,\\precsim)$ is a well-quasi-ordering;
•
$(Q,\\precsim)$ has no infinite ( $\\omega$ -) strictly decreasing chainsand no infinite antichains.
•
Every linear extension of $Q/_{\\approx}$ is a well-order, where $\\approx$ is the equivalence relation and $Q/_{\\approx}$ is the set of equivalence classes induced by $\\approx$ .
•
Any infinite ( $\\omega$ -) $Q$ -sequence contains anincreasing chain.

The equivalence of WQO to the second and the fourth conditions is proved by the infinite version of Ramsey’s theorem.

单词	WellQuasiOrdering
释义	well quasi ordering Let $Q$ be a set and $\\precsim$ a quasi-order on $Q$ . Aninfinite sequence in $Q$ is referred to as bad if forall $i<j\\in{\\mathbf{N}}$ , $a_{i}\ot\\precsim a_{j}$ holds; otherwise it is calledgood. Note that an antichain is obviously a bad sequence. A quasi-ordering $\\precsim$ on $Q$ is a well-quasi-ordering (wqo) if for every infinite sequence is good. Every well-ordering is a well-quasi-ordering. The following proposition gives equivalent definitions forwell-quasi-ordering: Proposition 1. Given a set $Q$ and a binary relation $\\precsim$ over $Q$ , thefollowing conditions are equivalent: • $(Q,\\precsim)$ is a well-quasi-ordering; • $(Q,\\precsim)$ has no infinite ( $\\omega$ -) strictly decreasing chainsand no infinite antichains. • Every linear extension of $Q/_{\\approx}$ is a well-order, where $\\approx$ is the equivalence relation and $Q/_{\\approx}$ is the set of equivalence classes induced by $\\approx$ . • Any infinite ( $\\omega$ -) $Q$ -sequence contains anincreasing chain. The equivalence of WQO to the second and the fourth conditions is proved by the infinite version of Ramsey’s theorem.
随便看	residue systems ResolventFunctionIsAnalytic resolvent function is analytic ResolventMatrix resolvent matrix RestrictedDirectProduct restricted direct product RestrictedDirectProductOfAlgebraicSystems restricted direct product of algebraic systems RestrictedDivisorsOfTheFirst1000PositiveIntegers restricted divisors of the first 1000 positive integers RestrictedHomomorphism restricted homomorphism RestrictedLieAlgebra restricted Lie algebra RestrictionOfAContinuousMappingIsContinuous restriction of a continuous mapping is continuous RestrictionOfAFunction restriction of a function RestrictionRepresentation restriction representation Resultant resultant ResultantalternativeTreatment resultant (alternative treatment)