Ändlig mängd
Inom matematiken, speciellt inom mängdteorin betecknar ändlig mängd en mängd med ett ändligt antal element.[1] Exempelvis är
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:
Ä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
[redigera | redigera wikitext]Formellt kallas en mängd S ändlig om det existerar en bijektion
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):
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
[redigera | redigera wikitext]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.[2] 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.[3][4]
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[5], med
eftersom
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[5] med
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 2n .
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
[redigera | redigera wikitext]- Wiktionary har ett uppslag om ändlig.
Referenser
[redigera | redigera wikitext]- Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.
- ^ Ändlig mängd i Nationalencyklopedin.
- ^ Peter Rennen, 2005, Kardinalitet utan Urvalsaxiomet; ett potpourri, sid. 5.
- ^ Dedekind-infinite på Planetmath.org.
- ^ Gonçalo Gutierres da Conceição, 2004, The Axiom of Countable Choice in Topology, sid. 3.
- ^ [a b] Herbert B. Enderton, 1977, Elements of Set Theory, sid. 144 ISBN 9780122384400.