Hoe de Schröder-Bernstein Stelling Werkt: Een Inzicht in Injectiviteit en Surjectiviteit

De Schröder-Bernstein stelling is een fundamenteel resultaat in de verzamelingenleer en wiskundige logica, dat een krachtige verbinding legt tussen injectieve en surjectieve functies. Deze stelling wordt vaak gebruikt om de bijectiviteit van een functie te bewijzen, en kan vooral handig zijn in situaties waarin directe bewijsvoering van bijjectiviteit moeilijk of niet mogelijk is. Laten we de stelling stap voor stap analyseren om te begrijpen hoe we deze in de praktijk kunnen toepassen.

Een injectieve functie is een functie waarbij elk element in de domein verzameling $\alpha$ een uniek beeld heeft in de codomein $\beta$. Dit betekent dat voor elk $x_1, x_2 \in \alpha$, als $f(x_1) = f(x_2)$, dan moet $x_1 = x_2$. Surjectiviteit houdt in dat voor elk element $y \in \beta$, er een element $x \in \alpha$ bestaat zodanig dat $f(x) = y$.

Laten we beginnen met een voorbeeld. Stel dat we een element $x_1 \in \alpha$ hebben en willen aantonen dat de functie $h$ injectief is. Als $h(x_1) = h(x_2)$, kunnen we de injectiviteit van $f$ gebruiken om te stellen dat $x_1 = x_2$, op voorwaarde dat beide elementen in de verzameling $A$ liggen, die we gedefinieerd hebben als een subset van $\alpha$. Indien $x_1$ en $x_2$ zich niet in $A$ bevinden, kunnen we de surjectiviteit van $g$ gebruiken om de gelijkheid van $x_1$ en $x_2$ te bewijzen.

De surjectiviteit van de samengestelde functie $h$ wordt bewezen door twee gevallen te overwegen. In het eerste geval veronderstellen we dat $g(y)$ in de verzameling $A$ ligt. Omdat we weten dat $A$ niet de buitenste ring $S_0$ raakt, kan $g(y)$ niet in $S_0$ liggen. Dit betekent dat er een $x$ in de verzameling $S_n$ bestaat zodanig dat $g(f(x)) = y$, en dus kunnen we $h$ gebruiken om te laten zien dat $h(g(y)) = y$.

Het belangrijkste aspect van deze bewijsvoering is het vermogen om beide gevallen te hanteren via de injectiviteit van $f$ en de surjectiviteit van $g$. Door zorgvuldig gebruik te maken van de verzamelingen $A$ en $B$, en door tactieken zoals wlog en rcases effectief toe te passen, kunnen we de bijjectiviteit van de samengestelde functie $h$ aantonen.

Tot slot moeten we erkennen dat het bewijs van de Schröder-Bernstein stelling verder gaat dan alleen de bijectiviteit van $h$. Het biedt ons een systematische manier om een functie te construeren die zowel injectief als surjectief is, en dus bijectief, uit twee functies die injectief respectievelijk surjectief zijn. Dit opent de deur naar verdere toepassingen in verschillende takken van de wiskunde, zoals algebra, verzamelingenleer en de analyse van oneindige structuren.

Waarom zijn er oneindig veel priemgetallen? Een wiskundige benadering via inductie en eindige verzamelingen

Het principe van sterke inductie is een krachtig wiskundig hulpmiddel, en het wordt vaak gebruikt bij het bewijzen van stellingen die betrekking hebben op natuurlijke getallen. In de context van de stelling over priemgetallen, kan dit principe geformaliseerd worden door de zogenaamde Nat.strong_induction_on regel, die kan worden toegepast op een getal n om te bewijzen dat er altijd een priemgetal is dat een bepaalde eigenschap bezit. Dit wordt bereikt door gebruik te maken van inductie, waarbij de inductieve hypothese een cruciale rol speelt in het bewijsproces.

Stel je voor dat we beginnen met een getal n waarbij n ≥ 2. Als n een priemgetal is, dan is de bewering onmiddellijk waar. Maar als n geen priemgetal is, dan kan n worden gedeeld door een ander getal m (dat een niet-triviale deler van n is). Vervolgens kunnen we de inductieve hypothese toepassen op m, aangezien we weten dat m kleiner is dan n en dus voldoet aan de inductievoorwaarde. Dit proces maakt het mogelijk om systematisch alle mogelijke waarden voor n te onderzoeken, wat leidt tot de ontdekking van een priemgetal dat een deel van de oorspronkelijke waarde n is.

Deze benadering kan verder worden uitgediept door middel van een bewijs dat elke natuurlijke getal n groter dan of gelijk aan 2 een priemgetal heeft als deler. Een veelgebruikte methode hierbij is het zogenaamde factorial argument. Het idee is dat, voor een gegeven getal n, het getal n! + 1 (de faculteit van n plus één) altijd een priemgetal heeft dat groter is dan n. Dit principe wordt ondersteund door de stelling van de eindige priemverzameling en het idee dat er altijd een priemgetal bestaat dat niet in een eindige verzameling van priemgetallen voorkomt.

In Lean, de formele taal die wordt gebruikt om wiskundige beweringen te verifiëren, kunnen we deze inductie en argumenten verfijnen met behulp van de Finset-structuren, die eindige verzamelingen representeren. Deze verzamelingen stellen ons in staat om eigenschappen van priemgetallen in eindige sets te onderzoeken, en de inductie wordt dan uitgevoerd door te kijken naar de lege verzameling en door telkens één element toe te voegen. Hierdoor kunnen we de stelling bewijzen dat er altijd een priemgetal groter dan een gegeven verzameling van priemgetallen bestaat.

Een ander belangrijk hulpmiddel in deze context is het principe van inductie op eindige verzamelingen (Finset.induction_on). Dit principe stelt ons in staat om inductief bewijs te leveren voor eigenschappen die gelden voor eindige verzamelingen. Het bewijsproces begint met de lege verzameling en wordt verder uitgebreid door telkens een nieuw element toe te voegen aan de verzameling. Dit zorgt ervoor dat we altijd een priemgetal kunnen vinden dat niet in de oorspronkelijke eindige verzameling zit, wat de basis vormt voor de bewering over de oneindigheid van priemgetallen.

De stelling van de oneindigheid van priemgetallen kan ook op een andere manier worden geformuleerd: als we veronderstellen dat er een eindige verzameling van priemgetallen bestaat, dan kunnen we de priemgetallen binnen deze verzameling gebruiken om een getal te construeren dat geen priemgetal uit de verzameling heeft als deler. Dit leidt tot een tegenstrijdigheid, wat het idee van een eindige verzameling van priemgetallen ontkracht.

Dit bewijs kan verder worden versterkt door de eigenschappen van de Finset in Lean. Zo is er een belangrijke stelling, Finset.dvd_prod_of_mem, die ons vertelt dat als een getal n een element is van een eindige verzameling s, dan deelt n het product van de elementen van s. Dit kan worden gebruikt om de aanwezigheid van priemgetallen in dergelijke producten te onderzoeken en te bevestigen dat er altijd een priemgetal aanwezig is.

Bovendien is de filter functie van de Finset ook nuttig. Hiermee kunnen we een deelverzameling van priemgetallen binnen een eindige verzameling selecteren en de eigenschappen van deze deelverzameling verder onderzoeken. De stelling primes_infinite' toont aan dat er altijd een priemgetal bestaat dat niet in een gegeven eindige verzameling van priemgetallen voorkomt, en deze benadering benadrukt het concept van de oneindigheid van de priemgetallen in een formele context.

Wat belangrijk is om te begrijpen, is dat de oneindigheid van priemgetallen niet alleen een bewijs is dat er altijd grotere priemgetallen zullen zijn, maar ook dat er geen eindige verzameling is die alle priemgetallen bevat. Dit maakt het een krachtig argument in de getaltheorie, omdat het de eindigheid van de priemgetallen tegenspreekt en een fundament legt voor de studie van priemgetallen als een essentieel onderdeel van de wiskunde.