Ändlig mängd

Inom matematiken, speciellt inom mängdteorin betecknar ändlig mängd en mängd med ett ändligt antal element. Exempelvis är

$\{2,4,6,8,10\}\,\!$

en ändlig mängd med fem element. Antalet element i en ändlig mängd är ett naturligt tal och kallas mängdens kardinalitet. En mängd som inte är ändlig kallas oändlig mängd, exempelvis mängden av alla positiva heltal:

$\{1,2,3,4,5,...\}\,\!$

Ändliga mängder är särskilt viktiga inom kombinatorik. Många härledningar som innefattar ändliga mängder stöder sig på Dirichlets lådprincip som säger att det inte kan finnas en injektiv funktion från en större ändlig mängd till en mindre.

Definition och terminologi

Formellt kallas en mängd S ändlig om det existerar en bijektion

$f\colon S\rightarrow \{1,\ldots ,n\}$

för något naturligt tal n. Talet n är mängdens kardinalitet och betecknas |S|. Den tomma mängden {} eller Ø anses som ändlig och har kardinaliteten noll.

Om en mängd är ändlig kan den skrivas som en följd (på flera sätt):

$x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,1\leq i\leq n).$

Inom kombinatorik kallas en ändlig mängd med n element en n-mängd och en delmängd med k element för en k-delmängd. Så exempelvis är mängden {5,7,8} en 3-mängd och {5,7} en 2-delmängd av denna.

Grundläggande egenskaper

Varje äkta delmängd av en ändlig mängd S är ändlig och innehåller färre element än S. Som en följd härav kan det inte finnas en bijektion mellan en ändlig mängd och en äkta delmängd av denna. Varje mängd som har den här egenskapen kallas Dedekind-ändlig. Om man använder standardaxiomen för ZFC så är varje Dedekind-ändlig mängd också ändlig, men detta kräver åtminstone det uppräkneliga urvalsaxiomet.

Varje injektiv funktion mellan två ändliga mängder av samma kardinalitet är också en surjektiv funktion (en surjektion). På samma sätt är också varje surjektion mellan två ändliga mängder med samma kardinalitet också en injektion.

Unionen av två ändliga mängder är ändlig, med

$|S\cup T|\leq |S|+|T|.$

eftersom

$|S\cup T|=|S|+|T|-|S\cap T|.$

Detta kan generaliseras till att unionen av varje ändligt antal ändliga mängder är ändlig. Den cartesiska produkten av ändliga mängder är också ändlig med

$|S\times T|=|S|\times |T|.$

och på samma sätt är även den cartesiska produkten av ett ändligt antal ändliga mängder ändlig.

Potensmängden till en ändlig mängd med n element har kardinaliteten 2ⁿ .

Värdemängden till en funktion som verkar på elementen i en änlig mängd är ändlig.

Alla ändliga mängder är uppräkneliga, men inte alla uppräkneliga mängder är ändliga.

Externa länkar

• Wiktionary har ett uppslag om ändlig.
  Ordbok

Referenser

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.