Substitutionen: Ordnung

Substitution σ₁ ist allgemeiner als Substitution σ₂:

σ₁$\raisebox{-8pt}[0pt][0pt]{$\stackrel{\displaystyle <}{\sim}$}$σ₂$\iff$∃τ : σ₁oτ = σ₂

Beispiele:

• {X $\mapsto$ Y}$\raisebox{-8pt}[0pt][0pt]{$\stackrel{\displaystyle <}{\sim}$}${X $\mapsto$ a, Y $\mapsto$ a},
• {X $\mapsto$ Y}$\raisebox{-8pt}[0pt][0pt]{$\stackrel{\displaystyle <}{\sim}$}${Y $\mapsto$ X},
• {Y $\mapsto$ X}$\raisebox{-8pt}[0pt][0pt]{$\stackrel{\displaystyle <}{\sim}$}${X $\mapsto$ Y}.

Eigenschaften

• Relation $\raisebox{-8pt}[0pt][0pt]{$\stackrel{\displaystyle <}{\sim}$}$ ist Prä-Ordnung (..., ..., aber nicht ...)
• Die durch $\raisebox{-8pt}[0pt][0pt]{$\stackrel{\displaystyle <}{\sim}$}$ erzeugte Äquivalenzrelation ist die ...