universitaire olympiade bundel

universitaire olympiade bundel olympia 8 mei 2013

1

Inhoudsopgave 1

elementaire problem-solving 1.1

getaltheorie

4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2 gevorderde problem-solving

5

3 rekende problem-solving

6

3.1 4

5

calculus

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

voorbeeldcompetities

6 7

4.1

links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

4.2

ontbrekende oplossingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

bijlages

9

2

inleiding In deze bundel bespreken we de verschillende onderwerpen die op universitaire olympiades vaak voorkomen. We bespreken zowel kort de theorie als voorbeelden. Bij universitaire olympiades zijn er 3 soorten wiskunde zoals het door ons werd opgedeeld. (eventueel kan men hier zien wat men nog moet bestuderen ) 1. ëlementaire”problem-solving : Deze problem-solving is er van de soort waarbij ook jongere personen de oplossing kunnen verstaan. Het vinden van de oplossing is echter niet zoals de ”gedrilde”voorbeeld wiskunde van op de schoolbanken. Ze is dan ook van de aard zoals de olympiades in het middelbaar. Voorbeeld hiervan is middelbaar vs universitair. Deze vragen zijn dan ook vaak goed opgelost door creatieve personen die eerder op middelbare wedstrijden het goed deden. 2. gevorderde problem-solving: Bij deze vragen wordt gewerkt met theorie die niet iedereen kent, maar waarbij de vraag elegant opgelost wordt dankzij het toepassen van handige eigenschappen, constructies, stellingen en inzicht in deze gevorderde materie. Dit is vooral geschikt voor de oplettende wiskundestudent. 3. ”rekende problem-solving” Hiermee bedoelen dat op universitaire olympiade er gevraagd wordt om dingen te bereken ( evt. na de verwoording van de vraag te hebben ontcijferd). Deze vragen vergen vooral de technieken snel te kunnen toepassen, met een eventuele spitsvondigheid. Dit is misschien meer gepast voor een ingenieur. Dit bestand wordt nog meermaals bijgewerkt. Indien men met iets niet akkoord gaat, kan men dit met een mailtje naar [email protected] melden.

3

1

elementaire problem-solving

Voor een groot deel kan men hiervoor kijken op de totaalbundel voor de middelbare internationale olympiades.

1.1

getaltheorie

Bij getaltheorievragen worden stelling zoals de chinese reststelling etc toegepast. enkele voorbeelden 1. Vind het aantal positieve gehele getallen x van niet meer dan 2006 cijfers waarvoor x2 − x deelbaar is door 102006 . link 2. Zij x, y, z ∈ Z met 29|x4 + y 4 + z 4 . Toon aan dat 294 |x4 + y 4 + z 4 . link

4

2

gevorderde problem-solving

In deze sectie bespreken we oa de technieken uit de analyse, lineaire algebra . Aangezien we niet kunnen verwijzen naar andere lesbrieven, kunnen er bijlages worden bekeken wanneer men over een onderwerp te weinig kent: analyse beknopt groepentheorie enkele voorbeelden 1. Let A, B be matrices of dimension 2010 × 2010 which commute and have real entries, such that A2010 = B 2010 = I, where I is the identity matrix. Prove that if tr(AB) = 2010, then tr(A) = tr(B) bron 2. Zij f : R → R. Geef voor elk van volgende beweringen een bewijs of een tegenvoorbeeld: [list=a][*]Als f continu en surjectief is, dan is f monotoon.[*]Als f monotoon en surjectief is, dan is f continu.[*]Als f monotoon en continu is, dan is f surjectief.[/list:o] (merk op: f surjectief betekent hier dat range(f ) = R) oplossing

5

3

rekende problem-solving

3.1

calculus

Deze bevat rekenmethodes in verband met afgeleiden, integreren, reekssommen ... Deze theorie werd gezien in iedere universitaire richting. enkele voorbeelden cot 2x

1. Bereken limx→0 (cos x)

.

link 2. Zij H = {(x, y, z) : x2 + y 2 + z 2 = 1, z ≥ 0}, C = {(x, y, 0) : x2 + y 2 = 1} en P een regelmatig pentagon ingeschreven in C. Vind de verhouding van de oppervlakte van H gelegen boven P en de oorspronkelijke oppervlakte van H . link

6

4

voorbeeldcompetities

4.1

links

We geven hierbij links van enkele leuke universitaire olympiades waar de vragen ook te vinden zijn: IMC LIMO Putnam WINA PUMA MOAWOA MOAWOA 2012 MOAWOA 2012 opl Volgende site bevat bij Preparation material nogal wat interessante dingen: IMOmath Ieder — moet een percentageteken zijn in volgende link: http://mathsouls.110mb.com/Ebook/Math/En/Linear —20Algebra/Problems —20and —20Theorems —20in —20Linear —20Algebra.pdf , wat een interessant boek zou kunnen zijn voor algebra.

4.2

ontbrekende oplossingen

LIMO 2005 , vraag 4 a b bewijs lemma We bewijzen dat de functie g : R → R:g(x) = u({ax} − a) zoals geconstrueerd in de hint niet periodiek is en P (g, m) = m + 1. (met u de heavy cycle functie)

Veronderstel uit het ongerijmde dat g periodiek is met een periode p. Dan moet {pan} < a steeds gelden voor alle gehele n. Beschouw hiervoor een gehele waarde l zodat {apl} ∈ [2t , 2t+1 ] voor de kleinst mogelijke gehele waarde t indien dit mogelijk is. (we zullen bewijzen dat dit onmogelijk is) Neem l0 ∈ Z zodat {apl}l0 < 1 < {apl}(l0 + 1) voor een bepaalde n ∈ N. Nu is {apl(l0 + 1)} of {−apll0 } kleiner is dan 0.5{apl}. Contradictie met het feit dat t de kleinste mogelijke gehele waarde was. Dit betekent dat we een m ∈ Z kunnen nemen zodat {apm} < min(a, 1 − a) en aangezien er terug een l ∈ Z bestaat zodat {apml} < a < {apm(l + 1)} < 1 bekomen we een contradictie. 7

Deze functie g is dus niet periodiek.

Er geldt dat P (g, m) = m + 1 Bewijs:

We nemen nu f (n) gelijk aan 2 als 2|n en f (2k + 1) = g(k) met n = 2k + 1 als n oneven is. Door de constructie van g is f niet periodiek. Indien tussen 1, 2 · m t even en m − t oneven getallen zitten, geldt dat er m − t + 1 verschillende waarden voor P (m, f |n ≡ 0 (mod 2)) zijn als n even werd gekozen en P (m, f |n ≡ 1 (mod 2)) = t + 1 als we stellen dat n oneven werd gekozen. Samen geeft dit P (m, f ) = m − t + 1 + t + 1 = m + 2 verschillende m-tallen. Dit betekent dat P (m, f ) = m + 2 en f niet periodiek is, zodat deze f voldoet aan de voorwaarden.

8

5

bijlages

Hier nog enkele interessante pdf’s , zo ook is analyse en algebra samenvatting Gent

9

Wiskundige Analyse Christian Impens & Beukje Temmermans

Bert Seghers 1ste bachelor in de wiskunde Universiteit Gent

1

Ten geleide Beste lezer van deze samenvatting, Wat u op dit moment leest is een samenvatting van de cursus Wiskundige Analyse I van de faculteit Wetenschappen van de Universiteit Gent, academiejaar 2006-2007, gegeven door prof. dr. Christian Impens in eerste bachelor wiskunde en fysica. Ik heb gepoogd om, als hulp voor studenten wiskunde en fysica, de cursus van 193 pagina’s verkort en toch vlot weer te geven. Dit LATEX-document is dus bedoeld om antwoord te geven op de vraag wat er in de cursus staat, als de overvloed aan bewijzen die 70% van de ruimte in de cursus innemen je de bomen door het bos niet meer doet zien. Daarom koos ik voor de weglating van bewijzen, maar het behoud van de stellingen. Verder heb ik geopteerd om geen referenties te gebruiken omdat het de leessnelheid sterk reduceert als een samenvatting zinnen bevat zoals Door stelling 12.4.3.1 herleidt (12.35) zich tot (12.36)”. Niet alles ” van bemerkingen en beperkingen is opgenomen; vaak zijn bijvoegsels zoals over het interval U ” weggelaten. Het is niet de bedoeling om volledig te ” zijn, eerder om een samenvattend beeld te geven. Daarom is ook niet alles uitgelegd, bijvoorbeeld dat ı de identieke afbeelding x ÞÑ x voorstelt. Voor grondigere definities, onuitgelegde begrippen, bewijzen en nog veel meer wat niet opgenomen is in deze samenvatting verwijs ik graag naar de cursus van prof. Christian Impens. Alvast veel succes met de examens! Met vriendelijke groet, Bert Seghers

1

Inhoudsopgave 1 Drie getallenvelden 1.1 Rationaal en reëel . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Het complex getallenveld . . . . . . . . . . . . . . . . . . . . .

4 4 5

2 Re¨ ele rijen 2.1 Elementaire theorie . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Stelling van Bolzano-Weierstrass . . . . . . . . . . . . . . . .

5 5 5

3 Limieten van functies

6

4 Continu¨ıteit 4.1 Continu¨ıteit in een vast punt . . . . . . . . . . . . . . . . . . 4.2 Continu¨ıteit over een verzameling . . . . . . . . . . . . . . . .

6 6 7

5 Afleidbaarheid 5.1 Afgeleiden van de eerste orde . . . . . . . . . . . . . . . . . . 5.2 Afgeleiden van hogere orde . . . . . . . . . . . . . . . . . . .

7 7 8

6 Integratie 6.1 Onderintegraal, bovenintegraal, integraal . . . . . . . . . . . 6.2 Het kenmerk van Darboux . . . . . . . . . . . . . . . . . . . 6.3 Integraal met veranderlijke bovengrens - eerste hoofdstelling 6.4 Tweede hoofdstelling . . . . . . . . . . . . . . . . . . . . . . 6.5 partiële integratie en substitutie . . . . . . . . . . . . . . . .

. . . . .

8 8 9 9 10 10

7 Elementaire functies en praktische integratie-technieken 7.1 De hyperbolische familie . . . . . . . . . . . . . . . . . . . . 7.1.1 De logaritme . . . . . . . . . . . . . . . . . . . . . . 7.1.2 De exponentiële . . . . . . . . . . . . . . . . . . . . . 7.1.3 De machtfuncties . . . . . . . . . . . . . . . . . . . . 7.1.4 De hyperbolische functies . . . . . . . . . . . . . . . 7.1.5 De inverse hyperbolische functies . . . . . . . . . . . 7.2 De goniometrische familie . . . . . . . . . . . . . . . . . . . 7.2.1 De arcustangens . . . . . . . . . . . . . . . . . . . . 7.2.2 De tangens . . . . . . . . . . . . . . . . . . . . . . . 7.2.3 De sinus en cosinus . . . . . . . . . . . . . . . . . . . 7.2.4 De overige cyclometrische functies . . . . . . . . . . 7.3 Formules van Stirling en Wallis . . . . . . . . . . . . . . . . 7.4 Praktische integratietechnieken . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

10 10 10 10 11 11 11 11 11 12 12 13 13 13

2

8 Complexe reeksen 8.1 Twee aanvullingen over rijen . . . . . . . . . . . . . . . . . . 8.1.1 Boven- en onderlimiet . . . . . . . . . . . . . . . . . . 8.1.2 Convergentie van complexe rijen . . . . . . . . . . . . 8.2 Convergentie van complexe reeksen . . . . . . . . . . . . . . . 8.3 Convergentieregels voor reële reeksen zonder negatieve termen 8.3.1 Drie convergentieregels door vergelijking . . . . . . . . 8.3.2 Vier grote convergentieregels . . . . . . . . . . . . . . 8.4 Convergentie van reële wisselreeksen . . . . . . . . . . . . . .

15 15 15 15 15 16 16 16 17

9 Gelijkmatige convergentie 17 9.1 Gelijkmatige convergentie van rijen van functies . . . . . . . . 17 9.2 Gelijkmatige convergentie van reeksen van functies . . . . . . 18 10 Complexe machtreeksen 18 10.1 Puntsgewijze convergentie . . . . . . . . . . . . . . . . . . . . 18 10.2 Gelijkmatige convergentie . . . . . . . . . . . . . . . . . . . . 19 10.3 Taylorontwikkelingen . . . . . . . . . . . . . . . . . . . . . . . 20 11 Fourierreeksen 21 11.1 De Singuliere Integraal van Dirichlet . . . . . . . . . . . . . . 21 11.2 Convergentie van Fourierreeksen . . . . . . . . . . . . . . . . 22 12 Lineaire differentiaalvergelijkingen en stelsels 23 12.1 Lineaire differentiaalvergelijkingen van de eerste orde . . . . . 23 12.2 Lineaire differentiaalvergelijkingen van de tweede orde, veranderlijke coëfficiënten . . . . . . . . . . . . . . . . . . . . . . 23 12.3 Lineaire differentiaalvergelijkingen van de tweede orde, constante coëfficiënten . . . . . . . . . . . . . . . . . . . . . . . . 25 12.4 Stelsels lineaire differentiaalvergelijkingen van de eerste orde, constante coëfficiënten . . . . . . . . . . . . . . . . . . . . . . 26

3

Inleiding Notaties en definities

is strikte inclusie, samenvallen onmogelijk.

Definitieverzameling = domein = Df Waardenverzameling B in A Ñ B-afbeelding, wel Restricties, aftelbaarheid, reële, complexe, rationale, nietnegatieve functies.

Logica Implicatie, contrapositie, nodig en voldoende, onderstelde, gestelde, bewijs, volledige inductie

1 1.1

Drie getallenvelden Rationaal en re¨ eel

N, Z, Q en zelfs pQ, , , ¤q is een totaal geordend veld Maar met gaten! ñ Stelling: er bestaat geen rationaal getal met kwadraat 2 (+Bewijs) Bovengrens, ondergrens, begrensd, grootste element of maximum, minimum, supremum, infimum Stelling (Dedekind): R bestaat, heeft alle eigenschappen en vertoont geen gaten, mits supremumprincipe: elke naar boven begrensde deelverzameling van R heeft een supremum. Stelling: twee verzamelingen met elementen x y ñ Dξ : x ¤ ξ ¤ y (+Bewijs) Stelling: Tussen twee reële getallen liggen oneindig veel rationale en oneindig veel irrationale. (+Bewijs) Stelling: ω sup X ô @x : x ¤ ω ^ @ε ¡ 0 : Dx met ω ε x. (+Bewijs)

Stelling: @x : Dy : x ¤ y ñ sup X ¤ sup Y. (+Bewijs)

Stelling: X Y ñ sup X ¤ sup Y (+Bewijs)

Stelling: suppX (Y q sup X sup Y (+Bewijs) sup X pc ¡ 0q

Stelling: suppcX q cc inf (+Bewijs) X pc 0q

Stelling: suppXY q sup X sup Y voor X en Y bestaande uit nietnegatieve getallen (+Bewijs) suppf g q ¤ sup f sup g inf pf g q ¥ inf f inf g Stellingen: (+Bewijzen) suppf g q ¤ sup f sup g inf pf g q ¥ inf f inf g Stelling: |f pxq f px1 q| C @a ¤ x, x1 ¤ b ñ sup f inf f ¤ C (+Bewijs)

ra,bs

4

ra,bs

Negen soorten intervallen, drie soorten grenzen (r, s, 8) Stelling: V is een interval ô Elk punt tussen twee punten van V behoort tot V. (+Bewijs)

1.2

Het complex getallenveld

Complex getal = koppel reële getallen px, y q met x reëel deel en y imaginair deel. Imaginaire getallen gelijk als delen gelijk. Imaginaire eenheid, i2 1, inversie, complex toegevoegde. Stelling: Het veld C kan onmogelijk geordend worden. (+Bewijs)

2 2.1

Re¨ ele rijen Elementaire theorie

Reële rij pxn q = x1 , x2 , . . . DEF convergentie van pxn q naar a

Ñ a ô p@ε ¡ 0qpDN P Nqp@n P Nqpn ¥ N ñ |xn a| εq DEF divergentie van pxn q naar 8 xn Ñ 8 ô p@M P RqpDN P Nqp@n P Nqpn ¥ N ñ xn ¡ M q xn

Stelling: De limiet van een convergente rij is uniek. (+Bewijs) Stelling: Elke convergente rij is begrensd. (+Bewijs) Stelling (Insluitstelling): Als xn ¤ yn ¤ Xn en xn Ñ a en Xn Ñ a, dan ook yn Ñ a (+Bewijs) Stelling: Limiet van een som is som van de limieten voor rijen. (+Bewijs) Stelling: xn Ñ 0 ^ yn begrensd ñ xn yn Ñ 0 (+Bewijs) Stelling: xn Ñ a ^ yn Ñ b ñ xn yn Ñ ab (Limiet product = product limieten) (+Bewijs) Stelling: Absolute waarde limiet is limiet absolute waarde (+Bewijs) Stelling: xn Ñ a 0 ñ xn 0 vanaf een zeker rangnummer en x1n Ñ a1 (+Bewijs) Stelling: xn ¥ 0@n, xn Ñ a, dan a ¥ 0 (+Bewijs) Stelling: Als alle termen van een convergente rij in ra, bs liggen, ligt ook de limiet daarin. (+Bewijs)

2.2

Stelling van Bolzano-Weierstrass

Stelling: xn stijgend en naar boven begrensd ñ convergent met lim xn sup xn (+Bewijs) Stelling: Elke deelrij van een convergente rij is zelf convergent naar dezelfde limiet als de oorspronkelijke. (+Bewijs) Stelling: Elke rij heeft een monotone deelrij! (+Bewijs) 5

Stelling (Stelling van Bolzano-Weierstrass): Als alle rijtermen in ra, bs liggen, dan bestaat er een deelrij die convergeert naar een punt uit ra, bs. (+Bewijs) Stelling (Kenmerk van Cauchy): xn convergeert ô p@ε ¡ 0qpDNε P Nqp|xn xm | ε als n ¡ Nε , m ¡ Nε q (+Bewijs) Stelling (Stelling van de vernestelde compacte intervallen): Is dit een rij van compacte interval met de eigenschap: ra1 , b1 s ra2 , b2 s ra3 , b3 s T . . ., dan is nPN ran , bn s niet ledig, m.a.w. er bestaat een reële ξ die tot alle intervallen behoort. Als bovendien limpbn an q 0, dan is die ξ uniek en gelijk aan lim an lim bn . (+Bewijs) Stelling (Cantor): Een compact interval is niet aftelbaar, en bijgevolg ook R niet(Geen bewijs)

3

Limieten van functies

Omgeving, basisomgeving, open bal, ophopingspunt. DEF L is de limiet van f pxq voor x Ñ a lim f pxq L ô p@ε ¡ 0qpDδ

x

Ña

¡ 0qp@x P Dqp0 |x a| δ ñ |f pxq L| εq

Stelling (Rijenkenmerk voor limieten):(+Bewijs) lim f pxq L ô @rij xn

x

Ña

Ña:

rij f pxn q Ñ f paq

Stelling: Limiet bestaat ñ linkerlimiet en rechterlimiet bestaan en zijn gelijk (en omgekeerd) (+Bewijs) Stelling (Eigenschap van limiet): L bestaat ñ D doorprikte omgeving: f pxq begrensd (+Bewijs) Stelling (Eigenschap van positieve limiet): L ¡ 0 ñ D doorprikte omgeving: f pxq ¡ 0 (+Bewijs) DEF f pxq divergeert naar 8 voor x Ñ a ô p@M P RqpDδ ¡ 0qp@x P Dqp0 |x a| δ ñ f pxq ¡ M q Toepassing: lim 8 xn 8 en alle veeltermfuncties ook naar 8.

4 4.1

Continu¨ıteit Continu¨ıteit in een vast punt

DEF f pxq continu in aô p@ε ¡ 0qpDδ ¡ 0qp@x P Dqp|x a| δ ñ |f pxq f paq| εq Alle soorten stellingen van limieten uitgebreid naar continu¨ıteit met f paq L Stellingen: bewerkingen op continue functies = continu; veeltermfuncties altijd continu, samenstelling van zo’n functies continu, behoud van teken (+Bewijsjes) 6

4.2

Continu¨ıteit over een verzameling

DEF f pxq continu over verzameling A ô f {A continu ô p@x P Aqp@ε ¡ 0qpDδ ¡ 0qp@t P Aqp|t x| δ ñ |f ptq f pxq| εq Stelling: De volgende uitdrukkingen van continu¨ıteit zijn equivalent (+Bewijs)

p@x Psa, brqp@ε ¡ 0qpDδ ¡ 0qp@x Psa, brqp|t x| δ ñ |f ptq f pxq| εq p@x Psa, brqp@ε ¡ 0qpDδ ¡ 0qp@x P Df qp|t x| δ ñ |f ptq f pxq| εq Stelling: f continu over ra, bs ô continu over sa, br, rechtscontinu in a en

linkscontinu in b (+Bewijs) Stelling (Speciaal geval van tussenwaardestelling, voor 0): (+Bewijs) a b, f paqf pbq 0, f continu over ra, bs ñ Dc Psa, br: f pcq 0 Stelling (Tussenwaardestelling van Bolzano): f continu over interval I. Elk getal tussen twee functiewaarden is zelf functiewaarde van getal in f {I. (+Bewijs) Definities van (strikt) stijgend,... en inverse functies Stelling van inversie van continue strikt monotone functies: Functie strikt stijgend dalend en continu over interval I ñ Er bestaat een inverse strikt stijgend dalend en continu over f pI q. (+Bewijs) Stelling (Extremumstelling van Weierstrass): f {ra, bs continu over dit compact interval ñ f/[a,b] bereikt minimum en maximum m.a.w. Dx1 , x2 P ra, bs : @x P ra, bs : f px1q ¤ f pxq ¤ f px2q (+Bewijs) continu¨ıteit vs. gelijkmatige continu¨ıteit:

p@x P Aqp@ε ¡ 0qpDδx,ε ¡ 0qp@x1 P Aqp|x x1| δ ñ |f pxq f px1q| εq p@ε ¡ 0qpDδε ¡ 0qp@x P Aqp@x1 P Aqp|x x1| δ ñ |f pxq f px1q| εq Stelling van Heine: f continu over compact interval ñ automatisch gelijkmatig continu (+Bewijs)

5 5.1

Afleidbaarheid Afgeleiden van de eerste orde

f afleidbaar ô Dα, r : f pa hq f paq αh hrphq met rphq Ñ 0 als h Ñ 0 Stelling: afleidbaar in a ñ continu in a. (+Bewijs) Stelling, eigenschap van positieve afgeleide: f 1 paq ¡ 0 ñ Dδ ¡ 0 : @a x a δ : f pxq ¡ f paq en a δ x a : f pxq f paq (+Bewijs) pf gq1paq = f 1paq g1paq pf gq1paq = f 1paqgpaq f paqg1paq Rekenregels: (+Bewijs) f f 1 paqg paq f paqg 1 paq p aq = g g 2 paq 7

Stelling, kettingregel: f aflb in a, g in f paq, F g pf pxqq ñ F 1 pxq g 1 pf pxqq f 1 pxq (+Bewijs) Stelling voor het afleiden van de inverse (+Bewijs) ϕ1 pf pcqq

1

f 1 pcq

Stelling, nodige voorwaarde voor extremum van Fermat: lokaal extremum + aflb in a ñ f 1 paq 0 (+Bewijs) Stelling (Middelwaardestelling): Dc Psa, br: f pbq f pa q pb aqf 1 pcq (+Bewijs: Rolle + Lagrange) Stellingen over (strikt) stijgen/dalen en teken afg. (+Bewijs adhv middelwaardestelling) Stelling (Veralgemeende middelwaardestelling): (+Bewijs) f pbq f pa g pbq pa

q f 1pcq q g1pcq

Stelling, De l’Hˆ opital (+Bewijs) f 1 pxq g 1 pxq

f pxq A P R ñ xlim Ña gpxq A Toepassing: zelfde stelling, maar met f en g Ñ 8 als x Ñ 8 (+Bewijs) lim

x

5.2

Ña

Afgeleiden van hogere orde

over klassen C 1 , C n , C 8

6

Integratie

6.1

Onderintegraal, bovenintegraal, integraal

Partitie π: genummerde eindige deelverzameling van interval. Bovensom Ondersom Bovenintegraal Bovenintegraal

S π pf q

sπ pf q

Z

a

sup f `k

k 1 Ik m X

k 1

b

Za b

m X

inf f `k Ik

f

inf Sπ

f

sup sπ

Stelling: Voegt men partitiepunten toe, wordt de bovensom niet groter en de ondersom niet kleiner (+Bewijs) Stelling: Willekeurige ondersom ¤ willekeurige bovensom (+Bewijs) 8

DEF ñ integreerbaar, is gemene waarde. Stelling: Integreren is een lineaire operatie: (+Bewijs) R

R

R

Z

b

a

cf

c

Z

b

f,

Z

b

f

g

a

a

Z

Z

b

f

b

g

a

a

Stelling van positiviteit van de integraal: (+Bewijs)

@a x b

f pxq ¥ 0 ñ

Z

b

f

a

¥0

Stelling van monotoniteit van de integraal: (+Bewijs)

@a x b

f pxq ¤ g pxq ñ

Z

b

f

a

¤

Z

b

g

a

c c Stelling van additiviteit van de integraal: ab f b f a f (+Bewijs, eerst hulpstelling van boven- en onderintegraal) Stelling: Integreerbaar over interval I Rñ ook over deelinterval J (+Bewijs) R Stelling: f pxq ¥ 0 over I {J ñ J f ¤ I f (+Bewijs) Stelling: f integreerbaar, maar gewijzigd in een eindig aantal punten blijft R integreerbaar en verandert niet (+Bewijs)

R

6.2

R

R

Het kenmerk van Darboux

Stelling van Darboux: Integreerbaar ô @ε ¡ 0, Dπ, Sπ sπ ε (+Bewijs) Stelling: continu over sa, br met eenzijdige limieten in de uiteinden of continu over ra, bs ñ integreerbaar (+Bewijs) DEF f , f Stelling: f , f , |f | integreerbaar als f integreerbaar en: (+Bewijs)

Stelling: f en g integreerbaar

6.3

Z b f a

¤

Z

b

a

|f |

ñ ook f g (+Bewijs)

Integraal met veranderlijke bovengrens - eerste hoofdstelling

Stelling (Continu¨ıteit van een integraal met veranderlijke bovenRx grens): f integrb over sa, brñ F pxq : x0 f continu over sa, br. Stelling (Eerste hoofdstelling): D F ptq f ptq dus F 1 ptq lim f puq (+Bewijs) DEF Primitieve F van f : F 1

u

f , notatie F

9

R

f

Ñt

6.4

Tweede hoofdstelling

Stelling (Tweede hoofdstelling, integratie van een afgeleide): (+Bewijs) Z

b

a

6.5

f 1 rf sba : f pbq f pa

q

Z

of

b

f

a

Z

f

b

a

parti¨ ele integratie en substitutie

ãÑ Bewijzen vragen veel voorwaarden! R R 1 1

Stelling: ab f g rf g sba ab gf (+Bewijs) Stelling (grens-naar-grens-transformatie): (+Moeilijk bewijs) Z

b

a

f pθxqθ1 x dx

pq f py q dy θ pa q

Z

θ b

Stelling: ab f pxqdx ba f py qdy Stelling:R f integreerbaar over sa, br (periode b a) Rb over lengte periode (+Bewijs) a f R

7

R

ñ overal integreerbaar,

Elementaire functies en praktische integratietechnieken

Voor integratie heeft men genoeg aan veeltermen,

7.1 7.1.1

De hyperbolische familie

R

1 x

en

De logaritme DEF

ln x :

Z

1

x

dt t

R

ÑR

Stelling: ln x 1 ñ x 2, 6 e 2, 8 (+Bewijs) Stelling: lnpxy q ln x ln y (+Bewijs) Stelling: 1 x1 ¤ ln x ¤ x 1 (+Bewijs) 7.1.2

De exponenti¨ ele DEF

Stelling: Stelling: Stelling: Stelling:

exp x : ln1

RÑR

Onbepaald afleidbaar en exp1 exp (+Bewijs) exp x exp y exppx y q (+Bewijs) 1 x ¤ exp x ¤ 11 x (+Bewijs) lim8 veelterm 0 (+Bewijs) exp 10

R

1 . 1 x2

7.1.3

De machtfuncties xy : ey ln x

DEF Stelling: ax 1

xa 1

ax ln a DEF

√ n

Stelling van Euler: limtÑ 7.1.4

0a : 0

axa1 (+Bewijs)

a :

(

als a ¡ 0, n P N als a 0, n P 2N

1

an

paq x t t

8 1

1 n

ex (+Bewijs)

De hyperbolische functies

sinh x :

ex ex 2

cosh x :

ex

ex

tanh x :

2

e2x 1 e2x 1

Stelling: cosh2 sinh2 1 (+Bewijs) Stelling: coshpx y q cosh x cosh y sinh x sinh y (+Bewijs) Stelling: sinhpx y q sinh x cosh y cosh x sinh y (+Bewijs) sinh1 x cosh 7.1.5

arg cosh x arg tanh x

7.2.1

tanh1 x

1 cosh2

De inverse hyperbolische functies arg sinh x

7.2

cosh1 x sinh

lnpx lnpx ln

√

√ x2 1q

s

1q

x2

1 x 1x

Z Z

Z

√ √

1 x2

1

1

x2 1 1 1 x2

De goniometrische familie De arcustangens DEF

arctan x :

Z

0

x

dt 1

t2

RÑR

¤ arctan x ¤ x (+Bewijs) ( π2 x 0 (+Bewijs) Stelling: arctan x arctan x1 π 2 x¡0 8 π2 (+Bewijs) Stelling: arctan strikt Õ met asymptoten: 8 π2 Stelling:

x 1 x2

11

7.2.2

De tangens tan x : arctan1

DEF

tanpx

DEF

@xP

kπ q : tan x

π2 , π2

R \p2 Z 1q

π 2

ÑR

2 tan x2 (+Bewijs) 1 tan2 x2 Stelling: tan1 x 1 tan2 x (+Bewijs) Stelling: tan x

7.2.3

DEF

De sinus en cosinus sin x :

(

2 tan x2 1 tan2 x2

cos x :

0

(

1 tan2 1 tan2

1

@x P R\p2 Z 1q π2 @x P p2 Z 1q π2

x 2 x 2

Allemaal basiseigenschappen van sinus en cosinus kunnen bewijzen adhv ↑. Stelling: sinpx y q sin x cos y cos x sin y (+Bewijs) Stelling: cospx y q cos x cos y sin x sin y (+Bewijs) Stelling: sinpx y q sin x cos y cos x sin y (+Bewijs) Stelling: cospx y q cos x cos y sin x sin y (+Bewijs) Stelling, formule van de Moivre: pcos x i sin xqn cos nx i sin nx (+Bewijs) π Stelling, ongelijkheid van Jordan: 2x π sin x x 0 x 2 (+Bewijs) ( cos θ α Stelling: met α2 β 2 1 heeft juist 1 oplossing in elk sin θ β halfopen interval met lengte 2π. (+Bewijs) Toepassing: poolcoördinaten p Modulus van x iy z P C x2 y 2 . Vandaar ook goniometrische voorstelling van z |z |pcos θ i sin θq. Complexe wortels uit ζ n z0 |z0 |pcos θ0 i sin θ0 q : ζ0

ζ1

ζ2

.. . ζn1

q n

|z 0 |

q n

|z 0 |

q n

|z 0 |

q n

|z 0 |

cos cos

cos

cos

θ0 n θ0

i sin

θ0 n

2π

i sin

n θ0

4π

i sin

n θ0

θ0 n θ0

2 (n 1) π n

(+Bewijs van uniciteit) 12

2π 4π n

i sin

θ0

2 (n 1) π n

7.2.4

De overige cyclometrische functies

arcsin : sin |r π2 , π2 s 1

r1, 1s Ñ r π2 , π2 s

arccos : cos |r0,πs 1

7.3

r1, 1s Ñ r0, πs arcsin x arccos x π2

arcsin1 x √

1

1 x2 1 arccos1 x √ 1 x2

Formules van Stirling en Wallis

Veelvoorkomende integralen, nodig voor de stelling van Wallis: (+Bewijs)

Z

Z

π 2

cos2n

0

π 2

cos2n

1

0

2n 1 2n 3 34 12 π2 2n 2n 2 2n 2n 2 42 2n 1 2n 1 53

Stelling van Wallis: (+Bewijs) r

1 n

1 2

Stelling van Stirling: De rij

π

21 43 65 2n2n 1 √1nπ

n!en

is strikt dalend en convergent naar n √ n Voor grote waarden is dan ook n! 2πn ne . (+Bewijs)

7.4

n

1 2

√

2π.

Praktische integratietechnieken

Men kan integreren mits kennis van bekende integraaltypes, partiële integratie, substitutie en splitsen in partieelbreuken. Bekende belangrijke onbepaalde integralen

De meeste verondersteld gekend Bij |x|: correct afleiden, vermenigdvuldigen met het teken Z dx 1 2 tan x Z sin x dx x arg tanhpcos xq ln tan 2 Z sin x dx x π arg tanhpsin xq ln tan cos x 2 4

13

|x | . x

afg

h

sin x

cos x

tan x

cos x

sin x

1 cos2 x

cosh x

sinh x

1 cosh2 x

√

arc arg

√

h

x2

√

1

√

1

1 1 x2

1

1

1 x2

1

x2

1 1

1 x2

x2 1

Alles is op te lossen Stelling: Alle integralen van rationale functies kunnen uitgedrukt worden d.m.v. rationale, ln en arctan. (+Bewijs: deling, splitsen in partieelbreuken) Stelling: De volgende functies kunnen door substituties herleid worden tot rationale integranda: (+Bewijs) q

b qdx Rpx, k ax √ cx d 2 Rpx, ax bx

Exponenti¨ ele

veelterm

Stelling: Het gedrag van namelijk (+Bewijs) Z

exp veelterm van n-de graad is te voorspellen,

R

e P pxqdx e µx

Rpeax qdx cqdx Rpsin x, cos xqdx

µx

cn n x µ

termen van lagere graad

Eerstegraadsdifferentiaalvergelijkingen met gescheiden veranderlijken g pypxq q yp1 xq

fpxq

dy Gemakkelijk op te lossen door y 1 pxq dx , waaruit g py qdy f pxqdx of zelfs R R g py qdy f pxqdx C. Eventuele beginwaarden invullen om C te bepalen.

14

8

Complexe reeksen

8.1

Twee aanvullingen over rijen

8.1.1

Boven- en onderlimiet

Vanaf nu 2 getallen i.p.v. 1 associëren met begrensde rij, waarvoor L1 ε xn L2 ε. Constructie: Dalende rij van suprema: sup{x1 , x2 , x3 , . . .} sup{x2 , x3 , . . .} sup{x3 , . . .} lim : lim sup xk inf sup xk Ñ 8 nÑ 8 k¥n nPN k¥n

n

lim : lim inf xk

Ñ 8

n

Ñ 8 k ¥n

n

sup kinf x ¥n k P

n N

Stelling (Hoofdeigenschap): (+Bewijs)

@ε P R, DN P N, @n ¡ N : xn limnÑ 8 ε Stelling: een rij is conv plim Lq ô lim lim L. (+Bewijs)

Rekenregeltjes voor lim en lim (+Bewijs) 8.1.2

Convergentie van complexe rijen

De theorie voor reële rijen kan uitgebreid worden naar complexe, alleen voor het kenmerk van Cauchy is nodig: ¯ p0, Rq heeft een Stelling van de convergente complexe deelrij: elke rij uit B ¯ p0, Rq (+Bewijs) convergente deelrij Ñ z0 P B Driehoeksongelijkheid voor complexe getallen: || z1 | |z2 || ¤ |z1 z2 | ¤ |z 1 | | z 2 |

8.2

Convergentie van complexe reeksen

Definitie en onderscheid tussen rij, reeks, reekssom. P conv ô sn Stelling: Een reële reeks xn , xn ¥ 0 div ô sn P Stelling: zn conv ñ zn Ñ 0 (+Bewijs)

De Xcomplexe meetkundige reeks ρn

¥

n 0

n 0

ô |ρ| 1 (+ Bewijs) 1 (+ Bewijs) ρn 1ρ

1

ρ

conv

8 X

ρ2

...

ρn1

11ρρ

n

15

¤M ¥M

(+Bewijs)

Stelling (Grote convergentieregel van Cauchy): (+Bewijs) X

ô |zn

zn conv

1

zn

2

...

zn

p

| ε als n ¡ N en p P N

Absolute convergentie: als |zn | ook conv is. Stelling: Haken plaatsen is OK, weglaten of verplaatsen niet (+Bewijs) Omschikking: termen van plaatsen veranderen, elke term an juist 1 in P reeks bn . Stelling: Omschikking heeft geen invloed op convergentie en reekssom van absoluut convergente reeksen. (+Bewijs)

8.3

P

Convergentieregels voor re¨ ele reeksen zonder negatieve termen

8.3.1

Drie convergentieregels door vergelijking P

Majoratie: xn wordt gemajoreerd door 1 K xn vanaf een zeker rangnummer. Stelling (Majorantenregel): (+Bewijs) X

xn

!

X

x1n ,

X

x1n conv

Stelling (Quoti¨ entregel): (+Bewijs) xn lim nÑ 8 yn

APR

0 0

P

x1n , of

ñ

X

P x conv P n

yn conv

P

xn

! P x1n als xn ¤

xn conv.

P ôP yn conv ñ xn conv

Stelling (Vergelijking van groeisnelheid): (+Bewijs) xn 1 xn 8.3.2

¥ yny

1

vanaf zeker rangnummer:

n

X

xn conv

ñ

X

yn conv

Vier grote convergentieregels

Stelling (Integraaltest van Cauchy): f dalend en naar beneden begrensd s : partieelsom functiewaarden met n In : integraal van f van 1 tot n. ñ De verschilrij psn Inq is dalend en convergent naar lim P rondergrens, f p1qs. ñ Pn¥1 f pnq conv ô In conv. (+Bewijs) De hyperharmonische reeks X

n1p n¥0

Toepassing integraaltest: conv ô p ¡ 1 (+ Bewijs) X 1

De harmonische n is divergent en stijgt zo vlug als ln x. n¥0 16

X

Voor n groot genoeg is n1 ln x γ n¥0

γ 0.5772 de constante van Euler Uitbreiding van bovenlimiet: kan ook 8 zijn als reeks onbegrensd is. Stelling (Worteltest van Cauchy): (+Bewijs) limnÑ

√ n

8 xn

1 ¡1

P x conv P n

xn div en xn

Û0

Stelling (Convergentieregel van D’Alembert): (+Bewijs)

Ñ

n

xn 1 8 xn

lim

1 ¡1

P x conv P n

xn div en xn

Û0

Stelling (Convergentieregel van Raabe): (+Bewijs)

xn lim n nÑ 8 xn 1

1

¡1 1

P x conv P n

xn div

De laatste drie convergentieregels hebben absolute varianten voor convergentie van complexe reeksen. Vervang xn door |zn |.

8.4

Convergentie van re¨ ele wisselreeksen

Stelling (Kenmerk van Leibniz voor wisselreeksen): (+Bewijs) p 1 ¡ p2 pn Ñ 0

9

)

¡ ... ñ

wisselreeks p1 p2 p3 . . . convergent en reekssom tussen twee opeenvolgende partieelsommen.

Gelijkmatige convergentie

9.1

Gelijkmatige convergentie van rijen van functies

Puntsgewijze convergentie

van functies:

A @z P A : fnpzq Ñ f pzq notatie: fn Ñ f @z P A : @ε ¡ 0 : DNz,ε P N : @n P N : n ¥ Nz,ε ñ |fnpzq f pzq| ε  π  x¡0  2 R 0 x 0 De limietfunctie is niet continu. Voorbeeld: arctan nx Ñ   π x 0 2

17


van functies (notatie fn

Ñ f ): A

@ε ¡ 0 : DNz,ε P N : @z P A :@n P N : n ¥ Nz,ε ñ |fnpzq f pzq| ε ra,bs

Ñ f , elke beperking f {r

Stelling (Overdracht van continu¨ıteit): fn continu ñ f {ra,bs continu. (+Bewijs)

n

Stelling (Omwisselen limiet en integraal): fn en b (+Bewijs) Z

gn pxq dan gn

lim

Ñ 8

n

9.2

x0

ra,bs

Ñ g, of

x

Z

x

x0

fn ptqdt

fn ptqdt

g pxq

Z

x

Z

x

x0

ra,bs

Ñ f, x en x

0

s

a,b

tussen a

f ptqdt

lim fn ptqdt Ñ 8

x0 n

Gelijkmatige convergentie van reeksen van functies

Reeks van functies: f1 Puntsgewijze conv

sn

f2

f3

...

P

A Ñ f @ z : f pz q

fn met sn

8 X

f1

...

fn

fn pz q over A

n 1

Gelijkmatige conv

sn

Ñf A

@ε . . . : f pzq

8 X

fn pz q gelijkmatig over A

n 1

P

R

Eveneens overdracht van continu¨ıteit en omwisselen en . P Stelling (M-test van Weierstrass): fn complexe functiereeks (+Bewijs)

Dan : fnpzq ¤ an @z ^

X

an conv

ñ

X

fn gelijkmatig convergent

ñ om de gelijkmatige convergentie van reeksen van functies na te gaan. 10

Complexe machtreeksen

10.1

Puntsgewijze convergentie

Een machtreeks is een oneindige som van de vorm n¥80 an z n waarbij an constanten zijn en z complex of reëel kan zijn (dan meestal x). Dit is een speciaal geval omdat, in de punten (z) waarvoor deze reeksen convergent zijn, ze absoluut1 convergent zijn. De punten z liggen in een schijf in het complexe vlak van Gauss. P

1

Uitzondering: dit geldt niet voor punten met modulus gelijk aan de convergentiestraal

18

De convergentiestraal R :

P r0, 8s

1 lim

Ñ 8

n

q n

|an|

R wordt de convergentiestraal genoemd en B p0, Rq de convergentieschijf. Stelling: (+Bewijs) R0 ñ Pn¥80 anzn alleen convergent voor z 0 P 8 n absoluut convergent voor |z | R 0 R 8 ñ n¥0 an z niet convergent voor |z | ¡ R R8 ñ Pn¥80 anzn over heel C convergent Stelling: De convergentiestraal van bestaat (+Bewijs) Stelling: an begrensd ñ R ¥ 1 en

8 ¥

P

n 0 an z

an

n

is limnÑ

8 anan 1 als die

Û 0 ñ R ¤ 1 (+Bewijs)

Termsgewijze afgeleide van een machtreeks

8 X ¥

an z n :

n 0

8 X ¥

an nz n1

n 1

Stelling: Een complexe machtreeks en haar termsgewijze afgeleide hebben dezelfde convergentiestraal (+Bewijs) n n b a n Hulpstelling: ba na 1 ¤ |b a|rn2 npn21q (+Bewijs) Stelling: De afgeleide van de limietfunctie is de limietfunctie van de termsgewijze afgeleide. (+Bewijs) Stelling: De reekssom van een complexe machtreeks is P C 8 (+Bewijs) Stelling: Het kan niet anders dan dat de coëfficiënten er als volgt uitzien: (+Bewijs) 8 X f pnq p0q f pz q an z n ñ an n! n0 Termsgewijze integratie van een r

8 X ¥

an z n :

n 0

8 X ¥

n 0

an

zn 1 n 1

Stelling: Voor reële x geldt: (complexe integratie is complex) (+Bewijs) Z

0

10.2

x

8 X

n 0

an t

n

!

dt

8 X

n 0

an

xn 1 n 1


¯ p0, rq Stelling: Complexe machtreeksen convergeren gelijkmatig over elke B B p0, Rq. (+Bewijs) Wat met randpunten? Voor reële machtreeksen wordt in de cursus het trio van Abel bewezen voor R 1 en x 1. 19

Stelling (Ongelijkheid van Abel): Als p1 willekeurige complexe getallen: (+Bewijs)

|p1C1

p2 C2

...

¥ p2 ¥ . . . ¥ pN ¥ 0 en C 1s

pN CN | ¤ p1 max{|C1 |, |C1

C2 |, . . . , |C1

. . . C N |}

Stelling (Convergentiestelling van Abel): Een reële machtreeks die conv is in x R 1, is gelijkmatig convergent over r0, 1s. (+Bewijs) Stelling (Limietstelling van! Abel): Als reekssom conv in x 1, dan is de reekssom daar limxÑ1

10.3

8 X

8 X

an

gelijk aan de limiet voor de limietfunctie

n 0

an xn (+Bewijs)

n 0

Taylorontwikkelingen f pxq a0

a2 x2

a1 x

an xn

...

@x P I

...

De oneindige veelterm uit het rechterlid is de Taylorontwikkeling van f . pnq De coëfficiënten an zijn uniek bepaald, namelijk, f n!p0q . Uit de meetkundige reeks 1 1

x

1x

Dit wordt gewoon bekomen door in

x2 x3

8 X

...

q n in te vullen q

n 0 1 1 x2

en lorberekeningen. Analoog worden door termsgewijze integratie arctan x, lnp1

x, dus geen Tay-

1 1 x2

bekomen. Hieruit vloeien xq, arg tanh x.

Uit de formule van Taylor Stelling (Formule van Taylor): Als n geldt @x P I : (+Bewijs) f pxq f p0q xf 1 p0q x2 en Dξ

P r0, xs of rx, 0s :

f pxq f p0q

PN

,

I

f 2 p0q f pn1q p0q . . . xn1 2 pn 1q!

xf 1 p0q

x2

f 2 p0q 2

...

xn1

Q 0, Z

0

x

f

P C npI q, dan

px tqn1 f pnqptqdt pn 1q!

f pn1q p0q pn 1q!

xn

f pnq pξ q pnq!

Hierin is bovenaan de integraalgedaante van de restterm uitgedrukt en onderaan de restterm van Lagrange. 20

Stelling (Voldoende voorwaarde voor Taylorontwikkeling): De gehele oneindige ontwikkeling valt pas samen met f pxq over ]a, a[ als: f P C 8 ]a, a[ f pnqpxq ¤ G p@n P N, @x P ]a, a[q (+Bewijs) Stelling: De volgende Taylorontwikkelingen voldoen aan de voldoende voorwaarde over gans R. (+Bewijs) sin x

x

cos x

1

x3 3! x2 2!

ex

1

x

sinh x

x

cosh x

1

x5 5! x4 4!

... ...

x2 x3 ... 2! 3! x3 x5 ... 3! 5! x2 x4 ... 2! 4!

Uit de binomiaalreeks Stelling: Voor α, ook

p1

xqα

1

αx

P R\N geldt @x P ]1, 1[: (+Bewijs) αpα 1q 2 αpα 1q . . . pα n x ... 2

n!

1q

xn

...

Stelling: Als α ¡ 0, ook voor 1 ¤ x ¤ 1 conv, absoluut en gelijkmatig in [1, 1]. (+Bewijs) Hieruit kunnen we (met α 21 ) de ontwikkeling afleiden voor √11 x , en zo ook

ÝÑ √11x ÝÑ arcsin x ÝÑ arccos x en arg sinh x.

11

2

Fourierreeksen

Startvraag: kan iedere f ontwikkeld worden in sinussen en cosinussen?

11.1

De Singuliere Integraal van Dirichlet

Stelling (Hulpstelling van Riemann): Als f integreerbaar is over [a, b]: (+Bewijs) lim

Ñ 8

λ

Z

b

a

f pxq sin λx dx 0

DEF f is stuksgewijze Lipschitzcontinu over [a, b] met een partitie π als DC ¡ 0 : |f pxq f px1 q| ¤ C |x x1 | voor alle x en x1 binnen eenzelfde deelinterval van π. Stelling: Als stuksgewijze Lipschitzcontinu, dan: (+Bewijs) 21

Gelijkmatig continu in ieder deelinterval

f pa q, f pbq, f pxq, f px q bestaan voor alle x.

Integreerbaar

Stelling: Onderstaande schrijfwijzen van Dk (kernfunctie van Dirichlet) zijn gelijk. (+Bewijs) 1 π

1 2

cos x

cos 2x

...

cos kx





1 1  sin k 2 x  2π sin x2

Stelling (De Singuliere Integraal van Dirichlet of de zeefeigenschap): (+ Niet vanzelfsprekend bewijs) f stuksg. L-continu over [π, π] ñ lim k

11.2

Z

π

Ñ 8 π

f Dk

f p0 q 2 f p0q

Convergentie van Fourierreeksen

De Fourierreeks van f is de reeks a0 X an cos nx 2 n¥1

bn sin nx

waarbij an : π1 R ππ f puq cos nu du en bn : π1 ππ f puq sin nu du. Wanneer zal de Fourierreeks nu conv Ñ f ? Stelling (Convergentiestelling van Fourrierreeksen voor periodieke functies): Als f stuksgewijze Lipschitzcontinu is over [π, π] en f is 2πperiodiek, dan geldt @x: (+Bewijs, niet simpel) R

a0 2

8 X

bn sin nx

an cos nx

f px

q

f pxq

2

n 1

Als f stuksgewijze Lipschitzcontinu is: DEF f π is de periodieke uitbreiding van f Ñ f {[π,π] voortgezet met periode 2π. DEF f π,ν is de genormaliseerde periodieke uitbreiding van f Ñ @x P R : f px q 2 f pxq . ñ Convergentiestelling van Fourrierreeksen voor periodieke func-

ã

ã

ties: a0 2

8 X

an cos nx

bn sin nx f π,ν

n 1

Uitbreiding: met [L, L] ipv [π, π]. bn an

a0 2

1 L

X

¥

Z

L

L

f puq sin nu cos

an cos nx

n 1

22

π L

π du L

bn sin nx

π L

12 12.1

Lineaire differentiaalvergelijkingen en stelsels Lineaire differentiaalvergelijkingen van de eerste orde y 1 pxq

apxqy pxq

apxqy pxq

y 1 pxq

Rpxq 0

De laatste vergelijking is de homogene gedaante van de eerste. Stelling (Bestaan en enigheid): Als U een open interval is dat x0 bevat, met a en R continue functies over U en α P R, dan heeft y 1 pxq

apxqy pxq Rpxq,

y px0 q α

juist 1 oplossing over U , namelijk: (+Bewijs) ϕ e

R

a

c

Z

R

Re

a

Stelling: Als de oplossing van de homogene een nulpunt heeft over U , dan is ze daar identisch 0. (+Bewijs)

12.2

Lineaire differentiaalvergelijkingen van de tweede orde, veranderlijke co¨ effici¨ enten

De homogene vergelijking y2

ay 1

by

0

Hierin zijn a en b reële functies die afhangen van x, maar genoteerd a en b ipv apxq en bpxq. ϕ1 en ϕ2 kunnen twee oplossingen zijn, dan wordt de functie W pϕ1 , ϕ2 q gedefinieerd als

ϕ 1 ϕ2 . ϕ11 ϕ12

Stelling: Als W pϕ1 , ϕ2 q een nulpunt heeft, dan 0. (+Bewijs) DEF ϕ1 en ϕ2 zijn twee onafhankelijke oplossingen als W pϕ1 , ϕ2 q 0 in heel het interval. Hulpstelling: (+Bewijs) convergeert puntgew. in heel U f Jf J 2 f J 3 f . . . conv. gelijkmatig in elk compact interval K Q x0 voor If pxq :

Z

x

x0

f ptq dt,

Jf pxq : apxqIf pxq bpxq (I pIf q) pxq

23

Stelling: Een stel onafhankelijke oplossingen van y 2 gegeven door: (+Bewijs) ϕ1

1 I2

8 X

8 X

ay 1

by

0 wordt

J nb

n 0

ϕ2

ı I2

J n pa

bıq

n 0

Stelling (Verlaging van de orde): Als ϕ1 een nulpuntloze oplossing, dan wordt een tweede oplossing ϕ2 , onafhankelijk van ϕ1 , gegeven door: (+Bewijs) Z 1 R ϕ2 ϕ1 ϕ21 e a Stelling (Bestaan en(enigheid): De vergelijking y 2 ay 1 y px0 q α , namelijk (+Bewijs) juist 1 oplossing voor y 1 px0 q β c1 ϕ1

by

0 heeft

c1 ϕ2

Stelling: Oplossing ϕ van de homogene met afgeleide en waarde tegelijk 0 ñ ϕ 0 over U . (+Bewijs) Stelling: ϕ1 , ϕ2 onafhankelijke oplossingen ñ {c1 ϕ1 c2 ϕ2 |c1 , c2 P R} is de gehele oplossingenverzameling. (+Bewijs) De niet-homogene vergelijking y2

ay 1

by

R

Waarbij R geschreven wordt voor Rpxq, een continue functie over U . Verrassend feit: Stelling (Variatie van de constanten): Als ϕ1 en ϕ2 onafh oplossingen zijn van de homogene, wordt een oplossing van de niet-homogene gegeven door (+Bewijs) ψ

ϕ2

Z

ϕ1 R W pϕ 1 , ϕ 2 q

ϕ1

Z

ϕ2 R W pϕ1 , ϕ2 q

Stelling (Bestaan en(enigheid): De vergelijking y 2 ay 1 y px0 q α juist 1 oplossing voor , namelijk (+Bewijs) y 1 px0 q β c1 ϕ1 Stelling: {c1 ϕ1 (+Bewijs)

c2 ϕ2

ψ |c1 , c2

c1 ϕ2

by

R heeft

ψ

P R} is de gehele oplossingenverzameling. 24

12.3

Lineaire differentiaalvergelijkingen van de tweede orde, constante co¨ effici¨ enten

De homogene vergelijking y2

py 1

qy

0

x2 px q wordt de kenmerkende drieterm genoemd. De exponentiële van een complex getal wordt gedefinieerd als ea

ib

: ea pcos b

i sin bq, zodat eλx

1

λeλx

Stelling: De oplossingenverzameling is afhankelijk van de nulpunten van de karakteristieke drieterm en wordt gegeven door: (+Bewijs) 2x reëel Ñ opl {eλ1x, eλ2x} 2 Nulptn van x px q : toeg. complex Ñ opl {eax cos bx, eax sin bx} dubbelwortel Ñ opl {eλx, xeλx} De niet-homogene vergelijking y2

py 1

qy

R

Analoog als bij de veranderlijke coëfficiënten: als ϕ1 en ϕ2 gekend zijn (evt. ϕ2 berekenen door verlaging van de orde), dan kan ψ gevonden worden door variatie van de constanten. In een speciaal, maar veelvoorkomend geval kan R R ϕ2 R ϕ1 R ψ zelfs gevonden worden zonder ϕ2 W pϕ1 ,ϕ2 q ϕ1 W pϕ1 ,ϕ2 q , namelijk als R van de vorm is eax (C pxq cos bx S pxq sin bx) of als de constanten ook complex mogen zijn:

ecx c0

c2 x2

c1 x

cN xN

...

De oplossingen worden door twee stellingen gegeven, de complexe hulpstelling en de reële variant. De oplossingen zijn afhankelijk van c, die al dan niet een wortel is van de kenmerkende drieterm. Stelling: De oplossingen van y2

py 1

qy

ecx

c0

worden gegeven door: (+Bewijs) c is geen wortel Ñ opl ecx d0 c is enkelv wortel

c is dubbelwortel

Ñ Ñ

d1 x

opl xecx d0

opl x2 ecx d0

ecx

c2 x2

c1 x

2

c0 x2

25

...

d1 x d1 x 3

c1 x6

...

...

cN xN

dN xN

dN xN

...

dN xN

...

cN pN

xN 2 1 N 2

qp

q .

De volgende stelling is de reële versie van de voorgaande stelling, en verloopt vrij analoog. Stelling (Onbepaalde co¨ effici¨ enten): De oplossingen van y 2 py 1 qy ax e (C pxq cos bx S pxq sin bx) worden gegeven door: (+Bewijs) a ib is geen wortel Ñ opl eax (C0pxq cos bx S0pxq sin bx) a ib is enkelv wortel Ñ opl xeax (C0 pxq cos bx S0 pxq sin bx) a is de dubbelwortel Ñ opl eax (2x ge¨ıntegr van C pxq van 0 Ñ x)

Waarbij C0 pxq en S0 pxq veeltermen zijn met max{grC0 , grS0 } max{grC, grS}

12.4   y11 x     y21 x

Stelsels lineaire differentiaalvergelijkingen van de eerste orde, constante co¨ effici¨ enten

pq pq

     y1 x n

pq

a11 y1 pxq a21 y2 pxq an1 yn pxq

a12 y2 pxq a22 y2 pxq .. .

an2 y2 pxq

... ...

a1n yn pxq R1 pxq, a2n yn pxq R2 pxq,

y1 px0 q α1 y2 px0 q α2 .. .

...

ann yn pxq Rn pxq, yn px0 q αn

Dit kan in matrixnotatie geschreven worden, met A een reële n n-matrix en alle ~ kolommatrices: y 1~pxq

Ay p~xq R~pxq,

y p~x0 q α ~

Stelling: De oplossing van voorgaand stelsel is, mits de juiste definitie voor exponentiële van een matrix en voor de hand liggende definities: (+Bewijs)

Z

ϕp~xq eAx ~c

26

eAx R~pxq dx

terug

37

Algebra¨ısche Structuren

K. Dekimpe, KULeuven Kulak

Stelling 1.4.2: De verzameling van de complexe getallen is algebra¨ısch gesloten. Dit wil zeggen dat elke veelterm van de vorm an xn + an−1 xn−1 + · · · + a1 x + a0 waarbij n ∈ N0 , a0 , a1 , . . . an ∈ C met an 6= 0, een wortel heeft in C. Opmerking: men kan hieruit zelfs afleiden dat er exact n wortels zijn, waarvan sommige echter meervoudig kunnen zijn. Deze bewering wordt heel precies gemaakt in de cursus Algebra I.

5

Toepassing Complexe getallen vinden hun toepassing binnen verschillende domeinen van de wiskunde (en daarbuiten). Om dit te illustreren geven we de volgende meetkundige toepassing.

Voorbeeld:

Zij o een punt in het vlak en L een rechte door o. Onderstel dat α een rotatie is over een hoek θ (in tegenwijzerzin) met centrum o en dat β de spiegeling door de rechte L voorstelt. Dan geldt: β ◦ α = α−1 ◦ β. (waarbij α−1 de inverse is van de rotatie α, met andere woorden, α−1 is de rotatie over θ graden in wijzerzin). Om bovenstaande bewering aan te tonen, kiezen we een orthonormaal assenstelsel in het vlak waarbij de x-as samenvalt met de rechte L en de oorsprong met het punt o. We beschouwen het vlak als zijnde het complexe vlak. De rotatie α komt dan precies neer op vermenigvuldiging met eiθ en spiegeling door de rechte L is dan hetzelfde als het nemen van de complex toegevoegde. Om bovenstaande bewering aan te tonen is het met andere woorden voldoende om na te gaan dat ∀z ∈ C : eiθ z = ei(−θ) z. Dit is eenvoudig na te gaan, daar eiθ z = eiθ z = ei(−θ) z, waardoor de bewering aangetoond wordt.

11

z eiθ z θ

θ e−iθ z

z

= eiθ z

6

De quaternionen van Hamilton Alhoewel de complexe getallen algebra¨ısch gesloten zijn en vanuit algebra¨ısch standpunt dus een uitstekende getallenverzameling vormen, bestaat er toch nog een uitbreiding van C die regelmatig gebruikt wordt. De elementen van deze nieuwe verzameling worden de quaternionen van Hamilton genoemd. Net zoals je de verzameling C bekomt door het invoeren van een extra getal i, bekomen we nu de quaternionen door het invoeren van drie extra getallen i, j en k die aan de volgende rekenregels voldoen: i2 = j 2 ij = k, jk = i, ki = j,

= k 2 = −1 ji = −k kj = −i ik = −j

De verzameling van de quaternionen H bestaat dan uit alle sommen van de vorm a + bi + cj + dk met a, b, c, d ∈ R. We kunnen met deze getallen rekenen op een analoge manier als we dit bij de complexe getallen gedaan hebben:

12

Voorbeeld:

We berekenen (1 + i)(i + j + k) = i + j + k + i2 + ij + ik = i+j+k−1+k−j

= −1 + i + 2k en eveneens

(i + j + k)(1 + i) = i + j + k + i2 + ji + ki = i+j+k−1−k+j

= −1 + i + 2j.

Merk op dat de volgorde waarin we elementen met elkaar vermenigvuldigen een rol speelt. We zullen later zeggen dat de vermenigvuldiging niet commutatief is.

Oefeningen: 1. Bereken (a + bi + cj + dk)(a − bi − cj − dk) (waarbij a, b, c, d ∈ R). 2. Wat is het invers van a + bi + cj + dk (indien a, b, c, d ∈ R niet allemaal 0 zijn)?

13

Hoofdstuk 2

Inleiding tot de groepentheorie 1

De basisdefinities Een algebra¨ısche structuur bestaat vaak uit een verzameling waarop één of meerdere bewerkingen gedefinieerd zijn. Het is bijgevolg noodzakelijk om eerst het begrip van een (inwendige) bewerking goed te omschrijven.

Definitie: Inwendige bewerking

Een inwendige bewerking (of samenstelling) ∗ op een verzameling A is een functie ∗ : A × A → A : (a, b) 7→ ∗ (a, b) .

We schrijven ook a ∗ b = ∗ (a, b) . Indien het definitiegebied van ∗ samenvalt met A × A dan zeggen we dat de inwendige bewerking overal bepaald is.

Voorbeeld: 1. + is een inwendige en overal bepaalde bewerking op N: + : N × N → N : (n, m) 7→ +(n, m) = n + m. 2. − is een inwendige, maar niet overal bepaalde bewerking op N: − : N × N → N : (n, m) 7→ −(n, m) = n − m Het definitiegebied van − is {(n, m) ∈ N × N | n ≥ m}. Binnen de wiskunde zijn niet alleen inwendige bewerkingen interessant, maar er worden ook andere bewerkingen gedefinieerd. Denk maar aan de (uitwendige) scalaire vermenigvuldiging in een vectorruimte R, V, + waarbij een vector ~v vermenigvuldigd wordt met een getal r ∈ R. Of denk maar aan het scalair product, dat met twee vectoren ~v en w ~ een reëel getal laat overeenkomen. Dergelijke niet-inwendige bewerkingen komen niet aan bod in deze cursus.

14

Definitie: groep

associatief

Een groep is een verzameling G die voorzien is van een inwendige bewerking ∗ : G × G → G, waarbij voldaan is aan de volgende 4 eigenschappen: (1) De bewerking ∗ is overal bepaald, m.a.w. x ∗ y bestaat voor willekeurige x, y ∈ G. (2) De bewerking ∗ is associatief: ∀x, y, z ∈ G : (x ∗ y) ∗ z = x ∗ (y ∗ z).

neutraal element

M.a.w. de plaats waar de haakjes staan heeft geen belang, een uitdrukking van de vorm x ∗ y ∗ z heeft dus een ondubbelzinnige betekenis. (3) G, ∗ heeft een neutraal element e: ∃e ∈ G : ∀x ∈ G : x ∗ e = e ∗ x = x.

invers element

(4) Elk element x van G heeft een invers element: ∀x ∈ G : ∃y ∈ G : x ∗ y = y ∗ x = e. We noteren een groep meestal door G, ∗.

Definitie: commutatief of abels

Een groep G, ∗ is commutatief (of abels) indien ∀x, y ∈ G : x ∗ y = y ∗ x. Opmerking: Indien we te maken hebben met een commutatieve groep, noteren we vaak de bewerking door middel van een + i.p.v. een ∗. (We houden hierbij de groepen Z, +, Q, +, R, +, . . . (zie volgend onderdeel) in gedachten). We zeggen dan dat de groep additief genoteerd wordt (in plaats van multiplicatief bij de ∗-notatie).

Oefening: We beschouwen de bewerkingen +, −, max en min op de verzameling Z. De bewerking max is als volgt gedefinieerd: max : Z × Z → Z : (a, b) 7→

(

a als a ≥ b b als b > a

Analoog wordt min(a, b) = a min b gedefinieerd als het minimum van de getallen a en b. Onderzoek aan welke van de 4 eigenschappen van het groep-zijn deze bewerkingen voldoen.

Stelling 2.1.1: In een groep G, ∗ is er precies één neutraal element. 15

Bewijs: Onderstel dat e en e0 beide neutrale elementen in de groep G, ∗ zijn, dan geldt e = e ∗ e0 want e0 is een neutraal element = e0 want e is een neutraal element

2 Deze eigenschap laat ons dus toe om te spreken van het neutraal element van een groep G, ∗. We zullen meestal e of eG gebruiken om het neutraal element van een groep G, ∗ aan te duiden. Bij het gebruik van de additieve notatie bij een commutative groep G, + noteert men dit neutraal element vaak als 0.

Stelling 2.1.2: In een groep G, ∗ heeft elk element x precies één invers element, m.a.w. ∀x ∈ G : ∃!y ∈ G : x ∗ y = y ∗ x = e. Bewijs: Onderstel dat y en y 0 beide inversen zijn van x (dus x ∗ y = y ∗ x = e = x ∗ y 0 = y 0 ∗ x), dan geldt: y = y ∗ e want ...

= y ∗ (x ∗ y 0 ) want ...

= (y ∗ x) ∗ y 0 want ... = e ∗ y 0 want ... = y 0 want ...

2 We kunnen dus spreken van het invers element van een gegeven element x ∈ G. We noteren dit dan ook vaak als x−1 (of als −x indien de groep additief wordt geschreven).

Stelling 2.1.3: Zij G, ∗ een groep, dan geldt ∀x, y ∈ G dat (x ∗ y)−1 = y −1 ∗ x−1 en (x−1 )−1 = x. Bewijs: (x ∗ y) ∗ (y −1 ∗ x−1 ) = x ∗ (y ∗ y −1 ) ∗ x−1 = x ∗ e ∗ x−1 = x ∗ x−1 = e en (y −1 ∗ x−1 ) ∗ (x ∗ y) = y −1 ∗ (x−1 ∗ x) ∗ y 16

= y −1 ∗ e ∗ y = y −1 ∗ y = e.

Dat (x−1 )−1 = x is triviaal aan te tonen. 2 Door de voorgaande eigenschappen zijn de volgende notaties in een groep G, ∗ geoorloofd: −n = (xn )−1 = (x−1 )n x0 = e, ∀n ∈ N0 : xn = x | ∗ x ∗{z· · · ∗ x} en x n keer x

of in additieve notatie voor een abelse groep G, +:

0x = 0, ∀n ∈ N0 : nx = |x + x + · · · + x} en (−n)x = −(nx) = n(−x) {z n keer x

In de additieve situatie gebruiken we ook x − y om x + (−y) aan te duiden.

2

Enkele bekende groepen 1. Ga na dat Z, +, Q, +, R, +, C, +, R0 , ·, C0 , · en R+ 0 , · commutatieve groepen zijn. 2. R2 , + is een commutatieve groep. Herinner u dat R2 = {(a, b) | a, b ∈ R} en dat de bewerking + componentsgewijs gedefinieerd is: + : R2 × R2 → R2 : ((a, b), (c, d)) 7→ (a, b) + (c, d) = (a + c, b + d). Op analoge wijze kunnen we de groepen Rn , + en Cn , + invoeren. 3. W, · = {z ∈ C | |z| = 1}, · is een commutatieve groep voor de vermenigvuldiging van de complexe getallen. 4. Met R[x] noteren we de verzameling van alle veeltermen in de veranderlijke x met coëfficiënten in R, dus R[x] = {a0 + a1 x + a2 x2 + · · · + an xn | n ∈ N en ∀i ∈ {0, 1, . . . , n} : ai ∈ R} R[x], + is een commutatieve groep.

+ Zie hoofdstuk 4 voor een formele invoering van Zn

Cayleytabel

5. De commutatieve groep Z12 , + Z12 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} en + is “optelling van uren”, dus o.a.: 7 + 3 = 10, 7 + 4 = 11, 7 + 5 = 0, 7 + 6 = 1, 7 + 7 = 2, . . . Analoog definieert men voor elk natuurlijk getal n ≥ 2 een groep Zn , + met n elementen. Als voorbeeld geven we hier de samenstellingstabel of Cayleytabel voor de groep Z7 , +: 17

+ 0 1 2 3 4 5 6

0 0 1 2 3 4 5 6

1 1 2 3 4 5 6 0

2 2 3 4 5 6 0 1

3 3 4 5 6 0 1 2

4 4 5 6 0 1 2 3

5 5 6 0 1 2 3 4

6 6 0 1 , waarbij o.a. 4 + 2 = 6. 2 3 4 5

Soms noteert men de elementen van Zn , + als getallen met een streepje erboven, dit om onderscheid te maken met de gewone gehele getallen. Op die manier schrijven we dus Z7 = {¯0, ¯1, ¯2, ¯3, ¯4, ¯5, ¯6}. 6. Zij X een willekeurige verzameling. Neem de verzameling SX = {f : X → X | f is een bijectie } van alle permutaties van X (ter herinnering: een permutatie is een bijectie van een verzameling naar zichzelf). Indien ◦ de samenstelling van afbeeldingen voorstelt, dan kan men nagaan dat SX, ◦ een groep vormt.

Neem als voorbeeld X = {1, 2, 3}, dan heeft SX 6 elementen die we voorstellen in de onderstaande figuren: 1

1 3

3

3

2

2

2

t(12)

c1

1

c2

1 3

2

t(13)

t(23)

1X 1

1 3

3

2

2

De Cayleytabel van deze groep wordt: ◦ 1X c1 c2 1X 1X c1 c2 c1 c1 c2 1X c2 c2 1X c1 t(12) t(12) t(23) t(13) t(13) t(13) t(12) t(23) t(23) t(23) t(13) t(12)

t(12) t(12) t(13) t(23) 1X c1 c2

t(13) t(13) t(23) t(12) c2 1X c1

t(23) t(23) t(12) t(13) c1 c2 1X

In de bovenstaande tabel hebben we twee elementen aangeduid, daardoor zien we dat t(13) = c1 ◦ t(12) en t(23) = t(12) ◦ c1 . 18

symmetrische groep

Dit toont aan dat de groep S{1, 2, 3}, ◦ niet commutatief is. Deze groep wordt verkort als S3 , ◦ genoteerd. In het algemeen bedoelen we met Sn , ◦ de groep SX, ◦, waarbij X = {1, 2, . . . , n} (Hoeveel elementen heeft Sn ?). Sn wordt de symmetrische groep van graad n genoemd. 7. Beschouw een regelmatige zeshoek in het vlak. Met D6 duiden we alle “starre bewegingen” van het vlak aan die deze 6-hoek op zichzelf afbeelden. D6 bevat 6 rotaties: 1 = rotatie rond o over een hoek van 0◦ graden in wijzerzin. a = rotatie rond o over een hoek van 60◦ graden in wijzerzin. a2 = rotatie rond o over een hoek van 120◦ graden in wijzerzin. a3 = rotatie rond o over een hoek van 180◦ graden in wijzerzin. a4 = rotatie rond o over een hoek van 240◦ graden in wijzerzin. a5 = rotatie rond o over een hoek van 300◦ graden in wijzerzin.

o a

In D6 zitten echter niet alleen rotaties, maar ook spiegelingen door rechten, bekijk bijvoorbeeld de spiegeling b door de rechte B:

B b

We kunnen nu ook a ◦ b berekenen:

19

1

2

b

6

2

1

4

2

64

33

5

3

a

4

a◦b

1

5

6

5

wat de spiegeling door de rechte G oplevert (zie figuur hieronder). Analoog vinden we dat

C a2 ◦ b = a3 ◦ b = a4 ◦ b = a5 ◦ b =

spiegeling spiegeling spiegeling spiegeling

door door door door

B

D

F E D C

E F G

Men kan intu¨ıtief inzien dat de 6 rotaties en de 6 spiegelingen de enige elementen zijn in D6 . De samenstellingstabel van D6 ziet er als volgt uit (we verkorten am ◦ b tot am b): ◦ 1 a a2 a3 a4 a5 b ab a2 b a3 b a4 b a5 b

1 1 a a2 a3 a4 a5 b ab a2 b a3 b a4 b a5 b

a a a2 a3 a4 a5 1 a5 b b ab a2 b a3 b a4 b

a2 a2 a3 a4 a5 1 a a4 b a5 b b ab a2 b a3 b

a3 a3 a4 a5 1 a a2 a3 b a4 b a5 b b ab a2 b

a4 a4 a5 1 a a2 a3 a2 b a3 b a4 b a5 b b ab

a5 a5 1 a a2 a3 a4 ab a2 b a3 b a4 b a5 b b

b b ab a2 b a3 b a4 b a5 b 1 a a2 a3 a4 a5

ab ab a2 b a3 b a4 b a5 b b a5 1 a a2 a3 a4

a2 b a2 b a3 b a4 b a5 b b ab a4 a5 1 a a2 a3

a3 b a3 b a4 b a5 b b ab a2 b a3 a4 a5 1 a a2

a4 b a4 b a5 b b ab a2 b a3 b a2 a3 a4 a5 1 a

a5 b a5 b b ab a2 b a3 b a4 b a a2 a3 a4 a5 1

Deze tabel maakt duidelijk dat ook de groep D6 een niet commutatieve groep is (waaruit blijkt dit?). Diëdergroep

In het algemeen kan men analoog een groep Dn invoeren voor elke n ≥ 3. Deze groep wordt de Di¨ edergroep van graad n genoemd en bestaat uit n rotaties 1, a, . . . , an−1 en n spiegelingen b, ab, . . . , an−1 b. De bewerking ◦ op Dn is volledig bekend door de volgende drie regels die geldig zijn in Dn , ◦: an = 1, b2 = 1 en ba = a−1 b (Zie de toepassing op pagina 11). 20

Oefening: Geef de Cayleytabel voor D3 , ◦. 8. Direct product van groepen. Het is mogelijk om op basis van gekende groepen, nieuwe groepen te construeren. Eén van deze technieken is deze van het maken van het direct product van twee (of meer) groepen.

Definitie: Direct product

Het direct product van twee groepen G, ∗ en H, 3 bestaat uit de verzameling G × H voorzien van de bewerking: 2 : (G × H) × (G × H) → (G × H) : ((g1 , h1 ), (g2 , h2 )) 7→ (g1 , h1 )2(g2 , h2 ) = (g1 ∗ g2 , h1 3h2 ).

Oefening: Toon aan dat G × H, 2 inderdaad een groep is! Opmerking: Indien we voor H, 3 dezelfde groep nemen als G, ∗, noteren we het direct product G × H, 2 als G2 , ∗. In G2 , ∗ hebben we dus dat (g1 , g2 ) ∗ (g3 , g4 ) = (g1 ∗ g3 , g2 ∗ g4 ). Meer algemeen kunnen we op die manier ook Gn , ∗ voor alle n ∈ N0 invoeren.

Voorbeeld:

In Z34 , + hebben we dat

(1, 3, 2) + (1, 2, 2) = (1 + 1, 3 + 2, 2 + 2) = (2, 1, 0).

3

Deelgroepen en nevenklassen Definitie: deelgroep

Zij G, ∗ een groep en H ⊆ G. Dan is H een deelgroep van G, ∗ als en slechts als H, ∗ een groep is.

Voorbeeld: 1. Z, + is een deelgroep van Q, +. 2. R+ 0 , · is geen deelgroep van R, + (waarom?). 3. Z0 , · is geen deelgroep van R0 , · (waarom?). 4. H = {1, a, a2 , a3 , a4 , a5 } is een deelgroep van D6 , ◦. Ook K = {1, b} is een deelgroep van D6 , ◦. De volgende eigenschap oogt misschien heel triviaal, maar moet toch eens vermeld en bewezen worden. 21

Stelling 2.3.1: Zij H een deelgroep van G, ∗, dan geldt het volgende: (1) het neutraal element van H, ∗ is gelijk aan het neutraal element van G, ∗. (2) ∀x ∈ H is het invers van x in H, ∗ gelijk aan het invers van x in G, ∗. Bewijs: Noem eH het neutraal element van H, ∗ en eG dat van G, ∗. We duiden het invers van x in G, ∗ aan door x−1 , terwijl we voor x ∈ H het invers van x in H, ∗ noteren als x ¯. Met deze notaties vinden we dat eH = eH ∗ eH (eH is neutraal in H, ∗) en eH = eH ∗ eG (eG is neutraal in G, ∗) Hieruit verkrijgen we

⇒

⇒

eH ∗ eH −1 eH ∗ (eH ∗ eH ) (e−1 H ∗ eH ) ∗ eH ⇒ eG ∗ eH

⇒ eH

= eH ∗ eG

= e−1 H ∗ (eH ∗ eG ) = (e−1 H ∗ eH ) ∗ eG = eG ∗ eG

= eG want ...

Neem nu x ∈ H, dan geldt x∗x ¯ = eH = x ¯ ∗ x en x ∗ x−1 = eG = x−1 ∗ x. Omdat nu eH = eG is x ¯ ook een invers voor x in G. Door de uniciteit van het invers element verkrijgen we dat x ¯ = x−1 . 2 Aangezien de definitie van een groep bestaat uit vier onderdelen moeten we in principe bij de vraag of een bepaalde H een deelgroep is van G, ∗ deze vier condities nagaan. In de praktijk kan men het werk echter sterk beperken. Dit wordt verklaard door de volgende stelling.

Stelling 2.3.2: “Deelgroepcriterium” Zij H een niet lege deelverzameling van een groep G, ∗, dan zijn de volgende 4 uitspraken equivalent: (1) (2) (3) (4)

H is een deelgroep van G, ∗. ∀x, y ∈ H : x ∗ y ∈ H en x−1 ∈ H. ∀x, y ∈ H : x ∗ y −1 ∈ H ∀x, y ∈ H : x−1 ∗ y ∈ H

Bewijs: We bewijzen deze stelling volgens het schema (1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒ (1) (1) ⇒ (2) Volgt onmiddellijk uit het feit dat H, ∗ een groep is. 22

(2) ⇒ (3) Neem x, y ∈ H. Uit (2) volgt dat ook y −1 ∈ H. Aangezien x ∈ H en y −1 ∈ H volgt nu (wederom (2)) dat x ∗ y −1 ∈ H. (3) ⇒ (4) (a) Neem x ∈ H (H 6= ∅). Uit (3) volgt dat x ∗ x−1 = e ∈ H en dus ook dat e ∗ x−1 ∈ H. (b) Uit (a) weten we dat voor willekeurige x, y ∈ H eveneens x−1 , y −1 ∈ H, waaruit we halen dat x−1 ∗ (y −1 )−1 = x−1 ∗ y ∈ H. (4) ⇒ (1) (a) Analoog als in het vorige geval toont men aan dat e ∈ H en x−1 ∈ H voor elke x ∈ H (doe dit!). (b) Voor willekeurige x, y ∈ H weten we dus dat x−1 en y ∈ H, waaruit volgt dat (x−1 )−1 ∗ y = x ∗ y ∈ H. We kunnen dus besluiten dat ∗ een inwendige overal bepaalde wet is op H. De wet ∗ is associatief (waarom?) en e ∈ H is een neutraal element voor ∗. Bovendien bezit elke x ∈ H een invers element x−1 dat ook tot H behoort. H, ∗ is dus een groep. 2 In additieve notatie kunnen we dus zeggen: Zij H een niet lege deelverzameling van een abelse groep G, +, dan is H een deelgroep van G, + als en slechts als ∀x, y ∈ H : x − y ∈ H

23

Neem H = {(a, 2a) | a ∈ R} ⊆ R2 , dan is H een deelgroep Inderdaad

Voorbeeld: van

R2 , +.

1. H 6= ∅, bv. (1, 2) ∈ H. 2. ∀p, q ∈ H : p − q ∈ H (We kunnen additief werken!), want neem twee willekeurige elementen p = (a, 2a) en q = (b, 2b) met a, b ∈ R, dan is p − q = (a, 2a) − (b, 2b) = (a − b, 2(a − b)) ∈ H.

H

2a

o

a

Op een analoge manier kan men aantonen dat elke rechte L door o = (0, 0) een deelgroep is van R2 , +. Beschouwen we nu eens de rechte L met als vergelijking L ↔ y = 2x + 1

L

2a + 1

H

2a

o

a

24

Dan vinden we dat L = {(a, 2a + 1) | a ∈ R}. Deze rechte is geen deelgroep van R2 , + want (2, 5) ∈ L en (1, 3) ∈ L, maar (2, 5) − (1, 3) = (1, 2) 6∈ L. Merk echter op dat voor elke p, q ∈ L geldt dat p − q ∈ H. Inderdaad, voor p = (a, 2a + 1) en q = (b, 2b + 1) vinden we dat p − q = (a − b, 2(a − b)) ∈ H. Kies nu een vast punt q = (α, 2α + 1) ∈ L. We hebben zonet aangetoond dat er voor elk punt p ∈ L een element h ∈ H bestaat zodat p − q = h of dus p = h + q. Omgekeerd, voor elke h ∈ H geldt dat h + q ∈ L. Inderdaad, neem een willekeurige h = (a, 2a) ∈ H, dan is h + q = (a + α, 2a + 2α + 1) = (a + α, 2 (a + α) +1) ∈ L. | {z } β

| {z } β

We hebben dus aangetoond dat L = H + q waarbij H + q de verkorte notatie is voor {h + q | h ∈ H}. Deze redenering motiveert de volgende definitie:

Definitie: Zij H een deelgroep van een groep G, ∗ en g ∈ G, dan noemen we g ∗ H = {g ∗ h | h ∈ H} nevenklasse

de linkernevenklasse van g volgens H en H ∗ g = {h ∗ g | h ∈ H} de rechternevenklasse van g volgens H. Opmerking: Voor een commutatieve groep G, + is g + H = H + g voor elke g ∈ G.

25

Voorbeeld: 1. We hebben daarnet gezien dat elke rechte L in R2 die niet door de oorsprong gaat, kan aanzien worden als een nevenklasse q + H van de rechte H, evenwijdig met L en door de oorsprong, volgens een willekeurig element q van L. 2. Beschouw de deelgroep H = {1, a, a2 , a3 , a4 , a5 } van D6 , ◦. Dan is (∗ = ◦) b ◦ H = {b, b ◦ a, b ◦ a2 , b ◦ a3 , b ◦ a4 , b ◦ a5 }

= {b, a5 ◦ b, a4 ◦ b, a3 ◦ b, a2 ◦ b, a ◦ b}

= {b, a ◦ b, a2 ◦ b, a3 ◦ b, a4 ◦ b, a5 ◦ b} = H ◦b

We zien dus dat alhoewel D6 , ◦ niet commutatief is, we toch kunnen hebben dat de linker– en de rechternevenklassen samenvallen. 3. Neem nu de deelgroep K = {1, b} van D6 , dan berekenen we a ◦ K = {a, a ◦ b}

K ◦ a = {a, b ◦ a}

= {a, a5 ◦ b}

zodat we hier wel degelijk een voorbeeld hebben van een situatie waarbij de linkernevenklasse verschillend is van de rechternevenklasse.

Oefening: Bereken alle mogelijke linkernevenklassen van K = {1, b} in D6 en

stel ze voor op een Venn-diagram.

Stelling 2.3.3: Zij H een deelgroep van een groep G, ∗ en x, y ∈ G. dan is (a) x ∗ H = y ∗ H ⇔ y −1 ∗ x ∈ H (⇔ x−1 ∗ y ∈ H) (b) H ∗ x = H ∗ y ⇔ x ∗ y −1 ∈ H (⇔ y ∗ x−1 ∈ H) Formuleer ook zelf deze eigenschap in additieve notatie voor commutatieve groepen G, + Bewijs: We bewijzen de situatie (a). Onderstel dat x ∗ H = y ∗ H. Aangezien x = x ∗ e ∈ x ∗ H = y ∗ H bestaat er dus een h ∈ H met x = y ∗ h. Hieruit volgt nu onmiddellijk dat y −1 ∗ x = y −1 ∗ y ∗ h = h ∈ H. Omgekeerd, veronderstel dat y −1 ∗ x ∈ H, d.w.z. ∃h0 ∈ H : y −1 ∗ x = h0 of dus 26

x = y ∗ h0 . Voor elke h ∈ H geldt dus dat x ∗ h = y ∗ h0 ∗ h ∈ y ∗ H ⇒ x ∗ H ⊆ y ∗ H. Anderzijds halen we uit y = x ∗ h−1 0 dat ∀h ∈ H: y ∗ h = x ∗ h−1 0 ∗ h ∈ x ∗ H ⇒ y ∗ H ⊆ x ∗ H. We kunnen dus besluiten dat x ∗ H = y ∗ H. De situatie (b) mag je zelf bewijzen.

2

Enkele gevolgen Zij G, ∗ een groep en H een deelgroep van G, ∗: 1. ∀x ∈ G : x ∗ H = H ⇔ x ∈ H (Waarom?) 2. ∀x, y ∈ G: y ∈ x ∗ H ⇔ x ∗ H = y ∗ H (Waarom?) 3. ∀x, y ∈ G: (x ∗ H) ∩ (y ∗ H) 6= ∅, dan is x ∗ H = y ∗ H (Waarom?) M.a.w. twee nevenklassen zijn ofwel volledig identiek, ofwel volledig disjunct.

Opmerking: Zij H een deelgroep van een groep G, ∗, dan verdelen de linkernevenklassen (resp. rechternevenklassen) de verzameling G in onderling disjuncte delen. Onderstaande figuur illustreert deze opmerking voor de deelgroep H = {1, a2 , a4 } van D6 , ◦. (Ga na dat H inderdaad een deelgroep is!). D6 1

a

b

ab

a2

a3

a4 b

a5 b

a4

a5

a2 b

a3 b

H

b◦H

a◦H

Merk eveneens op dat H = a2 ◦ H = a4 ◦ H

a ◦ H = a3 ◦ H = a5 ◦ H

b ◦ H = a2 b ◦ H = a4 b ◦ H

ab ◦ H = a3 b ◦ H = a5 b ◦ H 27

ab ◦ H

In dit voorbeeld zien we ook dat elke nevenklasse precies evenveel elementen heeft als H. Dit is niet toevallig en is ook in het algemeen geldig.

Stelling 2.3.4: Zij G, ∗ een eindige groep, H een deelgroep van G, ∗ en x ∈ G, dan is #(H) = #(x ∗ H) = #(H ∗ x). (Met #(A) duiden we het aantal elementen van de verzameling A aan). Bewijs: We tonen hier aan dat #(H) = #(x ∗ H). Hiervoor is het voldoende te bewijzen dat er een bijectie f : H → x ∗ H bestaat. Het ligt voor de hand om de afbeelding f : H → x ∗ H : h 7→ x ∗ h te bekijken. f is injectief: H

Onderstel f (h1 ) = f (h2 ) −1

⇒x

⇒ x ∗ h1 = x ∗ h2

∗ (x ∗ h1 ) = x

−1

⇒ h1 = h2

f

h1 h2

∗ (x ∗ h2 )

x∗H x ∗ h1 = x ∗ h2

f is surjectief: Neem α ∈ x ∗ H, dan is α = x ∗ h = f (h) voor een h ∈ H, m.a.w. f is surjectief.

4

2

Ordes van groepen, deelgroepen en elementen Definitie: orde

Zij G, ∗ een eindige groep, dan is #(G) de orde van G.

Voorbeeld:

De orde van D6 , ◦ is 12. Laat ons ook even kijken naar de ordes van enkele deelgroepen van D6 , ◦. 1. H1 = {1, a, a2 , a3 , a4 , a5 } heeft orde 6. 2. H2 = {1, a2 , a4 } heeft orde 3. 3. H3 = {1, b} heeft orde 2.

Het blijkt dat de orde van elke deelgroep van D6 , ◦ een deler is van de orde van D6 , ◦. Ook deze observatie is geen toeval! 28

Stelling 2.4.1: “Stelling van Lagrange” Als H een deelgroep is van een eindige groep G, ∗, dan is de orde van H een deler van de orde van G. Bewijs: We kunnen G onderverdelen in nevenklassen volgens H: G

e∗H = g1 ∗ H

g2 ∗ H

g3 ∗ H

gk ∗ H

...

Inderdaad, twee nevenklassen zijn ofwel identiek ofwel volledig disjunct. We kunnen dus elementen g1 = e, g2 , . . . , gk ∈ G kiezen zodat G = (g1 ∗ H) ∪ (g2 ∗ H) ∪ (g3 ∗ H) ∪ · · · ∪ (gk ∗ H) en (gi ∗ H) ∩ (gj ∗ H) = ∅ indien i 6= j Hieruit volgt dat #G = #(g1 ∗H)+#(g2 ∗H)+· · ·+#(gk ∗H) = #H + #H + · · · + #H = k ·#H. Hieruit volgt dat #H een deler is van #G.

|

{z

k keer

}

2

Stelling 2.4.2: Zij G, ∗ een eindige groep en x ∈ G. Dan bestaat er een k ∈ N0 zodat xk = e. Formuleer deze eigenschap eveneens in additieve notatie voor commutatieve groepen G, +. Bewijs: Beschouw de rij e, x, x2 , x3 , . . .. Daar G eindig is kunnen er niet oneindig veel verschillende elementen in deze rij staan. We kunnen dus twee verschillende natuurlijke getallen m, l ∈ N, zeg m < l, vinden zodat xm = xl . Hieruit halen we nu: xm = xl ⇒ x−m ∗ xm = x−m ∗ xl ⇒ e = xl−m

Door nu k = l − m te nemen hebben we dat xk = e. De vorige eigenschap toont aan dat de volgende definitie zin heeft. 29

2

Definitie: orde van een element

Zij G, ∗ een eindige groep en x ∈ G. Dan noemen we de kleinste k ∈ N0 zodat xk = e, de orde van x.

Oefeningen: 1. Vind de ordes van alle elementen in D6 , ◦. 2. Vind de ordes van alle elementen in Z12 , +. Indien je deze oefeningen correct oplost zie je dat ook de ordes van de elementen een deler zijn van de orde van de volledige groep. We tonen dit in het algemeen aan in de volgende stelling.

Stelling 2.4.3: Zij G, ∗ een eindige groep en x ∈ G een element van orde k. Dan is H = {e, x, x2 , . . . , xk−1 } een deelgroep van G. Bijgevolg is de orde van x een deler van de orde van G. Bewijs: We gebruiken het deelgroepcriterium. H is niet leeg, want e ∈ H.

Neem twee willekeurige elementen xm , xl ∈ H, 0 ≤ m, l ≤ k − 1. We berekenen nu xm ∗ (xl )−1 : −1 xm ∗ (xl )−1 = |x ∗ x ∗{z· · · ∗ x} ∗ x ∗ x−1{z∗ . . . ∗ x−1} |

(∗)

l keer x−1

m keer x

Indien m ≥ l kunnen we alle factoren x−1 “schrappen” tesamen met een x en verkrijgen we Als m ≥ l: xm ∗ (xl )−1 = xm−l ∈ H, daar 0 ≤ m − l ≤ k − 1. Indien m < l, staan er in (∗) meer factoren van de vorm x−1 dan factoren van de vorm x, zodat na “schrappen” er enkel nog factoren van de vorm x−1 zouden blijven staan. Om dit te voorkomen vermenigvuldigen we het rechterlid van (∗) met xk = e. We verkrijgen dan: Als l > m is −1 −1 −1 xm ∗ (xl )−1 = xk ∗ xm ∗ (xl )−1 = x | ∗ x ∗{z· · · ∗ x} ∗ |x ∗ x {z∗ . . . ∗ x }

= x

k+m keer x m+k−l

l keer x−1

∈ H, daar 0 ≤ m + k − l ≤ k − 1.

Aangezien H k elementen heeft (Waarom zijn alle elementen uit H verschillend van elkaar?) volgt hieruit, door de stelling van Lagrange, dat k, de orde van x, een deler is van de orde van G. 2 30

5

Voortbrengende delen Een natuurlijke vraag die men zich kan stellen in verband met deelgroepen is de vraag hoe deelgroepen zich gedragen onder het nemen van doorsnedes en unies. Het typische gedrag wordt ge¨ıllustreerd aan de hand van het volgende voorbeeld.

Voorbeeld: 1. Beschouw in Z12 , + de deelgroepen H1 = {0, 2, 4, 6, 8, 10} en H2 = {0, 3, 6, 9}. Dan is het duidelijk dat H1 ∩ H2 = {0, 6} opnieuw een deelgroep is van Z12 , +, terwijl H1 ∪ H2 = {0, 2, 3, 4, 6, 8, 9, 10} geen deelgroep is van Z12 , +. 2. Hetzelfde fenomeen doet zich voor in de groep D8 , ◦. Bij het kiezen van de twee deelgroepen G1 = {1, a2 , a4 , a6 } en G2 = {1, a4 , b, a4 b} zien we dat G1 ∩ G2 = {1, a4 } wel en G1 ∪ G2 = {1, a2 , a4 , a6 , b, a4 b} geen deelgroep vormt van D8 , ◦. We zien dat deelgroepen zich goed gedragen t.o.v. doorsnedes, terwijl ze zich slecht gedragen t.o.v. unies. We tonen dit nu in het algemeen aan.

Stelling 2.5.1: Onderstel dat G, ∗ een groep is en H een niet lege verzameling is van deelgroepen van G, ∗. Dan is \

H = {g ∈ G | ∀H ∈ H : g ∈ H}

ook een deelgroep van G, ∗. Opmerking: In het eerste voorbeeld hierboven was H gelijk aan het paar {H1 , H2 } en in het tweede voorbeeld aan het paar {G1 , G2 }. In het algemeen mag H ook oneindig veel elementen bevatten. Bewijs: T We tonen aan dat H voldoet aan het deelgroepcriterium. T Omdat voor elke H ∈ H geldt dat e ∈ H, hebben we dat e ∈ H, zodat \

H 6= ∅.

T

Neem nu willekeurig twee elementen x, y ∈ H. Dan geldt voor elke H ∈ H dat x, y ∈ H. Omdat iedere H een deelgroep is van G, ∗, hebben we dan ook dat voor elke H ∈ H geldt dat x ∗ y −1 ∈ H. Dit betekent dat x ∗ y −1 ∈ We mogen besluiten dat

T

\

H.

H een deelgroep is van G, ∗.

2

Oefening: Onderstel dat H1 en H2 deelgroepen zijn van een groep G, ∗. Toon aan dat H1 ∪ H2 een deelgroep is van G, ∗ enkel en alleen wanneer H1 ⊆ H2 of H2 ⊆ H1 . 31

Gegeven een groep G, ∗ en een deelverzameling D ⊆ G, dan kunnen we kijken naar alle deelgroepen van G die D omvatten. We stellen HD = {H ⊆ G | H is deelgroep van G, ∗ and D ⊆ H}. We weten zeker dat HD niet leeg is omdat G ∈ HD . Omwille van de vorige stelling T is HD een deelgroep van G, ∗, die D omvat. Het is daarenboven de kleinste deelgroep van G, ∗ die D omvat (Waarom?). Hieruit volgt dat de volgende definitie zin heeft.

Definitie: deelgroep voortgebracht door

Voor een groep G, ∗ en een deelverzameling D ⊆ G definiëren we grp(D) = de kleinste deelgroep van G, ∗ die D omvat. =

\

{H ⊆ G | H is deelgroep van G, ∗ and D ⊆ H}.

We noemen grp(D) de deelgroep voortgebracht door D

Voorbeeld: 1. In een willekeurige groep G, ∗ geldt: (a) grp(G) = G (b) grp({e}) = {e} (c) grp(∅) = {e}

(d) voor elke deelgroep H van G, ∗ is grp(H) = H. 2. In Z12 , + geldt: (a) grp({1}) = Z12 (b) grp({8}) = {0, 4, 8}

(c) grp({3}) = {0, 3, 6, 9}

(d) grp({3, 8}) = Z12

3. In elke diëdergroep Dn , ◦ is grp({a, b}) = Dn . Naast de eigenlijke definitie van deelgroep voortgebracht door een deel D zoals we deze hierboven gezien hebben, bestaat er ook een meer constructieve manier om grp(D) te bepalen. Het is namelijk zo dat we grp(D) kunnen construeren door alle mogelijke producten van elementen uit D en hun inversen te vormen. We formuleren dit exact in de volgende stelling.

Stelling 2.5.2: Indien D een niet lege deelverzameling is van een groep G, ∗ dan is grp(D) = {d11 ∗ d22 ∗ · · · ∗ dnn | n ∈ N0 , d1 , . . . , dn ∈ D, 1 , . . . , n ∈ {1, −1}}. 32

Bewijs: Zij E = {d11 ∗ d22 ∗ · · · ∗ dnn | n ∈ N0 , d1 , . . . , dn ∈ D, 1 , . . . , n ∈ {1, −1}}. Omdat grp(D) een groep is die D omvat, bevat grp(D) zeker alle elementen van de vorm d11 ∗ d22 ∗ · · · ∗ dnn met n ∈ N0 , d1 , . . . , dn ∈ D, 1 , . . . , n ∈ {1, −1}} en is het duidelijk dat E ⊆ grp(D). Om aan te tonen dat ook de omgekeerde inclusie geldt (grp(D) ⊆ E) is het voldoende om aan te tonen dat E een deelgroep is van G, ∗ die D omvat. Dat E alle elementen van D bevat volgt onmiddellijk uit de definitie van E (neem n = 1). We moeten dus enkel nog aantonen dat E een deelgroep is. Het is duidelijk dat E een niet lege deelverzameling is van G. Beschouw nu twee willekeurige elementen x = d11 ∗ d22 ∗ · · · ∗ dnn en y = eµ1 1 ∗ eµ2 2 ∗ · · · ∗ eµmm uit E (n, m ∈ N0 , d1 , . . . , dn , e1 , . . . , em ∈ D en 1 , . . . , n , µ1 , . . . , µm ∈ {1, −1}), dan is ook 1 m x ∗ y −1 = d11 ∗ d22 ∗ · · · ∗ dnn ∗ e−µ ∗ · · · e−µ ∈ E. m 1

Hieruit volgt dat E voldoet aan het deelgroepcriterium en bijgevolg is E een deelgroep van G, ∗ die D omvat. 2

Oefening: Onderstel dat G, ∗ een groep is en x ∈ G. Toon aan dat grp({x}) = {xz | z ∈ Z}.

Opmerking: Onderstel dat G, ∗ een groep is en dat x ∈ G een element is van orde k ∈ N0 . Via de redenering op pagina 30 kan je inzien dat grp({x}) = {e, x, x2 , x3 , . . . , xk−1 }.

In de voorbeelden hierboven hebben we gezien dat voor sommige deelverzamelingen D van een groep G, ∗ geldt dat grp(D) = G. Deze delen noemen we voortbrengend.

Definitie: voortbrengend deel

Een deelverzameling D van een groep G, ∗ heet een voortbrengend deel van G indien grp(D) = G.

Voorbeeld: 1. G (en zelfs G\{e}) is een voortbrengend deel van G, ∗. 2. ∅ is een voorbrengend deel van de groep met 1 element {e}, ∗. 3. {a, b} is een voortbrengend deel van Dn , ◦. 4. {6, 10, 15} is een voortbrengend deel van Z, +.

33

6

Homomorfismen en Isomorfismen Na het invoeren van een bepaald wiskundig object (groep, ring, topologische ruimte, vectorruimte, . . . ), bestudeert men ook steeds de afbeeldingen tussen dergelijke objecten die de structuur bewaren. Binnen (maar ook soms buiten) de algebra, noemt men dergelijke afbeeldingen (homo)morfismen.

Definitie: homomorfisme

Zij G, ∗ en H, 3 twee groepen. Een homomorfisme van G naar H is een afbeelding f : G → H, zodat ∀g1 , g2 ∈ G : f (g1 ∗ g2 ) = f (g1 )3f (g2 ).

isomorfisme

Een isomorfisme tussen G en H is een homomorfisme f : G → H dat bovendien een bijectie is. Twee groepen G en H worden isomorf genoemd (genoteerd als G ∼ = H), indien er een isomorfisme f : G → H bestaat.

Voorbeeld: 1. f1 : R2 → R : (x, y) 7→ 2x − y is een morfisme van R2 , + naar R, +. Inderdaad, voor elke (x1 , y1 ), (x2 , y2 ) ∈ R2 geldt dat f1 ((x1 , y1 ) + (x2 , y2 )) = f1 ((x1 + x2 , y1 + y2 )) = 2(x1 + x2 ) − (y1 + y2 ) = (2x1 − y1 ) + (2x2 − y2 ) = f1 ((x1 , y1 )) + f1 ((x2 , y2 )). 2. f2 : R2 → R : (x, y) 7→ 3x + 2y + 1 is geen morfisme van R2 , + naar R, +. Want f2 ((1, 0) + (0, 2)) = f2 ((1, 2)) = 8 terwijl f2 ((1, 0)) + f2 ((0, 2)) = 4 + 5 = 9. 3. f3 : R → R0 : x 7→ ex is een morfisme van R, + naar R0 , ·, want voor elke x, y ∈ R geldt dat f3 (x + y) = ex+y = ex · ey = f3 (x) · f3 (y). iπz

4. f4 : Z → C0 : z 7→ e 1302 is een morfisme van Z, + naar C0 , ·. (Waarom?)

34

Stelling 2.6.1: Zij G, ∗ een groep met neutraal element eG en H, 3 een groep met neutraal element eH . Indien f : G → H een homomorfisme is dan geldt (1) f (eG ) = eH (2) ∀g ∈ G : f (g −1 ) = f (g)−1 Indien f bovendien een isomorfisme is, dan is ook f −1 : H → G een isomorfisme. Bewijs: (1)

f (eG ∗ eG ) = f (eG ) ⇓

f (eG )3f (eG ) = f (eG ) ⇓ (vermenigvuldig beide leden met f (eG )−1 )

f (eG ) = eH (2)

f (g ∗ g −1 ) = f (eG ) = f (g −1 ∗ g) −1

)=

f (g

−1

f (g)3f (g

)

⇓

eH ⇓

=

= f (g −1 )3f (g) f (g)−1

Indien f nu bijectief is, bestaat f −1 (h), voor elke h ∈ H en is de afbeelding f −1 : H → G ook bijectief. Daarenboven geldt voor alle h1 , h2 ∈ H dat f −1 (h1 3h2 ) = f −1 (f (f −1 (h1 ))3f (f −1 (h2 ))) = f −1 (f (f −1 (h1 ) ∗ f −1 (h2 ))) = f −1 (h1 ) ∗ f −1 (h2 ).

2

Definitie: Zij f : G → H een homomorfisme tussen twee groepen, dan is kern beeld

(1) De kern van f gelijk aan Ker(f ) = {g ∈ G | f (g) = eH }. (2) Het beeld van f gelijk aan Im(f ) = {f (g) | g ∈ G}.

35

Voorbeeld:

Voor de morfismen uit de voorbeelden hierboven hebben we

dat 1. Ker(f1 ) = {(x, y) | y = 2x}. Dit is de rechte H uit het voorbeeld op pagina 24. Im(f1 ) = R. 2. Ker(f3 ) = {0} en Im(f3 ) = R+ 0. 3. Ker(f4 ) = 2604Z en Im(f4 ) = C2604 = {z ∈ C | z 2604 = 1}. In de voorbeelden hierboven is het steeds zo dat zowel kern als beeld een deelgroep vormen van de groep waarin ze omvat zitten. Dit is ook in het algemeen geldig.

Stelling 2.6.2: Indien f : G → H een morfisme is van G, ∗ naar H, 3, dan is • Ker(f ) een deelgroep van G, ∗ en • Im(f ) een deelgroep van H, 3

Oefening: Bewijs deze eigenschap. De kern van een morfisme meet in zekere zin hoeveel informatie er verloren gaat wanneer men naar het beeld kijkt, in plaats van naar de oorspronkelijke groep. Dit wordt iets preciezer geformuleerd in de volgende eigenschap.

Stelling 2.6.3: Zij f : G → H een homomorfisme tussen twee groepen G, ∗ en H, 3. Dan geldt ∀x, a ∈ G: f (x) = f (a) m

x ∗ Ker(f ) = a ∗ Ker(f ) m

x ∈ a ∗ Ker(f ) Bewijs: x ∈ a ∗ Ker(f ) m

x ∗ Ker(f ) = a ∗ Ker(f ) x f (x

−1

−1

m

∗ a ∈ Ker(f ) m

∗ a) = eH m

36

f (x)−1 3f (a) = eH m

f (a) = f (x) 2 R2

We beschouwen opnieuw het morfisme f1 : → R : (x, y) 7→ 2x−y tussen de groepen R2 , + en R, +. Neem (a, b) = (0, 1), dan is f1 ((a, b)) = 2 · 0 − 1 = −1. Om nu alle (x, y) ∈ R2 te vinden die eveneens op 1 afgebeeld worden, zoeken we dus

Voorbeeld:

L = f1−1 (−1) = {(x, y) ∈ R2 | 2x − y = −1} = {(x, y) ∈ R2 | y = 2x + 1}. Dit is precies de rechte L uit het voorbeeld op pagina 24. We hebben toen reeds aangetoond dat deze rechte L geschreven kan worden als de nevenklasse L = (0, 1) + H = (0, 1) + Ker(f1 ) zoals in voorgaande eigenschap ook bewezen werd.

Definitie: monomorfisme epimorfisme

Een morfisme f : G → H tussen twee groepen G, ∗ en H, 3 noemen we een monomorfisme indien f injectief is en een epimorfisme indien f surjectief is Een isomorfisme is bijgevolg een morfisme dat bovendien een monomorfisme en een epimorfisme is.

Stelling 2.6.4: Een morfisme f : G → H tussen twee groepen G, ∗ en H, 3 is een monomorfisme als en slechts als Ker(f ) = {eG }

Oefening: Toon deze eigenschap aan. Oefeningen: Zij f : G, ∗ → H, 3 een homomorfisme tussen twee groepen. 1. Toon aan dat ∀x ∈ G: x ∗ Ker(f ) = Ker(f ) ∗ x. 2. Indien G eindig is, geldt #G = #Ker(f ) × #Im(f ).

37

Een morfisme is volledig bepaald, indien we de beelden kennen van de elementen van een voortbrengend deel van die groep.

Stelling 2.6.5: Zij G, ∗ een groep met voortbrengend deel D ⊆ G en zij ook H, 3 een groep. Indien f1 , f2 : G → H twee morfismen zijn zodat hun beperkingen tot D gelijk zijn, t.t.z. f1|D = f2|D , dan is f1 = f2 . Bewijs: We moeten aantonen dat voor alle g ∈ G geldt dat f1 (g) = f2 (g). Indien D = ∅, is G = {eG } en dan weten we dat f1 (eG ) = eH = f2 (eG ), zodat f1 = f2 . We mogen dus veronderstellen dat D 6= ∅. Een willekeurig element g ∈ G kan dan geschreven worden als g = d11 ∗ d22 ∗ · · · ∗ dnn , met n ∈ N0 , d1 , d2 , . . . , dn ∈ D en 1 , 2 , . . . , n ∈ {1, −1}. Er geldt dan dat f1 (g) = f1 (d11 ∗ d22 ∗ · · · ∗ dnn )

= f1 (d11 )3f1 (d22 )3 · · · 3f1 (dnn )

= f1 (d1 )1 3f1 (d2 )2 3 · · · 3f1 (dn )n

= f2 (d1 )1 3f2 (d2 )2 3 · · · 3f2 (dn )n = f2 (d11 )3f2 (d22 )3 · · · 3f2 (dnn ) = f2 (d11 ∗ d22 ∗ · · · ∗ dnn ) = f2 (g)

Omdat g willekeurig was, is f1 = f2 .

2

Oefeningen: 1. Toon aan dat R, + isomorf is met R+ 0 , ·. 2. Toon aan dat Q, + niet isomorf is met Q+ 0 , ·. Dit is een moeilijke oefening! Hint: voor de rationale getallen hebben we de volgende eigenschappen: • Neem een willekeurige q0 ∈ Q. Indien q0 6= 0 dan geldt in de groep Q, +: ∀q ∈ Q, ∃n ∈ N0 : n · q ∈ grp({q0 }). • Neem 2 ∈ Q0 en 3 ∈ Q0 , dan geldt in de groep Q+ 0 ,· ∀n ∈ N0 : 3n 6∈ grp({2}). Gebruik deze twee eigenschappen om te besluiten dat Q, + niet isomorf kan zijn met Q+ 0 , ·. 38

7

Cyclische groepen De meest eenvoudige groepen zijn wellicht de groepen die kunnen voortgebracht worden door een singleton.

Definitie: cyclische groep

Een groep G, ∗ is cyclisch indien er een element g ∈ G bestaat zodat G = grp({g}). We zeggen ook soms dat G voortgebracht wordt door het element g (in plaats van door het singleton {g}).

Voorbeeld: 1. De groep Z, + is cyclisch, want {1} is een voortbrengend deel. (Ook {−1} is een voortbrengend deel). 2. De groep Zn , + is cyclisch, want {¯1} is een voortbrengend deel. 3. De groep Cn , · van complexe n-de eenheidswortels (Cn = {z ∈ C | z n = 2π 1}) is cyclisch, want {ei n } brengt Cn voort. 4. De groep Q, + is niet cyclisch, want neem een willekeurig element q ∈ Q. Indien q = 0 is grp({q}) = {0}. Indien q 6= 0, dan is grp({q}) = {zq | z ∈ Z}, waaruit we halen dat 2q 6∈ grp({q}). We hebben bijgevolg voor elke q ∈ Q dat Q 6= grp({q}), waaruit we kunnen besluiten dat Q niet cyclisch is. Opmerking: In deze sectie zullen we elementen uit een groep Zn voorstellen als getallen met een streep erboven, dit om duidelijk onderscheid te maken tussen elementen van Zn en elementen van Z. (Om heel precies te zijn, zouden we in onze notatie ook moeten aangeven over welke n het precies gaat. Een mogelijke notatie waarin dit eveneens aangegeven wordt zullen we zien in het volgende hoofdstuk.) In essentie kennen we alle cyclische groepen:

Stelling 2.7.1: Een cyclische groep G, ∗ is isomorf met Z, + of Zk , + voor een k ∈ N0 . Bewijs: Omdat G een cyclische groep is, bestaat er een g ∈ G zodat G = grp({g}). We weten dat grp({g}) = {g z | z ∈ Z}. We onderscheiden nu twee gevallen: Geval A: Voor alle z1 , z2 ∈ Z geldt g z1 = g z2 ⇔ z1 = z2 . In dit geval definiëren we een afbeelding ϕ : Z → G : z 7→ g z . 39

Door de voorwaarde weten we zeker dat ϕ een bijectie is. Daarenboven is ϕ ook een morfisme tussen Z, + en G, ∗ omdat voor alle z1 , z2 ∈ Z: ϕ(z1 + z2 ) = g z1 +z2 = g z1 ∗ g z2

= ϕ(z1 ) ∗ ϕ(z2 )

Geval B: Er bestaan z1 , z2 ∈ Z zodat z1 6= z2 maar toch g z1 = g z2 . Zonder verlies van algemeenheid mogen we aannemen dat z1 > z2 . Uit g z1 = g z2 , volgt dat g z1 −z2 = e. Dit toont aan dat er natuurlijke getallen n ∈ N0 zijn waarvoor g n = e. Zij nu k het kleinste van die natuurlijke getallen (dus k is de orde van g), dan is (zie pagina 30) G = grp({g}) = {e = g 0 , g 1 , g 2 , . . . , g k−1 }. Dit laat ons toe om de volgende bijectie ϕ : Zk → G te definiëren: ϕ : Zk → G ¯0 7→ g 0 = e ¯1 7→ g 1 ¯2 7→ g 2 .. .

k − 1 7→ g k−1 Deze bijectie ϕ is eveneens een morfisme, want beschouw twee elementen x ¯, y¯ ∈ Zk (met 0 ≤ x, y < k). Dan kunnen we twee situaties onderscheiden: ofwel is x + y < k en dan is x ¯ + y¯ = x + y, ofwel is k ≤ x + y < 2k − 1 en dan is x ¯ + y¯ = x + y − k. We beschouwen deze twee situaties apart: x + y < k: Dan is ϕ(¯ x + y¯) = ϕ(x + y) = g x+y = g x ∗ g y = ϕ(¯ x) ∗ ϕ(¯ y ). k < x + y < 2k − 1: Dan is ϕ(¯ x + y¯) = ϕ(x + y − k) = g x+y−k = g x ∗ g y ∗ g −k = g x ∗ g y = ϕ(¯ x) ∗ ϕ(¯ y ). We mogen besluiten dat ϕ een isomorfisme is tussen Zk , + en G, ∗.

2

Voorbeeld: 1. De groep Cn , · van complexe n-de eenheidswortels is isomorf met Zn , +. 2. Voor elke d ∈ N0 is dZ = {dz | z ∈ Z} een deelgroep (waarom?) van Z, + die isomorf is met Z, + (waarom?). Dit laatste voorbeeld geeft in feite de algemene situatie van deelgroepen van Z weer. 40

Als een onmiddellijk gevolg van het bewijs van de correctheid van het algoritme van Euclides, vinden we de volgende stelling:

Stelling 3.2.2: Stelling van Bachet–Bezout Zij a, b ∈ Z, dan bestaan er α, β ∈ Z zodat ggd(a, b) = αa + βb. Bewijs: Het is duidelijk dat we ons mogen beperken tot de situatie waarbij a > b > 0. Uit het vorige bewijs volgt dat ∀i ∈ {1, 2, . . . , k}: bi = ri−1 = ai−1 − qi−1 bi−1 . Door inductie zie je nu dat elke bi en ai kan geschreven worden als een gehele lineaire combinatie van a en b. Bijgevolg kunnen we ook bk schrijven als een dergelijke gehele lineaire combinatie. 2

Oefeningen: 1. Bepaal d = ggd(1023, 333) en vind α, β ∈ Z zodat d = α1023 + β333. 2. Schrijf een JAVA-programma om bij een invoer van twee gehele getallen a, b ∈ Z, d = ggd(a, b) te bepalen alsook om α, β ∈ Z te vinden zodat d = αa + βb. 3. Zijn de α en β uit de voorgaande stelling uniek bepaald? 4. Toon aan dat elke gemene deler van a en b ook ggd(a, b) deelt. Gebruik dit om aan te tonen dat ggd(a1 , a2 , . . . , an ) = ggd(ggd(a1 , a2 ), a3 , . . . , an ). Opmerking: Het algoritme van Euclides heeft een zeer goede tijdscomplexiteit. We hebben dat ri+2 = bi+1 − qi+2 ri+1 = ri − qi+2 ri+1

en dus is (omdat alle qj ≥ 1)

ri = ri+1 qi+2 + ri+2 ≥ ri+1 + ri+2 > 2ri+2 . Dus is

r1 r1 r1 r1 , r5 < , r7 < , . . . , r2k+1 < k . 2 4 8 2 De termen ri dalen dus exponentieel snel, waardoor het algoritme na een zeer korte tijd zal eindigen. r3 <

Stelling 3.2.3: Veralgemeende stelling van Bachet-Bezout Zij a1 , a2 , . . . , an , dan bestaan er α1 , α2 , . . . , αn ∈ Z zodat ggd(a1 , a2 , . . . , an ) = α1 a1 + α2 a2 + · · · + αn an . 47

Bewijs: We bewijzen deze stelling door inductie op n. Voor n = 2 is de stelling waar. Neem nu n > 2 en veronderstel dat de stelling geldig is voor alle waarden tot en met n − 1. We hebben dat ggd(a1 , a2 , . . . , an ) = ggd(ggd(a1 , a2 ), a3 , . . . , an ). Er bestaan door de inductiehypothese getallen γ2 , γ3 , . . . , γn ∈ Z zodat ggd(a1 , a2 , . . . , an ) = γ2 ggd(a1 , a2 ) + γ3 a3 + · · · + γn an .

We weten eveneens dat er α, β ∈ Z bestaan, waarvoor ggd(a1 , a2 ) = αa1 + βa2 . Bijgevolg is

ggd(a1 , a2 , . . . , an ) = (αγ2 )a1 + (βγ2 )a2 + γ3 a3 + · · · + γn an . Wat het te bewijzen aantoont.

2

Stelling 3.2.4: Zij a, b, c ∈ Z0 . 1. Als c|ab en ggd(a, c) = 1, dan c|b. 2. Als a|c, b|c en d = ggd(a, b), dan

ab d |c.

Bewijs: 1. Uit de stelling van Bachet-Bezout halen we α, β ∈ Z zodat αa + βc = 1. Bijgevolg is ook αab + βbc = b. Aangezien nu c een deler is van het linkerlid van bovenstaande gelijkheid, moet c ook b delen. 2. Opnieuw wegens de stelling van Bachet-Bezout weten we dat er α, β ∈ Z bestaan, waarvoor d = αa + βb. Er bestaan eveneens q, q 0 ∈ Z zodat c = aq = bq 0 . Bijgevolg is dc = αac + βbc = αabq 0 + βabq = (αq 0 + βq)ab. Hieruit volgt dat c = (αq 0 + βq) wat aantoont dat

ab , d

ab d |c.

2

Oefening: Analoog aan de grootste gemene deler van twee getallen kan men ook het kleinste gemeen veelvoud, kgv(a, b), van twee gehele getallen invoeren. Toon met behulp van voorgaande stelling aan dat ∀a, b ∈ N0 : kgv(a, b) = 48

ab . ggd(a, b)

3

Priemgetallen Definitie: priem

Een priem(getal) is een natuurlijk getal p > 1 dat alleen deelbaar is door ±1 en ±p.

Stelling 3.3.1: Zij p een priemgetal en a, b ∈ Z, dan p|ab ⇒ p|a of p|b Bewijs: Onderstel dat p|ab. Neem d = ggd(a, p). Omdat d|p, moet 1. ofwel d = 1 2. ofwel d = p. In het tweede geval vinden we onmiddellijk dat p|a, wat de correctheid van de stelling in dit geval aantoont. In het eerste geval, dus 1 = ggd(a, p), zegt de vorige stelling (eerste geval, met c = p) dat p|b, wat de correctheid in dit geval aantoont. 2 Deze eigenschap is cruciaal om de volgende stelling aan te tonen die volledig de structuur van een natuurlijk getal vastlegt.

Stelling 3.3.2: Unieke priemfactorisatie Elk natuurlijk getal n > 1 kan geschreven worden als een product van priemgetallen. Deze ontbinding is uniek op volgorde van de factoren in dat product na. Bewijs: We bewijzen eerst het bestaan van een dergelijke productontbinding en daarna tonen we de uniciteit aan. Bestaan: We bewijzen dit per inductie op n. Voor n = 2 is dit duidelijk, we nemen gewoon een product met één factor. Onderstel nu dat n ≥ 2 en dat er een dergelijk product bestaat voor elke waarde k tussen 2 en n. We tonen aan dat het bestaan van een dergelijke ontbinding ook geldt voor n + 1. Indien n + 1 een priemgetal is, valt er niets te bewijzen. Indien n + 1 geen priemgetal is, bestaat er een m, met 2 ≤ m ≤ n zodat m|(n+1). Merk op dat we eveneens hebben dat 2 ≤ n+1 m ≤ n. Door nu de inductiehypothese toe te passen op m en n+1 , vinden we dat n + 1 = m n+1 m m ontbonden kan worden als een product van priemgetallen. Uniciteit: Zij n ≥ 2 en n = p1 p2 . . . pr en n = q1 q2 . . . qs 49

waarbij p1 , . . . , pr , q1 , . . . , qs priemgetallen zijn. We moeten aantonen dat r = s en dat na een eventuele hernummering pi = qi (voor i = 1, 2, . . . , r). We doen dit per inductie op r. De situatie voor r = 1 is duidelijk. We onderstellen nu dat de stelling klopt voor getallen die kunnen ontbonden worden in r − 1 priemfactoren. Beschouw nu een element n = p1 p2 . . . pr = q1 q2 . . . qs . Daar p1 |n moet wegens de vorige stelling (meerdere keren toe te passen) p1 |q1 of p1 |q2 of . . . of p1 |qs . Door eventueel de qi ’s van volgorde om te wisselen, mogen we veronderstellen dat p1 |q1 . Maar omdat q1 ook een priemgetal is, moet dan p1 = q1 . Omdat nu n n = = p2 p3 . . . pr = q2 q3 . . . qs p1 q1 kunnen we per inductie besluiten dat r = s en dat na hernummering van de qi ’s ook p2 = q2 en . . . en pr = qr . 2 Tot slot nog dit:

Stelling 3.3.3: Stelling van Euclides Er bestaan oneindig veel priemgetallen. Bewijs: We bewijzen deze stelling uit het ongerijmde. Veronderstel dat er slechts eindig veel priemgetallen zijn, zeg p1 , p2 , . . . , pN . Beschouw nu het natuurlijk getal P = p1 p2 . . . pN + 1. Daar P ontbonden kan worden als een product van priemen, bestaat er dus minstens 1 priemgetal p zodat p|P . Aangezien we veronderstellen dat p1 , p2 , . . . , pN de enige priemgetallen zijn, is er dus een i ∈ {1, 2, . . . , N } zodat pi |P , maar dan moet pi ook een deler zijn van P − p1 p2 . . . pN = 1, wat een contradictie is. 2

50

4

Ringen en velden Op de verzameling Z kennen we de twee bewerkingen + (optelling) en × (vermenigvuldiging). Deze bewerkingen zijn ook verbonden met elkaar door de distributiviteitseigenschappen, bv. 7(3 + 4) = 7 × 3 + 7 × 4. Dergelijke structuren worden in de wiskunde ringen genoemd.

Definitie: ring

Een verzameling R voorzien van twee inwendige bewerkingen + en × wordt een ring genoemd indien 1. R, + is een abelse groep. 2. De bewerking × is overal bepaald. 3. De bewerking × is associatief. 4. ∀x, y, z ∈ R: x × (y + z) = x × y + x × z en (y + z) × x = y × x + z × x. We noteren een ring als R, +, ×.

eenheids– element

Een ring wordt een commutatieve ring genoemd (men spreekt NIET van een abelse ring) indien ∀x, y ∈ R: x × y = y × x. In de praktijk wordt net als bij Z het × teken vaak weggelaten en we schrijven xy i.p.v. x × y. Indien er een 1 ∈ R bestaat zodat 1x = x = x1, ∀x ∈ R, dan zeggen we dat R een ring met eenheidselement is. In elke ring is er een element 0 ∈ R, dat het neutraal element is voor de optelling. We hebben steeds dat x0 = x(0 + 0) = x0 + x0 waaruit we halen dat x0 = 0. Analoog is 0x = 0 voor elke x ∈ R. Indien R meer dan één element heeft, kan R, × nooit een groep zijn. Het is echter wel mogelijk dat R0 = R\{0} voorzien van de bewerking × een groep is. In dat geval spreken we van een lichaam (of indien de bewerking × commutatief is, van een veld).

Definitie: lichaam veld

Indien R, +, × een ring is met eenheidselement 1, dan noemen we R, +, × een lichaam als R0 , × een groep is. Indien R, +, × bovendien een com– mutatieve ring is, noemen we R, +, × een veld.

51

Voorbeeld: 1. Z, +, × is een commutatieve ring, die geen veld is. 2. Q, +, ×, R, +, × en C, +, × zijn velden. 3. H, +, × is een lichaam (en geen veld). Hierbij staat H = {a + bi + cj + dk k a, b, c, d ∈ R}, voor de quaternionen die we in het eerste hoofdstuk ingevoerd hebben. In dit hoofdstuk zullen we kennismaken met een belangrijke klasse van eindige ringen en eindige velden.

5

Congruenties en restklassen Definitie: congruent

Zij n ∈ N0 en x, y ∈ Z. We noemen x congruent met y modulo n (notatie x ≡ y mod n) als x mod n = y mod n.

Oefening: Toon aan dat de relatie . . . ≡ . . . mod n een equivalentierelatie is.

De verzameling Z wordt bijgevolg opgedeeld in equivalentieklassen. Toon aan dat er precies n equivalentieklassen zijn.

Voorbeeld: We tekenen de equivalentieklassen van de relatie . . . ≡ . . . mod 4 Z

4

1

0

-4

8 -8 ...

5

-3

2

9

-7

-2 -6

...

6

3 10

...

-1

7 -5

...

Stelling 3.5.1: Zij n ∈ N0 en x, x0 , y, y 0 ∈ Z, dan gelden 1. x ≡ y mod n ⇔ n|(x − y) ⇔ x + nZ = y + nZ ⇔ ∃k ∈ Z : x = y + kn. 2. Als x ≡ x0 mod n en y ≡ y 0 mod n, dan is ook x + y ≡ x0 + y 0 mod n. 3. Als x ≡ x0 mod n en y ≡ y 0 mod n, dan is ook xy ≡ x0 y 0 mod n. 52

Bewijs: 1.

• Onderstel dat x ≡ y mod n. Dan bestaan er r ∈ {0, 1, . . . , n − 1} en q, q 0 ∈ Z zodat x = qn + r en y = q 0 n + r. Dit impliceert dat x − y = n(q − q 0 ) of n|(x − y).

• Indien n|(x − y), geldt dat x − y ∈ nZ en hieruit volgt (door gebruik te maken van de stelling op pagina 26) dat x + nZ = y + nZ. • Uit x + nZ = y + nZ, volgt dat x ∈ y + nZ en dus bestaat er een k ∈ Z zodat x = y + kn. • Onderstel dat x = y + kn en neem r = x mod n. Dit wil zeggen dat er een q bestaat zodat x = qn + r met 0 ≤ r < n. Maar dan is y = (q − k)n + r met 0 ≤ r < n, wat aantoont dat r = y mod n. 2. We hebben dat n|(x − x0 ) en n|(y − y 0 ), bijgevolg geldt ook dat n|(x − x0 + y − y 0 ) ⇒ x + y ≡ x0 + y 0 mod n. 3. Er bestaan k, l ∈ Z zodat x = x0 + kn en y = y 0 + ln. Maar dan is ook xy = x0 y 0 + ky 0 n + lx0 n + kln2 = x0 y 0 + (ky 0 + lx0 + kln)n wat aantoont dat xy ≡ x0 y 0 mod n.

Definitie: restklasse

Zij n ∈ N0 . De restklasse (of congruentieklasse) van x modulo n is de verzameling x ¯ = {y ∈ Z | y ≡ x mod n} = x + nZ. Dit is dus de equivalentieklasse van x voor de equivalentierelatie . . . ≡ . . . mod n. Indien het uit de context niet blijkt met welke n er op dat moment gewerkt wordt, schrijven we voor de duidelijkheid [x]n i.p.v. x ¯.

Voorbeeld:

Indien n = 4 hebben we dat

¯ 0 = {. . . , −8, −4, 0, 4, 8, . . .} = ¯4 = ¯8 = . . . = −4 = −8 = . . . ¯ 1 = {. . . , −7, −3, 1, 5, 9, . . .} = ¯5 = ¯9 = . . . = −7 = −3 = . . . We zijn nu klaar om de verzameling Zn in te voeren:

53

2

terug

76

universitaire olympiade bundel

Recommend Documents