Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        STUDIA        

relacja częściowego porządku



  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
1 odpowiedź w tym temacie

#1 Informatyk

Informatyk

    Nowicjusz

  • Użytkownik
  • 1 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 02.02.2014 - 17:40

Pokaż, że jeśli R i S są relacjami częściowo porządkującymi, to R ∊ S
też jest relacją częściowo porządkującą. Czy wtedy R ∪ S też jest relacją
częściowo porządkującą?

Ktoś potrafi pomóc? 


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 02.02.2014 - 20:32

Trzeba pokazać, że R\cap S jest relacją częściowo porządkującą, a więc jest zwrotna, przechodnia i antysymetryczna.

 

  1. Skoro R i S są zwrotne, to \forall_x (x,x)\in R i (x,x)\in S więc (x,x)\in (R\cap S)
  2. Jeśli (x,y)\in (R\cap S) i (y,z)\in (R\cap S) to w szczególności obydwie pary należą do R i do S. Ponieważ obydwie relacje są przechodnie, to (x,z)\in R i (x,z)\in S. W takim razie (x,z)\in(R\cap S)
  3. Załóżmy, że (x,y)\in(R\cap S) i (y,x)\in(R\cap S). W szczególności (x,y)\in R i (y,x)\in R a więc x=y

Czemu suma nie zawsze będzie relacją częściowego porządku? Jako przykład można wziąć relacje na zbiorze liczb naturalnych: (x,y)\in R gdy x\leq y oraz (x,y)\in S gdy x\geq y. Dla dowolnych liczb x<y mamy (x,y)\in R oraz (y,x)\in S. Stąd obydwie pary należą do R\cup S ale x\neq y. Suma tych relacji nie jest więc antysymetryczna. 


  • 0