Uspořádání dvojic

Úloha číslo: 3405

Které z následujících relací na množině \({\Bbb N}^2\) (dvojice přirozených čísel) jsou uspořádáními? Která z těchto uspořádání jsou lineární?

  • Varianta

    Porovnání po obou souřadnicích \(\le_S\):

    \((a,b)\le_S(x,y) \Leftrightarrow a\le x \wedge b\le y\)

  • Varianta

    Porovnání v alespoň jedné souřadnici \(\le_U\):

    \((a,b)\le_U(x,y) \Leftrightarrow a\le x \vee b\le y\)

  • Varianta

    Porovnání v obou složkách různými směry \(\le_Z\):

    \((a,b)\le_Z(x,y) \Leftrightarrow a\le x \wedge b\ge y\)

  • Varianta

    Slovníkové (lexikografické) porovnání \(\le_L\):

    \((a,b)\le_L(x,y) \Leftrightarrow a<x \vee (a=x \wedge b\le y)\)

  • Varianta

    Slovníkovo-maximové porovnání \(\le_M\):

    \((a,b)\le_M(x,y) \Leftrightarrow \max(a,b) < \max(x,y) \vee (a,b)\le_L(x,y)\)

  • Varianta

    Maximové porovnání s tím, že nerozhodné případy se porovnají lexikograficky \(\le_N\):

    \((a,b)\le_N(x,y) \Leftrightarrow \max(a,b) < \max(x,y) \vee [\max(a,b)=\max(x,y) \wedge (a,b)\le_L(x,y)]\)

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze