Involuce (matematika) - Involution (mathematics)

v matematika, an involuce, nebo involutární funkce, je funkce F to je jeho vlastní inverzní,
- F(F(X)) = X
pro všechny X v doména z F.[1] Ekvivalentně, použití F dvakrát vytvoří původní hodnotu.
Termín anti-involuce odkazuje na involuce založené na antihomomorfismy (vidět § Kvaternionová algebra, skupiny, poloskupiny níže)
- F(xy) = F(y) F(X)
takhle
- xy = F(F(xy)) = F( F(y) F(X) ) = F(F(X)) F(F(y)) = xy.
Obecné vlastnosti
Jakákoli involuce je a bijekce.
The mapa identity je triviální příklad involuce. Mezi běžné příklady matematiky netriviálních involucí patří násobení o -1 in aritmetický, převzetí reciproční, doplňování v teorie množin a komplexní konjugace. Mezi další příklady patří kruhová inverze, rotace o půl otáčky a vzájemné šifry tak jako ROT13 transformace a Beaufort polyalfabetická šifra.
Počet involucí, včetně involuce identity, na sadě s n = 0, 1, 2, ... prvků je dáno a relace opakování našel Heinrich August Rothe v roce 1800:
- a pro
Prvních několik termínů této sekvence je 1, 1, 2, 4, 10, 26, 76, 232 (sekvence A000085 v OEIS ); tato čísla se nazývají telefonní čísla, a také počítají počet Mladé obrazy s daným počtem buněk.[2]The složení G ∘ F dvou involucí F a G je involuce právě tehdy, když dojíždí: G ∘ F = F ∘ G.[3]
Každá involuce na liché číslo prvků má alespoň jeden pevný bod. Obecněji řečeno, pro involuci na konečnou sadu prvků je počet prvků a počet pevných bodů stejný parita.[4]
Involuce v celé oblasti matematiky
Pre-počet
Základní příklady involucí jsou funkce:
- nebo , stejně jako jejich složení
Nejedná se pouze o evoluce před výpočtem. Další v pozitivních realitách je:
The graf involuce (na reálných číslech) je lineárně symetrický přes čáru . To je způsobeno skutečností, že inverzní k jakémukoli Všeobecné funkce bude jeho odraz nad 45 ° úsečkou . To lze vidět „výměnou“ s . Pokud je to zejména funkce involuce, pak bude sloužit jako vlastní odraz.
Další elementární involuce jsou užitečné v řešení funkčních rovnic.
Euklidovská geometrie
Jednoduchý příklad involuce trojrozměrného Euklidovský prostor je odraz přes a letadlo. Provedení odrazu dvakrát vrátí bod zpět na původní souřadnice.
Další involuce je odraz skrz původ; nikoli odraz ve výše uvedeném smyslu, a tak, zřetelný příklad.
Tyto transformace jsou příklady afinní involuce.
Projektivní geometrie
Involuce je a projektivita období 2, tj. projektivity, která zaměňuje dvojice bodů.[5]:24
- Jakákoli projektivita, která zaměňuje dva body, je involuce.
- Tři páry protilehlých stran a kompletní čtyřúhelník setkat se s jakoukoli linií (ne vrcholem) ve třech párech involuce. Tato věta byla nazývána Desargues Věta o involuci.[6] Jeho počátky lze pozorovat u lemmatu IV lemmat k Porismy Euklida ve svazku VII Sbírka z Pappus Alexandrijský.[7]
- Pokud má involuce jednu pevný bod, má další a skládá se z korespondence mezi harmonické konjugáty s ohledem na tyto dva body. V tomto případě se involuce nazývá „hyperbolická“, zatímco pokud neexistují žádné pevné body, je „eliptická“. V rámci projektivit se nazývají pevné body dvojité body.[5]:53
Dalším typem involuce vyskytující se v projektivní geometrii je a polarita což je korelace období 2.[8]
Lineární algebra
V lineární algebře je involuce lineární operátor T na vektorovém prostoru, takový . S výjimkou charakteristiky 2 jsou takové operátory diagonalizovatelné pro daný základ s pouhými 1 s a -1 s na úhlopříčce odpovídající matice. Pokud je operátor kolmý (an ortogonální involuce), je ortonormálně diagonalizovatelný.
Předpokládejme například, že základem pro vektorový prostor PROTI je vybrán, a to E1 a E2 jsou základní prvky. Existuje lineární transformace F který posílá E1 na E2a odešle E2 na E1, a která je identitou na všech ostatních základních vektorech. To lze zkontrolovat F(F(X)) = X pro všechny X v PROTI. To znamená, F je involuce PROTI.
Pro konkrétní základ může být jakýkoli lineární operátor reprezentován a matice T. Každá matice má a přemístit, získané výměnou řádků za sloupce. Tato transpozice je involucí na množině matic.
Definice involuce se snadno rozšíří na moduly. Vzhledem k modulu M přes prsten R, an R endomorfismus F z M se nazývá involuce, pokud F 2 je homomorfismus identity M.
Zapojení se vztahují k idempotentům; pokud je 2 invertibilní, pak oni korespondovat způsobem jedna ku jedné.
Kvartérová algebra, skupiny, poloskupiny
V čtveřice algebra, (anti-) involuce je definována následujícími axiomy: uvažujeme-li transformaci pak je to involuce, pokud
- (je to jeho vlastní inverze)
- a (je lineární)
Anti-involuce se neřídí posledním axiomem, ale místo toho
Tento bývalý zákon se někdy nazývá antidistribuční. Objevuje se také v skupiny tak jako (xy)−1 = y−1X−1. Vezmeme-li to jako axiom, vede to k představě poloskupina s involucí, z nichž existují přirozené příklady, které nejsou skupinami, například násobení čtvercové matice (tj plný lineární monoid ) s přemístit jako involuce.
Prstenová teorie
v teorie prstenů, slovo involuce se obvykle rozumí antihomomorfismus to je jeho vlastní inverzní funkce. Příklady involucí ve společných prstencích:
- komplexní konjugace na složité letadlo
- násobení j v rozdělit-komplexní čísla
- přičemž transponovat v maticovém kruhu.
Skupinová teorie
v teorie skupin, prvek a skupina je involuce, pokud má objednat 2; tj. involuce je prvek A takhle A ≠ E a A2 = E, kde E je prvek identity.[9]
Původně tato definice souhlasila s první definicí výše, protože členové skupin byli vždy bijekcemi ze sady do sebe; tj., skupina to mělo znamenat permutační skupina. Na konci 19. století skupina byla definována širší a podle toho také involuce.
A permutace je involuce přesně tehdy, když ji lze zapsat jako produkt jednoho nebo více nepřekrývajících se transpozice.
Involuce skupiny mají velký dopad na strukturu skupiny. Studie involucí měla zásadní význam v klasifikace konečných jednoduchých skupin.
Prvek X skupiny G je nazýván silně reálné pokud dojde k involuci t s Xt = X−1 (kde Xt = t−1⋅X⋅t).
Skupiny coxeterů jsou skupiny generované involucemi se vztahy určenými pouze vztahy danými pro páry generujících involucí. Skupiny Coxeter lze mimo jiné použít k popisu možného pravidelný mnohostěn a jejich zobecnění na vyšší dimenze.
Matematická logika
Provoz doplňku v Booleovy algebry je involuce. V souladu s tím negace v klasické logice vyhovuje zákon dvojí negace: ¬¬A je ekvivalentní k A.
Obecně se v neklasické logice nazývá negace, která splňuje zákon dvojí negace involutivní. V algebraické sémantice je taková negace realizována jako involuce do algebry pravdivostní hodnoty. Příklady logik, které mají involutivní negaci, jsou Kleene a Bochvar logika se třemi hodnotami, Łukasiewicz mnohohodnotná logika, fuzzy logika IMTL atd. Involutivní negace se někdy přidává jako další spojovací prvek k logice s neinvolutivní negací; to je obvyklé například v t-norm fuzzy logiky.
Involutivita negace je důležitou vlastnost charakterizace pro logiku a odpovídající odrůdy algeber. Například charakterizuje involutivní negace Booleovy algebry mezi Ahoj algebry. Odpovídajícím způsobem klasické Logická logika vzniká přidáním zákona dvojí negace do intuicionistická logika. Stejný vztah platí i mezi MV-algebry a BL-algebry (a tedy odpovídajícím způsobem mezi Łukasiewiczova logika a fuzzy logika BL ), IMTL a MTL a další dvojice důležitých odrůd algebry (resp. odpovídající logiky).
Ve studii o binární vztahy, každý vztah má a konverzní vztah. Protože konverzace konverzace je původní relace, je operace převodu involucí na kategorie vztahů. Binární vztahy jsou nařízeno přes zařazení. I když je toto pořadí obráceno pomocí doplňování involuce, je zachována při převodu.
Počítačová věda
The XOR bitový provoz s danou hodnotou pro jeden parametr je involuce. XOR masky kdysi byly použity k kreslení grafiky na obrázky takovým způsobem, že jejich dvojité kreslení na pozadí vrátí pozadí do původního stavu. The NE bitová operace je také involucí a je zvláštním případem operace XOR, kde jeden parametr má všechny bity nastaveny na 1.
Dalším příkladem je bitová maska a funkce posunu fungující na barevných hodnotách uložených jako celá čísla, řekněme ve tvaru RGB, která zamění R a B, což má za následek tvar BGR.f (f (RGB)) = RGB, f (f (BGR )) = BGR.
The RC4 kryptografická šifra je involuce, protože operace šifrování a dešifrování používají stejnou funkci.
Prakticky všechny mechanické šifrovací stroje implementují a reciproční šifra, involuce u každého zadaného dopisu. Namísto navrhování dvou druhů strojů, jednoho pro šifrování a druhého pro dešifrování, mohou být všechny stroje identické a lze je nastavit (klíčovat) stejným způsobem.[10]
Viz také
Reference
- ^ Russell, Bertrand (1903), Základy matematiky (2. vydání), W. W. Norton & Company, Inc, str. 426, ISBN 9781440054167
- ^ Knuth, Donald E. (1973), Umění počítačového programování, Svazek 3: Třídění a vyhledávání, Reading, Mass.: Addison-Wesley, str. 48, 65, PAN 0445948.
- ^ Kubrusly, Carlos S. (2011), Prvky teorie operátora Springer Science & Business Media, Problém 1.11 (a), s. 27, ISBN 9780817649982.
- ^ Zagier, D. (1990), „Jednovětový důkaz, že každý připravuje p≡ 1 (mod 4) je součet dvou čtverců ", Americký matematický měsíčník, 97 (2): 144, doi:10.2307/2323918, PAN 1041893.
- ^ A b AG Pickford (1909) Elementární projektivní geometrie, Cambridge University Press přes Internetový archiv
- ^ J. V. Field a J. J. Gray (1987) Geometrické dílo Girarda Desarguesa, (New York: Springer), str. 54
- ^ Ivor Thomas (redaktor) (1980) Výběry ilustrující historii řecké matematiky, Svazek II, číslo 362 v Loeb Classical Library (Cambridge a London: Harvard a Heinemann), s. 610–3
- ^ H. S. M. Coxeter (1969) Úvod do geometrie, str. 244–8, John Wiley & Sons
- ^ John S. Rose.„Kurz teorie skupin“.p. 10, oddíl 1.13.
- ^ Greg Goebel.„Mechanizace šifer“.2018.
Další čtení
- Ell, Todd A .; Sangwine, Stephen J. (2007). "Čtvrtletní involuce a anti-involuce". Počítače a matematika s aplikacemi. 53 (1): 137–143. arXiv:matematika / 0506034. doi:10.1016 / j.camwa.2006.10.029.
- Knus, Max-Albert; Merkurjev, Alexander; Rost, Markus; Tignol, Jean-Pierre (1998), Kniha involucí, Publikace kolokvia, 44„S předmluvou J. Titsa, Providence, RI: Americká matematická společnost, ISBN 0-8218-0904-0, Zbl 0955.16001
- "Involuce", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]