Diszkr´ et matematika I. k¨ oz´ epszint
Diszkr´et matematika I. k¨oz´epszint 5. el˝ oad´as
M´erai L´aszl´ o di´ai alapj´an Komputeralgebra Tansz´ ek
2014. ˝ osz
2014. ˝ osz
1.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
Sz´amfogalom b˝ov´ıt´ese A term´eszetes sz´amokb´ol kiindulva megkonstru´alhat´ ok a term´eszetes sz´amok: N = {0, 1, . . . }; eg´esz sz´amok: Z = {. . . , −1, 0, 1, . . . }; racion´alis sz´amok: Q = {p/q : p, q ∈ Z, q 6= 0}; val´os sz´amok: R =?; komplex sz´amok: C = {a + bi : a, b ∈ R}. K´ erd´ esek Milyen fontos tulajdons´agokkal rendelkeznek az adott sz´amhalmazok? Mik a val´os sz´amok? Mi a pontos kapcsolat a m˝ uveletek ´es a sz´amhalmazok k¨oz¨ott? N-ben nincs kivon´as, de Z-ben van, Z-ben nincs oszt´as, de Q-ban van. . .
2014. ˝ osz
2.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
Term´eszetes sz´amok Peano-axi´om´ak Legyen N egy halmaz, + egy un´er m˝ uvelet (r´ak¨ ovetkez˝ o). Ekkor 1. 0 ∈ N; 2. n ∈ N ⇒ n+ ∈ N; 3. n ∈ N ⇒ n+ 6= 0; 4. n, m ∈ N eset´en n+ = m+ ⇒ n = m; 5. (S ⊂ N, 0 ∈ S, (n ∈ S ⇒ n+ ∈ S)) ⇒ S = N. Megjegyz´ esek Az axi´om´ak egy´ertelm˝ uen defini´alj´ak N-et. Mindegyik axi´oma sz¨ uks´eges. N halmaz megkonstru´alhat´ o: 0 := ∅, 0+ := {∅}, + (0+ ) := ∅, {∅} ,. . . 1 := 0+ , 2 := 1+ , . . .
2014. ˝ osz
3.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
M˝uveletek term´eszetes sz´amokkal N-en term´eszetes m´odon defini´alhatjuk az ¨ osszead´ast (HF), p´eld´aul + n + 1 := n+ , n + 2 := (n+ ) , . . .
´ ıt´as All´ Ha k, m, n ∈ N, akkor 1. (k + m) + n = k + (m + n) (asszociativit´as); 2. k + m = m + k (kommutativit´as); 3. 0 + n = n + 0 = n (van nullelem/egys´egelem/semleges elem).
2014. ˝ osz
4.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
F´elcsoportok Defin´ıci´o A G halmaz a ∗ m˝ uvelettel f´elcsoport, ha ∗ asszociat´ıv G -n. Ha l´etezik n ∈ G : ∀g ∈ G : n ∗ g = g ∗ n = g , akkor az n egys´egelem (nullelem, neutr´alis elem), G pedig egys´egelemes f´elcsoport.
P´elda N az + m˝ uvelettel egys´egelemes f´elcsoport n = 0 egys´egelemmel. Q a · m˝ uvelettel egys´egelemes f´elcsoport n = 1 egys´egelemmel. k×k C a m´atrixszorz´assal egys´egelemes f´elcsoport az egys´egm´atrixszal, mint egys´egelemmel.
5.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
Eg´esz sz´amok Az N halmazon nem (mindig) tudjuk a kivon´ast elv´egezni. ol ki tudjuk vonni az A kivon´as elv´egz´es´ehez el´eg (lenne), hogy a 0-b´ adott n sz´amot (ellentett):
Defin´ıci´o Legyen G egy egys´egelemes f´elcsoport a ∗ m˝ uvelettel ´es n egys´egelemmel. A g ∈ G elem inverze (ellentettje) a g −1 ∈ G elem, melyre g ∗ g −1 = g −1 ∗ g = n. Ha minden g ∈ G elemnek l´etezik inverze, akkor G csoport. Ha ∗ kommutat´ıv, akkor G Abel-csoport.
´ ıt´as All´ Z a legsz˝ ukebb olyan (Abel-) csoport, mely tartalmazza N-et. Megjegyz´ es Z megkonstru´alhat´o N-b˝ ol: az (r , s) ∼ (p, q), ha r + q = p + s ekvivalenciarel´aci´o oszt´alyai az eg´esz sz´amok.
2014. ˝ osz
6.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Csoportok Tov´abbi p´eld´ak csoportokra: Q az + m˝ uvelettel, a 0 egys´egelemmel. Q∗ = Q \ {0} a · m˝ uvelettel, az 1 egys´egelemmel. {M ∈ Ck×k : det M 6= 0} a m´atrixszorz´assal, ´es az egys´egm´atrixszal, mint egys´egelemmel. X → X bijekt´ıv f¨ uggv´enyek a ◦ m˝ uvelettel, ´es az idX : x 7→ x identikus lek´epz´essel, mint egys´egelemmel.
7.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
Eg´esz sz´amok szorz´asa Az eg´esz sz´amok k¨or´eben defini´alhatjuk a · m˝ uveletet: Ha n ∈ N, m ∈ Z, akkor legyen n · m = m + m + · · · + m. | {z } n darab Ha n 6∈ N, akkor legyen n · m = − (−n) · m .
´ ıt´as All´ A Z a · m˝ uveletre kommutat´ıv egys´egelemes f´elcsoport. (A · kommutat´ıv, asszociat´ıv, van egys´egelem.) A k´et m˝ uvelet nem ,,f¨ uggetlen”:
´ ıt´as All´ Z-n a · az +-ra n´ezve disztribut´ıv: ∀k, l, m ∈ Z-re: k · (l + m) = k · l + k · m.
2014. ˝ osz
8.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Gy˝ur˝uk Defin´ıci´o Legyen R egy halmaz k´et bin´er m˝ uvelettel: ∗, ◦. Ekkor az R gy˝ ur˝ u, ha R a ∗ m˝ uvelettel Abel-csoport (0-val, mint egys´egelemmel); R a ◦ m˝ uvelettel f´elcsoport; a ◦ a ∗-ra n´ezve disztribut´ıv: r ◦ (s ∗ t) = (r ◦ s) ∗ (r ◦ t); (s ∗ t) ◦ r = (s ◦ r ) ∗ (t ◦ r ). Az R egys´egelemes gy˝ ur˝ u, ha R-en a ◦ m˝ uveletre n´ezve van egys´egelem. Az R kommutat´ıv gy˝ ur˝ u, ha a ◦ m˝ uvelet (is) kommutat´ıv.
P´elda Z az (+, ·) m˝ uveletekre egys´egelemes kommutat´ıv gy˝ ur˝ u. A p´aros sz´amok halmaza gy˝ ur˝ u, de nem egys´egelemes. Q, R, C egys´egelemes kommutat´ıv gy˝ ur˝ uk. Ck×k egys´egelemes gy˝ ur˝ u, de nem kommutat´ıv.
9.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Nulloszt´omentes gy˝ur˝uk A gy˝ ur˝ ukben ´altal´aban nem lehet elv´egezni az oszt´ast: Z-ben nem oldhat´ o meg a 2x = 1 egyenlet. 2×2 R -ben nem oldhat´ o meg az al´abbi egyenlet 1 0 1 0 ·X = 0 0 0 1
Defin´ıci´o Ha egy (R, ∗, ◦) gy˝ ur˝ uben ∀r , s ∈ R, r , s 6= 0 eset´en r ◦ s 6= 0, akkor R nulloszt´omentes gy˝ ur˝ u.
P´elda Nem nulloszt´omentes gy˝ ur˝ u 0 0 1 0 0 0 R2×2 : · = 0 1 0 0 0 0
10.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
Testek Szeretn´enk Z-ben az oszt´ast elv´egezni. Mivel az oszt´as nem ,,sz´ep” m˝ uvelet (nem asszociat´ıv), ez´ert azt a reciprokkal (inverzzel) val´o szorz´assal helyettes´ıten´enk.
Defin´ıci´o Legyen K egy halmaz, azon k´et m˝ uvelet: ∗, ◦. A K ferdetest, ha K gy˝ ur˝ u; ∗ K = K \ {0} a ◦ m˝ uvelettel csoport. Megjegyz´ es Ha K ∗ csoport, akkor minden elemnek l´etezik inverze (reciproka), ´ıgy minden elemmel tudunk osztani.
´ ıt´as All´ Q az N-et tartalmaz´o legsz˝ ukebb test. Megjegyz´ es Q megkonstru´alhat´o Z seg´ıts´eg´evel: az (r , s) ∼ (p, q) (s, q 6= 0), ha r · q = p · s ekvivalenciarel´aci´ o oszt´alyai a racion´alis sz´amok.
2014. ˝ osz
11.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Testek P´elda R, C √ {r + s 2 : r , s ∈ Q}: 1 1 √ = √ r +s 2 r +s 2 √ r −s 2 = 2 r − 2s 2
√ r −s 2 √ = · r −s 2 r −s √ = 2 + 2 2 2 r − 2s r − 2s 2
Kvaterni´ok H = {a + bi + cj + dk : a, b, c, d ∈ R}, tov´abb´a i 2 = j 2 = k 2 = −1, ij = k, ji = −k, . . . Nemkommutat´ıv ferdetest! j i k
12.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Sz´amok ´es rendez´es Z-n a term´eszetes m´odon defini´alhatjuk a rendez´est: Adott n ∈ N, n 6= 0 eset´en legyen 0 < n. Legyen tov´abb´a n < m, ha 0 < m − n. Ekkor a rendez´es kompatibilis a m˝ uveletekkel:
´ ıt´as All´ Ha k, m, n ∈ Z, akkor k < m ⇒ k + n < m + n, m, n > 0 ⇒ m · n > 0.
Defin´ıci´o Egy R gy˝ ur˝ u rendezett gy˝ ur˝ u, ha van az R-en defini´alva egy rendez´es, mely kiel´eg´ıti a fenti tulajdons´agokat.
13.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Rendezett testek p r < , ha ps < rq. q s A kiterjeszt´es azonban nem lesz ,,teljes”, Q nem lesz fels˝o hat´ar tulajdons´ag´ u. Eml´ ekeztet˝ o Egy X halmaz fels˝o hat´ar tulajdons´ag´ u, ha minden ∅ = 6 Y ⊂ X fel¨ ulr˝ol korl´atos r´eszhalmaznak van supremuma. A Z-n defini´alt rendez´es kiterjeszthet˝ o Q-ra:
´ ıt´as All´ √
2 6∈ Q. √ Speci´alisan Q nem fels˝o hat´ar tulajdons´ u: {r ∈ Q : r ≤ 2} fel¨ ulr˝ol √ag´ korl´atos, de nincs supremuma (sup = 2 6∈ Q).
Bizony´ıt´as Indirekt tfh ∃n, m ∈ N+ : (m/n)2 = 2. V´alasszuk azt az m, n p´art, ahol (m, n) = 1. Most m2 = 2n2 ⇒ 2 | m. Legyen m = 2k ⇒ m2 = 4k 2 = 2n2 ⇒ 2 | n ⇒ (m, n) ≥ 2.
14.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
Val´os sz´amok Val´os sz´amok axi´om´aja Legyen R az N-et tartalmaz´ o legsz˝ ukebb fels˝ o hat´ar tulajdons´aggal rendelkez˝o rendezett test. Megjegyz´ es A val´os sz´amok halmaza l´enyeg´eben egy´ertelm˝ u. R megkonstru´alhat´o: legyen R a Q kezd˝ oszeletei: Egy A ⊂ Q kezd˝oszelet, ha A 6= Q, ´es r ∈ A, s < r ⇒ s ∈ A; √ √ p´eld´aul 2 ↔ {r ∈ Q : r ≤ 2}. N, Z, Q defini´alhat´o R seg´ıts´eg´evel is: N: a 0, 1 ∈ R elemeket tartalmaz´ o legsz˝ ukebb f´elcsoport; Z = N ∪ (−N); Q = {r /s ∈ R : r , s ∈ Z, s 6= 0}.
2014. ˝ osz
15.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
¨ Osszefoglal´ o M˝ uveletek halmazokon Strukt´ ura
P´ elda
Peano axi´om´ak
N
f´elcsoport: van asszociat´ıv m˝ uvelet
(N, +), (Z, ·)
csoport: van inverz
(Z, +), (Q∗ , ·), (Zm , +), (Z∗p , ·)
gy˝ ur˝ u: k´et m˝ uvelet,
(Z, +, ·), (Zm , +, ·),
∗-ra kommutat´ıv csoport,
(Rk×k , +, ·)
◦-re f´elcsoport, disztributivit´as ferdetest: k´et m˝ uvelet, ∗-ra kommutat´ıv csoport, ◦-re a 0 kiv´etel´evel csoport, disztributivit´as
Q, R, C, H, Zp
16.
Sz´ amfogalom b˝ ov´ıt´ ese
Diszkr´ et matematika I. k¨ oz´ epszint
¨ Osszefoglal´ o M˝ uveletek ´ es rendez´ es Strukt´ ura
P´ elda
f´elcsoport: van asszociat´ıv m˝ uvelet rendezett gy˝ ur˝ u
Z
rendezett test
Q, R
fels˝ohat´ar tulajdons´ag´ u test
R
2014. ˝ osz
17.
