Tw. Jeżeli R X2, to idx
R R
= Re
Dow. Udowodnimy, że idx
R R ∞ jest najmniejszą relacją równoważności zawierającą R.
R (idx
R R ) ∞ idx R R
= idx
R R ∞
idx idx
R R
idx R R
idx R R
jest przechodnia
Indukcyjnie pokazujemy, że id
R R
= id
R R
, n
N
1) n=1
L= id
R R
= id
R R
P= id
R R
= id
R R
2) Z: id
R R
= id
R R
T: id
R R
= id
R R
D: id
R R
= id
R R
· id
R R
=
= id
R R
· id
R R
=
= id
R R
· id
R R
= id
R R
= P
3) Na mocy 1), 2) oraz zasady indukcji matematycznej równość jest prawdziwa.
idx R R
=
∞
idx R R
=
∞
idx R R
=
=
∞
idx R R
=
∞
idx
R
R
=
∞
idx R R
=
= idx
R R
, czyli idx
R R
jest relacją równoważności.
Biorę T X2 taką, że R T i T jest relacją równoważności idx T
R T => idx
R R
T, n
N
R-1 T-1 = T
Indukcyjnie pokazujemy, że idx
R R
T, n
N
Założenie: idx
R R
T
Teza: idx
R R
T
Dowód: idx
R R
= idx
R R
idx R R
T T T ,
∞
idx R R
T , czyli idx
R R
T ,
Z poprzedniego twierdzenia wynika, że R = idx
R R
Def. Niech R X2 i S Y2
Produktem (iloczynem kartezjańskim) relacji R i S nazywamy relację R S
X x Y taką, że
(x1,y1)R S(x2,y2) :<=> x1Rx2^y1Sy2
Tw. Jeżeli R X2 i S Y2 są relacjami równoważności, to R S jest relacją równoważności na XxY
i x, y
x x y
Dow. Wykażę, że relacja produktowa R S jest relacją równoważności, czyli jest zwrotna, symetryczna i przechodnia.
Zwrotność:
biorę dowolną uporządkowaną parę x, y
XxY, wówczas x, y
XxY x !^y Y " x, x
R ^ y, y
S
$ x, y , x, y
R S
1) Założenie zwrotności relacji R i S
2) Z definicji relacji produktowej
Symetria: Niech x , x
X i y , y
Y oraz x , y , x , y
XxY będą takimi elementami, że % x , y , x , y &
R S , wówczas:
x , x
R^ y , y
S " x , x
R^ y , y
S % x , y , x , y & R S
1) Założenie symetrii relacji R i S
Przechodniość: Niech x , x , x'
X i y , y , y' Y oraz x ,y , x ,y , x',y'
XxY będą takimi elementami, że
% x , y , x , y & R S oraz % x , y , x', y' & R S mamy wówczas:
% x , y , x , y & R S^% x , y , x', y' & R S x , x R^ y , y
S ^ x , x' R^ y ,y'
S
" x , x'
R^ y , y'
S % x , y , x', y' & R S
x,y x x y , biorę dowolną parę (x’,y’) należącą do klasy abstrakcji x,y wówczas: x(, y)
x, y % x(, y) , x, y & R S x(,x
R^ y(, y
S x(
x ^y)
y
x(, y(
x x y
Przykład
1) Niech relacja R
N taką, że (n1,m1)R(n2,m2) <=> n1 + m2 = m1 + n2
Pokazujemy, że R jest relacją równoważności.
Zwrotność: biorę dowolną uporządkowaną parę (n,m), gdzie n, m
, n, m
x zachodzi (n,m)R(n,m), bo
n+m=m+n
Symetryczność: wiemy, że n , m R n , m
n + m m + n , co możemy zapisać jako n , m n , m ,
stąd n , m n , m co oznacza n , m R n , m
Przechodniość: biorę dowolne pary uporządkowane n , m , n , m , n', m'
x , gdzie
n , n , n', m ,m ,m'
1)
n , m R n , m
n1 + m2 = m1 + n2
n , m n , m
2)
n , m R n',m' n2 + m3 = m2 + n3 n , m n' , m'
Z 1) i 2) =>
n1 - m1 = n3 – m3
n + m' m + n' n , m R n',m'
Niech :=
R
- = . n, m
/ n, m
0
n, m
1 k. l
: n + l m + k6 = 1 k, l
: n , m k , l6
2) Niech S
x \.00 taką, że (p1,q1)S(p2,q2) <=> p1q2 = p2q1
Pokazujemy, że S jest relacją równoważności
Zwrotność: biorę dowolną uporządkowaną parę p, q
x \.00 , gdzie p i q
\.00
p, q
x \.00 zachodzi p, q S p, q , bo pq=pq
;
;
Symetryczność: Wiemy, że p , q S p , q
p q p q co możemy zapisać jako < ;>
> ;<
=
stąd
co oznacza
<
=>
=>
=<
p , q S p , q
Przechodniość: biorę dowolne pary uporządkowane p , q , p , q , p', q' , gdzie p , p , p'
, q , q , q'
\.00
1)
p , q S p , q
p q p q
;< ;>
=
<
=>
2)
p , q S p',q' p q' p'q ;> ;?
=
>
=?
;
Z 1) i 2) => < ;? p q
=
' p'q
@
p , q S
<
=?
;<,=< ;?,=? , %
\.A0&>
p', q'
Niech
:= x \ .00 S
- = 1 p, q :p
, q
\.006
p, q = B r, s
x \.00: ps qrE = 1 r, s
x \.00: ; F6
=
G
Def. Niech R X2 będzie relacją równoważności, X H I.
Odwzorowaniem kanonicznym dla zbioru X i relacji R nazywamy odwzorowanie pR: X J X R
- takie, że Kx
X: p x L x
Def. Niech f: X J Y. Jądrem funkcji f nazywamy relacją Kerf X2 taką, że x1Kerfx2 :<=> f(x1) = f(x2) Tw. Jeżeli R X2 jest relacją równoważności i X H I,to odwzorowanie p jest surjekcją.
Dow. (to nie jest dowód surjektywności!)
Biorę dowolne [x1]R, [x1]R = {y X: x1Ry}
[x1]R – ustalone, [x1]R – niepuste, bo x1∈ [x1]R
pR(x1) = [x1]R dla dowolnego [x1]R
Tw. Jeżeli f: X J Y i X H I, to Kerf jest relacją równoważności.
Dow.
Biorę dowolne x1, x2
x1 kerf x2
f(x1) =f(x2)
1) x1 kerf x2 ⇨ f(x1) =f(x2) ⇨ f(x2) =f(x1) ⇨ x2 kerf x1⇨ symetria 2) x1 kerf x2 - x2 kerf x3 ⇨ f(x1) =f(x2) = f(x2) -f(x3) ⇨ f(x1) = f(x3) ⇨ x1 kerf x3 ⇨ przechodniość 3) xkerf x ‹ f(x) =f(x) ⇨ zwrotność
Tw. (o rozkładzie kanonicznym funkcji)
Jeżeli f: X J Y i X H I, to istnieje dokładnie jedna iniekcja g: X K
- erf J Y taka, że f = g pR FS
Dow. (istnienie)
Niech g x R FS /= f x
1) Biorę x1,x2∈ X takie, że x R FS = x R FS =T g x R FS = f x ^ g x R FS = f x ^ x1Kerfx2
=>g x R FS = f x ^ g x R FS = f x ^ f x
= f x , g jest funkcją
2) Biorę x R FS, x R FS takie, że g x R FS = g x R FS =>f x
= f x => x1Kerfx2 => x R FS = x R FS ,
czyli g jest iniekcją
3) Biorę x ∈ X g pR FS x = g%pR FS x & = g x R FS = f x czyli g pR FS = f 4) Jednoznaczność
Biorę g , g : X K
- erf J Y -iniekcje i g pR FS = f = g pR FS
Biorę dowolne x R FS
g
x R FS = g pR FS x = f x
=>g = g
g
x R FS = g pR FS x = f x
De
D f
e .f Niech X H I. Mówimy, że relacja ≼⊂ X2 jest relacją częściowego porządku na X: ≼ jest zwrotna, antysymetryczna i przechodnia.
ozn.x≺ y: x ≼ y ∧x H y
Przykład:
1 ℝ, ≤
2 o, |
3 P x , ⊂
De
D f
e .f Niech R ⊂ X2 i A ⊂ X. Relację zawężoną obciętą do A nazywamy relację R|A ⊂ A2, taką, że
∀a, b ∈ AaR|A b: aRb
Tw
T .
w Jeżeli ≼⊂ X2 jest relacją częściowego porządku i A ⊂ X, to ≼|A jest relacją częściowego porządku w A.
Do
D w
o .
w A ⊂ X, to a1, a2, a3 ∈ A ⇨ a1, a2, a3 ∈ X
bzo:
(a ≼
1 |A a1 ‹ a1≼ a1) ⇨zwrotność
a ≼
≼
1 |A a2, to a1≼ a2⇨ ~( a2≼ a1) ⇨ ~( a2 |Aa1)⇨antysymetryczność (źle!) a ≼
≼
≼
1 |A a2 ∧ a2 |A a3 ⇨ a1 ≼ a2 ∧ a2≼ a3 ⇨ a1 ≼ a3 ⇨a3 |Aa3⇨ przechodniość ∎
Di
D a
i g
a r
g a
r m
a y
m
y H
a
H a
a s
a e
s g
e o
g
Jeżeli zbiór A ⊂ X, A jest skończony i ≼⊂ X2 jest relacją częściowego porządku, to relację ≼|A możemy przedstawić na diagramie w sposób następujący:
1) Jeżeli x<y, to x leży na diagramie poniżej y.
2) Jeżeli x<y i ~∃z ∈A: x<z<y, to x i y łączymy odcinkiem.
3) x jest połączone z x odcinkiem zredukowanym (punktem).
4) x<y, to x jest połączone z y łamaną wznoszącą się od x do y.
Przykład: Narysujmy diagram {2, 4, 6, 7, 8, 10, 12}
max A nie istnieje
min A nie istnieje
elementy maksymalne ∈ {8, 12, 10, 7}
elementyminimalne∈ {2, 7}
Major A = {k * NWW (10, 8, 12, 7): k∈ ℕ+ }
Minor A = {1}
sup A = NWW (10, 8, 12, 7)
inf A = NWD (2, 7) = 1
De
D f
e .
f Niech ≼⊂ X2 będzie relacją częściowego porządku i A ⊂ X
x0 jest elementem największym w zbiorze A:
x0∈ A ∧∀x ∈ A: x ≼x0 (ozn. x0 = maxA)
x0 jest elementem najmniejszym w zbiorze A:
x0∈ A ∧∀x ∈ A: x0≼x (ozn. x0 = minA)
x0 jest elementem maksymalnym w zbiorze A:
x0∈ A ∧~∃x ∈ Ax0≺ x
x0 jest elementem minimalnym w zbiorze A:
x0∈ A ∧~∃x ∈ Ax ≺ x0
x0 jest ograniczeniem górnym (majorantą) zbioru A:
∀‚ ∈ A: x ≼ ‚0 (ozn. x0 ∈ Major A)
x0 jest ograniczeniem dolnym (minorantą) zbioru A:
∀‚ ∈ A: x0≼ x (ozn. x0 = Minor A)
x0 jest kresem górnym (supremum) w zbiorze A:
x0 = min Major A(ozn. x0 = supA)
x0 jest kresem dolnym (infimum) w zbiorze A:
x0 = max Major A(ozn. x0 = infA)
Tw
T .
w Jeżeli ≼⊂ X2 jest relacją częściowego porządku i A ⊂ X, to 1. x0 jest elementem maksymalnym zbioru A
x0∈ A ∧ ∀‚ ∈ A: (x0≼x ⇨ x0= x)
Do
D w
o :
w x0 jest elementem maksymalnym zbioru A
x0∈ A ∧ ~∃x ∈ A: x0 ≺ x
x0∈ A ∧ ~∃x ∈ A: (x0 ≼ x ∧ x0≠ x)
x0∈ A ∧ ∀x ∈ A: (~x0 ≼ x ∨ x0= x)
x0∈ A ∧ ∀x ∈ A (x0≼x ⇨ x0= x) ∎
2. x0 jest elementem minimalnym zbioru A
x0∈ A ∧ ∀‚ ∈ A: (x≼ x0⇨x= x0)
Do
D w
o :
w x0 jest elementem minimalnym zbioru A
x0∈ A ∧ ~∃x ∈ A: x ≺ x0
x0∈ A ∧ ~∃x ∈ A:
(x ≼ x0 ∧ x0 ≠ x)
x0∈ A ∧ ∀x ∈ A: (~x ≼ x0∨ x0= x)
x0∈ A ∧ ∀x ∈ A: (x ≼ x0⇨x0= x)∎
∀ x ∈ A: x ≼ x0 ∧ ∀y[∀x ∈ A: x ≼ y ⇨x0≼ y]
Do
D w
o :
w x0 = supA
x0 = min(Major A) ⇨ x0 ∈ Major A ∧ ∀y ∈ Major A: x0 ≼ y
∀x ∈ A: x≼ x0 ∧
∀y ∈ X: (y ∈ Major A ⇨ x0 ≼ y)
∀x ∈ A: x ≼ x0 ∧ ∀y ∈ X: (∀x ∈ A: x ≼ y ⇨x0≼ y)∎
4. x0 = infA
∀ x ∈ A: x ≼ x0 ∧ ∀y[∀x ∈ A: y ≼ x =>y ≼ x0]
Do
D w
o :
w x0 = infA
x0 = max(Minor A)⇨ x0 ∈ Minor A ∧ ∀y ∈ Minor A: y ≼ x0
∀x ∈ A: x0≼ x ∧
∀y ∈ X: (y ∈ Minor A ⇨y ≼ x0)
∀x ∈ A: x ≼ x0 ∧ ∀y ∈ X: (∀x ∈ A: y ≼ x⇨ y ≼ x0)∎
Przykład:
Pokaż, że jeśli x ≠∅, R ∈ P(x), ⊂ jest relacją częściowego porządku w P(x), to supR = ⋃R (względem Õ)
infR = ⋂R
∀…œ†: …Õ»†fl»†œ‡ˆ‰Š‹†
biorę dowolne Y tże ∀…œ†: …ÕŒfl »†ÕŒfl »† = •Ž•†.
∀…œ†: …†Õ…fl…†œ‡•‘Š‹†
biorę dowolne Y tże ∀…œ†: ŒÕ…fl ŒÕ…†fl …† = •‘’†.
∎
De
D f
e :
f Niech f: X → Y, ≼1 jest relacją częściowego porządku w X, ≼2 jest relacją częściowego porządku w Y.
f nazywamy homomorfizmem:
∀x1, x2 ∈ X: [x1 ≼ x2 ⇨f(x1) ≼ f(x2)]
f nazywamy epimorfizmem:
f jest homomorfizmem i suriekcją
f nazywamy monomorfizmem:
f jest iniekcją ∧ ∀x1, x2 ∈ X: x1 ≼ x2
f(x1) ≼ f(x2)
f nazywamy izomorfizmem:
f jest monomorfizmem i epimorfizmem
f nazywamy endomorfizmem:
f: X → X ∧ f jest homomorfizmem
f nazywamy automorfizmem:
f: X → X ∧ f jest izomorfizmem