Kardinalitet

Kardinaliteti^[1]

Termi kardinalitet vie nga përdorimi i rëndomtë i termit numra kardinal, dhe paraqet madhësinë e bashkësisë në kuptimin se sa i madh është numri i elementeve të asaj bashkësie.

Kardinaliteti i bashkësive të fundme

Le të jetë ${\displaystyle S}$ një bashkësi e cila ka saktësisht ${\displaystyle n}$ elementë të ndryshme, ku ${\displaystyle n}$ është numër i plotë jonegativ. Themi se ${\displaystyle S}$ është një bashkësi e fundme dhe se ${\displaystyle n}$ paraqet numrin e elementeve të asaj bashkësie ose ndryshe kardinalitetin e bashkësisë ${\displaystyle S}$. Kardinaliteti shënohet zakonisht me ${\displaystyle |S|}$, por mund të shkruhet edhe si ${\displaystyle n(S)}$, ${\displaystyle S}$ ose ${\displaystyle \operatorname {card} (S)}$.
P.sh nëse bashkësia ${\displaystyle S}$ e dhënë me ${\displaystyle S=\{0,2,4,6,8\}}$ përmban 5 elemente të ndryshme, themi se kjo bashkësi ka kardinalitet të barabartë me 5, pra ${\displaystyle |S|=5}$.

• Përkufizim 1: Bashkësitë A dhe B kanë të njëjtin kardinalitet vetëm atëherë kur ekziston një bijeksion nga ${\displaystyle A}$ në ${\displaystyle B}$ ose anasjelltas, dhe me këtë rast shënojmë ${\displaystyle |A|=|B|}$.

• Përkufizim 2: Nëse nga bashkësia A në bashkësinë B ekziston funksioni injektiv ${\displaystyle (1-1)}$, themi se kardinaliteti i ${\displaystyle A}$ është më i vogël ose baraz me kardinalitetin e ${\displaystyle B}$ dhe simbolikisht shënojmë ${\displaystyle |A|}$ ≤ ${\displaystyle |B|}$. Nëse përveq kësaj vlen edhe se kardinaliteti i bashkësisë ${\displaystyle A}$ është i ndryshëm nga kardinaliteti i bahshkësisë ${\displaystyle B}$, atëherë themi se kardinaliteti i ${\displaystyle A}$-së është më i vogël se kardinaliteti i ${\displaystyle B}$-së, dhe shënojmë ${\displaystyle |A|<|B|}$.
• Përkufizim 3: Çdo bashkësi, kardinaliteti i së cilës është më i vogël se i numrave natyrorë, quhet bashkësi e fundme. Çdo bashkësi e fundme është bashkësi e numrueshme.

Kardinaliteti i bashkësive të pafundme

Kardinaliteti i bashkësive si kuptim, zgjerohet edhe në bashkësitë e pafundme. Bashkësitë e pafundme i ndajmë në bashkësi të pafundme të numrueshme dhe bashkësi të pafundme të panumrueshme.

• Përkufizim 4: Bashkësia e cila është e fundme, ose është e pafundme me kardinalitet të njëjtë me bashkësinë e numrave natyrorë ℕ, quhet bashkësi e numrueshme. Bashkësia e cila nuk është e numrueshme quhet e panumrueshme. Kur një bashkësi e pafundme ${\displaystyle S}$ është e numrueshme, shënojmë kardinalitetin e ${\displaystyle S}$ me ℵ₀, pra ${\displaystyle |S|=}$ℵ₀ (lexohet "alef zero").
  
  Shembull: Tregoni se bashkësia e numrave pozitiv tek është bashkësi e numrueshme.
  Zgjidhje: Për ta treguar se bashkësia e numrave pozitiv tek është e numrueshme, gjejmë një funksion bijektiv nga kjo bashkësi në bashkësinë e numrave natyrorë, ose anasjelltas.
  Marrim funksionin ${\displaystyle f(n)=2n-1}$ nga bashkësia ℕ në bashkësinë e numrave natyrorë tek të dhënë me ${\displaystyle A}$. Tregojmë se ${\displaystyle f}$ është bijektiv, duke treguar se është ${\displaystyle 1-1(injektiv)}$ dhe ${\displaystyle mbi(surjektiv)}$.
  Për të parë se ${\displaystyle f}$ është ${\displaystyle 1-1}$, supozojmë se ${\displaystyle f(n)=f(m)}$. Atëherë kemi:
  ${\displaystyle f(n)=f(m)}$
  ${\displaystyle 2n-1=2m-1}$
  ${\displaystyle 2n=2m}$
  ${\displaystyle n=m}$
  Pra, funksioni ${\displaystyle f}$ është injektiv.
  Për të treguar se ${\displaystyle f}$ është mbi, supozojmë se ${\displaystyle t}$ është numër natyrorë tek.
  Atëherë ${\displaystyle t}$ është për 1 më i vogël se një numër qift ${\displaystyle 2k}$, ku ${\displaystyle k}$ është numër natyrorë.
  Pra kemi ${\displaystyle t=2k-1=f(k)}$ që do të thotë se ∀${\displaystyle x}$ ∈ ℕ, ∃${\displaystyle y}$ ∈ ${\displaystyle A}$ i tillë që ${\displaystyle f(x)=2x-1=y}$
  Andaj funksioni ${\displaystyle f}$ është mbi.
  Pasi që ${\displaystyle f}$ është ${\displaystyle 1-1}$ dhe ${\displaystyle mbi}$, atëherë funksioni është bijektiv, që d.m.th se bashkësia ${\displaystyle A}$ është e numrueshme, çka edhe duhej vërtetuar.
  Një bashkësi e pafundme është e numrueshme atëherë dhe vetëm atëherë kur mund ti radhisim elementet e saj në varg (me indeks numra natyrorë). Kjo sepse bijeksioni ${\displaystyle f}$ nga bashkësia e numrave natyrorë në një bashkësi ${\displaystyle S}$ mund të shkruhet si varg:
  ${\displaystyle a}$₁, ${\displaystyle a}$₂, … , ${\displaystyle a}$_n, …, ku ${\displaystyle a}$₁ = f(1), ${\displaystyle a}$₂ = f(2), … , ${\displaystyle a}$_n = f(n), … .
• Teoremë 1: Nëse ${\displaystyle A}$ dhe ${\displaystyle B}$ janë bashkësi të numrueshme, atëherë edhe ${\displaystyle A}$∪${\displaystyle B}$ është e numrueshme.
• Teoremë 2: Teorema e SCHRÖDER-BERNSTEIN Nëse ${\displaystyle A}$ dhe ${\displaystyle B}$ janë bashkësi të tilla që ${\displaystyle |A|}$ ≤ ${\displaystyle |B|}$ dhe ${\displaystyle |B|}$ ≤ ${\displaystyle |A|}$ atëherë ${\displaystyle |A|=|B|}$.
  Nëse ekzistojnë funksione injektive ${\displaystyle f}$ nga ${\displaystyle A}$ në ${\displaystyle B}$ dhe ${\displaystyle g}$ nga ${\displaystyle B}$ në ${\displaystyle A}$, atëherë ekziston një funksion bijektiv në mes ${\displaystyle A}$ dhe ${\displaystyle B}$.
  

1. Rosen, Kenneth (2019). Discrete Mathematics and Its Applications(Eighth Edition) (në anglisht). 2 Penn Plaza, New York, NY 10121, United States of America: McGraw-Hill Education. fq. 179–186. ISBN 978-1-259-67651-2.{{cite book}}: Mirëmbajtja CS1: Vendodhja (lidhja)