”Wst¸ep do Teorii Mnogości”, rok akademicki 2009/2010

5. Relacje

Zadanie 5.1 Niech relacja R ⊆ R × R. Jaki jest sens geometryczny D( R) i D∗( R)? Jaka jest geometryczna interpretacja nast¸epuj¸acych wÃlasności relacji R:

(a) zwrotności;

(b) przeciwzwrotności;

(c) symetrii;

(d) przeciwsymetrii (asymetrii);

(e) sÃlabej antysymetrii;

(f) przechodniości;

(g) spójności.

Zadanie 5.2 Zbadać wÃlasności zwrotności, przeciwzwrotności, symetrii, przeciwsymetrii,

sÃlabej antysymetrii, przechodniości i spójności dla nast¸epuj¸acych relacji:

(a) R ⊆ R × R, xRy ⇔ x ≤ |y|;

(b) R ⊆ Z × Z, xRy ⇔ 3 |( x − y);

(c) R ⊆ (N \ { 0 })2, xRy ⇔ ( x|y ∧ x 6= y); (d) R ⊆ R2 × R2, ( a, b) R( c, d) ⇔ a = c; (e) R ⊆ N × N, xRy ⇔ y = x 2;

(f) R ⊆ Z × Z, xRy ⇔ |x| + |y| 6= 4;

(g) R ⊆ N × N, xRy ⇔ xy = 10.

Zadanie 5.3 Udowodnić, że jeżeli relacje R i S s¸a zwrotne, to zwrotne s¸a też relacje: R ∪ S, R ∩ S, R− 1 i R ◦ S.

Zadanie 5.4 Sprawdzić, czy jeżeli relacje R i S s¸a spójne, to spójne s¸a też relacje: R ∪ S i R ∩ S.

Zadanie 5.5 Udowodnić, że jeżeli relacje R i S s¸a przechodnie, to przechodnie s¸a też relacje: R ∩ S i R− 1.

Zadanie 5.6 Udowodnić, że dla relacji R, S i T zachodz¸a zwi¸azki: (a) R ◦ ( S ◦ T ) = ( R ◦ S) ◦ T ;

(b) ( R ∪ S) ◦ T = ( R ◦ T ) ∪ ( S ◦ T ).

Zadanie 5.7 Narysować tabelki i grafy nast¸epuj¸acych relacji:

(a) R ⊂ X × X, X = { 1 , 2 , 3 , 4 }, xRy ⇔ 2 |( x + y); (b) R ⊂ X × X, X = { 1 , 2 , . . . , 10 }, xRy ⇔ ( x|y ∧ x 6= y).

Zadanie 5.8 Znaleźć liczb¸e relacji w X × Y , gdzie X = {a, b, c} i Y = { 1 , 2 }.

Zadanie 5.9 Udowodnić, że dla relacji R i S zachodz¸a zwi¸azki:

(a) \R− 1 = ( \R) − 1;

(b) ( R ◦ S) − 1 = S− 1 ◦ R− 1;

(c) R ⊆ S ⇒ R− 1 ⊆ S− 1.

Zadanie 5.10 Niech R = {a, b, c}, S = {b, c, d} i T = {a, d}. Konstruuj¸ac odpowiednie drzewo znaleźć R × S × T .