29.2. Leképezések fixpontja

29.2.1.Parciális rendezés, irányított halmaz

29.12. Definíció (Parciális rendezés).

Legyen egy halmaz, pedig a halmaz felett értelmezett bináris reláció. Ha a reláció reflexív, tranzitív és antiszimmetrikus, akkor parciális rendezésnek nevezzük.

A elemet legkisebb elemnek nevezzük, ha . Ha létezik legkisebb elem, akkor az egyértelmű. Legyen . az felső korlátja, ha . Ha az halmaznak létezik legkisebb felső korlátja, akkor az egyértelmű. az alsó korlátja, ha . Ha az halmaznak létezik legnagyobb alsó korlátja, akkor az egyértelmű.

29.2.2.Teljes hálók

A rendezett párt teljes hálónak nevezzük, ha a reláció parciális rendezés a felett és bármely részhalmazának van legkisebb felső és legnagyobb alsó korlátja -ben.

Egy alaphalmaz hatványhalmaza teljes háló a relációra nézve. Az alaphalmaz felett definiált logikai függvényekre is kiterjeszthető a parciális rendezés:

29.13. Definíció (Parciális rendezés logikai függvények felett).

Legyen . pontosan akkor, ha , ahol a logikai függvény igazsághalmaza (. def.).

29.4. Megjegyzés (Parciális rendezés logikai relációk felett).

A . def. kiterjeszthető logikai relációkra is, ebben az esetben a definiált reláció preorder, amely egy parciális rendezést generál [[???Hen 88]] .

29.2.3.Monoton leképezések tulajdonságai, fixpontok

Az függvény monoton, ha . A továbbiakban és jelöljenek monoton függvényeket: .

-et az leképezés fixpontjának nevezzük, ha .

29.1. Tétel.

Teljes háló felett minden monoton függvénynek van legkisebb és legnagyobb fixpontja [[???Par 79]].

  • legkisebb fixpontja , (röviden: ),

  • fixpont indukció legkisebb fixpontra: ha , akkor ,

  • ,

  • legnagyobb fixpontja: , (röviden: ),

  • fixpont indukció legnagyobb fixpontra: ha , akkor ,

  • .