Wersja z 18:02, 5 lut 2009 edytuj LaaknorBot (dyskusja \| edycje) 100 453 edycje m robot dodaje: ru:Предпорядок ← poprzednia edycja		Wersja z 17:54, 11 lut 2009 edytuj anuluj edycję Milek80 (dyskusja \| edycje) Redaktorzy 2780 edycji m drobne techniczne, WP:SK następna edycja →
Linia 1: '''Praporządek''' ([[język angielski\|ang.]] ''pre-order''), zwany także quasi-porządkiem (ang. ''quasi-order'') to [[relacja]], która jest [[relacja zwrotna\|zwrotna]] i [[relacja przechodnia\|przechodnia]]. == Przykłady praporządków == * Szczególnym przypadkiem praporządku jest [[częściowy porządek]]. * Każda [[relacja równoważności]] jest praporządkiem. * Niech <math>X=\{a,b,c,d\}\;</math> i niech relacja <math>R \subseteq X \times X</math>, będzie zadana następująco: <math>R=\{(a,b),(a,c),(a,d),(b,d),(c,d),(b,c),(c,b)\}\;</math>. Wówczas <math>R\;</math> jest praporządkiem na <math>X</math> który nie jest porządkiem częściowym. : * Rozważmy zbiór <math>{}^{\mathbb N}{\mathbb N}</math> wszystkich [[Funkcja\|funkcji]] ze zbioru [[Liczby naturalne\|liczb naturalnych]] <math>{\mathbb N}</math> w <math>{\mathbb N}</math>. Określmy relację <math>\~~leq~~leqslant^</math> na <math>{}^{\mathbb N}{\mathbb N}</math> przez : <math>f\~~leq~~leqslant^ g</math> wtedy i tylko wtedy gdy <math>\big(\exists N\in {\mathbb N}\big)\big(\forall n\~~geq~~geqslant N\big)(f(n)\~~leq~~leqslant g(n)\big)</math> : (gdzie <math>\~~leq~~leqslant</math> oznacza naturalny porządek na <math>{\mathbb N}</math>). Wówczas <math>\~~leq~~leqslant^</math> jest praporządkiem ale nie porządkiem częściowym. Rozważmy zbiór <math>[{\mathbb N}]^{\omega}</math> wszystkich nieskończonych [[Podzbiór\|podzbiorów]] zbioru liczb naturalnych <math>{\mathbb N}</math>. Określmy relację <math>\subseteq^</math> na <math>[{\mathbb N}]^{\omega}</math> przez : <math>A\subseteq^ B</math> wtedy i tylko wtedy gdy [[~~Różnica zbiorów\|~~różnica zbiorów]] <math>A\setminus B</math> jest skończona. : Wówczas <math>\subseteq^</math> jest praporządkiem ale nie porządkiem częściowym. == Redukcja do porządków == W niektórych rozważaniach w matematyce (np. w teorii [[forsing]]u) traktujemy praporządki tak jakby były one porządkami częściowymi przez '''utożsamienie''' elementów które ''powinny być'' równe. Formalnie postępuje się w następujący sposób. Przypuśćmy, że <math>(P, \sqsubseteq)</math> jest praporządkiem, tzn. <math>\sqsubseteq</math> jest zwrotną i przechodnią relacją na zbiorze <math>P</math>. Zdefiniujmy relacje binarną <math>\equiv</math> na <math>P</math> przez : <math>p\equiv q</math> wtedy i tylko wtedy gdy <math>p\sqsubseteq q</math> oraz <math>q\sqsubseteq p.</math> Wówczas <math>\equiv</math> jest [[Relacja równoważności\|równoważnością]] na <math>P</math>. Ponadto : jeśli <math>p\equiv p'</math>, <math>q\equiv q'</math> oraz <math>p\sqsubseteq q</math>, to także <math>p'\sqsubseteq q'.</math> Dlatego możemy określić relację binarną <math>\~~leq~~leqslant</math> na [[Klasa abstrakcji\|przestrzeni ilorazowej]] <math>P/\equiv</math> przez : <math>[p]_\equiv \~~leq~~leqslant [q]_\equiv</math> wtedy i tylko wtedy gdy <math>p\sqsubseteq q.</math> Można sprawdzić, że <math>\~~leq~~leqslant</math> jest relacją zwrotną, przechodnią i (słabo) [[Relacja antysymetryczna\|antysymetryczną]], czyli jest to częściowy porządek. == Zobacz też == [[przegląd zagadnień z zakresu matematyki]], * [[częściowy porządek]],

Praporządek: Różnice pomiędzy wersjami