Delfunktion - Partial function

I matematik , en partiell funktion f från en uppsättning X till en uppsättning Y är en funktion från en delmängd S av X (eventuellt X självt) till Y . Delmängden S , det vill säga domänen för f betraktad som en funktion, kallas definitionsdomänen för f . Om S är lika med X , det vill säga om f definieras på varje element i X , sägs f vara total .

Mer tekniskt är en partiell funktion en binär relation över två uppsättningar som associerar varje element i den första uppsättningen till högst ett element i den andra uppsättningen; det är alltså en funktionell binär relation . Det generaliserar begreppet en (total) funktion genom att inte kräva att varje element i den första uppsättningen ska associeras med exakt ett element i den andra uppsättningen.

En partiell funktion används ofta när dess exakta definitionsdomän inte är känd eller svår att specificera. Detta är fallet i kalkylen , där till exempel kvoten för två funktioner är en partiell funktion vars definitionsdomän inte kan innehålla nollarnas nollor . Av denna anledning, i kalkyl, och mer allmänt i matematisk analys , kallas en partiell funktion vanligtvis bara en funktion . I beräkbarhetsteori är en allmän rekursiv funktion en partiell funktion från heltal till heltal; för många av dem kan ingen algoritm existera för att avgöra om de faktiskt är totalt.

När pilnotering används för funktioner, skrivs en partiell funktion från till ibland som f : X ⇸ Y , eller det finns dock ingen allmän konvention, och den senare notationen används oftare för injektionsfunktioner .. ${\ displaystyle f}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle f: X \ rightharpoonup Y,}$ ${\ displaystyle f: X \ nrightarrow Y,}$${\ displaystyle f: X \ hookrightarrow Y.}$

Specifikt, för en partiell funktion och någon har antingen: ${\ displaystyle f: X \ rightharpoonup Y,}$${\ displaystyle x \ i X,}$

• ${\ displaystyle f (x) = y \ i Y}$(det är ett enda element i Y ), eller
• ${\ displaystyle f (x)}$ är odefinierad.

Till exempel, om är kvadratrotfunktionen begränsad till heltal${\ displaystyle f}$

${\ displaystyle f: \ mathbb {Z} \ to \ mathbb {N},}$ definieras av:

${\ displaystyle f (n) = m}$ om och endast om, ${\ displaystyle m ^ {2} = n,}$ ${\ displaystyle m \ in \ mathbb {N}, n \ in \ mathbb {Z},}$

då definieras endast om det är en perfekt fyrkant (det vill säga ). Så men är odefinierad. ${\ displaystyle f (n)}$${\ displaystyle n}$${\ displaystyle 0,1,4,9,16, \ ldots}$${\ displaystyle f (25) = 5}$${\ displaystyle f (26)}$

Grundläggande koncept

Ett exempel på en partiell funktion som är injektiv .

Ett exempel på en funktion som inte är injektiv.

En partiell funktion sägs vara injektiv , surjektiv eller bijektiv när den funktion som ges av begränsningen av den partiella funktionen till dess definitionsdomän är injektiv, surjectiv respektive bijektiv.

Eftersom en funktion är triviellt surjectiv när den är begränsad till dess bild, betecknar termen partiell bifogning en partiell funktion som är injektiv.

En injektiv delfunktion kan inverteras till en injektionsdelfunktion, och en partiell funktion som är både injektiv och surjektiv har en injektionsfunktion som invers. Vidare kan en injektionsfunktion inverteras till en injektionspartiell funktion.

Begreppet transformation kan också generaliseras till partiella funktioner. En partiell transformation är en funktion där både och är delmängder av någon uppsättning${\ displaystyle f: A \ rightharpoonup B,}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle X.}$

Fungera

En funktion är en binär relation som är funktionell (även kallad höger-unik) och seriell (även kallad vänster-total). Detta är en starkare definition än en delfunktion som endast kräver den funktionella egenskapen.

Funktionsutrymmen

Uppsättningen av alla delfunktioner från en uppsättning till en uppsättning som betecknas med är föreningen av alla funktioner definierade i delmängder med samma kod : ${\ displaystyle f: X \ rightharpoonup Y}$${\ displaystyle X}$${\ displaystyle Y,}$${\ displaystyle [X \ rightharpoonup Y],}$${\ displaystyle X}$${\ displaystyle Y}$

${\ displaystyle [X \ rightharpoonup Y] = \ bigcup _ {D \ subseteq {X}} [D \ to Y],}$

den senare också skriven som I finite case, dess kardinalitet är ${\ textstyle \ bigcup _ {D \ subseteq {X}} Y ^ {D}.}$

${\ displaystyle | [X \ rightharpoonup Y] | = (| Y | +1) ^ {| X |},}$

eftersom någon delfunktion kan utsträckas till en funktion med vilket fast värde som helst som inte finns i så att kodmenyn är en operation som är injektiv (unik och inverterbar genom begränsning). ${\ displaystyle c}$${\ displaystyle Y,}$${\ displaystyle Y \ cup \ {c \},}$

Diskussion och exempel

Det första diagrammet högst upp i artikeln representerar en partiell funktion som inte är en funktion eftersom elementet 1 i vänster uppsättning inte är associerat med något i högeruppsättningen. Medan det andra diagrammet representerar en funktion eftersom varje element i vänster uppsättning är associerat med exakt ett element i högeruppsättningen.

Naturlig logaritm

Tänk på den naturliga logaritmfunktionen som kartlägger de verkliga siffrorna för sig själva. Logaritmen för ett icke-positivt real är inte ett reellt tal, så den naturliga logaritmfunktionen associerar inte något reellt tal i kodmenyn med något icke-positivt reellt tal i domänen. Därför är den naturliga logaritmfunktionen inte en funktion betraktad som en funktion från verkligheten till sig själva, utan den är en partiell funktion. Om domänen är begränsad till att endast inkludera de positiva realerna (det vill säga om den naturliga logaritmfunktionen ses som en funktion från de positiva realerna till realerna), är den naturliga logaritmen en funktion.

Subtraktion av naturliga tal

Subtraktion av naturliga tal (icke-negativa heltal ) kan ses som en partiell funktion:

${\ displaystyle f: \ mathbb {N} \ times \ mathbb {N} \ rightharpoonup \ mathbb {N}}$

${\ displaystyle f (x, y) = xy.}$

Det definieras endast när ${\ displaystyle x \ geq y.}$

Bottenelement

I denotationssemantik betraktas en partiell funktion som att returnera bottenelementet när det är odefinierat.

Inom datavetenskap motsvarar en partiell funktion en subrutin som ger ett undantag eller slingrar för alltid. Den IEEE flyttals standarden definierar en inte-en-nummer värde som returneras när en flyttalsoperation är odefinierad och undantag undertrycks, t ex när kvadratroten ur ett negativt tal begärs.

På ett programmeringsspråk där funktionsparametrar är typiskt skrivna kan en funktion definieras som en delvis funktion eftersom språkets typsystem inte kan uttrycka den exakta domänen för funktionen, så programmeraren ger den istället den minsta domänen som kan uttryckas som en typ och innehåller domänen för definitionen av funktionen.

I kategoriteori

I kategoriteori , när man överväger funktionen av morfismkomposition i konkreta kategorier , är kompositionoperationen en funktion om och endast om den har ett element. Anledningen till detta är att två morfismer och bara kan vara sammansatta som om det är, kodmoden för måste vara lika med domänen för${\ displaystyle \ circ \;: \; \ hom (C) \ times \ hom (C) \ to \ hom (C)}$${\ displaystyle \ operatorname {ob} (C)}$${\ displaystyle f: X \ till Y}$${\ displaystyle g: U \ till V}$${\ displaystyle g \ circ f}$${\ displaystyle Y = U,}$${\ displaystyle f}$${\ displaystyle g.}$

Kategorin uppsättningar och partiella funktioner motsvarar men inte isomorf med kategorin spetsiga uppsättningar och punktbevarande kartor. En lärobok konstaterar att "Denna formella komplettering av uppsättningar och partiella kartor genom att lägga till" felaktiga "," oändliga "element återuppfanns många gånger, särskilt i topologi ( enpunkts komprimering ) och i teoretisk datavetenskap ."

Kategorin uppsättningar och partiella bifogningar motsvarar dess dubbla . Det är den prototypiska inversa kategorin .

I abstrakt algebra

Partiell algebra generaliserar begreppet universell algebra till partiella operationer . Ett exempel skulle vara ett fält där multiplikationsinversionen är den enda korrekta partiella operationen (eftersom division med noll inte är definierad).

Uppsättningen av alla partiella funktioner (partiella transformationer ) på en given basuppsättning, bildar en vanlig semigrupp som kallas semigruppen för alla partiella transformationer (eller den partiella transformationshalvgruppen på ), typiskt betecknad med Uppsättningen av alla partiella bijektioner på bildar den symmetriska inversen halvgrupp . ${\ displaystyle X,}$${\ displaystyle X}$${\ displaystyle {\ mathcal {PT}} _ {X}.}$${\ displaystyle X}$

Diagram och atlas för grenrör och fiberbuntar

Diagram i atlaserna som anger strukturen hos grenrör och fiberbuntar är partiella funktioner. När det gäller grenrör är domänen punktuppsättningen för grenröret. När det gäller fiberbuntar är domänen fiberbuntens utrymme. I dessa applikationer är den viktigaste konstruktionen övergångskartan , som är sammansättningen av ett diagram med det inversa av ett annat. Den initiala klassificeringen av grenrör och fiberbuntar uttrycks till stor del i termer av begränsningar för dessa övergångskartor.

Anledningen till användningen av partiella funktioner istället för funktioner är att tillåta generella globala topologier att representeras genom att sy samman lokala fläckar för att beskriva den globala strukturen. "Uppdateringarna" är domänerna där diagrammen definieras.

Se även

• Analytisk fortsättning  - Utvidgning av en analytisk funktions domän (matematik)
• Flervärdesfunktion  - generalisering av en funktion som kan producera flera utgångar för varje ingång
• Tätt definierad operatör  - Funktion som definieras nästan överallt (matematik)

Referenser

• Martin Davis (1958), Computability and Unsolvability , McGraw – Hill Book Company, Inc, New York. Återutgiven av Dover 1982. ISBN  0-486-61471-9 .
• Stephen Kleene (1952), Introduction to Meta-Mathematics , North-Holland Publishing Company, Amsterdam, Nederländerna, 10: e tryckningen med korrigeringar tillagda vid 7: e tryckningen (1974). ISBN  0-7204-2103-9 .
• Harold S. Stone (1972), Introduction to Computer Organization and Data Structures , McGraw – Hill Book Company, New York.