of 7/7
Heft  1 0 ISS N 0720-9991 ISBN  3  798311919

Wissenschaftsmagazin Mathematische Logik

  • View
    220

  • Download
    0

Embed Size (px)

Text of Wissenschaftsmagazin Mathematische Logik

  • 7/25/2019 Wissenschaftsmagazin Mathematische Logik

    1/7

    Heft

    10

    ISS N 0720-9991

    ISBN3798311919

  • 7/25/2019 Wissenschaftsmagazin Mathematische Logik

    2/7

    Aus dem Inhalt

    Wolfgang Schwarz

    Manfred Fr icke

    Robert Paul Knigs

    Barbara Windscheid

    Klaus Habetha

    Helmut Neunzert

    Wol fgang Haack

    Eberhard Knobloch

    Dorothee Stacke

    Dirk Ferus

    Erwin Bolthausen

    Chr is t ian Pommerenke

    H. Schwichtenberg

    Ulrich Pinkall

    R ichard Koch

    Alfred K. Louis

    Rolf Dieter Grigorieff

    G. Frey, E. Lamprecht, H. G. Zimmer

    Rudolf Fritsch

    Stefan Polonyi

    Rudolf Wille

    Wol fgang G lebe

    S eite 1 V orwo rt

    S eite 4 E ditorial

    S eite 5 Die F rderung mathematische r F orsc hung

    S eite 9 Ma thematikzentrum im S chwa rzwa ld

    S eite 13 F ach informa tion in der M athe matik

    S eite 16 Ma thematik und Industrie: Von der Notwe ndig keit

    eines Brckenschlags zwischen Theorie und Praxis

    S eite 20 R cksc hau ber 85 J ahre

    S eite 24 Vo m U mgang der Ma thematiker mit de m Un endlic hen

    im 17. J ahrhunde rt

    S eite 27 Da malt man furch tbar viele F ormeln

    und schreibt halbe Stze hin".

    Der Mathematiker - das unzugngliche Wesen?

    S eite 29 Un lsbarkeit

    S eite 32 Das G ese tz der gro en Zahle n

    und Wahrscheinl ichkeiten groer A bweic hunge n

    S eite 37 Einige P robleme aus der Funktionentheo rie

    S eite 39 Ma thematische Logik

    S eite 43 Differentialgeometrie ges chlos sen er F lchen

    S eite 46 Ana lytisch besc hreibbare F lchen

    in der geome trischen Da tenverarbeitung

    S eite 49 Numerik: Die Lsung von An wend ungs proble men

    S eite 52 E ffekthasch erei in der Nu merik

    der Diskretisierungsmethoden

    S eite 61 Neuere E rgebnisse ber dioph antisc he G leichun gen

    S eite 68 Zahlen in der allgemeinbilde nden S chule

    S eite 75 Ma thematik und Ba uwes en

    S eite 84 Mu siktheorie und Ma thematik

    S eite 94 M athematisc he S pielereien

    Neues Puzzlefieber mit Rubiks Magic"

  • 7/25/2019 Wissenschaftsmagazin Mathematische Logik

    3/7

    Forschung

    Publikationen

    Personalia

    Tagungen

    Impressum

    Seite 100

    Seite 104

    Seite

    109

    Seite

    111

    Seite 112

  • 7/25/2019 Wissenschaftsmagazin Mathematische Logik

    4/7

    Mathematische Logik

    Wir wollen uns hier mit der Frage befassen, was

    mathematische Beweise sind,und fr welchen Zweck

    man sie verwenden kann (auer fr den offensichtli

    chen Zweck, da sie die Wahrheit der betreffenden

    Behauptung sicherstellen). Es gibt viele andere Frage

    stellungen in der mathematischen Logik, auf die wir

    hier nicht eingehen knnen; eine gute, fr Mathemati

    ker ohne Logik-Kenntnisse bestimmte bersicht fin

    det man in dem Handbook of Mathematical Logic",

    herausgegeben von J . Barwise, North-Holland Publis

    hing Company (Amsterdam 1977). Eine fr ein breite

    res Publikum bestimmte, sehr lesenswerte Abhand

    lung ber mathematische Logik ist von G. Kreisel

    unter dem Titel Was hat die Wissenschaft von der

    mathematischen L ogik? " im J ahrbuch 1982 der

    schweizerischen naturforschenden Gesellschaft,

    1982,

    S. 163-173, verffentlicht worden.

    1.Reine Logik

    Wichtige Kennzeichen der formalen und damit

    auch der mathematischen Logik sind (1) die Trennung

    von Syntax und Semantik (mit Syntax bezeichnet man

    die Lehre von der formalen Gestalt sprachlicher Aus

    drcke, mit Semantik die Lehre von der Bedeutung

    sprachlicher Ausdrcke), und (2) die genaue Festle

    gung der sprachlichen Mittel, mit denen etwas ber

    den zugrunde gelegten Bereich von Objekten ausge

    sagt werden

    soll .

    Der Grund fr dieTrennung von Syn

    tax und Semantik liegt darin, da man andernfalls

    leicht zu Antinomien etwa der Form Was ich jetzt

    schreibe ist falsch" kommt. Die genaue Festlegung

    der sprachlichen Mittel ist notwendig, da Logiken ber

    verschiedenen Sprachen ganz verschiedene Eigen

    schaften haben.

    Wir beschrnken uns hier auf die sogenannte Pr

    dikatenlogik erster Stufe. In ihr stehen folgende

    sprachliche Mittel zurVerfgung.

    1.

    Symbole (Namen) fr einzelne Objekte,

    2. Symbole fr Prdikate oder Relationen zwischen

    Objekten (z.B. die Teilbarkeitsrelation zwischen natr

    lichen Zahlen, oder die Relation ist Tochter von"

    zw i

    schen gegenwrtig lebenden Menschen),

    3. Symbole fr Funktionen, die auf Objekten definiert

    sind und Objekte als Werte haben (z.B. die Quadrat

    funktion fr natrliche Zahlen),

    4.

    Symbole fr die aussagenlogischen Verknpfun

    gen und" (geschrieben: ), wenn - so" (geschrie

    ben:-), das Falsum" (geschrieben:

    1 ,

    5. Variablen x, y, z, x

    2

    , . . . fr Objekte sowie S ym

    bole fr die Allquantoren fr alle x" (geschrieben: Vx).

    Die aussagenlogischen Verknpfungen nicht"

    (geschrieben: ) und oder" (geschrieben: v) werden

    definiert, und zwar durch A-> und A v B durch

    Helmut Schwichtenberg*

    ( ) .

    Ferner wird der Existenzquantor es

    gibt ein x" (geschrieben: 3x) definiert: 3xA steht fr

    "IVx HA. Hierbei bezeichnen , sogenannte For

    meln;

    sie werden mit den aussagenlogischen Verknp

    fungen ,

    - 1

    und dem Allquantor Vx aus sogenann

    ten Primformeln aufgebaut. P rimformeln wiederum

    entstehen, indem man Prdikatensymbole auf soge

    nannte Terme anwendet. Terme schliel ich werden

    mittels der Funktionssymbole aus Namen fr einzelne

    Objekte und aus Variablen aufgebaut. Ein Beispiel

    einer Formel ist

    Vx3y(y > Vz(zly-z=

    1

    vz =y));

    ber dem Bereich der natrlichen Zahlen drckt sie

    aus,

    da es unendlich viele Primzahlen gibt, wenn

    man die Relationen >, I und = als ist grer als",

    teilt" und ist gleich" interpretiert.

    Eine Formel heit allgemeingltig, wenn sie fr

    beliebige (nicht leere) Objektbereiche und bei beliebi

    ger Interpretation der in ihr vorkommenden Relations

    und Funktionssymbole sowie Namen in dem betreffen

    den Objektbereich gltig ist. (Man beachte, da ein

    eventuell in der Sprache vorkommendes Gleichheits

    symbol = ebenfalls beliebig interpretiert werden kann,

    also nicht notwendig durch die Gleichheitsrelation ber

    dem Objektbereich.) Zum Beispiel sind die Formeln

    VX

    (

    PX- QX

    )

    A

    P a Qa

    und

    VX

    (

    PX QX

    )

    A

    Pa-3xQx

    allgemeingltig, nicht aber die Formel

    Vx( P x Qx) AP a VxQ x.

    Regeln zur Gewinnung allgemeingltiger Formeln

    lassen sich leicht angeben. Wir beschreiben hier ein

    Regelsystem, das von G. Gentzen 1934 in der Absicht

    aufgestellt wurde, das natrliche Schlieen mglichst

    unverndert wiederzugeben. Er ging von der Beob

    achtung aus, da in mathematischen Beweisen hufig

    zustzliche Annahmen eingefhrt und spter wieder

    beseitigt werden. Dementsprechend werden in dem

    Regelsystem des natrlichen Schlieens nicht For

    meln schlechthin hergeleitet, sondern Formeln aus

    Annahmeformeln A

    15

    . . ., A

    n

    . Wir verwenden folgende

    Regeln

    Annahmeeinfhrung Aus der Annahme ist die For

    mel selbst herleitbar.

    Einfhrung Sind sowohl die Formel als auch die

    Formel jeweils aus gewissen Annahmen herleitbar,

  • 7/25/2019 Wissenschaftsmagazin Mathematische Logik

    5/7

    so ist die Formel aus allen Annahmen gemein

    sam herleitbar.

    ^-Beseitigung. Ist die Formel aus gewissen

    Annahmen herleitbar, so sind sowohl die Formel Aals

    auch die Formel aus diesen Annahmen herleitbar.

    -^-Einfhrung.

    Ist die Formel aus Annahmen

    A

    1f

    . . ., A

    n

    und eventuell der Annahme herleitbar, so

    ist die Formel A-B aus den Annahmen A

    15

    . . ., A

    n

    allein herleitbar.

    ^-Beseitigung.

    Sind sowohl die Formel A- als auch

    die Formel jeweils aus gewissen Annahmen herleit

    bar, so ist die Formel aus allen Annahmen gemein

    sam herleitbar.

    V-Einfhrung. Ist die Formel aus gewissen Annah

    men herleitbar, und kommt in keiner dieser Annahme

    formeln die Variable frei vor, so ist die Formel VxA aus

    diesen Annahmen herleitbar.

    \f-Beseitigung. Ist die Formel VxA aus gewissen

    Annahmen herleitbar, und ist r ein Term, so ist auch die

    Formel A

    x

    [r] aus diesen Annahmen herleitbar; A

    x

    [r]

    bezeichnet das E rgebnis der Substitution des Terms r

    fr alle freien Vorkommen der Variablen in der For

    mel A.

    Prinzip des indirekten Beweises fr Primformeln. Fr

    jede P rimformel gilt die Formel

    ^

    als herleit

    bar.

    Man berlegt sich leicht, da jede mit diesen

    Regeln herleitbare Formel (ohne Annahmen) auch

    all

    gemeingltig ist. Die Umkehrung dieser Aussage, da

    nmlich jede allgemeingltige Formel mit den angege

    benen Regeln hergeleitet werden kann, ist - was

    angesichts der Einfachheit der angegebenen Regeln

    vielleicht berrascht - ebenfalls richtig; dies ist der

    Inhalt des von K. Gdel in seiner Dissertation 1930

    bewiesenen Vollstndigkeitssatzes.

    Es ist hier nicht der P latz, auf den Beweis des

    Vol l

    stndigkeitssatzes einzugehen. Hervorheben

    mchte ich jedoch einige zustzliche E insichten, die

    dieser Beweis vermittelt. Zunchst ist die Behaup

    tung A ist herlei tbar" im (klassischen) schwachen

    Sinn gemeint. D.h. im Beweis wird nicht etwa eine

    Herleitung konstruiert, sondern es wird aus der

    Annahme, da alle Herleitungen eine von verschie

    dene Endformel haben, ein Widerspruch abgeleitet.

    Ferner wird die Voraussetzung Ais t allgemeingltig"

    nicht in ihrer vollen Strke bentigt: Es gengt, da

    man die Al lgemeingltigkeit fr nur einen einzigen

    zugrunde liegenden Objektbereich fordert, nmlich

    fr die (abzhlbare) Menge aller Terme der formalen

    Sprache. Auch die Funktionssymbole sowie die

    Namen kann man fest (und in auf der Hand liegender

    Weise) ber dies em Termbereich interpretieren.

    Lediglich die Relationssymbole mssen - in Abhn

    gigkeit von A - geeignet interpretiert werden. Aber

    auch hier kann man sich auf Interpretationen

    beschrnken, die in der Form

    Fr alle Terme r gilt:

    1

    (r,t),

    und es gibt einen Term s mit e:

    2

    (s,t)

    mit entscheidbaren Eigenschaften

    1}

    2

    von Termen

    definiert sind. Die etwas uferlos erscheinende Voraus

    setzung A ist allgemeingltig" bildet also keinen

    Grund zur Beunruhigung.

    Aufgrund des Gdelschen Vollstndigkeitssatzes

    wissen wir, da die Menge der allgemeingltigen For

    meln mit der Menge der Formeln bereinstimmt, die

    durch die angegebenen R egeln formal hergeleitet wer

    den knnen. Durch systematisches Anwenden der

    Regeln erhlt man deshalb ein Verfahren, mit dem alle

    allgemeingltigen Formeln der Reihe nach aufgezhlt

    werden.

    Die Frage liegt nahe, ob man sogar ein Ent

    scheidungsverfahren fr die Menge aller allgemeingl

    tigen Formeln angeben kann, d.h. ein Verfahren, das

    fr jede vorgelegte Formel der Prdikatenlogik in end

    lich vielen Schritten entscheidet, ob die Formel allge

    meingltig ist oder nicht. Ein Satz von A. Church 1936

    sagt aus, da es ein solches Verfahren nicht geben

    kann. Daraus kann man folgern, da eine weitere

    naheliegende Frage negativ zu beantworten ist,

    nm

    lich ob es ein Aufzhlungsverfahren auch fr die

    Menge aller nicht allgemeingltigen Formeln gibt.

    Gbe es nmlich ein derartiges Aufzhlungsverfahren,

    so htte man auch ein Entscheidungsverfahren fr die

    Menge aller allgemeingltigen F ormeln: Man braucht

    nur die beiden Aufzhlungsverfahren parallel ablaufen

    zu lassen und nachsehen, in welcher der beiden Auf

    zhlungen die zu untersuchende Formel vorkommt.

    2.Arithmetik

    Bisher gingen wir davon aus, da wir mit unserer

    formalen Sprache etwas ber beliebige Objektberei

    che aussagen. Als allgemeingltig sehen wir F ormeln

    an,

    die fr solche beliebigen Objektbereiche und fr

    jede mgliche Interpretation der Symbole der Sprache

    gltig waren. Wir wollen uns jetzt mit der Frage befas

    sen, wie es mit dem Gltigkeitsbegriff aussieht, wenn

    wir speziell die Menge der natrlichen Zahlen 0, 1,

    2, . . . als Objektbereich verwenden, und wenn wir fer

    ner gewissen Symbole der Sprache nur im Standard

    sinn interpretieren, etwa die Symbole 0 (die Zahl 0),

    (die Nachfolgefunktion) und +

    ,

    (Addition und Multipli

    kation) sowie < und = (die Kleiner- und die Gleich

    heitsrelation). Die Herleitungsregeln aus 1 bleiben

    sicherlich gltig. Zustzlich gelten etwa die folgenden

    Axiome:

    -

    die Gleichheitsaxiome x =x, x=y->y =x und

    x =y A y=z->x =z, sowie Axiome, die die Vertrglich

    keit der Gleichheitsrelation mit den vorkommenden

    Funktions- und Relationssymbolen ausdrcken,

    also etwa

    X i

    =

    y i A X

    2

    = y

    2

    - x

    1

    + x

    2

    =y

    1

    +y

    2

    xi=yi

    A X 2 =y

    2

    A x

    1

    < X 2 -

    >

    = y i < y

    2

    - die beiden Peano-Axiome und Nx =Ny->x=y

    - die Definitonsgleichungen fr +, und 3*yB(y) einen realisierenden Term vom

    Typ der Funktionen von Objekten in Objekte, und die

    Formel (3*xA(x)->3*yB(y))-*3*zC(z) einen realisieren

    den Term vom Typ eines Funktionais, das Objektfunk

    tionen O bjekte zuordnet. J edes so lche Urteil lt sich

  • 7/25/2019 Wissenschaftsmagazin Mathematische Logik

    7/7

    nun mittels der von Kreisel 1959 angegebenen soge

    nannten modifizierten Realisierbarkeitsinterpretation

    bersetzen in eine Formel der ursprnglichen Sprache

    ohne den starken Existenzquantor, die man allerdings

    um Variablen hheren Typs erweitern mu. Zum Bei

    spiel wird rrea l is ie r t 3*xA(x) be rse tzt in A( r), r reali-

    s ier t

    3*x(Ax)-*3*yB(y) be rse tzt in V u( A (u )- B (r( w) ) und

    r rea l is ie r t (3*xA(x) ->3*yB(y) )-3*zC (z) be rsetzt in

    Vv[Vu(A (u) - B(v(w)) ] - C (r(v)).

    Die interdierte Bedeutung der Terme r sind offen

    bar berechenbare Funktionale. Dementsprechend ist

    der intendierte Bereich der Variablen hheren Typs der

    Bereich der approximierbaren Funktionale, die den

    natrlichen Definitionsbereich der berechenbaren

    Funktionale bilden. Es ist hier nicht der Platz, auf die

    zugehrige von Scott und Ersov entwickelte Theorie

    einzu gehe n; siehe dazu etwa D. S cott: Domains for

    Denotational Semantics, Lecture Notes in Computer

    Science 150, 1982, S 577-613. Nur soviel sei gesagt:

    Die berechenbaren (bzw. approximierbaren) Funktio

    nale ergeben sich als Ideale (bzw. rekursiv aufzhlbare

    Ideale) von endlichen Approximationen. Deshalb fhrt

    die oben beschriebene bersetzung der Urteile in

    eine Arithmetik zweiter Stufe, die konservativ ist ber

    der in 2 erwhnten P ean o-A rithmetik, d.h. in der

    Sprache ohne Variablen hheren Typs nicht mehr

    Stze als diese herzuleiten gestattet.

    4.

    Anwendungen

    Wir kommen nun auf die zu Beginn gestellte Frage

    zurck, fr welche Zwecke man mathematische

    Beweise verwenden kann. Betrachten wir zunchst

    eine Herleitung einer Formel der Gestalt Vx3yA(x,y)

    mit quantoren freiem A(x,y) etwa in der P ean o-A rith

    metik. Dann kann man, wie G. Kreisel 1953 gezeigt

    hat, aus dieser Herleitung ein Verfahren gewinnen, ein

    solches y in Abhngigkeit von zu berechnen, und

    man erhlt ferner gewisse (allerdings recht groe)

    Schranken fr die Gre von y sowie fr die Komplexi

    tt dieses Verfahrens. Die Art und Weise, in der dieses

    Verfahren oder Programm gewonnen wird, ist univer

    sell, hngt also nicht von der speziellen Herleitung ab.

    Man verwendet dazu die von G. Gentzen eingefhrte

    Technik der sogenannten Normalisierung. Zu beach

    ten ist, da der Existenzquantor vor dem y schwach

    ist. In der Herleitung braucht also das y nicht explizit

    konstruiert zu werden, dennoch enthlt sie immer

    implizit ein Berechnungsverfahren fr y. Dies gilt aller

    dings nur, wenn die Formel A(x,y) in V x3y A (x ,y) qua n-

    torenfrei ist.

    Ferner ist es mglich, die eben erwhnte Technik

    der No rmalisierung zur Ve reinfachung von P rog ram

    men einzusetzen. Man geht dabei etwa so vor, da

    man zun chs t die Terminierung eines vorg ege ben en

    Algorithmus formal beweist; diese Herleitung kann

    man als Teil einer hheren P rogra mmiers prac he auf

    fassen.

    Spezialisiert man dann diese Herleitung und

    gewisse Eingabedaten, so liefert die bereits oben

    beschriebene Umformung der Herleitung durch Nor

    malisierung einen spezielleren, den Eingabedaten

    angepaten Algor ithmus, in dem sozusagen automa

    t isch gewisse durch Besonderheiten der Eingabeda

    ten bedingte Redundanzen entfernt s ind . Genaueres

    hierber findet man in der Dissertation von C. Goad

    (Stanford 1979), oder auch in dem zu Anfang erwhn

    ten Artikel von G. Kreisel.

    Schlielich mchte ich noch eine bisher weitge

    hend ungel ste F rage erw hnen : Wa s wei man mehr,

    wenn man von einem Allsatz VxA(x) mit quantoren

    freiem A(x) nicht nur wei, da er wahr ist, sondern ihn

    sogar mit eingeschrnkten formalen Mitteln bewiesen

    hat? Es liegt nahe zu vermuten, da die Einsicht in die

    G ltigkeit von VxA( x) dann in bes ond ers uniformer"

    Weise gewonnen werden kann. Eine angemessene

    Formulierung dieses Uniformittsbegriffs steht aber

    noch aus ; eventuell eignet sich dafr der von J .-Y

    Girard krzlich eingefhrte Begriff des Dilators.

    'Professor

    Dr.rer.nat.

    He lmu t

    Schw i ch t enbe r g ,

    gebo ren 1942.

    S tudium der Mathema t ik an der

    FL) Berl in und der Universitt

    Mn ster ; dor t 1978 Prom ot ion,

    1974 Habi l i tation. 1974 bis 1978

    wissenschaf t l i cher Rat und Pro

    fessor an der Universitt Heidel

    berg, ab 1978 Inhaber des Lehr

    stuhls fr mathemat ische Logik

    an der Univers i t t Mnchen.

    Nume r i s che Ae rodynam i k

    Num er ische Me thoden we rden mi t H i l fe von Gro

    rechenan lagen zunehm end fr d ie En tw ick lung neue r

    Techno log ien de r Luft- und Raum fah r t genutzt. Dabe i

    geh t es vo r a l lem um e ine Ve rm inde rung des Luftwi

    de rs tands und dami t um e ine Ve r r inge rung ih res

    Treib

    stof fverbrauc hs. Nur durch e ine verstrkten Einsa tz

    nume r ische r En twur f s - und Nach reche nve r fah ren

    s ind wir tscha f t liche Entw rfe kurzf r is t ig ve rfgbar Die

    Grundbez iehungen de r S t rmung smech an ik s ind

    zwa r se i t langem a ls Integral- oder part ie l le Di f fe ren

    t ia lg le ichungen bekannt, konn ten jedoch zunchs t nu r

    un te r phys ika l isch ve re in fachenden Annahm en ge ls t

    we rden . In de r nume r ischen St rmung smech an ik s ind

    Phys ik und Num er ik von ve rg le ichba re r Bedeu tung .

    D ie Phys ik fo rmu l ie r t t re ff ende An fangs - und

    Rand

    beding unge n. Die Num erik um fa al le mit der In tegra

    t ion de r Gle ichungen zusam men hngenden Aufga

    ben .