Korrespondanse mellom sett A og B er en delmengde av deres kartesiske produkt

Med andre ord, par definerer en samsvar mellom settene A=(​) og B=( ), hvis regel R er spesifisert, ifølge hvilken et element fra sett B velges for et element i sett A.

Hvis et element er assosiert med et element, kalles b vei element a og skrives som følger: b = R (a). Deretter - prototype element, som har egenskapene til unikhet og fullstendighet:

1. Hver prototype tilsvarer et enkelt bilde;

2. Bildet må være komplett, akkurat som prototypen må være komplett.

Eksempel. Hvis A er et sett med parabler, B er et sett med punkter på et plan, og R er korrespondansen "toppunktet til en parabel", så er R (a) et punkt som er toppunktet til parabel a, og består av alle parabler med et toppunkt i punkt b (fig. 6)

Bildet av settet A med korrespondanse R kalles sett med betydninger Denne korrespondansen er betegnet med R (A) hvis R (A) består av bildene av alle elementene i settet A.

Det inverse bildet av settet B med en viss korrespondanse R kalles definisjonsdomene denne korrespondansen er merket med . I sin tur er omvendt matching for R.

Så for å matche R, gitt av poeng koordinatplan, definisjonsdomenet er settet med punkter på abscisseaksen, og settet med verdier er projeksjonen av punkter på ordinataksen (fig. 7). Derfor, på et tidspunkt

M (x, y) y er et bilde, og x er et inverst bilde for en viss korrespondanse R: Y = R (x) Korrespondansen mellom settene X er hensiktsmessig i form av et punkt på et plan ved bruk av den kartesiske koordinatmetoden .

La korrespondansen mellom R og Y=R (X) gis. Det tilsvarer punktene M med koordinater (x; y) (fig. 7). Da vil settet med punkter til flyet kjennetegnet ved kartleggingen R være rute.

For å beskrive samsvar mellom sett brukes begrepet kartlegging (funksjon) av ett sett til et annet.

For å stille inn displayet må du spesifisere:

1. Settet som er kartlagt (definisjonsdomenet til et gitt kart, ofte betegnet med );

2. Settet i (på) som et gitt definisjonsdomene er kartlagt (settet med verdier til denne kartleggingen er ofte betegnet med );

3. Loven eller korrespondansen mellom disse settene, i henhold til hvilke elementer (bilder) fra det andre settet velges for elementene i det første settet (prototyper, argumenter).

Betegnelser: .

Metoder for å spesifisere skjermer: analytisk(i form av formler), tabell, grafikk(diagrammer eller grafer).

Det finnes to hovedtyper av enkeltverditilordninger (funksjoner). Ved makt er de delt inn i surjektiv Og injektiv.

1. En korrespondanse der hvert element i sett A er indikert med et enkelt element i sett B, og hvert element i sett B kan angis med minst ett element i sett A, kalles en mapping av sett A å sette B(oversikt).

2. En korrespondanse der hvert element i sett A tilsvarer et enkelt element i sett B, og hvert element i B tilsvarer maksimalt ett forhåndsbilde fra A, kalles en mapping av sett A i mange B (injeksjon).

En mapping fra sett A til sett B, der hvert element i sett B tilsvarer et enkelt element i sett A, kalles en-til-en korrespondanse mellom to sett, eller bijeksjon.injeksjon og injeksjon.

Innføring i settteori og kombinatorikk

Praktisk arbeid nr. 8. Kartlegginger. Typer skjermer

Spørsmål til jobb

1. Hva er en "sett-til-sett-kartlegging"?
2. Hva er et "bilde", hva er en "prototype" i denne kartleggingen?
3. Hva er fullt f - bilde, hva er komplett f - prototype, når den vises f?
4. Nevn typene kartlegginger, gi deres definisjoner og gi eksempler.
5. Hvilke to sett sies å være likeverdige? Gi eksempler.
6. Hvilket sett kalles tellbar? Gi eksempler.

Eksempler på oppgaveløsninger

Eksempel 1. La A = {1; 2; 3; 4; 5; 6; 7; 8; 9} N og B = (0; 1) Z La oss matche hvert tall x A resten når den deles på 2.

Er dette samsvarende med en kartlegging? Hvilken type er denne skjermen? Hvilket element er bildet av element 6, 7? La oss finne det fullstendige inverse bildet av element 1.

Løsning. La oss representere den gitte korrespondansen ved å bruke en graf:

Vi ser at:

1) hvert element i settet EN , er utgangspunktet;

2) for hvert startpunkt er det kun ett ankomstpunkt. (Dette betyr at den angitte korrespondansen er en kartlegging av settet A til sett B);

3) Hvert element i settet I er ankomstpunktet. (Så dette er en kartlegging "til").

Siden det er mange I det er et element (for eksempel 0) som prototypen ikke er noe element fra EN , så er ikke denne tilordningen en-til-en.

Bildet av tallet 6 er tallet 0 I , bildet av tallet 7 er tallet 1 I . Full prototype av nummer 1 I det er et sett med tall (1; 3; 5; 7; 9) A .

Eksempel 2. La X være sett med plane trekanter, Y = R. La oss velge en måleenhet for lengder og tilordne et tall til hver trekant - omkretsen til denne trekanten. Vil denne kampen være en kartlegging? Hvilken type er den gitte skjermen? Hva er den komplette prototypen av nummeret på R?

Løsning. Hver trekant på planet har en unikt definert omkrets. Derfor hver trekant fra settet X samsvarer med et enkelt tall fra R , dvs. denne korrespondansen er en kartlegging X til R . I dette tilfellet kan to forskjellige trekanter ha samme omkrets. Kartleggingen er med andre ord ikke en-til-en. I tillegg er det ingen trekant hvis omkrets er lik et negativt tall, dvs. kartleggingen er ikke en "til"-kartlegging. La hos R. Deretter:

1. på > 0, det komplette bildet er settet av alle trekanter i planet hvis omkrets er lik tallet på , dette settet er uendelig.
2. på ≤ 0, er hele bildet et tomt sett.

Eksempel 3. X = (0; 1; 2; 3; 4) N, Y = Z. Mapping f av mengden X til mengden Y gitt som følger:

La oss bestemme typen av denne kartleggingen og bygge grafen.

Løsning. For hver x X la oss finne bildet y Y. Vi skriver de tilsvarende resultatene i tabellen:

y=f(x)	–2

Flere visningsverdier f er et sett

A = (–2; 1; 4; 7; 10) Y og B ≠ Y . Hvert element y B i X det er bare én prototype. Vi har derfor en en-til-en kartlegging av settet X for å sette Y.

Verdipar (x; y ) fra tabellen danner en graf over denne kartleggingen f: X→Y . I et rektangulært koordinatsystem ser denne grafen slik ut:

Eksempel 4. Gitt to sett med ord: X = (rød; blå; grønn; gul) og Y = (slips; lett; skjerf; laken). Er disse settene likeverdige?

Løsning. Disse settene er likeverdige, fordi det for dem er mulig å etablere en en-til-en-kartlegging "til".

For eksempel:

Eksempel 5. Oppgitte sett: A = ( x | x = 2 n , n N ) og

B = ( x | x = , n N ). Er disse settene likeverdige?

Løsning. Disse settene er likeverdige, siden det er mulig å velge en en-til-en-tilordning av settet A for å sette B.

For eksempel: f: A B

x = 2 n y = .

Øvelser

1. Mellom settet med navn X = (Andrey; Boris; Mikhail; Alexey; Konstantin; Vasily; Valentina; Clara; Semyon; Maria; Sophia; Oleg; Trofim4 Yuri; Yakov) og et sett Y (bokstaver i det russiske alfabetet) en korrespondanse er etablert der hvert navn er knyttet til dens første bokstav. Vil denne kampen vises X til Y ? Hvis ja, hvilken type? Finn bildet av settet X . Finn komplette prototyper av bokstaver A, B, K, L. Konstruer en graf av den angitte korrespondansen.

2. Hvert punkt M i segmentet AB La oss matche projeksjonen M til denne linjen L . Vil denne kampen være en kartlegging? Hvilken? Beskriv definisjonsdomenet, verdiområdet for denne kartleggingen.

3. Sett X består av alle rutene på planet, og settet Y fra alle sirkler på samme plan. La oss knytte hver firkant med en sirkel innskrevet i den. Er dette kartleggingskartlegging X til Y?

4. Er det mulig å stille inn displayet som følger: sett Og fra segmenter, på Y - fra trekanter; er hvert segment assosiert med en trekant der dette segmentet er midtlinjen?

5. Er det sant at overholdelse f: Z Z

X y = –5 x + 2

er det en tilordning "til"?

6. La X – sett med reelle tall. Hvert tall x X La oss matche kvadratet. Kan denne korrespondansen kalles en reversibel kartlegging?

7. Vis at følgende sett kan telles:

a) settet med odde naturlige tall;

b) settet med ikke-negative heltall;

c) settet med kvadrater av naturlige tall;

d) settet med naturlige tall som er multipler av 5;

e) settet med kuber av naturlige tall.

8. To sett er gitt: EN = (Paris; Moskva; Warszawa; Krakow; London; Saransk; Vladimir; Marseille) og B = (Frankrike; Russland; England; Polen; Sverige; Østerrike). La oss sette korrespondansen mellom dem: "by x A lokalisert i landet" La oss bygge grafer av denne korrespondansen. Vil denne kampen være en kartlegging? Hvilken type?

9. Er sett A med bilder likeverdige? bosetninger på kartet og mange B befolkede områder i området vist på kartet?

Individuell oppgave

1. Velg en skjerm fra de angitte kampene. Angi deres type, bygg en graf.

2. Tegn grafer over følgende relasjoner i et rektangulært kartesisk koordinatsystem Z . For hver relasjon, finn ut om det er en kartleggingÅ til Å, kartlegging av Z til Å , en-til-en-tilordning, overlegg:

1) x + y = 3; 7) kl< х + 2;

2) x – y ≤ 5; 8) y ≤ x + 2;

3) x + y = 4, x > 0; 9) y = 4;

4) x = y, – 4 ≤ x ≤ 6; 10) xy = 24, –6 ≤ x ≤ 6.

5) = y, – 4 ≤ x ≤ 6;

6) x > y;

Selvkontrolloppgaver

Slå sammen følgende sett med et "="-tegn hvis de er like og et "~"-tegn hvis de er like:

1) A - settet med sider i en trekant,

I - sett med vinkler av en trekant;

2) A - mange bokstaver i ordet "øre",

B = (o; k; s; 1);

3) A – mange ringer på en trestubbe,

I – mange år levd ved treet;

4) mange kontinenter på jorden og mange stater

KARTSETT §1. Grunnleggende definisjoner

Definisjon. La A og B være to sett. De sier at en mapping f av et sett A til B er gitt hvis en lov er spesifisert i henhold til hvilken ethvert element a fra A er assosiert med et enkelt element b fra settet B:

Tilordninger kalles også funksjoner.

Vi vil bruke følgende notasjon:

ƒ : A→ B. Mappingen f tar settet A til B;

A f B. Mengden A blir kartlagt til B når f er kartlagt.

Hvis element a, når f er kartlagt, går inn i element b, så skriv f(a)=b (venstre oppføring) eller af=b (høyre oppføring). Elementet b kalles bildet av elementet a under mappingen f; element a er det inverse bildet av b for

denne skjermen. Mengden ( f (a ) | a A ) = f (A ) er bildet av mengden A under mappingen f. Noter det

f(A)B.

A B

f f(A)

A - domene kartlegging f; IN - område kartlegging f (noen ganger – for eksempel i skolematematikk – anses verdiområdet for å være f(A), men vi vil vurdere det som B).

Merk at vi kun vurderer enkeltverdier.

Av alle skjermene er følgende typer spesielt utmerkede:

1. Surjection (kartlegging "på") er en avbildning f : A → B slik at f (A ) = B . Under surjeksjon har hvert element fra sett B minst ett inverst bilde.

2. Injeksjon – en kartlegging der ulike elementer transformeres til ulike, dvs. hvis a, a 1 A og a ≠ a 1, så f (a) ≠ f (a 1).

				f(a1)

3. Bijeksjon, eller en-til-en kartlegging er en kartlegging som både er en injeksjon og en injeksjon.

Eksempler på skjermer:.

1. La A være en hvilken som helst mengde og B være en mengde bestående av ett element, dvs. B=(b).

A . b

Kartleggingen f (a) = b, a A er en surjeksjon, fordi f(A)=B.

2. La mengden A være et segment på planet, sett B være en linje. Fra hvert punkt i segment A senker vi en perpendikulær til rett linje B og setter grunnflatene til disse perpendikulærene i samsvar med punktene til segment A.

A a

φ(a) V

La oss betegne denne kartleggingen med φ. Åpenbart,

ϕ (a) ≠ ϕ (a 1), a, a 1 A, a ≠ a 1.

Derfor er kartleggingen φ en injeksjon (men er ikke en injeksjon).

3. La mengden A være hypotenusen høyre trekant, og B er dens ben. La oss assosiere et hvilket som helst punkt av hypotenusen med dets projeksjon på benet. Vi får en en-til-en kartlegging fra A til B:

de. f er en bijeksjon.

Legg merke til at det er slik matematikk beviser at "antall" punkter på hypotenusen og benet er det samme (mer presist, disse settene har samme kardinalitet).

Kommentar. Det er ikke vanskelig å komme med en kartlegging som verken er en injeksjon, eller en injeksjon eller en bijeksjon.

4. Hvis f er en funksjon av en reell variabel, så er f en avbildning fra R til R.

§2. Kartmultiplikasjon

La A, B, C være tre sett og la to kart f : A → B og ϕ : B → C gis.

Definisjon 1. Produktet av disse tilordningene er kartleggingen som oppnås som et resultat av deres sekvensielle utførelse.

ϕf

Det er to opptaksalternativer.

1. Venstre inngang.
ƒ (a)=b, ϕ (b)=c.		angir ϕ f:
Da blir produktet av f og φ	oversett a til c, bør det være
(ϕ f ) (a ) = ϕ (f (a ) ) = ϕ (b ) = c , ϕ f : A → C (se figuren over).
Per definisjon (ϕ f ) (a ) = ϕ (f (a) ),	de. produkt av kartlegginger –	dette er en kompleks funksjon
satt til A.

2. Høyre oppføring.

aƒ =b, bϕ =c. Da a (f ϕ ) = (af ) ϕ = b ϕ = c ,

f ϕ : A → C.

Vi vil bruke venstre notasjon (merk at boken bruker høyre notasjon). Nedenfor vil vi betegne produktet av avbildninger med f ϕ.

Merknad 1. Fra definisjonen av multiplikasjon av tilordninger følger det at ikke noen tilordninger kan multipliseres, men bare de hvis "gjennomsnittlige" sett er de samme. For eksempel, hvis f : A → B ,ϕ : D → C , så for B=D kan tilordningene f og φ multipliseres, men for B≠D er det ikke mulig.

Egenskaper for kartleggingsmultiplikasjon

Definisjon 2. Kart f og g kalles like hvis deres definisjonsdomener og verdiområder sammenfaller, dvs. f : A → B , g : A → B og betingelsen er oppfylt: a A er sann

likhet f (a) = g (a).

1. Multiplikasjon av kart er ikke-kommutativ. Med andre ord, hvis fφ og φf eksisterer, så er de ikke nødvendigvis like.

La for eksempel mengdene A=B=C=R, f (x) = sin x,ϕ (x) Tenk på produktene:

(ϕ f) (x) = ϕ (f (x)) = ϕ (sin x) = e sin x,

(f ϕ ) (x ) = f (ϕ (x )) = f (e x ) = sin(e x ).

Derfor er funksjonene fφ og φf forskjellige.

2. Multiplikasjon av kartlegginger er assosiativ.

La f: A → B, ϕ: B → C, ψ: C → D. La oss bevise at (ψϕ ) f

Ex, f: R → R, ϕ: R → R.

og ψ (ϕ f ) eksisterer og er like, dvs. (ψϕ ) f =

ψ (ϕ f) . (1)

Det er åpenbart at (ψϕ ) f : A → D ,ψ (ϕ f ) : A → D .

For å bevise likhet (1), i kraft av definisjonen av likhet av kartlegginger, er det nødvendig å kontrollere at a A : ((ψϕ ) f ) (a ) = (ψ (ϕ f )) (a ) (2). Bruke definisjonen av kartleggingsmultiplikasjon (i venstre oppføring)

((ψϕ )f )(a ) = (ψϕ )(f (a) )= ψ (ϕ (f (a) )),

(ψ (ϕ f ))(a ) = ψ ((ϕ f )(a) )= ψ (ϕ (f (a) )). (4)

Fordi i likheter (3) og (4) hvis høyresidene er like, så er også venstresidene like, dvs. likhet (2) er sant, og så er (1) også sant.

Merknad 2. Assosiativiteten til multiplikasjon lar oss unikt bestemme produktet av tre, og deretter et hvilket som helst begrenset antall faktorer.

flere forbilder i A, eller ingen forbilder i det hele tatt. For et bijektivt kart f kan det motsatte imidlertid defineres.

La f : A → B være en bijeksjon, f (a) = b, a A, b B. Så, for ethvert element b B, per definisjon av en bijeksjon, er det et unikt inverst bilde under tilordningen f - dette er elementet a. Nå kan vi definere f − 1 : B → A ved å sette f − 1 (b) = a (b B). Det er lett å se at f − 1 er en bijeksjon.

Så, hver bijektiv kartlegging har en invers.

§3. Sett transformasjoner

Enhver tilordning f : A → A kalles transformasjon av settet A. Spesielt noen

en funksjon av en reell variabel er en transformasjon av mengden R.

Eksempler på transformasjoner av et sett med punkter på et plan er rotasjon av planet, symmetri om en akse, etc.

Siden transformasjoner er et spesielt tilfelle av kartlegginger, er alt som er sagt ovenfor om kartlegging sant for dem. Men multiplikasjon av transformasjoner av sett A har også spesifikke egenskaper:

1. for enhver transformasjon f og φ av sett A, eksisterer produktene fφ og φf;

2. det er en identitetstransformasjon av settet Aε: ε (a) = a, a A.

Det er lett å se at for enhver transformasjon f av denne mengden f ε = ε f = f, siden for eksempel (f ε ) (a ) = f (ε (a) ) = f (a) . Dette betyr at transformasjonen ε spiller rollen som enhetselementet når man multipliserer transformasjoner.

likhetene er enkle å sjekke. Dermed spiller den inverse transformasjonen rollen som et inverst element når man multipliserer transformasjoner.

La oss vurdere et annet viktig spesialtilfelle av det generelle begrepet korrespondanse - kartlegging av sett. Hvis kompatibel R mellom settene X Og Y elementbilde ENX kan være tom, eller kan inneholde flere elementer.

Forholdet mellom elementer i sett X Og Y kalt vise X VY , hvis hvert element X fra mange X bare ett element i settet samsvarer Y. Dette elementet kalles elementbildeX med denne skjermen: f(x). På en graf av en slik kartlegging fra hvert punkt i settet X Bare én pil kommer ut (fig. 29).

Tenk på følgende eksempel . La X– mange elever i publikum, og Y- mange stoler i samme auditorium. Match "student" X sitter på en stol på" settene vise X VY. Studentbilde X er en stol.

La X = Y = N- et sett med naturlige tall. Matchende "desimalnotasjon av et tall" X omfatter på sifre" bestemmer visningen N V N. Med dette displayet tilsvarer tallet 39 tallet 2, og tallet 45981 tilsvarer tallet 5 (39 er et tosifret tall, 45981 er et femsifret tall).

La X- mange firkanter, Y- mange sirkler. Matchende "firkant" X innskrevet i en sirkel på» er ikke en skjerm X V Y, siden det er firkanter som ikke kan skrives inn i en sirkel. Men i dette tilfellet sier de at resultatet er en kartlegging fra settet X inn i mengden Y.

Hvis skjerm X V Y slik at hvert element y fra mange
Y samsvarer med ett eller flere elementer X fra mange X, da kalles en slik kartlegging visning av settet X for mangeY.

En haug med X kalles kartleggingens definisjonsdomene f: XY, og mye Y- ankomstregionen til denne kartleggingen. En del av ankomstområdet som består av alle bilder y fra mange Y, kalt kartleggingsverdisettet f.

Hvis y=f(x), da kalles x prototype av element y når den vises f. Settet med alle forhåndsbilder av et element på de kaller det en komplett prototype: f(y).

Skjermer er av følgende typer: injektiv, surjektiv og bijektiv.

Hvis den komplette prototypen av hvert element yY inneholder høyst ett element (kan være tomt), så kalles slike tilordninger injektiv.

Viser XY slik at f(X)=Y, kalles kartlegginger X for hele mengden Y eller surjektiv(fra hvert punkt i settet X en pil kommer ut, og etter å ha endret retning på hvert punkt av settet X slutter) (Fig. 31).

Hvis en kartlegging er injektiv og surjektiv, kalles den en-til-en eller bijektiv.

Still inn display X kalles et sett bijektiv, hvis hvert element XX samsvarer med et enkelt element yY, og hvert element yY matcher bare ett element XX(fig. 32) .

Bijektive kartlegginger genererer like sett : X~Y.

Eksempel . La - X mange kåper i garderoben, Y- mange kroker der. La oss matche hvert strøk med kroken den henger på. Denne korrespondansen er en kartlegging X innY. Det er injektiv hvis ingen krok har mer enn ett strøk hengende på seg eller noen kroker er ledige. Denne kartleggingen er surjektiv hvis alle krokene er opptatt eller noen har flere strøk hengende på seg. Det vil være bijektivt hvis det bare henger ett strøk på hver krok.

La oss nå studere noen spørsmål knyttet til forholdet mellom settene.

Vi vil si at mellom settene er det gitt holdning(er i en relasjon) hvis noen (muligens alle) elementer fra tilsvarer noen elementer fra. Hvis et sett er i et forhold til et sett, vil vi skrive:

Hvis et element samtidig er assosiert med et element, vil vi betegne dette

Definisjon 1.1.2. Forholdet mellom sett kalles vise, hvis hver av dem er tildelt ett og bare ett element (se fig. 1.1.2. og 1.1.3). Med spesialiseringen av settenes natur oppstår spesielle typer kartlegginger, som har det spesielle navnet "funksjon", " vektorfunksjon", "operatør", "mål", "funksjonell", osv. Vi vil møte dem senere.

For å betegne en funksjon (mapping) fra v, vil vi bruke notasjonen

Fig.1.1.2. Visning Fig. 1.1.3 Forholdet som ikke er det

vise

Definisjon 1.1.3. Hvis er et element fra, kalles elementizaen som tilsvarer det bildet (når det vises), og settet med alle de som kalles en prototype og er utpekt (se fig. 1.1.4).

Fig.1.1.4. Prototypeb

Definisjon 1.1.4. Kartleggingen kalles en-til-en kartlegging, hvis hvert element av har et unikt bilde under tilordning og hvert element har et unikt inverst bilde under denne tilordningen.

Fig.1.1.5. En-til-en kartlegging

I det følgende vil vi kun vurdere tilordninger, siden det finnes teknikker som reduserer flerverditilordninger til enkeltverdier, som vi ganske enkelt kaller tilordninger.

Konseptet kartlegging spiller en avgjørende rolle i matematikk, spesielt i matematisk analyse er den sentrale plassen okkupert av konseptet funksjoner, som er tilordningen av ett numerisk sett til et annet.

1.7. Settets kraft

Når du studerer forhold mellom sett, er "volumet" av sett, antall elementer i dem, av stor interesse. Men å snakke om antall elementer er forståelig og berettiget hvis dette tallet er begrenset. Sett som består av et begrenset antall elementer vil bli kalt endelig . Imidlertid er mange av settene som vurderes i matematikk ikke endelige, for eksempel settet med reelle tall, settet med punkter på planet, settet med kontinuerlige funksjoner definert på et bestemt segment, etc. For å kvantitativt karakterisere uendelige (og til og med endelige) mengder, bruker settteori konseptet kraften til settet .

Vi vil si at sett har samme kraft , hvis det er en en-til-en-tilordning fra et sett til et sett (merk at i dette tilfellet er det også en en-til-en-tilordning fra sett B til sett A).

Hvis settene har samme kardinalitet, vil vi si at de tilsvarende , er dette betegnet: .

La være vilkårlige sett, da

de. ethvert sett er ekvivalent med seg selv; hvis et sett er ekvivalent med et sett, så ekvivalent; hvis, til slutt, et sett er ekvivalent med et sett som tilsvarer et sett, så ekvivalent.

Et sett som tilsvarer en egen delmengde kalles endeløs .

Hvis endelige mengder har forskjellig antall elementer, så er det klart at en av dem inneholder færre elementer enn den andre. Hvordan kan vi sammenligne uendelige sett i denne forstand? Vi vil si at kardinaliteten til et sett er mindre enn kardinaliteten til et sett hvis det er en delmengde av settet som er ekvivalent med settet, men selve mengdene er ikke ekvivalente.

Kardinalitet av et begrenset sett lik antall elementer. For uendelige sett er begrepet "kardinalitet" en generalisering av begrepet "antall elementer".

La oss angi noen klasser av sett som er nyttige for det som følger.

Settet kalles tellbar , hvis den har samme kardinalitet som en delmengde av settet (sett med naturlige tall). Et tellbart sett kan være endelig eller uendelig.

En uendelig mengde kan telles hvis og bare hvis den er ekvivalent med settet med naturlige tall.

Legg merke til at ethvert sett hvis kardinalitet er mindre enn kardinaliteten til et uendelig tellbart sett, er endelig.

Settet med reelle tall på intervallet fra null til én har kraftkontinuum , og i seg selv kalles ofte kontinuum . Kardinaliteten til dette settet er større enn kardinaliteten til et uendelig tellbart sett. Spørsmålet oppstår: finnes det en mengde hvis kardinalitet er større enn kardinaliteten til en uendelig tellbar mengde, men mindre enn kardinaliteten til kontinuumet? Dette problemet ble formulert i 1900 av en av verdens største matematikere, David Hilbert. Det viste seg at dette problemet har et noe uventet svar: vi kan anta at et slikt sett eksisterer, eller vi kan anta at det ikke eksisterer. De resulterende matematiske teoriene vil være konsistente. Beviset for dette faktum ble rapportert av den amerikanske forskeren Cohen i 1965 på World Congress of Mathematicians i Moskva. Merk at situasjonen med denne oppgaven minner om situasjonen med Euklids femte postulat: gjennom et punkt som ligger utenfor en gitt linje, kan bare én linje parallelt med den gitte trekkes. Som Lobachevsky viste, fører ikke avvisning av dette postulatet til motsetninger. Vi kan konstruere geometrier som dette postulatet gjelder, og geometrier som det ikke er sant for.

Avslutningsvis gir vi flere eksempler som demonstrerer metodikken for å bevise ekvivalensen av sett.

Eksempel 1.11. Settet med heltall kan telles.

Det er klart at den aktuelle mengden er uendelig (settet med naturlige tall er dens delmengde).

For å bevise tellbarheten til et sett med heltall, er det nødvendig å konstruere en en-til-en-kartlegging mellom settet med naturlige tall og det aktuelle settet. Den nødvendige tilordningen er gitt av regelen: ordne heltallene som følger:

og omnummerer dem med naturlige tall, og tilordne tall til dem (de er angitt ved siden av de aktuelle heltallene). Selvfølgelig vil hvert heltall motta et annet tall, med forskjellige tall som mottar forskjellige tall. Det motsatte er også sant: for hvert naturlig tall (for hvert tall) er det også et enkelt heltall som står under dette tallet. Dermed er den nødvendige en-til-en-kartleggingen konstruert.

Eksempel 1.12. Settet med rasjonelle tall kan telles.

Det er kjent at ethvert rasjonelt tall kan representeres som en irreduserbar brøk p/q, ved å bruke denne representasjonen vil vi ordne de rasjonelle tallene i samsvar med skjemaet:

. . . . . .

La oss omnummerere disse tallene på omtrent samme måte som i forrige eksempel (tallene er angitt øverst i parentes ved siden av tallene). Det er lett å verifisere at den formulerte regelen for nummerering av rasjonelle tall gir den nødvendige en-til-en-kartleggingen fra settet med naturlige tall til settet med rasjonelle tall.

Eksempel 1.13. Foreningen av et tellbart sett med tellbare sett er et tellbart sett.

Beviset for dette faktum ligner beviset på utsagnet i det forrige eksempelet.

Avslutningsvis presenterer vi en viktig uttalelse for videre diskusjon. Men for dette trenger vi en operasjon til på sett.

Direkte produkt av sett Og( Kartesisk produkt ) er settet med alle bestilte par, hvor og. Dette settet er utpekt. Dermed:

La oss betegne produktet av faktorer.

Teorem 1.1. for ethvert uendelig sett.

Spesielt, dvs. settet med punkter på en rett linje har samme kardinalitet som settet med punkter på et plan. Dessuten er det like mange punkter i rommet som det er på en rett linje.

Dette avslutter vårt bekjentskap med de grunnleggende begrepene matematisk logikk og settteori - grunnlaget for moderne matematikk. La oss merke oss at mange aspekter ved disse teoriene dessverre forble utenfor rammen av dette kapittelet; du kan bli kjent med dem, for eksempel ved og.