Niezmienny (matematyka) - Invariant (mathematics)

Tapety jest niezmienny zgodnie z nieskończonej liczby  tłumaczenia , członkami grupy , której działanie oznaczony jest złożenie funkcji .

W matematyce An niezmienna jest właściwością obiektu matematycznego (lub klasy obiektów matematycznych), która pozostaje niezmieniona po operacji lub transformacje określonego typu są stosowane do przedmiotów. Na konkretną klasę obiektów i rodzaj przekształceń wskazuje zwykle kontekst, w którym termin jest używany. Na przykład, obszar z trójkąta jest niezmienny w odniesieniu do izometrycznych w euklidesowej płaszczyźnie . Używane są wyrażenia „niezmienny pod” i „niezmienny względem” transformacji. Mówiąc bardziej ogólnie, niezmiennik w odniesieniu do relacji równoważności to właściwość, która jest stała dla każdej klasy równoważności .

Niezmienniki są używane w różnych dziedzinach matematyki, takich jak geometria , topologia , algebra i matematyka dyskretna . Niektóre ważne klasy przekształceń są definiowane przez niezmiennik, który pozostawiają bez zmian. Na przykład mapy konforemne są definiowane jako przekształcenia płaszczyzny, które zachowują kąty . Odkrycie niezmienników jest ważnym krokiem w procesie klasyfikacji obiektów matematycznych.

Przykłady

Prosty przykład niezmienności wyraża się w naszej zdolności do liczenia . Dla skończonego zbioru obiektów dowolnego rodzaju istnieje liczba, do której zawsze dochodzimy, niezależnie od kolejności, w jakiej liczymy obiekty w zbiorze . Ilość – liczba kardynalna – jest powiązana ze zbiorem i jest niezmienna w procesie liczenia.

Tożsamość jest równanie, które pozostaje prawdziwe dla wszystkich wartości jego zmiennych. Istnieją również nierówności, które pozostają prawdziwe, gdy zmieniają się wartości ich zmiennych.

Odległość między dwoma punktami na osi liczbowej nie ulega zmianie przez dodanie takiej samej ilości do obu numerów. Z drugiej strony mnożenie nie ma tej samej własności, ponieważ odległość nie jest niezmienna przy mnożeniu.

Kąty i stosunki odległości są niezmienne przy skalowaniach , obrotach , translacjach i odbiciach . Te przekształcenia dają podobne kształty, co jest podstawą trygonometrii . W przeciwieństwie do tego kąty i stosunki nie są niezmienne w przypadku skalowania niejednorodnego (takiego jak rozciąganie). Suma kątów wewnętrznych trójkąta (180°) jest niezmienna we wszystkich powyższych operacjach. Jako inny przykład, wszystkie koła są podobne: można je przekształcić w siebie, a stosunek obwodu do średnicy jest niezmienny (oznaczony grecką literą π ( pi )).

Kilka bardziej skomplikowanych przykładów:

MU puzzle

MU puzzle jest dobrym przykładem logicznego problemu gdzie ustalania niezmiennik jest użytkowania na dowód niemożności . Zagadka prosi o rozpoczęcie od słowa MI i przekształcenie go w słowo MU, używając w każdym kroku jednej z następujących reguł transformacji:

  1. Jeśli ciąg kończy się na I, można dodać U ( x I → x IU)
  2. Ciąg po M może być całkowicie zduplikowany (M x → M xx )
  3. Dowolne trzy kolejne I (III) można zastąpić jednym U ( x III yx U y )
  4. Można usunąć dowolne dwie kolejne litery U ( x UU yxy )

Przykładowe wyprowadzenie (z indeksami górnymi wskazującymi zastosowane reguły) to:

MI → 2 MII → 2 MIIII → 3 MUI → 2 MUIUI → 1 MUIUIU → 2 MUIUIUUIUIU → 4 MUIUIIUIU → ...

W związku z tym można się zastanawiać, czy możliwe jest przekształcenie MI w MU, używając tylko tych czterech reguł transformacji. Można by spędzić wiele godzin stosując te reguły transformacji do łańcuchów. Jednak szybciej może być znalezienie właściwości, która jest niezmienna w stosunku do wszystkich reguł (tj. nie jest zmieniana przez żadną z nich) i pokazuje, że dostanie się do MU jest niemożliwe. Patrząc na łamigłówkę z logicznego punktu widzenia, można zdać sobie sprawę, że jedynym sposobem na pozbycie się jakiegokolwiek „ja” jest posiadanie trzech kolejnych „ja” w łańcuchu. To sprawia, że ​​następujący niezmiennik jest interesujący do rozważenia:

Liczba I w ciągu nie jest wielokrotnością 3 .

Jest to niezmiennik problemu, jeśli dla każdej z reguł transformacji obowiązuje następująca zasada: jeśli niezmiennik zachował się przed zastosowaniem reguły, będzie również obowiązywał po jej zastosowaniu. Patrząc na efekt netto zastosowania reguł na liczbę I i U, można zauważyć, że tak naprawdę jest w przypadku wszystkich reguł:

Reguła #Jest #Nas Wpływ na niezmiennik
1 +0 +1 Liczba I pozostaje bez zmian. Jeśli niezmiennik się utrzyma, to nadal.
2 ×2 ×2 Jeśli n nie jest wielokrotnością 3, to 2× n też nie jest. Niezmiennik nadal obowiązuje.
3 -3 +1 Jeśli n nie jest wielokrotnością 3, n- 3 też nie jest. Niezmiennik nadal obowiązuje.
4 +0 -2 Liczba I pozostaje bez zmian. Jeśli niezmiennik się utrzyma, to nadal.

Powyższa tabela pokazuje wyraźnie, że niezmiennik obowiązuje dla każdej z możliwych reguł transformacji, co oznacza, że ​​którakolwiek reguła zostanie wybrana, w jakimkolwiek stanie, jeśli liczba I nie była wielokrotnością trzech przed zastosowaniem reguły, to nie być później.

Biorąc pod uwagę, że w początkowym ciągu MI występuje jedno ja i takie, które nie jest wielokrotnością trzech, można wnioskować, że przejście z MI do MU jest niemożliwe (ponieważ liczba ja nigdy nie będzie wielokrotnością trzech ).

Niezmienny zestaw

Podzbiór S domeny U z odwzorowaniem T : UU jest niezmienna zestaw pod odwzorowywania Należy zauważyć, że elementy z S nie są stałe , mimo że zbiór S jest zamocowany w zestawie zasilania z U . (Niektórzy autorzy używają terminologii niezmienniczość setwise, vs. niezmiennik punktowy, aby odróżnić te przypadki.) Na przykład okrąg jest niezmiennym podzbiorem płaszczyzny pod obrotem wokół środka okręgu. Ponadto, powierzchnia stożkowa jest niezmienny w zestawie pod jednokładności przestrzeni.

O niezmiennym zbiorze operacji T mówi się również, że jest stabilny pod T . Na przykład, normalne podgrupy, które są tak ważne w teorii grup, to te podgrupy, które są stabilne pod wewnętrznymi automorfizmami grupy otoczenia . W algebrze liniowej , jeśli transformacja liniowa T ma wektor własny v , to prosta przechodząca przez 0 i v jest zbiorem niezmienników pod T , w którym to przypadku wektory własne obejmują podprzestrzeń niezmienniczą , która jest stabilna pod T .

Gdy T jest przemieszczenie śruba The oś śruba jest niezmienna linia, choć jeśli murawa jest niezerowe, T nie ma stałego punktów.

Formalne oświadczenie

Pojęcie niezmienności jest sformalizowane w matematyce na trzy różne sposoby: poprzez działania grupowe , prezentacje i deformację.

Bez zmian w ramach działania grupowego

Po pierwsze, jeśli mamy grupę G działającą na obiekt matematyczny (lub zbiór obiektów) X, to możemy zapytać, które punkty x są niezmienne, „niezmiennicze” pod działaniem grupy, czy pod elementem g grupy.

Często mamy grupę działającą na zbiorze X , co pozostawia jedną osobę do określenia, które obiekty w skojarzonym zbiorze F ( X ) są niezmienne. Na przykład obrót w płaszczyźnie wokół punktu pozostawia punkt, wokół którego obraca się on niezmiennikiem, podczas gdy translacja w płaszczyźnie nie pozostawia niezmiennych żadnych punktów, ale wszystkie linie równoległe do kierunku ruchu translacji pozostawia jako linie. Formalnie zdefiniuj zbiór linii w płaszczyźnie P jako L ( P ); wtedy ruch sztywny płaszczyzny przenosi linie na linie – grupa ruchów sztywnych oddziałuje na zbiór linii – i można zapytać, które linie pozostają niezmienione działaniem.

Co ważniejsze, można zdefiniować funkcję na zbiorze, np. „promień okręgu na płaszczyźnie”, a następnie zapytać, czy ta funkcja jest niezmienna w działaniu grupowym, takim jak ruchy sztywne.

Podwójne do pojęcia niezmienników są koinwarianty , znane również jako orbity, które formalizują pojęcie kongruencji : obiekty, które mogą być sprowadzone do siebie poprzez działanie grupowe. Na przykład w grupie sztywnych ruchów płaszczyzny obwód trójkąta jest niezmiennikiem, a zbiór trójkątów przystających do danego trójkąta jest niezmiennikiem.

Są one połączone w następujący sposób: niezmienniki są stałe na koinwariantach (na przykład przystające trójkąty mają ten sam obwód), podczas gdy dwa obiekty, które zgadzają się co do wartości jednego niezmiennika, mogą być przystające lub nie (na przykład dwa trójkąty o tym samym obwodzie nie muszą być zgodne). W problemach klasyfikacyjnych można dążyć do znalezienia pełnego zbioru niezmienników , takiego, że jeśli dwa obiekty mają te same wartości dla tego zbioru niezmienników, to są one przystające.

Na przykład trójkąty takie, że wszystkie trzy boki są równe, są przystające pod sztywnymi ruchami, poprzez kongruencję SSS , a zatem długości wszystkich trzech boków tworzą kompletny zestaw niezmienników dla trójkątów. Trzy miary kąta trójkąta są również niezmienne w przypadku sztywnych ruchów, ale nie tworzą pełnego zestawu, ponieważ nieprzystające trójkąty mogą mieć te same miary kąta. Jeśli jednak dopuścimy skalowanie oprócz ruchów sztywnych, to kryterium podobieństwa AAA pokazuje, że jest to kompletny zestaw niezmienników.

Niezależnie od prezentacji

Po drugie, funkcję można zdefiniować w kategoriach jakiejś prezentacji lub rozkładu obiektu matematycznego; Na przykład, cecha Eulera z kompleksu komórki jest określona jako suma zmiennego liczby komórek w każdym wymiarze. Można zapomnieć o strukturze kompleksu komórkowego i patrzeć tylko na leżącą u podłoża przestrzeń topologiczną ( rozmaitość ) – ponieważ różne kompleksy komórkowe dają tę samą podstawową rozmaitość, można zapytać, czy funkcja jest niezależna od wyboru prezentacji, w tym przypadku jest to samoistnie zdefiniowany niezmiennik. Tak jest w przypadku charakterystyki Eulera, a ogólną metodą definiowania i obliczania niezmienników jest zdefiniowanie ich dla danej prezentacji, a następnie wykazanie, że są one niezależne od wyboru prezentacji. Zauważ, że w tym sensie nie ma pojęcia o działaniu grupowym.

Najczęstsze przykłady to:

Niezmieniony pod perturbacją

Po trzecie, jeśli badamy obiekt, który różni się w rodzinie, co jest powszechne w geometrii algebraicznej i geometrii różniczkowej , można zapytać, czy właściwość jest niezmieniona w przypadku zaburzeń (na przykład, czy obiekt jest stały w rodzinach lub niezmienny w przypadku zmiany metryczny).

Niezmienniki w informatyce

W informatyce można napotkać niezmienniki, na których można polegać podczas wykonywania programu lub podczas jego części. Jest to logiczne twierdzenie, które zawsze uważa się za prawdziwe podczas pewnej fazy egzekucji. Na przykład niezmiennik pętli to warunek, który jest spełniony na początku i na końcu każdego wykonania pętli.

Niezmienniki są szczególnie przydatne przy wnioskowaniu, czy program komputerowy jest poprawny. Teoria optymalizacji kompilatorów , metodologia projektowania na podstawie umowy oraz formalne metody określania poprawności programu , wszystkie w dużym stopniu opierają się na niezmiennikach.

Programiści często używają asercji w swoim kodzie, aby wyraźnie określić niezmienniki. Niektóre języki programowania obiektowego mają specjalną składnię do określania niezmienników klas .

Automatyczne wykrywanie niezmienników w programach imperatywnych

Narzędzia interpretacji abstrakcyjnej mogą obliczać proste niezmienniki danych imperatywnych programów komputerowych. Rodzaj właściwości, które można znaleźć, zależy od użytych domen abstrakcyjnych . Typowymi przykładowymi właściwościami są zakresy pojedynczych zmiennych całkowitych, takie jak 0<=x<1024, relacje między kilkoma zmiennymi, takie jak 0<=i-j<2*n-1, oraz informacje o module, takie jak y%4==0. Prototypy badań akademickich uwzględniają również proste właściwości struktur wskaźnikowych.

Bardziej wyrafinowane niezmienniki zazwyczaj muszą być wprowadzane ręcznie. W szczególności podczas weryfikowania programu imperatywnego za pomocą rachunku Hoare'a niezmiennik pętli musi być wprowadzony ręcznie dla każdej pętli w programie, co jest jednym z powodów, dla których takie podejście jest ogólnie niepraktyczne w przypadku większości programów.

W kontekście powyższego przykładu łamigłówki MU , obecnie nie ma ogólnego zautomatyzowanego narzędzia, które mogłoby wykryć, że wyprowadzenie z MI na MU jest niemożliwe przy użyciu tylko reguł 1–4. Jednak po ręcznej abstrakcji od łańcucha do liczby jego „I”, co prowadzi na przykład do następującego programu w C, narzędzie do interpretacji abstrakcyjnej będzie w stanie wykryć, że ICount%3nie może być 0, i stąd pętla "while" nigdy się nie kończy.

void MUPuzzle(void) {
    volatile int RandomRule;
    int ICount = 1, UCount = 0;
    while (ICount % 3 != 0)                         // non-terminating loop
        switch(RandomRule) {
        case 1:                  UCount += 1;   break;
        case 2:   ICount *= 2;   UCount *= 2;   break;
        case 3:   ICount -= 3;   UCount += 1;   break;
        case 4:                  UCount -= 2;   break;
        }                                          // computed invariant: ICount % 3 == 1 || ICount % 3 == 2
}

Zobacz też

Uwagi

Bibliografia

Linki zewnętrzne