Opodstatněný vztah - Well-founded relation

v matematika, a binární relace R je nazýván opodstatněný (nebo dobře založený) na třída X pokud každý neprázdný podmnožina S ⊆ X má minimální prvek s ohledem na R, tj živel m nesouvisí s sRm (například, "s není menší než m") pro všechny s ∈ S. Jinými slovy, vztah je opodstatněný, pokud

${ displaystyle ( forall S subseteq X) ; [S neq blankset implikuje ( existuje m in S) ( forall s in S) lnot (sRm)].}$

Někteří autoři zahrnují další podmínku, že R je set-like, tj. že prvky menší než kterýkoli daný prvek tvoří množinu.

Ekvivalentně, za předpokladu, že axiom závislé volby, je vztah opodstatněný, pokud neobsahuje žádné spočítatelné nekonečné sestupné řetězy: to znamená, že neexistuje žádná nekonečná sekvence X₀, X₁, X₂, ... prvků prvku X takhle X_n+1 R X_n pro každé přirozené číslo n.^[1][2]

v teorie objednávek, a částečná objednávka se nazývá opodstatněný, pokud odpovídající přísný řád je opodstatněný vztah. Pokud je objednávka a celková objednávka pak se nazývá a pořádek.

v teorie množin, sada X se nazývá a fundovaná sada pokud nastavit členství vztah je opodstatněný na přechodné uzavření z X. The axiom pravidelnosti, což je jeden z axiomů Teorie množin Zermelo – Fraenkel, tvrdí, že všechny sady jsou opodstatněné.

Vztah R je konverzovat opodstatněné, vzhůru opodstatněné nebo Noetherian na X, pokud konverzní vztah R⁻¹ je opodstatněný dne X. V tomto případě R je také řekl, aby uspokojil vzestupný stav řetězu. V kontextu přepis systémech, také se nazývá noetherianský vztah ukončení.

Indukce a rekurze

Důležitým důvodem, proč jsou zajímavé fundované vztahy, je verze verze transfinitní indukce lze na ně použít: pokud (X, R) je opodstatněný vztah, P(X) je nějaká vlastnost prvků Xa chceme to ukázat

P(X) platí pro všechny prvky X z X,

stačí ukázat, že:

Li X je prvek X a P(y) platí pro všechny y takhle y R x, pak P(X) musí být také pravda.

To znamená

${ displaystyle ( forall x in X) ; [( forall y in X) ; [yRx implikuje P (y)] implikuje P (x)] quad { text {implikuje}} quad ( forall x in X) , P (x).}$

Opodstatněná indukce se někdy nazývá noetherovská indukce,^[3] po Emmy Noetherová.

Stejně jako indukce podporují dobře založené vztahy také konstrukci objektů pomocí transfinitní rekurze. Nechť (X, R) být a set-like opodstatněný vztah a F funkce, která přiřadí objekt F(X, G) ke každému páru prvku X ∈ X a funkce G na počáteční segment {y: y R X} z X. Pak existuje jedinečná funkce G tak, že pro každého X ∈ X,

${ displaystyle G (x) = F left (x, G vert _ { left {y: , yRx right }} right).}$

To znamená, pokud chceme postavit funkci G na X, můžeme definovat G(X) pomocí hodnot z G(y) pro y R x.

Jako příklad zvažte dobře založený vztah (N, S), kde N je množina všech přirozená čísla, a S je graf nástupnické funkce X ↦ X+1. Poté zapněte indukci S je obvyklé matematická indukce a rekurze na S dává primitivní rekurze. Pokud vezmeme v úvahu vztah objednávky (N, <), získáváme úplná indukce, a rekurze hodnotových průběhů. Prohlášení, že (N, <) je opodstatněný, je také známý jako princip objednávání.

Existují další zajímavé speciální případy opodstatněné indukce. Když je opodstatněným vztahem obvyklé uspořádání ve třídě všech řadové číslovky se nazývá technika transfinitní indukce. Když je dobře podložená sada sada rekurzivně definovaných datových struktur, nazývá se technika strukturální indukce. Když je v fundovaném vztahu nastaveno členství v univerzální třídě, je tato technika známá jako ∈-indukce. V těchto článcích najdete další podrobnosti.

Příklady

Mezi opodstatněné vztahy, které nejsou zcela uspořádány, patří:

• pozitivní celá čísla {1, 2, 3, ...}, v pořadí definovaném A < b kdyby a jen kdyby A rozděluje b a A ≠ b.
• množina všech konečných struny přes pevnou abecedu v pořadí definovaném symbolem s < t kdyby a jen kdyby s je správný podřetězec t.
• sada N × N z páry z přirozená čísla, objednáno někým (n₁, n₂) < (m₁, m₂) právě tehdy n₁ < m₁ a n₂ < m₂.
• soubor všech regulární výrazy přes pevnou abecedu v pořadí definovaném symbolem s < t kdyby a jen kdyby s je správný podvýraz t.
• libovolná třída, jejíž prvky jsou sady, s relací ${ displaystyle in}$ („je prvek“). To je axiom pravidelnosti.
• uzly jakékoli konečné směrovaný acyklický graf, se vztahem R definované tak, že a R b právě tehdy, pokud existuje hrana z A na b.

Mezi příklady neopodstatněných vztahů patří:

• záporná celá čísla {−1, −2, −3,…} v obvyklém pořadí, protože libovolná neomezená podmnožina nemá nejmenší prvek.
• Sada řetězců přes konečnou abecedu s více než jedním prvkem, za obvyklých (lexikografický ) pořadí, protože posloupnost „B“> „AB“> „AAB“> „AAAB“>… je nekonečný sestupný řetězec. Tento vztah není opodstatněný, přestože celá sada má minimální prvek, konkrétně prázdný řetězec.
• the racionální čísla (nebo realita ) podle standardního uspořádání, protože například množině kladných racionálních (nebo skutečných) chybí minimum.

Další vlastnosti

Pokud (X, <) je opodstatněný vztah a X je prvek X, potom sestupné řetězy začínající na X jsou všechny konečné, ale to neznamená, že jejich délky jsou nutně ohraničené. Zvažte následující příklad: Let X být spojením kladných celých čísel a nového prvku ω, který je větší než jakékoli celé číslo. Pak X je dobře podložená množina, ale existují sestupné řetězce začínající na ω libovolné velké (konečné) délky; řetěz ω, n − 1, n - 2, ..., 2, 1 má délku n pro všechny n.

The Mostowského kolapsové lemma znamená, že členství v sadě je univerzální mezi extenzivními fundovanými vztahy: pro jakýkoli set-like fundovaný vztah R ve třídě X který je rozšiřující, existuje třída C takový, že (X, R) je izomorfní s (C, ∈).

Reflexivita

Vztah R se říká, že je reflexní -li ARA platí pro každého A v oblasti vztahu. Každý reflexivní vztah na neprázdné doméně má nekonečné sestupné řetězce, protože jakákoli konstantní sekvence je sestupným řetězcem. Například v přirozených číslech s jejich obvyklým řádem ≤ máme ${ displaystyle 1 geq 1 geq 1 geq cdots.}$ Abychom se vyhnuli těmto triviálním sestupným sekvencím, je při práci s částečným řádem ≤ běžné aplikovat definici opodstatněnosti (možná implicitně) na alternativní vztah A < b kdyby a jen kdyby A ≤ b a A ≠ b. Obecněji řečeno, při práci s a předobjednávka ≤, je běžné používat relaci A < b kdyby a jen kdyby A ≤ b a b ≰ A. V kontextu přirozených čísel to znamená, že se použije relace <, která je opodstatněná, namísto relace ≤, což není. V některých textech se definice opodstatněného vztahu mění z definice výše, aby zahrnovala tyto konvence.

Reference

• Just, Winfried a Weese, Martin (1998) Objevování moderní teorie množin. Já, Americká matematická společnost ISBN  0-8218-0266-6.
• Karel Hrbáček & Thomas Jech (1999) Úvod do teorie množin, 3. vydání, „Opodstatněné vztahy“, strany 251–5, Marcel Dekker ISBN  0-8247-7915-0