{"id":31,"date":"2021-12-15T09:52:58","date_gmt":"2021-12-15T09:52:58","guid":{"rendered":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/chapter\/beweise\/"},"modified":"2021-12-15T09:52:58","modified_gmt":"2021-12-15T09:52:58","slug":"beweise","status":"publish","type":"chapter","link":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/chapter\/beweise\/","title":{"raw":"Beweise","rendered":"Beweise"},"content":{"raw":"\n<style>.cmr-5{font-size:50%;}\n.cmr-7{font-size:70%;}\n.cmmi-5{font-size:50%;font-style: italic;}\n.cmmi-7{font-size:70%;font-style: italic;}\n.cmmi-10{font-style: italic;}\n.cmsy-5{font-size:50%;}\n.cmsy-7{font-size:70%;}\n.cmbx-10{ font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-7{font-size:70%;font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-5{font-size:50%;font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmex-7{font-size:70%;}\n.cmex-7x-x-71{font-size:49%;}\n.msam-7{font-size:70%;}\n.msam-5{font-size:50%;}\n.msbm-7{font-size:70%;}\n.msbm-5{font-size:50%;}\n.cmr-17{font-size:170%;}\n.cmr-12{font-size:120%;}\n.cmti-10{ font-style: italic;}\np{margin-top:0;margin-bottom:0}\np.indent{text-indent:0;}\np + p{margin-top:1em;}\np + div, p + pre {margin-top:1em;}\ndiv + p, pre + p {margin-top:1em;}\n@media print {div.crosslinks {visibility:hidden;}}\na img { border-top: 0; border-left: 0; border-right: 0; }\ncenter { margin-top:1em; margin-bottom:1em; }\ntd center { margin-top:0em; margin-bottom:0em; }\n.Canvas { position:relative; }\nmath { text-indent: 0em; }\nli p.indent { text-indent: 0em }\nli p:first-child{ margin-top:0em; }\nli p:last-child, li div:last-child { margin-bottom:0.5em; }\nli p~ul:last-child, li p~ol:last-child{ margin-bottom:0.5em; }\n.enumerate1 {list-style-type:decimal;}\n.enumerate2 {list-style-type:lower-alpha;}\n.enumerate3 {list-style-type:lower-roman;}\n.enumerate4 {list-style-type:upper-alpha;}\n.obeylines-h,.obeylines-v {white-space: nowrap; }\ndiv.obeylines-v p { margin-top:0; margin-bottom:0; }\n.overline{ text-decoration:overline; }\n.overline img{ border-top: 1px solid black; }\ntd.displaylines {text-align:center; white-space:nowrap;}\n.centerline {text-align:center;}\n.rightline {text-align:right;}\npre.verbatim {font-family: monospace,monospace; text-align:left; clear:both; }\n.fbox {padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.fbox {display:table}\ndiv.center div.fbox {text-align:center; clear:both; padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.minipage{width:100%;}\ndiv.center, div.center div.center {text-align: center; margin-left:1em; margin-right:1em;}\ndiv.center {text-align: left;}\ndiv.flushright, div.flushright div.flushright {text-align: right;}\ndiv.flushright div {text-align: left;}\ndiv.flushleft {text-align: left;}\n.underline{ text-decoration:underline; }\n.underline img{ border-bottom: 1px solid black; margin-bottom:1pt; }\n.framebox-c, .framebox-l, .framebox-r { padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\n.framebox-c {text-align:center;}\n.framebox-l {text-align:left;}\n.framebox-r {text-align:right;}\nspan.thank-mark{ vertical-align: super }\nspan.footnote-mark sup.textsuperscript, span.footnote-mark a sup.textsuperscript{ font-size:80%; }\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.tabbing-right {text-align:right;}\ndiv.float, div.figure {margin-left: auto; margin-right: auto;}\ndiv.float img {text-align:center;}\ndiv.figure img {text-align:center;}\n.marginpar,.reversemarginpar {width:20%; float:right; text-align:left; margin-left:auto; margin-top:0.5em; font-size:85%; text-decoration:underline;}\n.marginpar p,.reversemarginpar p{margin-top:0.4em; margin-bottom:0.4em;}\n.reversemarginpar{float:left;}\n.equation td{text-align:center; vertical-align:middle; }\ntd.eq-no{ width:5%; }\ntable.equation { width:100%; }\ndiv.math-display, div.par-math-display{text-align:center;}\nmtr.hline mtd{ border-bottom:black solid 1px; padding-top:2px; padding-bottom:0em; }\nmtr.hline mtd mo{ display:none }\nmath .texttt { font-family: monospace; }\nmath .textit { font-style: italic; }\nmath .textsl { font-style: oblique; }\nmath .textsf { font-family: sans-serif; }\nmath .textbf { font-weight: bold; }\nmo.MathClass-op + mi{margin-left:0.3em}\nmi + mo.MathClass-op{margin-left:0.3em}\n math mstyle[mathvariant=\"bold\"] { font-weight: bold; font-style: normal; }\n math mstyle[mathvariant=\"normal\"] { font-weight: normal; font-style: normal; }\n.partToc a, .partToc, .likepartToc a, .likepartToc {line-height: 200%; font-weight:bold; font-size:110%;}\n.index-item, .index-subitem, .index-subsubitem {display:block}\ndiv.caption {text-indent:-2em; margin-left:3em; margin-right:1em; text-align:left;}\ndiv.caption span.id{font-weight: bold; white-space: nowrap; }\nh1.partHead{text-align: center}\np.bibitem { text-indent: -2em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\np.bibitem-p { text-indent: 0em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\n.paragraphHead, .likeparagraphHead { margin-top:2em; font-weight: bold;}\n.subparagraphHead, .likesubparagraphHead { font-weight: bold;}\n.quote {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; margin-right:1em; text-align:justify;}\n.verse{white-space:nowrap; margin-left:2em}\ndiv.maketitle {text-align:center;}\nh2.titleHead{text-align:center;}\ndiv.maketitle{ margin-bottom: 2em; }\ndiv.author, div.date {text-align:center;}\ndiv.thanks{text-align:left; margin-left:10%; font-size:85%; font-style:italic; }\ndiv.author{white-space: nowrap;}\n.quotation {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; }\n.abstract p {margin-left:5%; margin-right:5%;}\ndiv.abstract {width:100%;}\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.equation-star td{text-align:center; vertical-align:middle; }\ntable.equation-star { width:100%; border-bottom-color: rgb(255,255,255); }\n#content table.equation-star, #content table.equation-star tbody tr td { border: 0px none rgb(255,255,255); }\nmtd.align-odd{margin-left:2em; text-align:right;}\nmtd.align-even{margin-right:2em; text-align:left;}\n.boxed{border: 1px solid black; padding-left:2px; padding-right:2px;}\n.rotatebox{display: inline-block;}\n.item-head{float:left;width:2em;clear:left;}\n.item-content{margin-left:2em;}\n .foreignobject {line-height:100%; font-size:120%; font-family:STIXgeneral,Times,Symbol,cmr10,CMSY10,CMEX10;padding:0; margin:0; text-align:center; }\nmath {vertical-align:baseline; line-height:100%; font-size:100%; font-family:STIXGeneral,Times,Symbol, cmr10,cmsy10,cmex10,cmmi10; font-style: normal; margin:0; padding:0; }\n\n.entry-title{display: none}\n\ndiv.newtheorem { margin-bottom: 2em; margin-top: 2em; border: 1px solid #333; background: #c7e4da; border-color: #4eb79e;}\ndiv.newtheorem h3 { background: #4eb79e; color: white; padding: 0px 15px 0px 15px; margin-top: 12px}\ndiv.newtheorem p { padding: 15px 15px 15px 15px; }\n\ndiv.newtheorem p span.head .ecbx-1095{font-weight: bold}\ndiv.newtheorem p .ecti-1095{font-style: italic}\ndiv.newtheorem div.custom-itemize{font-style: italic}\ndiv.quote{font-style: italic}\ndiv.newtheorem dl, dl.enumerate {display: grid; grid-template-columns: 5% auto; align-items: start; margin-top: 1em}\ndiv.newtheorem dl dd, dl.enumerate dd {margin-bottom: 0.5em}\ndiv.newtheorem dl dt, dl.enumerate dt {font-weight: normal; margin-top: 0px; text-align: right; margin-right: 15%}\ndiv.newtheorem dl dd {font-style: italic}\ndiv.newtheorem dl dt {font-style: italic}\ndiv.proof p span.ecti-1095 {font-style: italic}\ndiv.figure p img { margin-left: auto; margin-right: auto; display: block; }\ndiv.mefigcentered, div.figure { text-align: center }\n\ndl:after {content:\"\";display:table;clear:both;}\ndd {padding:.5em 0;}\ndl {width:100%;}\ndt, dd {display:inline-block; width:125%;}\ndt {text-align:right; font-weight:bold; clear:left; float:left;}\ndd {width:100%; padding-left:1em; padding-top: 0px; clear:right;}\ndd + dd {float:right; clear:both;}\ndd + dt {clear:both;}\ndt + dt {width: 100%; float: none; padding: 0 70% 0 0;}\ndt + dt + dd {margin-top: -2em;}\ndt + dt + dd + dt {margin-top: 2em;}\n<\/style>\n<style>\n\/* CSS Analysis-Skript D-Math ETHZ *\/\n\n\/* Uniform Font, also for headers *\/\nh3 {\n\tfont-family: \"Times New Roman\", serif;\n\tmargin-bottom: 35px;\n}\nh4 {\n\tfont-family: \"Times New Roman\", serif;\n}\nh5 {\n\tfont-family: \"Times New Roman\", serif;\n}\n\n\/* Bold font, e.g. for definitions *\/\n.ecbx-1095 {font-weight: 550 ;}\n\n\n\/* Uniform spacing, indent: larger, noindent, enumerate, itemize *\/\np.indent {\n\tmargin: 25px 0px 0px 0px;\n\ttext-indent: 0px; \n}\np.noindent {\n\tmargin: 15px 0px 0px 0px;\n\ttext-indent: 0px; \n}\ndl.enumerate {\n\tmargin: 0px 0px 0px 0px;\n}\ndl.enumerate dt, dl.enumerate dd {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\ndiv.custom-itemize {\n\tmargin: 0px 0px 0px 0px;\n}\ndiv.custom-itemize div.item-head {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n\ttext-align: center;\n}\ndiv.custom-itemize div.item-head:first-of-type {\n\tmargin-top: 0px;\n} \ndiv.custom-itemize div.item-content {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\n.MJXc-display {\n\tmargin: 15px 0px 0px 0px;\n}\n\n\n\n\/* green metheorem\/melemma CSS class for more\/medium important latex-theorem-environments *\/\n\/* metheorem box+header *\/\ndiv.metheorem {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #c7e4da;\n}\ndiv.metheorem h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* melemma box+header *\/\ndiv.melemma {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #F2F2F2;\n}\ndiv.melemma h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* meexample box+header *\/\ndiv.meexample {\n    margin-bottom: 30px;\n    margin-top: 30px;\n\tpadding: 0px 15px 15px 15px;\n\tborder-color: gainsboro;\n\tborder-style: solid;\n\tborder-width: thin;\n}\ndiv.meexample h4 {\n\tfont-size: inherit;\n\tfont-weight: bold;\n    padding: 15px 0px 0px 0px;\n\tmargin-top: 0px;\n\tmargin-bottom: 5px;\n}\ndiv.meexample h4+p.noindent, div.meexample h4+p.indent {\n\tmargin-top: 5px;\n\ttext-indent: 0px;\n}\n\/* padding and margins for stuff inside these boxes, CSS-selector &gt; doesn't work in WP *\/\ndiv.me details {\n\tmargin: 10px 0px 0px 0px;\n}\ndiv.me dd {\n    width: calc(100% - 30px);\n}\t\n\n\n\/* fixing background of pictures *\/\nimg {\n\tbackground: white;\n}\n\n\/* div-container for centered geoapplet *\/\ndiv.geoapplet {\n\tmargin-left: auto;\n\tmargin-right: auto;\n\tmargin-top: 15px;\n\tmax-width: 100%;\n}\ndiv.geoapplet iframe {\n\tborder-style: none;\n\tmax-height: 110vw;\n}\n\n\/* div-container for centered squeezed tables *\/\ndiv.websqueeze {\n\tmargin-left: auto;\n\tmargin-right: auto;\n}\n\n\/* two containers for squeezing text sizes *\/\ndiv.mesmalltext, div.mesmalltext * {\n\tfont-size: 15px;\n}\nspan.metinytext, span.metinytext * {\n\tfont-size: 12px;\n}\n\n\n\/* removing grid lines in equations *\/\n#content table.equation tr td, #content table.equation tr th {\n    border: none;\n}\n#content table.equation {\n    border: none;\n}\n\n\/* hover\/click-solution for short inline explanations and footnotes *\/\n.hover-text {    \/* hidden part *\/\n    display: none;\n}\n.marginpar {     \/* style for footnote as marginpar *\/\n\ttext-decoration: none;\n\tborder: solid;\n\tborder-width: 1pt;\n\tpadding: 3pt;\t\n\twidth: 30%;\n\tbackground: white;\n}\n.hover-trigger { \/* style for hover\/click-trigger text\/symbol *\/\n\tbackground: none;\n\tborder: none;\n\tpadding: 0;\n\toutline: inherit;\t\n\ttext-transform: none;\n\tfont: inherit;\n\tposition: inherit;\n\tvertical-align: baseline;\n    color: #FF7F00;\n\tcursor: help;\n}\n.hover-trigger:hover +.hover-text{\n    display: inline;\n}\n.hover-trigger:active +.hover-text{\n    display: inline;\n}\n\n\/* simplifying style of details\/summary, removing triangle *\/\ndetails summary {\n  background: none;\n  list-style: none;\n  outline: none;\n  cursor: pointer;\n}\ndetails summary::-webkit-details-marker { \n  display: inline;\n  display: none;\n}\n\n\/* MC-True\/False as inline details\/summary *\/\ndetails.mcquest, div.me details.mcquest {\n\tdisplay: inline;\n\tmargin-top: 0px;\n}\nsummary.mcquest {\n\tdisplay: inline;\n\tcolor: #FF7F00;\n\tcursor: help;\n}\n\n\/* proof style: simple black box with gray background \n                little black square at the end on the right *\/\ndiv.proof {\n\tborder-color: black;\n\tborder-style: solid;\n\tborder-width: thin;\n\tbackground-color: #F2F2F2;\n\tpadding: 15px;\n\tmargin-top: 1em; \n}\ndiv.proof p:first-of-type {\n\tmargin: 0px;\n}\ndiv.qed {\n\tmargin-top: -25px;\n\tmargin-bottom: -7px;\n\ttext-align: right;\n}\ntable.equation+div.qed {\n\tmargin-top: -65px;\n}\n\n\/* The following is making also math-formulas inside the headers of Lemmas, etc., white. *\/\ndiv.melemma h4 span {\n    color: white;\n}\ndiv.metheorem h4 span {\n    color: white;\n}\n\n\/* The following are used to avoid fullstop, period, colon, semicolon, and endquote (broader) to move by itself to the next line after a formula.\n   The math-environment before needs to be wrapped in span.maperiod and the fullstop etc. in a span.period --- together they achieve what we want.  *\/\nspan.maperiod {\n       margin-right: 5px;\n}\nspan.period {\n       display: inline-block;\n       width: 0px;\n       margin-left: -5px;\n       margin-right: 4.9px;\n\t   text-indent: 0px;\n}\nspan.maendquote {\n       margin-right: 8px;\n}\nspan.endquote {\n       display: inline-block;\n       width: 0px;\n       margin-left: -8px;\n       margin-right: 7.9px;\n}\n\n\n\/* The following is removing an extra space left of the equation side in aligned equations *\/\nspan.mjx-mtd {\n    padding-left: 0em !important;\n}\n\n\/* The following fixes the weird problem that math appears smaller if it was rendered while the details tag was closed. *\/\ndetails span.mjx-chtml, details span.MathJax_CHTML {\n font-size: 100% !important;\n}\n\n\/* trying to fix line breaks in verbatim, new lines are missing *\/\npre.verbatim {\n\twhite-space: pre-wrap;\n\tfont-size: small;\n}\n<\/style><h3 id=\"z5caf3255d15b\" class=\"sectionHead\"><span class=\"titlemark\">1.8 <\/span> <a id=\"x1-220008\"><\/a>Beweise<\/h3> <p class=\"noindent\">Die Mathematik hat als eine von wenigen Wissenschaften die Eigenschaft, dass alle Resultate der Vergangenheit (abgesehen von menschlichen Fehlern und gewissen Perioden, in denen wieder nach der korrekten Methode gesucht wurde) nach wie vor richtig sind (und nicht bloss in erster N\u00e4herung). Das Erfolgsrezept daf\u00fcr liegt im Aufbau der Mathematik. Das Fundament bilden die Axiome (beispielsweise jene der Mengenlehre oder die Peano-Axiome der nat\u00fcrlichen Zahlen), die als bekannt und richtig angenommen werden. Mittels Definitionen werden neue Begriffe eingef\u00fchrt und mittels Lemmata und Propositionen untersucht und in Verbindung zueinander gebracht, bis aus diesen S\u00e4tze und Theoreme bewiesen werden k\u00f6nnen. Selbstverst\u00e4ndlich kann man bezweifeln, ob die so entstandenen Theorien interessant oder relevant sind. \u00dcber Interessen l\u00e4sst sich nat\u00fcrlich streiten. Dennoch ist die Relevanz der heutigen mathematischen Theorien in vielen anderen Bereichen schwer zu bestreiten und dies obwohl wir in der Mathematik beispielsweise die <math display=\"inline\"><mn>0<\/mn><\/math> und die Zahl <math display=\"inline\"><mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mo class=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mn>8<\/mn><mn>0<\/mn><\/mrow><\/msup> <\/mrow><\/msup><\/math> (mit so vielen Nullen nach dem Komma wie nach derzeitigen Sch\u00e4tzungen Atome im Weltall) strikt unterscheiden. Zu diesem Thema m\u00f6chten wir dieses <a href=\"https:\/\/m.youtube.com\/watch?v=dK_narib4do\" target=\"_blank\" rel=\"noopener\">Video<\/a>, basierend auf dem lesenswerten <a href=\"http:\/\/www.maths.ed.ac.uk\/~aar\/papers\/wigner.pdf\" target=\"_blank\" rel=\"noopener\">Artikel<\/a> \u201eThe unreasonable effectiveness of mathematics in the natural sciences\u201c von Eugene Wigner, empfehlen. In eine \u00e4hnliche Richtung geht das f\u00fcr ein allgemeines Publikum gedachte <a href=\"https:\/\/www.youtube.com\/watch?v=8mve0UoSxTo&amp;app=desktop\" target=\"_blank\" rel=\"noopener\">Video<\/a> mit geringerer Informationsdichte, das die teilweise \u00fcberraschende N\u00fctzlichkeit der Mathematik in anderen Naturwissenschaften besonders hervorhebt. <\/p><p class=\"indent\">Wir m\u00f6chten an dieser Stelle einige Bemerkungen zu Beweisen machen. Ein Beweis, wie der Name schon sagt, soll die behauptete Aussage unter Verwendung von einfachen logischen Schritten aus vorher Bekanntem (zum Beispiel Axiomen) ableiten. Es gibt daf\u00fcr einige Methoden, die wir zum Teil schon angewendet haben und die unter anderem auch verkn\u00fcpft werden k\u00f6nnen. <\/p><p class=\"indent\">Manche von Ihnen werden sich fragen, warum wir in dieser Vorlesung immer \u201ediese Beweise\u201c besprechen m\u00fcssen. Diese Frage l\u00e4sst sich vielleicht mit der Frage an einen Physik-Professor vergleichen, wieso denn immer so viele Experimente durchgef\u00fchrt werden m\u00fcssen. Beweise sind im Aufbau der Mathematik unersetzlich. Selbst wenn Sie die hier entwickelte Theorie sp\u00e4ter m\u00f6glicherweise nicht in der hier verwendeten Exaktheit und Genauigkeit ben\u00f6tigen, werden Sie bei aktiver Mitarbeit abstraktes Denken erlernen, welches f\u00fcr die Mathematik aber auch f\u00fcr andere Wissenschaften und in der Praxis \u00e4usserst n\u00fctzlich sein wird. <a id=\"x1-22001r18\"><\/a> <\/p> <h4 id=\"zc52bf92806bf\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.1 <\/span> <a id=\"x1-230001\"><\/a>Widerspruchsbeweise<\/h4> <p class=\"noindent\">Angenommen wir wollen eine Aussage <math display=\"inline\"><mi>A<\/mi><\/math>                                                                                                                                                                           beweisen. Dann ist es manchmal einfacher zu zeigen, dass <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> nicht sein kann, also zu einem Widerspruch f\u00fchrt, als direkt <math display=\"inline\"><mi>A<\/mi><\/math> zu zeigen. Wir nennen <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> die <span class=\"ecbx-1095\">indirekte Annahme <\/span>und den Beweis einen <span class=\"ecbx-1095\">Widerspruchsbeweis<\/span>. Man spricht auch vom \u201eSatz vom ausgeschlossenen Dritten\u201c, da entweder <math display=\"inline\"><mi>A<\/mi><\/math> oder <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> gelten muss und es keine dritte M\u00f6glichkeit gibt.<button class=\"hover-trigger\" style=\"vertical-align: super;font: smaller\">\u2020<\/button><span class=\"hover-text\"><span class=\"marginpar\">\u2020 Man sollte dabei darauf achten, dass die Aussage <math display=\"inline\"><mi>A<\/mi><\/math> nicht von einer freien Variablen <math display=\"inline\"><mi>x<\/mi><\/math> abh\u00e4ngt, denn wenn die Aussage eigentlich <math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>X<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> ist, dann ist die Negation <math display=\"inline\"><mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>X<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> und nicht <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>X<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">.<\/span><\/span><\/span> <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"zbf9a58a5f01a\"> <a id=\"x1-23001r83\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 1.83.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Betrachten Sie nochmals die letzten drei Minuten von dem <\/span><a href=\"https:\/\/www.youtube.com\/watch?v=OxGsU8oIWjY\" target=\"_blank\" rel=\"noopener\"><span class=\"ecti-1095\">Video <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ber Hilberts Hotel<\/span><\/a><span class=\"ecti-1095\">.<\/span> <span class=\"ecti-1095\">Formulieren Sie  danach  einen  Widerspruchsbeweis  von  der  Aussage,  dass  die  Menge<\/span> <math display=\"inline\"><msup><mrow><mo class=\"MathClass-open\">{<\/mo><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><mo class=\"MathClass-close\">}<\/mo><\/mrow><mrow><mi>\u2115<\/mi> <\/mrow> <\/msup> <\/math> <span class=\"ecti-1095\">aller unendlich langen Zeichenketten in den Symbolen A und B <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berabz<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">hlbar unendlich ist.<\/span> <\/p> <\/div> <a id=\"x1-23002r23\"><\/a> <h4 id=\"z326894295eef\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.2 <\/span> <a id=\"x1-240002\"><\/a>Kontraposition<\/h4> <p class=\"noindent\">Sind <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><\/math> zwei Aussagen, dann sind die Aussagen <math display=\"inline\"><mi>A<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>B<\/mi><\/math> und <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo> <mspace class=\"thickpace\" width=\"0.28em\" \/> <mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> \u00e4quivalent. Die Aussage <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> wird die Kontraposition der Aussage <math display=\"inline\"><mi>A<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>B<\/mi><\/math> genannt. Wie man sich dies in einem Beweis zunutze machen kann, wollen wir in einem Beispiel illustrieren. <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"z40c79353dc40\"> <a id=\"x1-24001r84\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.84 <\/span>(\u00dcberdeckungen mit Dreiecken)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Folgendes Beispiel entstammt dem Buch von Blatter <\/span><span class=\"cite\"><span class=\"ecti-1095\">[<\/span><a href=\"#Xblatter\"><span class=\"ecti-1095\">Bla03<\/span><\/a><span class=\"ecti-1095\">]<\/span><\/span> <span class=\"ecti-1095\">(Kapitel 1, Seite 6). Sei<\/span> <math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">das gleichseitige Dreieck<\/span> <span class=\"ecti-1095\">mit Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mn>2<\/mn><\/math> <span class=\"ecti-1095\">und sei <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">eine<\/span> <span class=\"ecti-1095\">Zahl kleiner als <\/span><span class=\"maperiod\"><math display=\"inline\"><mn>2<\/mn><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Wir betrachten folgende Aussagen:<\/span> <\/p><blockquote class=\"quote\"> <p class=\"noindent\"><span class=\"maperiod\"><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">:<\/span> <math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst sich mit <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">gleichseitigen Dreiecken der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken.<\/span> <\/p><p class=\"noindent\"><span class=\"maperiod\"><math display=\"inline\"><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">:<\/span> <math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst sich mit <\/span><math display=\"inline\"><mn>5<\/mn><\/math> <span class=\"ecti-1095\">gleichseitigen Dreiecken der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken.<\/span><\/p><\/blockquote> <p class=\"noindent\"><span class=\"ecti-1095\">Bei einer <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">berdeckung durch Dreiecke sind auch <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">berlappungen erlaubt. Wir behaupten nun, dass<\/span> <math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mi>a<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn> <mo class=\"MathClass-punc\">:<\/mo> <mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d4<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">gilt. Auf Grund deren Definitionen impliziert die Aussage<\/span> <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">die<\/span> <span class=\"ecti-1095\">Aussage<\/span><span class=\"ecti-1095\">&nbsp;<\/span><math display=\"inline\"><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><span class=\"ecti-1095\">; in Symbolen<\/span> <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo> <mspace class=\"thickpace\" width=\"0.28em\" \/> <mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><span class=\"ecti-1095\">. Wir fixieren<\/span> <math display=\"inline\"><mi>a<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> <span class=\"ecti-1095\">und beweisen nun die<\/span> <span class=\"ecti-1095\">Implikation <\/span><math display=\"inline\"><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><span class=\"ecti-1095\">, in dem<\/span> <span class=\"ecti-1095\">wir die Kontraposition <\/span><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">beweisen. Wir nehmen <\/span><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">an, also dass sich <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">nicht mit <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">gleichseitigen Dreiecken <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst. Dann muss<\/span> <math display=\"inline\"><mi>a<\/mi> <mo class=\"MathClass-rel\">&lt;<\/mo> <mn>1<\/mn><\/math> <span class=\"ecti-1095\">gelten, denn sonst k<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">nnte<\/span> <span class=\"ecti-1095\">man <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">wie folgt mit Dreiecken<\/span> <span class=\"ecti-1095\">der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mn>1<\/mn><\/math> <span class=\"ecti-1095\">(und also<\/span> <span class=\"ecti-1095\">auch der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math><span class=\"ecti-1095\">)<\/span> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken:<\/span> <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><\/p><div class=\"mefigcentered\" id=\"wpsize=188&amp;url=Pictures\/Einfuehrung\/Kontraposition\/blatter1.pdf\"><img id=\"z46759be89c8b\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Kontraposition\/blatter1.svg\" width=\"188\"><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">Gegeben eine <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">berdeckung von <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">durch<\/span> <span class=\"ecti-1095\">Dreiecke der Seitenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math><span class=\"ecti-1095\">, dann<\/span> <span class=\"ecti-1095\">m<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ssen die in obiger Grafik erhaltenen <\/span><math display=\"inline\"><mn>6<\/mn><\/math> <span class=\"ecti-1095\">Punkte (unten in rot markiert)<\/span> <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><\/p><div class=\"mefigcentered\" id=\"wpsize=189&amp;url=Pictures\/Einfuehrung\/Kontraposition\/blatter2.pdf\"><img id=\"za6f137297623\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Kontraposition\/blatter2.svg\" width=\"189\"><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">in jeweils verschiedenen gleichseitigen Dreiecken der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">enthalten sein, da wir bereits erkannt haben, dass die Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">kleiner als<\/span> <math display=\"inline\"><mn>1<\/mn><\/math> <span class=\"ecti-1095\">ist. Insbesondere sind<\/span> <span class=\"ecti-1095\">mindestens <\/span><math display=\"inline\"><mn>6<\/mn><\/math> <span class=\"ecti-1095\">solche<\/span> <span class=\"ecti-1095\">Dreiecke notwendig, um <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">zu <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken; also gilt <\/span><span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">.<\/span> <\/p><div class=\"geoapplet\" style=\"width: 688px\"><iframe height=\"260px\" scrolling=\"no\" src=\"https:\/\/www.geogebra.org\/material\/iframe\/id\/tskrtvkk\/width\/688\/height\/260\/border\/888888\/rc\/false\/ai\/false\/sdz\/false\/smb\/false\/stb\/false\/stbh\/false\/ld\/false\/sri\/false\" style=\"border:0px\"><\/iframe><\/div><p class=\"indent\"> <\/p> <\/div> <a id=\"x1-24002r24\"><\/a> <h4 id=\"zd7d931897b30\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.3 <\/span> <a id=\"x1-250003\"><\/a>Induktionsbeweise<\/h4> <p class=\"noindent\">Wir haben die Beweismethode der vollst\u00e4ndigen Induktion schon im Beweis von Lemma&nbsp;<a href=\"..\/..\/chapter\/quadratur-der-parabel#x1-4006r3\">1.3<\/a> gesehen (und wissen jetzt, dass diese Methode genau einem definierenden Axiom von <math display=\"inline\"><mi>\u2115<\/mi><\/math> entspricht). Diese wird verwendet, um eine Aussage <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr alle nat\u00fcrlichen Zahlen <math display=\"inline\"><mi>n<\/mi><\/math> zu zeigen. Der <span class=\"ecbx-1095\">Induktionsbeweis <\/span>hat zwei wichtige Teilschritte: <\/p> <div class=\"custom-itemize\"><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><span class=\"ecbx-1095\">Induktionsanfang <\/span>(oder <span class=\"ecbx-1095\">Induktionsverankerung<\/span>): Man zeigt die Aussage <span class=\"maperiod\"><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">.<\/span> <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><span class=\"ecbx-1095\">Induktionsschritt<\/span>: Man zeigt, dass <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr alle nat\u00fcrlichen Zahlen <math display=\"inline\"><mi>n<\/mi><\/math> gilt.<\/div><\/div> <p class=\"noindent\">Man kann einen Beweis mit vollst\u00e4ndiger Induktion mit einem rekursiven Algorithmus vergleichen, der die Aussage f\u00fcr alle nat\u00fcrlichen Zahlen beweist: Wenn man wissen will, warum die Aussage f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><mn>0<\/mn><\/math>                                                                                                                                                                           stimmt, dann zeigt der Induktionsschritt, dass die Aussage stimmt, weil sie schon f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>9<\/mn><\/math> richtig ist. Die Aussage f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>9<\/mn><\/math> stimmt wiederum, weil sie f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>8<\/mn><\/math> stimmt und so weiter bis man bei <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math> angelangt ist. Der Fall <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math> verankert (daher \u201eInduktionsverankerung\u201c) die Rekursion und den Beweis, da wir diesen Fall direkt und ohne Annahme einer anderen, noch zu verifizierenden Aussage \u00fcberpr\u00fcfen. Im n\u00e4chsten Kapitel werden wir weitere Varianten des Induktionsbeweises kennenlernen. <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"z80921f96f293\"> <a id=\"x1-25001r85\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 1.85 <\/span>(Gauss\u2019sche Summationsformel)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Zeigen Sie mittels vollst<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">ndiger Induktion, dass f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r jede nat<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">rliche Zahl<\/span> <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2265<\/mo> <mn>1<\/mn><\/math> <span class=\"ecti-1095\">gilt<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mn>1<\/mn> <mo class=\"MathClass-bin\">+<\/mo> <mn>2<\/mn> <mo class=\"MathClass-bin\">+<\/mo> <mo class=\"MathClass-rel\">\u22ef<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mfrac><mrow><mi>n<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/mrow> <mrow><mn>2<\/mn><\/mrow><\/mfrac> <\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <\/div> <p class=\"indent\">Wir m\u00f6chten auch etwas \u201egeometrischere\u201c Probleme behandeln. <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"z2493f04997fe\"> <a id=\"x1-25002r86\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.86 <\/span>(Eine geometrische Induktion)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Sei <\/span><math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">eine nat<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">rliche Zahl. Wir betrachten das Quadrat mit Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><mi>n<\/mi> <\/mrow> <\/msup> <\/math><span class=\"ecti-1095\">, aus dem ein kleines<\/span> <span class=\"ecti-1095\">Quadrat der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mn>1<\/mn><\/math> <span class=\"ecti-1095\">entfernt wurde.<\/span> <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><\/p><div class=\"mefigcentered\" id=\"wpsize=235&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego1.pdf\"><img id=\"z59692107995d\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego1.svg\" width=\"235\"><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">Bei diesen beiden Quadraten und auch bei allen noch zu erscheinenden<\/span> <span class=\"ecti-1095\">Konstrukten m<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">chten wir nur Ecken an ganzzahligen Stellen (d.h. in<\/span> <math display=\"inline\"><msup><mrow><mi>\u2124<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <\/math><span class=\"ecti-1095\">)<\/span> <span class=\"ecti-1095\">zulassen. Wir behaupten nun, dass sich das obige<\/span> <span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Quadrat mit Loch<\/span><span class=\"ecti-1095\">\u201c<\/span> <span class=\"ecti-1095\">durch Objekte der Art<\/span> <span class=\"ecti-1095\">(rotieren ist erlaubt)<\/span> <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><\/p><div class=\"mefigcentered\" id=\"wpsize=59&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/legobaustein.pdf\"><img id=\"z766798166c63\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/legobaustein.svg\" width=\"59\"><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">abdecken l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst und beweisen dies per Induktion <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ber<\/span> <math display=\"inline\"><mi>n<\/mi><\/math><span class=\"ecti-1095\">. Zum Induktionsanfang<\/span> <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math><span class=\"ecti-1095\">: Das gr<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">ssere Quadrat<\/span> <span class=\"ecti-1095\">hat Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><span class=\"maperiod\"><math display=\"inline\"><mn>2<\/mn><\/math><\/span><span class=\"period\">,<\/span> <span class=\"ecti-1095\">also ist das Bild<\/span> <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><\/p><div class=\"mefigcentered\" id=\"wpsize=59&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego2.pdf\"><img id=\"z1943e7584ef2\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego2.svg\" width=\"59\"><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">und die Aussage stimmt. Angenommen wir wissen, dass die Behauptung f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r<\/span> <math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">korrekt ist. Wir zerlegen das<\/span> <span class=\"ecti-1095\">Quadrat mit Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><mi>n<\/mi><mo class=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msup><\/math> <span class=\"ecti-1095\">in <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">Quadrate der<\/span> <span class=\"ecti-1095\">Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><mi>n<\/mi><\/mrow><\/msup><\/math> <span class=\"ecti-1095\">und entfernen aus einem dieser Quadrate ein kleines Quadrat der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <span class=\"maperiod\"><math display=\"inline\"><mn>1<\/mn><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Zus<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">tzlich entfernen wir aus den anderen Quadraten je ein kleines Quadrat wie in folgendem Bild<\/span> <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><\/p><div class=\"mefigcentered\" id=\"wpsize=234&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego3.pdf\"><img id=\"z3079743f13c2\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego3.svg\" width=\"234\"><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">Die <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">so<\/span> <span class=\"ecti-1095\">entstandenen Objekte (Quadrate mit Loch) lassen sich aber jeweils abdecken nach dem<\/span> <span class=\"ecti-1095\">Induktionsschritt, also folgt die Behauptung.<\/span> <\/p> <\/div> <p class=\"indent\">Vollst\u00e4ndige Induktion ist ein unentbehrliches Hilfsmittel f\u00fcr Beweise in der Mathematik, genauso wie die Rekursion als Programmiermethode in der Informatik. Manchmal hat man jedoch das Gef\u00fchl, dass Induktion zwar den Zweck erf\u00fcllt (also das Lemma, die Proposition oder den Satz beweist), aber trotzdem nicht erkl\u00e4rt, warum eine Aussage richtig sein soll. Ein Beispiel dazu liefert Lemma <a href=\"..\/..\/chapter\/quadratur-der-parabel#x1-4006r3\">1.3<\/a>, da wir aus dem Beweis beispielsweise nicht erkennen k\u00f6nnen, wie wir das Lemma f\u00fcr <math display=\"inline\"><msup><mrow><mn>1<\/mn><\/mrow><mrow><mn>4<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mn>2<\/mn><\/mrow><mrow><mn>4<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mn>3<\/mn><\/mrow><mrow><mn>4<\/mn> <\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mo class=\"MathClass-rel\">\u22ef<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>4<\/mn><\/mrow><\/msup><\/math> verallgemeinern k\u00f6nnten. Vielleicht w\u00fcrden Sie vermuten, dass diese Summe gleich einem Ausdruck der Form <math display=\"inline\"><mfrac><mrow><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>5<\/mn> <\/mrow> <\/msup> <\/mrow> <mrow><mn>5<\/mn><\/mrow><\/mfrac> <mo class=\"MathClass-bin\">+<\/mo> <mi>a<\/mi><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>4<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mi>b<\/mi><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>3<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mi>c<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mi>d<\/mi><mi>n<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mi>e<\/mi><\/math> f\u00fcr gewisse rationale Zahlen <math display=\"inline\"><mi>a<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>b<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>c<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>d<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>e<\/mi><\/math> ist. Es fragt sich jedoch, wie wir diese Konstanten finden k\u00f6nnten. Die Induktionsmethode ist dabei nicht sehr hilfreich, da sie verwendet werden kann um die Wahrheit zu best\u00e4tigen, wenn man sie woanders bereits gefunden hat. Wir werden einen zweiten allgemeineren Beweis von Lemma <a href=\"..\/..\/chapter\/quadratur-der-parabel#x1-4006r3\">1.3<\/a> im Abschnitt <a href=\"..\/..\/chapter\/die-fakultaet-und-der-binomialsatz#x1-850003\">3.3<\/a> besprechen. <a id=\"x1-25003r25\"><\/a> <\/p> <h4 id=\"zbbc74eb96460\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.4 <\/span> <a id=\"x1-260004\"><\/a>Das Schubfachprinzip<\/h4> <p class=\"noindent\">Mancher Existenzbeweis kann auf das Schubfachprinzip (Proposition <a href=\"..\/..\/chapter\/endliche-und-abzaehlbare-mengen#x1-21003r75\">1.75<\/a>) zur\u00fcckgef\u00fchrt werden. Ein Beispiel aus dem Alltag haben wir gleich nach Proposition <a href=\"..\/..\/chapter\/endliche-und-abzaehlbare-mengen#x1-21003r75\">1.75<\/a> erkl\u00e4rt. Hier m\u00f6chten wir das Schubfachprinzip an einem mathematischen Beispiel illustrieren. <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"z70b5e4d8c5b8\"> <a id=\"x1-26001r87\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.87.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Wir betrachten die Abfolge von Zahlen<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">und behaupten, dass es eine davon geben muss, welche durch<\/span> <math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar ist. Dazu<\/span> <span class=\"ecti-1095\">definieren wir die Menge <\/span><math display=\"inline\"><mi>R<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mrow><mo fence=\"true\" form=\"prefix\"> {<\/mo><mrow><mn>0<\/mn><mo class=\"MathClass-punc\">,<\/mo><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">,<\/mo><mn>1<\/mn><mn>6<\/mn><\/mrow><mo fence=\"true\" form=\"postfix\">}<\/mo><\/mrow><\/math> <span class=\"ecti-1095\">(die Reste mod <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math><span class=\"ecti-1095\">)<\/span> <span class=\"ecti-1095\">und die Schubf<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">cher<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><msub><mrow><mi>S<\/mi><\/mrow><mrow><mi>r<\/mi><\/mrow><\/msub> <mo class=\"MathClass-rel\">=<\/mo> <mrow><mo fence=\"true\" form=\"prefix\"> {<\/mo><mrow><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2115<\/mi><mo class=\"MathClass-rel\">\u2223<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>r<\/mi><mstyle class=\"text\"><mtext>&nbsp;ist&nbsp;durch&nbsp;<\/mtext><\/mstyle><mn>1<\/mn><mn>7<\/mn><mstyle class=\"text\"><mtext>&nbsp;teilbar<\/mtext><\/mstyle><\/mrow><mo fence=\"true\" form=\"postfix\">}<\/mo><\/mrow><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r <\/span><math display=\"inline\"><mi>r<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>R<\/mi><\/math><span class=\"ecti-1095\">. Nach Division mit<\/span> <span class=\"ecti-1095\">Rest muss jede der Zahlen <\/span><math display=\"inline\"><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><\/math> <span class=\"ecti-1095\">in einem der Schubf<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">cher <\/span><math display=\"inline\"><msub><mrow><mi>S<\/mi><\/mrow><mrow><mi>r<\/mi><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">enthalten sein und es gibt jeweils genau ein solches Schubfach. Da wir aber genau<\/span> <math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">Schubf<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">cher haben und unendlich viele Zahlen darin verstauen wollen, m<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ssen sicherlich zwei<\/span> <span class=\"ecti-1095\">dieser Zahlen im gleichen Schubfach liegen. Formaler betrachtet man die Abbildung<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"> <mrow><mo fence=\"true\" form=\"prefix\"> {<\/mo><mrow><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><\/mrow><mo fence=\"true\" form=\"postfix\">}<\/mo><\/mrow> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>R<\/mi><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"quad\" width=\"1em\" \/><mi>x<\/mi><mo class=\"MathClass-rel\">\u21a6<\/mo><msub><mrow><mi>r<\/mi><\/mrow><mrow><mi>x<\/mi><\/mrow><\/msub><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">wobei <\/span><math display=\"inline\"><msub><mrow><mi>r<\/mi><\/mrow><mrow><mi>x<\/mi> <\/mrow> <\/msub> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>R<\/mi><\/math> <span class=\"ecti-1095\">die eindeutig<\/span> <span class=\"ecti-1095\">bestimmte Zahl mit <\/span><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <msub><mrow><mi>S<\/mi><\/mrow><mrow><msub><mrow><mi>r<\/mi><\/mrow><mrow><mi>x<\/mi><\/mrow><\/msub><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">ist. Wie erw<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">hnt kann diese Abbildung aber nicht injektiv sein. Es gibt also einen Rest<\/span> <math display=\"inline\"><mi>r<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>R<\/mi><\/math> <span class=\"ecti-1095\">und zwei<\/span> <span class=\"ecti-1095\">Zahlen <\/span><math display=\"inline\"><mi>x<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>y<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2115<\/mi><\/math> <span class=\"ecti-1095\">von<\/span> <span class=\"ecti-1095\">der Form <\/span><math display=\"inline\"><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mn>1<\/mn><\/math> <span class=\"ecti-1095\">mit <\/span><math display=\"inline\"><mi>x<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>y<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <msub><mrow><mi>S<\/mi><\/mrow><mrow><mi>r<\/mi><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">und<\/span> <math display=\"inline\"><mi>y<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mi>x<\/mi><\/math><span class=\"ecti-1095\">. Die Differenz<\/span> <span class=\"ecti-1095\">von <\/span><math display=\"inline\"><mi>x<\/mi><\/math> <span class=\"ecti-1095\">und <\/span><math display=\"inline\"><mi>y<\/mi><\/math> <span class=\"ecti-1095\">ist<\/span> <span class=\"ecti-1095\">von der Form<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo><munder class=\"msub\"><mrow><munder accentunder=\"false\"><mrow> <mn>1<\/mn><mn>1<\/mn><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mn>1<\/mn><\/mrow><mo>\ufe38<\/mo><\/munder><\/mrow><mrow><mo class=\"MathClass-rel\">=<\/mo><mi>a<\/mi><\/mrow><\/munder><munder class=\"msub\"><mrow><munder accentunder=\"false\"><mrow> <mn>0<\/mn><mn>0<\/mn><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mn>0<\/mn><\/mrow><mo>\ufe38<\/mo><\/munder><\/mrow><mrow><mi>n<\/mi><mstyle class=\"text\"><mtext>&nbsp;Nullen<\/mtext><\/mstyle><\/mrow><\/munder> <mo class=\"MathClass-rel\">=<\/mo> <mi>a<\/mi> <mo class=\"MathClass-bin\">\u22c5<\/mo> <mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mi>n<\/mi><\/mrow><\/msup><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">wobei <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">in unserer<\/span> <span class=\"ecti-1095\">Liste vorkommt und <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2115<\/mi><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Des Weiteren ist <\/span><math display=\"inline\"><mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>x<\/mi><\/math> <span class=\"ecti-1095\">wegen<\/span> <\/p> <table id=\"z7a1f570031ce\" class=\"equation-star\"><tr><td> <math class=\"equation\" display=\"block\"> <mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mo class=\"MathClass-open\">(<\/mo><mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>r<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">\u2212<\/mo> <mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>r<\/mi><mo class=\"MathClass-close\">)<\/mo> <\/math><\/td><\/tr><\/table> <p class=\"indent\"><span class=\"ecti-1095\">durch <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar. Da<\/span> <span class=\"ecti-1095\">aber <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">eine Primzahl<\/span> <span class=\"ecti-1095\">ist und weder <\/span><math display=\"inline\"><mn>1<\/mn><mn>0<\/mn><\/math> <span class=\"ecti-1095\">noch <\/span><math display=\"inline\"><mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mi>n<\/mi> <\/mrow> <\/msup> <\/math> <span class=\"ecti-1095\">durch<\/span> <math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar<\/span> <span class=\"ecti-1095\">ist, ist <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">durch <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar.<\/span> <\/p> <\/div> <p class=\"indent\">Das Schubfachprinzip ist gemeinsam mit vielen Weiterentwicklungen eine sehr verbreitete Beweismethode in der Mathematik. Die allgemeine Einsetzbarkeit hat aber gewissermassen auch einen Preis, denn wenn das Schubfachprinzip f\u00fcr einen Existenzbeweis verwendet wird, so gibt der Beweis meist keinerlei Aufschl\u00fcsse, wie man denn das Objekt (im Beispiel die konkrete, durch 17 teilbare Zahl) effektiv (also abgesehen von ausprobieren) finden k\u00f6nnte. <a id=\"x1-26002r26\"><\/a> <\/p> <h4 id=\"z96d0aef8bb52\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.5 <\/span> <a id=\"x1-270005\"><\/a>Weitere Methoden<\/h4> <p class=\"noindent\">Es gibt noch viele weitere Beweismethoden. Beispielsweise gibt es Aussagen, die in verschiedenen F\u00e4llen einfachere (aber verschiedene) Beweise haben. Falls diese F\u00e4lle alle M\u00f6glichkeiten abdecken, haben wir den Beweis der Aussage mittels Fallunterscheidung erhalten. <\/p><p class=\"indent\">Ein anderes Beispiel einer Beweismethode (vor allem aus der Kombinatorik) ist die folgende: Angenommen wir wollen die endliche Kardinalit\u00e4t einer Menge bestimmen. Mit Hilfe einer geschickt gew\u00e4hlten Bijektion von dieser Menge in eine andere kann man dieses Z\u00e4hlproblem an einen Ort transportieren, wo man die Antwort einfacher zu finden ist oder bereits kennt. <\/p><p class=\"indent\">Wir haben auch bereits erw\u00e4hnt, dass manche Beweise sozusagen durch die Definitionen der involvierten Objekte erzwungen werden. Letzteres k\u00f6nnen Sie aber nur bemerken, wenn Sie die bereits besprochenen <span class=\"ecti-1095\">Definitionen im Ged<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">chnis <\/span>haben. Wir werden klare F\u00e4lle derartiger Beweise im eSkript als \ud83e\ude86  Matrjoschkabeweise kennzeichnen, da diese Beweise aus mehreren Schichten bestehen, die genauso wie die russischen Matrjoschkapuppen auf nur eine Art und Weise vern\u00fcnftig zusammengebaut werden k\u00f6nnen. Bei Auffinden der Matrjoschkapuppe im eSkript, empfehlen wir Ihnen den folgenden Beweis eigenst\u00e4ndig nach                                                                                                                                                                           folgendem Schema zu formulieren: Angenommen wir wollen f\u00fcr bereits definierte Aussagen <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>C<\/mi><\/math> zeigen, dass <math display=\"inline\"><mi>A<\/mi> <mo class=\"MathClass-bin\">\u2227<\/mo> <mi>B<\/mi><\/math> die Aussage <math display=\"inline\"><mi>C<\/mi><\/math> impliziert. Wenn sie die Definition von <math display=\"inline\"><mi>C<\/mi><\/math> nachsehen, wird dort \u00fcblicherweise wiederum eine Vorraussetzung \u00fcber die Objekte (Zahlen, Vektoren, Funktionen, \u2026) von Interesse auftauchen. Nun nehmnen sie diese Vorraussetzung und erinnern sich an die Definitionen von <math display=\"inline\"><mi>A<\/mi><\/math> und <span class=\"maperiod\"><math display=\"inline\"><mi>B<\/mi><\/math><\/span><span class=\"period\">,<\/span> mit dem Ziel zu sehen, was sie mit der Vorraussetzung in <math display=\"inline\"><mi>C<\/mi><\/math> zum Beispiel mittels <math display=\"inline\"><mi>A<\/mi><\/math> erhalten k\u00f6nnen. Diese Aussage ist dann aber vielleicht genau die Vorrausetzung in <span class=\"maperiod\"><math display=\"inline\"><mi>B<\/mi><\/math><\/span><span class=\"period\">,<\/span> womit sie eine weitere Aussage \u00fcber die Objekte erhalten. Mit etwas Gl\u00fcck ist dies nun die gew\u00fcnschte Aussage, die in <math display=\"inline\"><mi>C<\/mi><\/math> behauptet wird, und sie haben damit <math display=\"inline\"><mi>A<\/mi> <mo class=\"MathClass-bin\">\u2227<\/mo> <mi>B<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>C<\/mi><\/math> bewiesen. Dieses Schema tauchte zum Beispiel im Beweis von Lemma <a href=\"..\/..\/chapter\/mengenlehre-und-abbildungen#x1-13025r40\">1.40<\/a>(i) auf, wobei in diesem Fall <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>C<\/mi><\/math> jeweils die Injektivit\u00e4t der Funktionen <math display=\"inline\"><mi>g<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>f<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>g<\/mi> <mo class=\"MathClass-bin\">\u2218<\/mo> <mi>f<\/mi><\/math> besagten. Mit \u00dcbung werden sie dieses Schema aber auch in deutlich komplizierteren Beweisen zumindest teilweise wiederfinden. <a id=\"x1-27001r27\"><\/a> <\/p> <h4 id=\"z4e0cf2059777\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.6 <\/span> <a id=\"x1-280006\"><\/a>Anspr\u00fcche an Beweise<\/h4> <p class=\"noindent\">Wie bereits angedeutet, gibt es mehrere W\u00fcnsche, die man an einen Beweis stellen k\u00f6nnte. In erster Linie muss dieser nat\u00fcrlich einen vollst\u00e4ndigen Beweis darstellen, doch k\u00f6nnte man sich auch folgende Punkte w\u00fcnschen: Der Beweis k\u00f6nnte eine gute Erkl\u00e4rung f\u00fcr die Aussage liefert, k\u00f6nnte Verallgemeinerungen zulassen oder k\u00f6nnte bereits als Anleitung gelesen werden, wie man aus dem Existenzbeweis einen Algorithmus zum Auffinden des gesuchten Objektes erstellen kann. F\u00fcr all diese Aussagen werden wir viele Beispiele sehen. Das Auffinden eines zweiten Beweises einer Aussage ist zwar logisch gesehen unn\u00f6tig (und f\u00fcr uns aus Zeitgr\u00fcnden oft nicht m\u00f6glich), kann aber mitunter diese weiteren W\u00fcnsche besser abdecken und insgesamt das Verst\u00e4ndnis der Theorie st\u00e4rken. <a id=\"x1-28001r28\"><\/a> <\/p> <h4 id=\"z3c36ca921dd1\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.7 <\/span> <a id=\"x1-290007\"><\/a>Beweise finden<\/h4> <p class=\"noindent\">Sie fragen sich vielleicht bereits, wie man Beweise (wie zum Beispiel f\u00fcr die \u00dcbungen) finden kann. Die Antwort ist mit \u00dcbung, Hartn\u00e4ckigkeit und Gl\u00fcck. Des Weiteren empfehlen wir Ihnen, Beweise aus der Vorlesung, diesem Skript oder anderer Literatur aus dem Ged\u00e4chtnis zu wiederholen. Dadurch bekommen Sie \u00dcbung und ein gewisses Gesp\u00fcr f\u00fcr die inneren                                                                                                                                                                           Mechanismen von Beweisen. Zus\u00e4tzlich erkennen Sie vielleicht, dass viele Beweise \u00e4hnliche Bauformen aufweisen. Wenn sie die fr\u00fchere <span class=\"ecti-1095\">Beweise bereits im Ged<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">chnis <\/span>haben, so werden sie diese \u00c4hnlichkeiten schneller sehen und Teile dieser Beweise wiederverwenden k\u00f6nnen. <a id=\"x1-29001r29\"><\/a> <\/p> <h4 id=\"zb94cb1e6bdc9\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.8 <\/span> <a id=\"x1-300008\"><\/a>Beweise aufschreiben<\/h4> <p class=\"noindent\">Nachdem Sie die Idee f\u00fcr den Beweis gefunden haben, wollen Sie diesen kommunizieren und aufschreiben. Auch dazu ist (viel) \u00dcbung n\u00f6tig und Sie m\u00fcssen den Beweis vielleicht umstellen oder komplett neu formulieren, bevor er f\u00fcr andere verst\u00e4ndlich wird (was das Ziel sein sollte). Mitunter ist die Reihenfolge der Argumente, wie man sie gefunden hat, m\u00f6glicherweise komplett anders als die Reihenfolge der Argumente, wie man sie pr\u00e4sentieren sollte. Weiters darf ein Beweis nicht nur aus Formeln bestehen, sondern muss dieser auch die Gedanken enthalten, die diesen Formeln Sinn und Zusammenhang geben. Wir verweisen auf <span class=\"cite\">[<a href=\"#Xschichl-steinbauer\">SS12<\/a>]<\/span> und das Buch \u201e Das ist o.B.d.A. trivial\u201c (<span class=\"cite\">[<a href=\"#Xtrivial\">Beu09<\/a>]<\/span>) von Beutelspacher f\u00fcr weitere Tipps in diese Richtung. <\/p><p class=\"indent\">An dieser Stelle m\u00f6chten wir noch die W\u00f6rter \u201eo.B.d.A.\u201c und \u201etrivial\u201c im obigen Buchtitel kommentieren. Die Abk\u00fcrzung \u201eo.B.d.A.\u201csteht f\u00fcr \u201eohne Beschr\u00e4nkung der Allgemeinheit\u201c. Wir verwenden diese, wenn wir den Beweis einer Aussage auf den Beweis eines Spezialfalls reduzieren. Folgendes Beispiel illustriert dies: <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"zdd2ca80fe4f0\"> <a id=\"x1-30001r88\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.88 <\/span>(o.B.d.A)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Sei <\/span><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">die Aussage <\/span><math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <\/mrow><\/msup> <mo class=\"MathClass-rel\">&gt;<\/mo> <msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup><\/math> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ber ganze Zahlen <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>n<\/mi><\/math><\/span><span class=\"period\">,<\/span> <span class=\"ecti-1095\">die die Eigenschaft <\/span><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d4<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mo class=\"MathClass-bin\">\u2212<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r jede ganze Zahl <\/span><math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">erf<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">llt. Wollen wir die Wahrheit der Aussage <\/span><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">nachweisen, so reicht es anzunehmen, dass <\/span><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2265<\/mo> <mn>0<\/mn><\/math> <span class=\"ecti-1095\">ist, denn ein m<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">gliches Vorzeichen von <\/span><math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">wird von der Funktion <\/span><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2124<\/mi><mo class=\"MathClass-rel\">\u21a6<\/mo><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2124<\/mi><\/math> <span class=\"ecti-1095\">absorbiert. Wir schreiben zu Beginn des Beweises also<\/span> <span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Sei o.B.d.A. <\/span><span class=\"maendquote\"><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2265<\/mo> <mn>0<\/mn><\/math><\/span><span class=\"endquote\">\u201c<\/span><span class=\"ecti-1095\">.<\/span> <\/p> <\/div> <p class=\"indent\">Das Wort \u201e trivial\u201c (abgeleitet von lat. \u201etrivium\u201c) bedeutet \u201ebekannt\u201c oder \u201eallgemein bekannt\u201c und sollte entgegen dem \u00fcblichen Gebrauch nicht mit dem Wort \u201eoffensichtlich\u201c verwechselt werden. Wenn also \u201e\u2026ist trivial\u201c geschrieben wird, so sollte man dies als Aufforderung verstehen, zu                                                                                                                                                                           verifizieren, wieso genau die Aussage \u201ebekannt\u201c sein sollte. Dennoch werden wir und sollten Sie auf den Gebrauch dieses Wortes komplett verzichten. Selbiges betrifft W\u00f6rter wie <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\">\u201eoffensichtlich\u201c , \u201eevident\u201c, \u201eeinfach\u201c und \u201eleicht\u201c<\/p><\/div> <p class=\"noindent\">oder Phrasen wie <\/p> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\">\u201e\u2026ist klar\u201c und \u201eEs ist leicht zu sehen, dass \u2026\u201c.<\/p><\/div> <p class=\"noindent\">Grund daf\u00fcr ist, dass diese Ausdr\u00fccke aus Sicht des Lesers als Affront aufgefasst werden k\u00f6nnen; es liegt nicht an der Verfasserin oder dem Verfasser, die Schwierigkeit einer Aussage zu beurteilen, die sie oder er selbst hingeschrieben hat. Des Weiteren kann man eine (vermeintlich) einfache Aussage oft auch in wenigen Worten erkl\u00e4ren. <a id=\"x1-30002r30\"><\/a> <\/p> <h4 id=\"zf5ac672a4b38\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.9 <\/span> <a id=\"x1-310009\"><\/a>Beweise lesen<\/h4> <p class=\"noindent\">Ein wichtiger erster Schritt ist die zu beweisende Aussage zu lesen, zu verstehen und zu erkennen, was \u00fcberhaupt zu beweisen ist. Wenn Sie dann den Beweis lesen, dann sollten Sie jeden Schritt hinterfragen und dabei fast so stur wie ein Computer beim Abarbeiten eines Programms vorgehen. Man kann dazu auch das Motto der Royal Society zitieren: <\/p><blockquote class=\"quote\"> <div class=\"center\"> <p class=\"noindent\"> <\/p><p class=\"noindent\"><span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Nullus in verba<\/span><span class=\"ecti-1095\">\u201c<\/span> <span class=\"ecti-1095\">oder<\/span> <span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Take nobody\u2019s word for it<\/span><span class=\"ecti-1095\">\u201c<\/span><span class=\"ecti-1095\">.<\/span><\/p><\/div> <\/blockquote> <p class=\"noindent\">Sollten Sie einen Schritt nicht verstehen oder nicht einsehen, wieso dieser m\u00f6glich sein soll, dann fragen Sie bei Mitstudenten, bei Assistenten oder beim Professor nach, bis Sie eine zufriedenstellende Antwort bekommen haben. Bem\u00fchen Sie sich jetzt, wo die Themen noch nicht so verflochten sind, ein vollst\u00e4ndiges Verst\u00e4ndnis der besprochenen Begriffe und S\u00e4tze zu entwickeln, und warten Sie nicht darauf bis die Themen \u201einteressanter\u201c werden. Denn dann werden diese auch schwieriger und es wird zunehmend schwieriger werden, den Einstieg zu finden.                                                                                                                                                                           <\/p><p class=\"indent\">Umgekehrt sollten Ihre Beweise auch so aufgeschrieben sein, dass auch ein sturer Leser nicht umhin kommt, die von Ihnen bewiesene Aussage zu akzeptieren. Es hilft, wenn Sie Ihren Beweis einen oder zwei Tage sp\u00e4ter nochmals lesen, da es f\u00fcr Sie dann wahrscheinlich leichter ist, bewusst zu vergessen, was Sie sich beim Niederschreiben gedacht haben und dann vielmehr lesen, was Sie tats\u00e4chlich niedergeschrieben haben. <a id=\"x1-31001r31\"><\/a> <\/p> <h4 id=\"z7286dc7e772b\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.10 <\/span> <a id=\"x1-3200010\"><\/a>Pr\u00e4dikatenlogik vs Umgangssprache<\/h4> <p class=\"noindent\">Wir werden unsere Beweise in der Umgangssprache (also in Deutsch anstatt in formalen Symbolen) formulieren, doch empfehlen wir Ihnen, die \u00dcbersetzung zwischen Umgangssprache und Pr\u00e4dikatenlogik zu \u00fcben. Wenn wir die Analogie zur Informatik etwas weiter ziehen, dann sollten Sie die Pr\u00e4dikatenlogik als Maschinensprache der Beweise verstehen und die Umgangssprache als die h\u00f6here Programmiersprache, die es uns Menschen leichter machen wird, Zusammenh\u00e4nge zu sehen, eine Intuition f\u00fcr die Theorie zu entwickeln und Konversationen \u00fcber den Beweis zu f\u00fchren. Der Autor eines Beweises muss also \u201eals Programmierer\u201c sicherstellen, dass die umgangssprachliche Formulierung ohne Zweideutigkeiten in die Pr\u00e4dikatenlogik \u00fcbersetzt werden kann. Genauso sollte der Leser die Rolle des \u201esturen Computers\u201c spielen und \u00fcberpr\u00fcfen, ob der Beweis \u201e ohne Fehler abl\u00e4uft\u201c. <\/p><p class=\"indent\">Wir werden anfangs unsere Diskussionen n\u00e4her an der Pr\u00e4dikatenlogik halten und mitunter (entgegen \u00fcblichen mathematischen Konventionen) auch die Quantoren <math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">,<\/mo> <mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">,<\/mo> <mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">!<\/mo><\/math> in Symbolen verwenden. Doch werden wir sehen, dass weder die Lineare Algebra noch die Analysis sinnlose Formelsammlungen in Buchstaben und den Symbolen <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-bin\">\u2227<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-bin\">\u2228<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d4<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">!<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-rel\">=<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-rel\">\u2208<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-rel\">\u2286<\/mo><\/math><\/span><span class=\"period\">,<\/span> \u2026bilden. Vielmehr stellen sie zwei sehr massive Geb\u00e4ude mit vielen Stockwerken, interessanten Verzierungen und Erkern sowie mehreren Br\u00fccken zwischen einander und anderen Geb\u00e4uden dar. Wenn Sie das \u201eGeb\u00e4ude\u201c der Linearen Algebra oder das \u201eGeb\u00e4ude\u201c der Analysis verstehen wollen, dann m\u00fcssen Sie zwar die einzelnen Bausteine (in Form von Definitionen, Lemmata und S\u00e4tzen), aber eben auch den Lageplan des Geb\u00e4udes (das w\u00e4ren die Zusammenh\u00e4nge) kennen. Es sind diese Zusammenh\u00e4nge, die in umgangsprachlich formulierten Beweisen klarer werden.                                                                                                                                                                           <\/p><p class=\"indent\">Wir wollen Ihnen am Ende des Hauptteiles dieses Kapitels noch einen <a href=\"http:\/\/www.bbc.co.uk\/programmes\/b00dshx3\" target=\"_blank\" rel=\"noopener\">Podcast<\/a> der BBC empfehlen, der neben geschichtlichen Informationen auch noch eine Zusammenfassung vieler Themen dieses Kapitels bietet. <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"z4394653ef886\"> <span class=\"ecti-1095\">Bemerkung.<\/span><\/h4> <p class=\"indent\">Eigentlich besch\u00e4ftigt sich obiger Podcast mit G\u00f6del\u2019s Unvollst\u00e4ndigkeitssatz, welcher Teil der mathematischen Logik ist. Dieses Teilgebiet der Mathematik besch\u00e4ftigt sich mit der Theorie des Beweisens und Fragen wie \u201eist die Aussage \u2026&nbsp;aus den Axiomen \u2026&nbsp;beweisbar?\u201c. Interessanterweise gibt es in dieser Theorie nicht bloss einen Unvollst\u00e4ndigkeitssatz, sondern auch einen Vollst\u00e4ndigkeitssatz.  Die  Aufl\u00f6sung  dieses  scheinbaren  Paradox  w\u00fcrde  uns jedoch zu weit vom Thema abbringen. <\/p> <\/div> <a id=\"x1-32001r22\"><\/a> \n","rendered":"\n<style scoped=\"scoped\">.cmr-5{font-size:50%;}\n.cmr-7{font-size:70%;}\n.cmmi-5{font-size:50%;font-style: italic;}\n.cmmi-7{font-size:70%;font-style: italic;}\n.cmmi-10{font-style: italic;}\n.cmsy-5{font-size:50%;}\n.cmsy-7{font-size:70%;}\n.cmbx-10{ font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-7{font-size:70%;font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-5{font-size:50%;font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmex-7{font-size:70%;}\n.cmex-7x-x-71{font-size:49%;}\n.msam-7{font-size:70%;}\n.msam-5{font-size:50%;}\n.msbm-7{font-size:70%;}\n.msbm-5{font-size:50%;}\n.cmr-17{font-size:170%;}\n.cmr-12{font-size:120%;}\n.cmti-10{ font-style: italic;}\np{margin-top:0;margin-bottom:0}\np.indent{text-indent:0;}\np + p{margin-top:1em;}\np + div, p + pre {margin-top:1em;}\ndiv + p, pre + p {margin-top:1em;}\n@media print {div.crosslinks {visibility:hidden;}}\na img { border-top: 0; border-left: 0; border-right: 0; }\ncenter { margin-top:1em; margin-bottom:1em; }\ntd center { margin-top:0em; margin-bottom:0em; }\n.Canvas { position:relative; }\nmath { text-indent: 0em; }\nli p.indent { text-indent: 0em }\nli p:first-child{ margin-top:0em; }\nli p:last-child, li div:last-child { margin-bottom:0.5em; }\nli p~ul:last-child, li p~ol:last-child{ margin-bottom:0.5em; }\n.enumerate1 {list-style-type:decimal;}\n.enumerate2 {list-style-type:lower-alpha;}\n.enumerate3 {list-style-type:lower-roman;}\n.enumerate4 {list-style-type:upper-alpha;}\n.obeylines-h,.obeylines-v {white-space: nowrap; }\ndiv.obeylines-v p { margin-top:0; margin-bottom:0; }\n.overline{ text-decoration:overline; }\n.overline img{ border-top: 1px solid black; }\ntd.displaylines {text-align:center; white-space:nowrap;}\n.centerline {text-align:center;}\n.rightline {text-align:right;}\npre.verbatim {font-family: monospace,monospace; text-align:left; clear:both; }\n.fbox {padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.fbox {display:table}\ndiv.center div.fbox {text-align:center; clear:both; padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.minipage{width:100%;}\ndiv.center, div.center div.center {text-align: center; margin-left:1em; margin-right:1em;}\ndiv.center {text-align: left;}\ndiv.flushright, div.flushright div.flushright {text-align: right;}\ndiv.flushright div {text-align: left;}\ndiv.flushleft {text-align: left;}\n.underline{ text-decoration:underline; }\n.underline img{ border-bottom: 1px solid black; margin-bottom:1pt; }\n.framebox-c, .framebox-l, .framebox-r { padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\n.framebox-c {text-align:center;}\n.framebox-l {text-align:left;}\n.framebox-r {text-align:right;}\nspan.thank-mark{ vertical-align: super }\nspan.footnote-mark sup.textsuperscript, span.footnote-mark a sup.textsuperscript{ font-size:80%; }\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.tabbing-right {text-align:right;}\ndiv.float, div.figure {margin-left: auto; margin-right: auto;}\ndiv.float img {text-align:center;}\ndiv.figure img {text-align:center;}\n.marginpar,.reversemarginpar {width:20%; float:right; text-align:left; margin-left:auto; margin-top:0.5em; font-size:85%; text-decoration:underline;}\n.marginpar p,.reversemarginpar p{margin-top:0.4em; margin-bottom:0.4em;}\n.reversemarginpar{float:left;}\n.equation td{text-align:center; vertical-align:middle; }\ntd.eq-no{ width:5%; }\ntable.equation { width:100%; }\ndiv.math-display, div.par-math-display{text-align:center;}\nmtr.hline mtd{ border-bottom:black solid 1px; padding-top:2px; padding-bottom:0em; }\nmtr.hline mtd mo{ display:none }\nmath .texttt { font-family: monospace; }\nmath .textit { font-style: italic; }\nmath .textsl { font-style: oblique; }\nmath .textsf { font-family: sans-serif; }\nmath .textbf { font-weight: bold; }\nmo.MathClass-op + mi{margin-left:0.3em}\nmi + mo.MathClass-op{margin-left:0.3em}\n math mstyle[mathvariant=\"bold\"] { font-weight: bold; font-style: normal; }\n math mstyle[mathvariant=\"normal\"] { font-weight: normal; font-style: normal; }\n.partToc a, .partToc, .likepartToc a, .likepartToc {line-height: 200%; font-weight:bold; font-size:110%;}\n.index-item, .index-subitem, .index-subsubitem {display:block}\ndiv.caption {text-indent:-2em; margin-left:3em; margin-right:1em; text-align:left;}\ndiv.caption span.id{font-weight: bold; white-space: nowrap; }\nh1.partHead{text-align: center}\np.bibitem { text-indent: -2em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\np.bibitem-p { text-indent: 0em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\n.paragraphHead, .likeparagraphHead { margin-top:2em; font-weight: bold;}\n.subparagraphHead, .likesubparagraphHead { font-weight: bold;}\n.quote {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; margin-right:1em; text-align:justify;}\n.verse{white-space:nowrap; margin-left:2em}\ndiv.maketitle {text-align:center;}\nh2.titleHead{text-align:center;}\ndiv.maketitle{ margin-bottom: 2em; }\ndiv.author, div.date {text-align:center;}\ndiv.thanks{text-align:left; margin-left:10%; font-size:85%; font-style:italic; }\ndiv.author{white-space: nowrap;}\n.quotation {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; }\n.abstract p {margin-left:5%; margin-right:5%;}\ndiv.abstract {width:100%;}\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.equation-star td{text-align:center; vertical-align:middle; }\ntable.equation-star { width:100%; border-bottom-color: rgb(255,255,255); }\n#content table.equation-star, #content table.equation-star tbody tr td { border: 0px none rgb(255,255,255); }\nmtd.align-odd{margin-left:2em; text-align:right;}\nmtd.align-even{margin-right:2em; text-align:left;}\n.boxed{border: 1px solid black; padding-left:2px; padding-right:2px;}\n.rotatebox{display: inline-block;}\n.item-head{float:left;width:2em;clear:left;}\n.item-content{margin-left:2em;}\n .foreignobject {line-height:100%; font-size:120%; font-family:STIXgeneral,Times,Symbol,cmr10,CMSY10,CMEX10;padding:0; margin:0; text-align:center; }\nmath {vertical-align:baseline; line-height:100%; font-size:100%; font-family:STIXGeneral,Times,Symbol, cmr10,cmsy10,cmex10,cmmi10; font-style: normal; margin:0; padding:0; }\n\n.entry-title{display: none}\n\ndiv.newtheorem { margin-bottom: 2em; margin-top: 2em; border: 1px solid #333; background: #c7e4da; border-color: #4eb79e;}\ndiv.newtheorem h3 { background: #4eb79e; color: white; padding: 0px 15px 0px 15px; margin-top: 12px}\ndiv.newtheorem p { padding: 15px 15px 15px 15px; }\n\ndiv.newtheorem p span.head .ecbx-1095{font-weight: bold}\ndiv.newtheorem p .ecti-1095{font-style: italic}\ndiv.newtheorem div.custom-itemize{font-style: italic}\ndiv.quote{font-style: italic}\ndiv.newtheorem dl, dl.enumerate {display: grid; grid-template-columns: 5% auto; align-items: start; margin-top: 1em}\ndiv.newtheorem dl dd, dl.enumerate dd {margin-bottom: 0.5em}\ndiv.newtheorem dl dt, dl.enumerate dt {font-weight: normal; margin-top: 0px; text-align: right; margin-right: 15%}\ndiv.newtheorem dl dd {font-style: italic}\ndiv.newtheorem dl dt {font-style: italic}\ndiv.proof p span.ecti-1095 {font-style: italic}\ndiv.figure p img { margin-left: auto; margin-right: auto; display: block; }\ndiv.mefigcentered, div.figure { text-align: center }\n\ndl:after {content:\"\";display:table;clear:both;}\ndd {padding:.5em 0;}\ndl {width:100%;}\ndt, dd {display:inline-block; width:125%;}\ndt {text-align:right; font-weight:bold; clear:left; float:left;}\ndd {width:100%; padding-left:1em; padding-top: 0px; clear:right;}\ndd + dd {float:right; clear:both;}\ndd + dt {clear:both;}\ndt + dt {width: 100%; float: none; padding: 0 70% 0 0;}\ndt + dt + dd {margin-top: -2em;}\ndt + dt + dd + dt {margin-top: 2em;}\n<\/style>\n<style scoped=\"scoped\">\n\/* CSS Analysis-Skript D-Math ETHZ *\/\n\n\/* Uniform Font, also for headers *\/\nh3 {\n\tfont-family: \"Times New Roman\", serif;\n\tmargin-bottom: 35px;\n}\nh4 {\n\tfont-family: \"Times New Roman\", serif;\n}\nh5 {\n\tfont-family: \"Times New Roman\", serif;\n}\n\n\/* Bold font, e.g. for definitions *\/\n.ecbx-1095 {font-weight: 550 ;}\n\n\n\/* Uniform spacing, indent: larger, noindent, enumerate, itemize *\/\np.indent {\n\tmargin: 25px 0px 0px 0px;\n\ttext-indent: 0px; \n}\np.noindent {\n\tmargin: 15px 0px 0px 0px;\n\ttext-indent: 0px; \n}\ndl.enumerate {\n\tmargin: 0px 0px 0px 0px;\n}\ndl.enumerate dt, dl.enumerate dd {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\ndiv.custom-itemize {\n\tmargin: 0px 0px 0px 0px;\n}\ndiv.custom-itemize div.item-head {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n\ttext-align: center;\n}\ndiv.custom-itemize div.item-head:first-of-type {\n\tmargin-top: 0px;\n} \ndiv.custom-itemize div.item-content {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\n.MJXc-display {\n\tmargin: 15px 0px 0px 0px;\n}\n\n\n\n\/* green metheorem\/melemma CSS class for more\/medium important latex-theorem-environments *\/\n\/* metheorem box+header *\/\ndiv.metheorem {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #c7e4da;\n}\ndiv.metheorem h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* melemma box+header *\/\ndiv.melemma {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #F2F2F2;\n}\ndiv.melemma h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* meexample box+header *\/\ndiv.meexample {\n    margin-bottom: 30px;\n    margin-top: 30px;\n\tpadding: 0px 15px 15px 15px;\n\tborder-color: gainsboro;\n\tborder-style: solid;\n\tborder-width: thin;\n}\ndiv.meexample h4 {\n\tfont-size: inherit;\n\tfont-weight: bold;\n    padding: 15px 0px 0px 0px;\n\tmargin-top: 0px;\n\tmargin-bottom: 5px;\n}\ndiv.meexample h4+p.noindent, div.meexample h4+p.indent {\n\tmargin-top: 5px;\n\ttext-indent: 0px;\n}\n\/* padding and margins for stuff inside these boxes, CSS-selector &gt; doesn't work in WP *\/\ndiv.me details {\n\tmargin: 10px 0px 0px 0px;\n}\ndiv.me dd {\n    width: calc(100% - 30px);\n}\t\n\n\n\/* fixing background of pictures *\/\nimg {\n\tbackground: white;\n}\n\n\/* div-container for centered geoapplet *\/\ndiv.geoapplet {\n\tmargin-left: auto;\n\tmargin-right: auto;\n\tmargin-top: 15px;\n\tmax-width: 100%;\n}\ndiv.geoapplet iframe {\n\tborder-style: none;\n\tmax-height: 110vw;\n}\n\n\/* div-container for centered squeezed tables *\/\ndiv.websqueeze {\n\tmargin-left: auto;\n\tmargin-right: auto;\n}\n\n\/* two containers for squeezing text sizes *\/\ndiv.mesmalltext, div.mesmalltext * {\n\tfont-size: 15px;\n}\nspan.metinytext, span.metinytext * {\n\tfont-size: 12px;\n}\n\n\n\/* removing grid lines in equations *\/\n#content table.equation tr td, #content table.equation tr th {\n    border: none;\n}\n#content table.equation {\n    border: none;\n}\n\n\/* hover\/click-solution for short inline explanations and footnotes *\/\n.hover-text {    \/* hidden part *\/\n    display: none;\n}\n.marginpar {     \/* style for footnote as marginpar *\/\n\ttext-decoration: none;\n\tborder: solid;\n\tborder-width: 1pt;\n\tpadding: 3pt;\t\n\twidth: 30%;\n\tbackground: white;\n}\n.hover-trigger { \/* style for hover\/click-trigger text\/symbol *\/\n\tbackground: none;\n\tborder: none;\n\tpadding: 0;\n\toutline: inherit;\t\n\ttext-transform: none;\n\tfont: inherit;\n\tposition: inherit;\n\tvertical-align: baseline;\n    color: #FF7F00;\n\tcursor: help;\n}\n.hover-trigger:hover +.hover-text{\n    display: inline;\n}\n.hover-trigger:active +.hover-text{\n    display: inline;\n}\n\n\/* simplifying style of details\/summary, removing triangle *\/\ndetails summary {\n  background: none;\n  list-style: none;\n  outline: none;\n  cursor: pointer;\n}\ndetails summary::-webkit-details-marker { \n  display: inline;\n  display: none;\n}\n\n\/* MC-True\/False as inline details\/summary *\/\ndetails.mcquest, div.me details.mcquest {\n\tdisplay: inline;\n\tmargin-top: 0px;\n}\nsummary.mcquest {\n\tdisplay: inline;\n\tcolor: #FF7F00;\n\tcursor: help;\n}\n\n\/* proof style: simple black box with gray background \n                little black square at the end on the right *\/\ndiv.proof {\n\tborder-color: black;\n\tborder-style: solid;\n\tborder-width: thin;\n\tbackground-color: #F2F2F2;\n\tpadding: 15px;\n\tmargin-top: 1em; \n}\ndiv.proof p:first-of-type {\n\tmargin: 0px;\n}\ndiv.qed {\n\tmargin-top: -25px;\n\tmargin-bottom: -7px;\n\ttext-align: right;\n}\ntable.equation+div.qed {\n\tmargin-top: -65px;\n}\n\n\/* The following is making also math-formulas inside the headers of Lemmas, etc., white. *\/\ndiv.melemma h4 span {\n    color: white;\n}\ndiv.metheorem h4 span {\n    color: white;\n}\n\n\/* The following are used to avoid fullstop, period, colon, semicolon, and endquote (broader) to move by itself to the next line after a formula.\n   The math-environment before needs to be wrapped in span.maperiod and the fullstop etc. in a span.period --- together they achieve what we want.  *\/\nspan.maperiod {\n       margin-right: 5px;\n}\nspan.period {\n       display: inline-block;\n       width: 0px;\n       margin-left: -5px;\n       margin-right: 4.9px;\n\t   text-indent: 0px;\n}\nspan.maendquote {\n       margin-right: 8px;\n}\nspan.endquote {\n       display: inline-block;\n       width: 0px;\n       margin-left: -8px;\n       margin-right: 7.9px;\n}\n\n\n\/* The following is removing an extra space left of the equation side in aligned equations *\/\nspan.mjx-mtd {\n    padding-left: 0em !important;\n}\n\n\/* The following fixes the weird problem that math appears smaller if it was rendered while the details tag was closed. *\/\ndetails span.mjx-chtml, details span.MathJax_CHTML {\n font-size: 100% !important;\n}\n\n\/* trying to fix line breaks in verbatim, new lines are missing *\/\npre.verbatim {\n\twhite-space: pre-wrap;\n\tfont-size: small;\n}\n<\/style><h3 id=\"z5caf3255d15b\" class=\"sectionHead\"><span class=\"titlemark\">1.8 <\/span> <a id=\"x1-220008\"><\/a>Beweise<\/h3> <p class=\"noindent\">Die Mathematik hat als eine von wenigen Wissenschaften die Eigenschaft, dass alle Resultate der Vergangenheit (abgesehen von menschlichen Fehlern und gewissen Perioden, in denen wieder nach der korrekten Methode gesucht wurde) nach wie vor richtig sind (und nicht bloss in erster N\u00e4herung). Das Erfolgsrezept daf\u00fcr liegt im Aufbau der Mathematik. Das Fundament bilden die Axiome (beispielsweise jene der Mengenlehre oder die Peano-Axiome der nat\u00fcrlichen Zahlen), die als bekannt und richtig angenommen werden. Mittels Definitionen werden neue Begriffe eingef\u00fchrt und mittels Lemmata und Propositionen untersucht und in Verbindung zueinander gebracht, bis aus diesen S\u00e4tze und Theoreme bewiesen werden k\u00f6nnen. Selbstverst\u00e4ndlich kann man bezweifeln, ob die so entstandenen Theorien interessant oder relevant sind. \u00dcber Interessen l\u00e4sst sich nat\u00fcrlich streiten. Dennoch ist die Relevanz der heutigen mathematischen Theorien in vielen anderen Bereichen schwer zu bestreiten und dies obwohl wir in der Mathematik beispielsweise die <math display=\"inline\"><mn>0<\/mn><\/math> und die Zahl <math display=\"inline\"><mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mo class=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mn>8<\/mn><mn>0<\/mn><\/mrow><\/msup> <\/mrow><\/msup><\/math> (mit so vielen Nullen nach dem Komma wie nach derzeitigen Sch\u00e4tzungen Atome im Weltall) strikt unterscheiden. Zu diesem Thema m\u00f6chten wir dieses <a href=\"https:\/\/m.youtube.com\/watch?v=dK_narib4do\" target=\"_blank\" rel=\"noopener\">Video<\/a>, basierend auf dem lesenswerten <a href=\"http:\/\/www.maths.ed.ac.uk\/~aar\/papers\/wigner.pdf\" target=\"_blank\" rel=\"noopener\">Artikel<\/a> \u201eThe unreasonable effectiveness of mathematics in the natural sciences\u201c von Eugene Wigner, empfehlen. In eine \u00e4hnliche Richtung geht das f\u00fcr ein allgemeines Publikum gedachte <a href=\"https:\/\/www.youtube.com\/watch?v=8mve0UoSxTo&amp;app=desktop\" target=\"_blank\" rel=\"noopener\">Video<\/a> mit geringerer Informationsdichte, das die teilweise \u00fcberraschende N\u00fctzlichkeit der Mathematik in anderen Naturwissenschaften besonders hervorhebt. <\/p><p class=\"indent\">Wir m\u00f6chten an dieser Stelle einige Bemerkungen zu Beweisen machen. Ein Beweis, wie der Name schon sagt, soll die behauptete Aussage unter Verwendung von einfachen logischen Schritten aus vorher Bekanntem (zum Beispiel Axiomen) ableiten. Es gibt daf\u00fcr einige Methoden, die wir zum Teil schon angewendet haben und die unter anderem auch verkn\u00fcpft werden k\u00f6nnen. <\/p><p class=\"indent\">Manche von Ihnen werden sich fragen, warum wir in dieser Vorlesung immer \u201ediese Beweise\u201c besprechen m\u00fcssen. Diese Frage l\u00e4sst sich vielleicht mit der Frage an einen Physik-Professor vergleichen, wieso denn immer so viele Experimente durchgef\u00fchrt werden m\u00fcssen. Beweise sind im Aufbau der Mathematik unersetzlich. Selbst wenn Sie die hier entwickelte Theorie sp\u00e4ter m\u00f6glicherweise nicht in der hier verwendeten Exaktheit und Genauigkeit ben\u00f6tigen, werden Sie bei aktiver Mitarbeit abstraktes Denken erlernen, welches f\u00fcr die Mathematik aber auch f\u00fcr andere Wissenschaften und in der Praxis \u00e4usserst n\u00fctzlich sein wird. <a id=\"x1-22001r18\"><\/a> <\/p> <h4 id=\"zc52bf92806bf\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.1 <\/span> <a id=\"x1-230001\"><\/a>Widerspruchsbeweise<\/h4> <p class=\"noindent\">Angenommen wir wollen eine Aussage <math display=\"inline\"><mi>A<\/mi><\/math>                                                                                                                                                                           beweisen. Dann ist es manchmal einfacher zu zeigen, dass <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> nicht sein kann, also zu einem Widerspruch f\u00fchrt, als direkt <math display=\"inline\"><mi>A<\/mi><\/math> zu zeigen. Wir nennen <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> die <span class=\"ecbx-1095\">indirekte Annahme <\/span>und den Beweis einen <span class=\"ecbx-1095\">Widerspruchsbeweis<\/span>. Man spricht auch vom \u201eSatz vom ausgeschlossenen Dritten\u201c, da entweder <math display=\"inline\"><mi>A<\/mi><\/math> oder <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> gelten muss und es keine dritte M\u00f6glichkeit gibt.<button class=\"hover-trigger\" style=\"vertical-align: super;font: smaller\">\u2020<\/button><span class=\"hover-text\"><span class=\"marginpar\">\u2020 Man sollte dabei darauf achten, dass die Aussage <math display=\"inline\"><mi>A<\/mi><\/math> nicht von einer freien Variablen <math display=\"inline\"><mi>x<\/mi><\/math> abh\u00e4ngt, denn wenn die Aussage eigentlich <math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>X<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> ist, dann ist die Negation <math display=\"inline\"><mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>X<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> und nicht <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>X<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">.<\/span><\/span><\/span> <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"zbf9a58a5f01a\"> <a id=\"x1-23001r83\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 1.83.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Betrachten Sie nochmals die letzten drei Minuten von dem <\/span><a href=\"https:\/\/www.youtube.com\/watch?v=OxGsU8oIWjY\" target=\"_blank\" rel=\"noopener\"><span class=\"ecti-1095\">Video <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ber Hilberts Hotel<\/span><\/a><span class=\"ecti-1095\">.<\/span> <span class=\"ecti-1095\">Formulieren Sie  danach  einen  Widerspruchsbeweis  von  der  Aussage,  dass  die  Menge<\/span> <math display=\"inline\"><msup><mrow><mo class=\"MathClass-open\">{<\/mo><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><mo class=\"MathClass-close\">}<\/mo><\/mrow><mrow><mi>\u2115<\/mi> <\/mrow> <\/msup> <\/math> <span class=\"ecti-1095\">aller unendlich langen Zeichenketten in den Symbolen A und B <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berabz<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">hlbar unendlich ist.<\/span> <\/p> <\/div> <a id=\"x1-23002r23\"><\/a> <h4 id=\"z326894295eef\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.2 <\/span> <a id=\"x1-240002\"><\/a>Kontraposition<\/h4> <p class=\"noindent\">Sind <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><\/math> zwei Aussagen, dann sind die Aussagen <math display=\"inline\"><mi>A<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>B<\/mi><\/math> und <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo> <mspace class=\"thickpace\" width=\"0.28em\" \/> <mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> \u00e4quivalent. Die Aussage <math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><\/math> wird die Kontraposition der Aussage <math display=\"inline\"><mi>A<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>B<\/mi><\/math> genannt. Wie man sich dies in einem Beweis zunutze machen kann, wollen wir in einem Beispiel illustrieren. <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"z40c79353dc40\"> <a id=\"x1-24001r84\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.84 <\/span>(\u00dcberdeckungen mit Dreiecken)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Folgendes Beispiel entstammt dem Buch von Blatter <\/span><span class=\"cite\"><span class=\"ecti-1095\">[<\/span><a href=\"#Xblatter\"><span class=\"ecti-1095\">Bla03<\/span><\/a><span class=\"ecti-1095\">]<\/span><\/span> <span class=\"ecti-1095\">(Kapitel 1, Seite 6). Sei<\/span> <math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">das gleichseitige Dreieck<\/span> <span class=\"ecti-1095\">mit Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mn>2<\/mn><\/math> <span class=\"ecti-1095\">und sei <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">eine<\/span> <span class=\"ecti-1095\">Zahl kleiner als <\/span><span class=\"maperiod\"><math display=\"inline\"><mn>2<\/mn><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Wir betrachten folgende Aussagen:<\/span> <\/p><blockquote class=\"quote\"> <p class=\"noindent\"><span class=\"maperiod\"><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">:<\/span> <math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst sich mit <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">gleichseitigen Dreiecken der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken.<\/span> <\/p><p class=\"noindent\"><span class=\"maperiod\"><math display=\"inline\"><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">:<\/span> <math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst sich mit <\/span><math display=\"inline\"><mn>5<\/mn><\/math> <span class=\"ecti-1095\">gleichseitigen Dreiecken der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken.<\/span><\/p><\/blockquote> <p class=\"noindent\"><span class=\"ecti-1095\">Bei einer <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">berdeckung durch Dreiecke sind auch <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">berlappungen erlaubt. Wir behaupten nun, dass<\/span> <math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mi>a<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn> <mo class=\"MathClass-punc\">:<\/mo> <mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d4<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">gilt. Auf Grund deren Definitionen impliziert die Aussage<\/span> <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">die<\/span> <span class=\"ecti-1095\">Aussage<\/span><span class=\"ecti-1095\">&nbsp;<\/span><math display=\"inline\"><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><span class=\"ecti-1095\">; in Symbolen<\/span> <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo> <mspace class=\"thickpace\" width=\"0.28em\" \/> <mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><span class=\"ecti-1095\">. Wir fixieren<\/span> <math display=\"inline\"><mi>a<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> <span class=\"ecti-1095\">und beweisen nun die<\/span> <span class=\"ecti-1095\">Implikation <\/span><math display=\"inline\"><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><span class=\"ecti-1095\">, in dem<\/span> <span class=\"ecti-1095\">wir die Kontraposition <\/span><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">beweisen. Wir nehmen <\/span><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">an, also dass sich <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">nicht mit <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">gleichseitigen Dreiecken <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst. Dann muss<\/span> <math display=\"inline\"><mi>a<\/mi> <mo class=\"MathClass-rel\">&lt;<\/mo> <mn>1<\/mn><\/math> <span class=\"ecti-1095\">gelten, denn sonst k<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">nnte<\/span> <span class=\"ecti-1095\">man <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">wie folgt mit Dreiecken<\/span> <span class=\"ecti-1095\">der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mn>1<\/mn><\/math> <span class=\"ecti-1095\">(und also<\/span> <span class=\"ecti-1095\">auch der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math><span class=\"ecti-1095\">)<\/span> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken:<\/span> <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><div class=\"wp-nocaption \"><\/div><div class=\"mefigcentered\" id=\"wpsize=188&amp;url=Pictures\/Einfuehrung\/Kontraposition\/blatter1.pdf\"><img decoding=\"async\" id=\"z46759be89c8b\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Kontraposition\/blatter1.svg\" width=\"188\" \/><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">Gegeben eine <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">berdeckung von <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">durch<\/span> <span class=\"ecti-1095\">Dreiecke der Seitenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mi>a<\/mi><\/math><span class=\"ecti-1095\">, dann<\/span> <span class=\"ecti-1095\">m<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ssen die in obiger Grafik erhaltenen <\/span><math display=\"inline\"><mn>6<\/mn><\/math> <span class=\"ecti-1095\">Punkte (unten in rot markiert)<\/span> <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><div class=\"wp-nocaption \"><\/div><div class=\"mefigcentered\" id=\"wpsize=189&amp;url=Pictures\/Einfuehrung\/Kontraposition\/blatter2.pdf\"><img decoding=\"async\" id=\"za6f137297623\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Kontraposition\/blatter2.svg\" width=\"189\" \/><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">in jeweils verschiedenen gleichseitigen Dreiecken der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">enthalten sein, da wir bereits erkannt haben, dass die Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">kleiner als<\/span> <math display=\"inline\"><mn>1<\/mn><\/math> <span class=\"ecti-1095\">ist. Insbesondere sind<\/span> <span class=\"ecti-1095\">mindestens <\/span><math display=\"inline\"><mn>6<\/mn><\/math> <span class=\"ecti-1095\">solche<\/span> <span class=\"ecti-1095\">Dreiecke notwendig, um <\/span><math display=\"inline\"><mi>D<\/mi><\/math> <span class=\"ecti-1095\">zu <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">berdecken; also gilt <\/span><span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><mi>B<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>a<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">.<\/span> <\/p><div class=\"geoapplet\" style=\"width: 688px\"><iframe height=\"260px\" scrolling=\"no\" src=\"https:\/\/www.geogebra.org\/material\/iframe\/id\/tskrtvkk\/width\/688\/height\/260\/border\/888888\/rc\/false\/ai\/false\/sdz\/false\/smb\/false\/stb\/false\/stbh\/false\/ld\/false\/sri\/false\" style=\"border:0px\"><\/iframe><\/div><div class=\"wp-nocaption \"><\/div> <\/div> <a id=\"x1-24002r24\"><\/a> <h4 id=\"zd7d931897b30\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.3 <\/span> <a id=\"x1-250003\"><\/a>Induktionsbeweise<\/h4> <p class=\"noindent\">Wir haben die Beweismethode der vollst\u00e4ndigen Induktion schon im Beweis von Lemma&nbsp;<a href=\"..\/..\/chapter\/quadratur-der-parabel#x1-4006r3\">1.3<\/a> gesehen (und wissen jetzt, dass diese Methode genau einem definierenden Axiom von <math display=\"inline\"><mi>\u2115<\/mi><\/math> entspricht). Diese wird verwendet, um eine Aussage <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr alle nat\u00fcrlichen Zahlen <math display=\"inline\"><mi>n<\/mi><\/math> zu zeigen. Der <span class=\"ecbx-1095\">Induktionsbeweis <\/span>hat zwei wichtige Teilschritte: <\/p> <div class=\"custom-itemize\"><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><span class=\"ecbx-1095\">Induktionsanfang <\/span>(oder <span class=\"ecbx-1095\">Induktionsverankerung<\/span>): Man zeigt die Aussage <span class=\"maperiod\"><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/math><\/span><span class=\"period\">.<\/span> <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><span class=\"ecbx-1095\">Induktionsschritt<\/span>: Man zeigt, dass <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr alle nat\u00fcrlichen Zahlen <math display=\"inline\"><mi>n<\/mi><\/math> gilt.<\/div><\/div> <p class=\"noindent\">Man kann einen Beweis mit vollst\u00e4ndiger Induktion mit einem rekursiven Algorithmus vergleichen, der die Aussage f\u00fcr alle nat\u00fcrlichen Zahlen beweist: Wenn man wissen will, warum die Aussage f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><mn>0<\/mn><\/math>                                                                                                                                                                           stimmt, dann zeigt der Induktionsschritt, dass die Aussage stimmt, weil sie schon f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>9<\/mn><\/math> richtig ist. Die Aussage f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>9<\/mn><\/math> stimmt wiederum, weil sie f\u00fcr <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>8<\/mn><\/math> stimmt und so weiter bis man bei <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math> angelangt ist. Der Fall <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math> verankert (daher \u201eInduktionsverankerung\u201c) die Rekursion und den Beweis, da wir diesen Fall direkt und ohne Annahme einer anderen, noch zu verifizierenden Aussage \u00fcberpr\u00fcfen. Im n\u00e4chsten Kapitel werden wir weitere Varianten des Induktionsbeweises kennenlernen. <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"z80921f96f293\"> <a id=\"x1-25001r85\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 1.85 <\/span>(Gauss\u2019sche Summationsformel)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Zeigen Sie mittels vollst<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">ndiger Induktion, dass f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r jede nat<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">rliche Zahl<\/span> <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2265<\/mo> <mn>1<\/mn><\/math> <span class=\"ecti-1095\">gilt<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mn>1<\/mn> <mo class=\"MathClass-bin\">+<\/mo> <mn>2<\/mn> <mo class=\"MathClass-bin\">+<\/mo> <mo class=\"MathClass-rel\">\u22ef<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mfrac><mrow><mi>n<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/mrow> <mrow><mn>2<\/mn><\/mrow><\/mfrac> <\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <\/div> <p class=\"indent\">Wir m\u00f6chten auch etwas \u201egeometrischere\u201c Probleme behandeln. <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"z2493f04997fe\"> <a id=\"x1-25002r86\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.86 <\/span>(Eine geometrische Induktion)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Sei <\/span><math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">eine nat<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">rliche Zahl. Wir betrachten das Quadrat mit Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><mi>n<\/mi> <\/mrow> <\/msup> <\/math><span class=\"ecti-1095\">, aus dem ein kleines<\/span> <span class=\"ecti-1095\">Quadrat der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><mn>1<\/mn><\/math> <span class=\"ecti-1095\">entfernt wurde.<\/span> <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><div class=\"wp-nocaption \"><\/div><div class=\"mefigcentered\" id=\"wpsize=235&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego1.pdf\"><img decoding=\"async\" id=\"z59692107995d\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego1.svg\" width=\"235\" \/><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">Bei diesen beiden Quadraten und auch bei allen noch zu erscheinenden<\/span> <span class=\"ecti-1095\">Konstrukten m<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">chten wir nur Ecken an ganzzahligen Stellen (d.h. in<\/span> <math display=\"inline\"><msup><mrow><mi>\u2124<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <\/math><span class=\"ecti-1095\">)<\/span> <span class=\"ecti-1095\">zulassen. Wir behaupten nun, dass sich das obige<\/span> <span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Quadrat mit Loch<\/span><span class=\"ecti-1095\">\u201c<\/span> <span class=\"ecti-1095\">durch Objekte der Art<\/span> <span class=\"ecti-1095\">(rotieren ist erlaubt)<\/span> <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><div class=\"wp-nocaption \"><\/div><div class=\"mefigcentered\" id=\"wpsize=59&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/legobaustein.pdf\"><img decoding=\"async\" id=\"z766798166c63\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/legobaustein.svg\" width=\"59\" \/><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">abdecken l<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">sst und beweisen dies per Induktion <\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ber<\/span> <math display=\"inline\"><mi>n<\/mi><\/math><span class=\"ecti-1095\">. Zum Induktionsanfang<\/span> <math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math><span class=\"ecti-1095\">: Das gr<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">ssere Quadrat<\/span> <span class=\"ecti-1095\">hat Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><span class=\"maperiod\"><math display=\"inline\"><mn>2<\/mn><\/math><\/span><span class=\"period\">,<\/span> <span class=\"ecti-1095\">also ist das Bild<\/span> <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><div class=\"wp-nocaption \"><\/div><div class=\"mefigcentered\" id=\"wpsize=59&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego2.pdf\"><img decoding=\"async\" id=\"z1943e7584ef2\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego2.svg\" width=\"59\" \/><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">und die Aussage stimmt. Angenommen wir wissen, dass die Behauptung f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r<\/span> <math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">korrekt ist. Wir zerlegen das<\/span> <span class=\"ecti-1095\">Quadrat mit Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><mi>n<\/mi><mo class=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msup><\/math> <span class=\"ecti-1095\">in <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">Quadrate der<\/span> <span class=\"ecti-1095\">Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge <\/span><math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><mi>n<\/mi><\/mrow><\/msup><\/math> <span class=\"ecti-1095\">und entfernen aus einem dieser Quadrate ein kleines Quadrat der Kantenl<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">nge<\/span> <span class=\"maperiod\"><math display=\"inline\"><mn>1<\/mn><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Zus<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">tzlich entfernen wir aus den anderen Quadraten je ein kleines Quadrat wie in folgendem Bild<\/span> <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><div class=\"wp-nocaption \"><\/div><div class=\"mefigcentered\" id=\"wpsize=234&amp;url=Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego3.pdf\"><img decoding=\"async\" id=\"z3079743f13c2\" alt=\"PIC\" src=\"https:\/\/people.math.ethz.ch\/~einsiedl\/Pictures\/Einfuehrung\/Induktionsbeispiele\/Lego\/lego3.svg\" width=\"234\" \/><\/div>  <\/div> <p class=\"noindent\"><span class=\"ecti-1095\">Die <\/span><math display=\"inline\"><mn>4<\/mn><\/math> <span class=\"ecti-1095\">so<\/span> <span class=\"ecti-1095\">entstandenen Objekte (Quadrate mit Loch) lassen sich aber jeweils abdecken nach dem<\/span> <span class=\"ecti-1095\">Induktionsschritt, also folgt die Behauptung.<\/span> <\/p> <\/div> <p class=\"indent\">Vollst\u00e4ndige Induktion ist ein unentbehrliches Hilfsmittel f\u00fcr Beweise in der Mathematik, genauso wie die Rekursion als Programmiermethode in der Informatik. Manchmal hat man jedoch das Gef\u00fchl, dass Induktion zwar den Zweck erf\u00fcllt (also das Lemma, die Proposition oder den Satz beweist), aber trotzdem nicht erkl\u00e4rt, warum eine Aussage richtig sein soll. Ein Beispiel dazu liefert Lemma <a href=\"..\/..\/chapter\/quadratur-der-parabel#x1-4006r3\">1.3<\/a>, da wir aus dem Beweis beispielsweise nicht erkennen k\u00f6nnen, wie wir das Lemma f\u00fcr <math display=\"inline\"><msup><mrow><mn>1<\/mn><\/mrow><mrow><mn>4<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mn>2<\/mn><\/mrow><mrow><mn>4<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mn>3<\/mn><\/mrow><mrow><mn>4<\/mn> <\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mo class=\"MathClass-rel\">\u22ef<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>4<\/mn><\/mrow><\/msup><\/math> verallgemeinern k\u00f6nnten. Vielleicht w\u00fcrden Sie vermuten, dass diese Summe gleich einem Ausdruck der Form <math display=\"inline\"><mfrac><mrow><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>5<\/mn> <\/mrow> <\/msup> <\/mrow> <mrow><mn>5<\/mn><\/mrow><\/mfrac> <mo class=\"MathClass-bin\">+<\/mo> <mi>a<\/mi><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>4<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mi>b<\/mi><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>3<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <msup><mrow><mi>c<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mi>d<\/mi><mi>n<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mi>e<\/mi><\/math> f\u00fcr gewisse rationale Zahlen <math display=\"inline\"><mi>a<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>b<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>c<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>d<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>e<\/mi><\/math> ist. Es fragt sich jedoch, wie wir diese Konstanten finden k\u00f6nnten. Die Induktionsmethode ist dabei nicht sehr hilfreich, da sie verwendet werden kann um die Wahrheit zu best\u00e4tigen, wenn man sie woanders bereits gefunden hat. Wir werden einen zweiten allgemeineren Beweis von Lemma <a href=\"..\/..\/chapter\/quadratur-der-parabel#x1-4006r3\">1.3<\/a> im Abschnitt <a href=\"..\/..\/chapter\/die-fakultaet-und-der-binomialsatz#x1-850003\">3.3<\/a> besprechen. <a id=\"x1-25003r25\"><\/a> <\/p> <h4 id=\"zbbc74eb96460\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.4 <\/span> <a id=\"x1-260004\"><\/a>Das Schubfachprinzip<\/h4> <p class=\"noindent\">Mancher Existenzbeweis kann auf das Schubfachprinzip (Proposition <a href=\"..\/..\/chapter\/endliche-und-abzaehlbare-mengen#x1-21003r75\">1.75<\/a>) zur\u00fcckgef\u00fchrt werden. Ein Beispiel aus dem Alltag haben wir gleich nach Proposition <a href=\"..\/..\/chapter\/endliche-und-abzaehlbare-mengen#x1-21003r75\">1.75<\/a> erkl\u00e4rt. Hier m\u00f6chten wir das Schubfachprinzip an einem mathematischen Beispiel illustrieren. <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"z70b5e4d8c5b8\"> <a id=\"x1-26001r87\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.87.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Wir betrachten die Abfolge von Zahlen<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">und behaupten, dass es eine davon geben muss, welche durch<\/span> <math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar ist. Dazu<\/span> <span class=\"ecti-1095\">definieren wir die Menge <\/span><math display=\"inline\"><mi>R<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mrow><mo fence=\"true\" form=\"prefix\"> {<\/mo><mrow><mn>0<\/mn><mo class=\"MathClass-punc\">,<\/mo><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">,<\/mo><mn>1<\/mn><mn>6<\/mn><\/mrow><mo fence=\"true\" form=\"postfix\">}<\/mo><\/mrow><\/math> <span class=\"ecti-1095\">(die Reste mod <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math><span class=\"ecti-1095\">)<\/span> <span class=\"ecti-1095\">und die Schubf<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">cher<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><msub><mrow><mi>S<\/mi><\/mrow><mrow><mi>r<\/mi><\/mrow><\/msub> <mo class=\"MathClass-rel\">=<\/mo> <mrow><mo fence=\"true\" form=\"prefix\"> {<\/mo><mrow><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2115<\/mi><mo class=\"MathClass-rel\">\u2223<\/mo><mi>n<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>r<\/mi><mstyle class=\"text\"><mtext>&nbsp;ist&nbsp;durch&nbsp;<\/mtext><\/mstyle><mn>1<\/mn><mn>7<\/mn><mstyle class=\"text\"><mtext>&nbsp;teilbar<\/mtext><\/mstyle><\/mrow><mo fence=\"true\" form=\"postfix\">}<\/mo><\/mrow><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r <\/span><math display=\"inline\"><mi>r<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>R<\/mi><\/math><span class=\"ecti-1095\">. Nach Division mit<\/span> <span class=\"ecti-1095\">Rest muss jede der Zahlen <\/span><math display=\"inline\"><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><\/math> <span class=\"ecti-1095\">in einem der Schubf<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">cher <\/span><math display=\"inline\"><msub><mrow><mi>S<\/mi><\/mrow><mrow><mi>r<\/mi><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">enthalten sein und es gibt jeweils genau ein solches Schubfach. Da wir aber genau<\/span> <math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">Schubf<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">cher haben und unendlich viele Zahlen darin verstauen wollen, m<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ssen sicherlich zwei<\/span> <span class=\"ecti-1095\">dieser Zahlen im gleichen Schubfach liegen. Formaler betrachtet man die Abbildung<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"> <mrow><mo fence=\"true\" form=\"prefix\"> {<\/mo><mrow><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><\/mrow><mo fence=\"true\" form=\"postfix\">}<\/mo><\/mrow> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>R<\/mi><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"quad\" width=\"1em\" \/><mi>x<\/mi><mo class=\"MathClass-rel\">\u21a6<\/mo><msub><mrow><mi>r<\/mi><\/mrow><mrow><mi>x<\/mi><\/mrow><\/msub><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">wobei <\/span><math display=\"inline\"><msub><mrow><mi>r<\/mi><\/mrow><mrow><mi>x<\/mi> <\/mrow> <\/msub> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>R<\/mi><\/math> <span class=\"ecti-1095\">die eindeutig<\/span> <span class=\"ecti-1095\">bestimmte Zahl mit <\/span><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <msub><mrow><mi>S<\/mi><\/mrow><mrow><msub><mrow><mi>r<\/mi><\/mrow><mrow><mi>x<\/mi><\/mrow><\/msub><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">ist. Wie erw<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">hnt kann diese Abbildung aber nicht injektiv sein. Es gibt also einen Rest<\/span> <math display=\"inline\"><mi>r<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>R<\/mi><\/math> <span class=\"ecti-1095\">und zwei<\/span> <span class=\"ecti-1095\">Zahlen <\/span><math display=\"inline\"><mi>x<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>y<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2115<\/mi><\/math> <span class=\"ecti-1095\">von<\/span> <span class=\"ecti-1095\">der Form <\/span><math display=\"inline\"><mn>1<\/mn><mn>1<\/mn><mn>1<\/mn><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mn>1<\/mn><\/math> <span class=\"ecti-1095\">mit <\/span><math display=\"inline\"><mi>x<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>y<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <msub><mrow><mi>S<\/mi><\/mrow><mrow><mi>r<\/mi><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">und<\/span> <math display=\"inline\"><mi>y<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mi>x<\/mi><\/math><span class=\"ecti-1095\">. Die Differenz<\/span> <span class=\"ecti-1095\">von <\/span><math display=\"inline\"><mi>x<\/mi><\/math> <span class=\"ecti-1095\">und <\/span><math display=\"inline\"><mi>y<\/mi><\/math> <span class=\"ecti-1095\">ist<\/span> <span class=\"ecti-1095\">von der Form<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo><munder class=\"msub\"><mrow><munder accentunder=\"false\"><mrow> <mn>1<\/mn><mn>1<\/mn><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mn>1<\/mn><\/mrow><mo>\ufe38<\/mo><\/munder><\/mrow><mrow><mo class=\"MathClass-rel\">=<\/mo><mi>a<\/mi><\/mrow><\/munder><munder class=\"msub\"><mrow><munder accentunder=\"false\"><mrow> <mn>0<\/mn><mn>0<\/mn><mi class=\"MathClass-op\">\u2026<\/mi><mo> <\/mo><mn>0<\/mn><\/mrow><mo>\ufe38<\/mo><\/munder><\/mrow><mrow><mi>n<\/mi><mstyle class=\"text\"><mtext>&nbsp;Nullen<\/mtext><\/mstyle><\/mrow><\/munder> <mo class=\"MathClass-rel\">=<\/mo> <mi>a<\/mi> <mo class=\"MathClass-bin\">\u22c5<\/mo> <mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mi>n<\/mi><\/mrow><\/msup><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">wobei <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">in unserer<\/span> <span class=\"ecti-1095\">Liste vorkommt und <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2115<\/mi><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Des Weiteren ist <\/span><math display=\"inline\"><mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>x<\/mi><\/math> <span class=\"ecti-1095\">wegen<\/span> <\/p> <table id=\"z7a1f570031ce\" class=\"equation-star\"><tr><td> <math class=\"equation\" display=\"block\"> <mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mo class=\"MathClass-open\">(<\/mo><mi>y<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>r<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">\u2212<\/mo> <mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>r<\/mi><mo class=\"MathClass-close\">)<\/mo> <\/math><\/td><\/tr><\/table> <p class=\"indent\"><span class=\"ecti-1095\">durch <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar. Da<\/span> <span class=\"ecti-1095\">aber <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">eine Primzahl<\/span> <span class=\"ecti-1095\">ist und weder <\/span><math display=\"inline\"><mn>1<\/mn><mn>0<\/mn><\/math> <span class=\"ecti-1095\">noch <\/span><math display=\"inline\"><mn>1<\/mn><msup><mrow><mn>0<\/mn><\/mrow><mrow><mi>n<\/mi> <\/mrow> <\/msup> <\/math> <span class=\"ecti-1095\">durch<\/span> <math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar<\/span> <span class=\"ecti-1095\">ist, ist <\/span><math display=\"inline\"><mi>a<\/mi><\/math> <span class=\"ecti-1095\">durch <\/span><math display=\"inline\"><mn>1<\/mn><mn>7<\/mn><\/math> <span class=\"ecti-1095\">teilbar.<\/span> <\/p> <\/div> <p class=\"indent\">Das Schubfachprinzip ist gemeinsam mit vielen Weiterentwicklungen eine sehr verbreitete Beweismethode in der Mathematik. Die allgemeine Einsetzbarkeit hat aber gewissermassen auch einen Preis, denn wenn das Schubfachprinzip f\u00fcr einen Existenzbeweis verwendet wird, so gibt der Beweis meist keinerlei Aufschl\u00fcsse, wie man denn das Objekt (im Beispiel die konkrete, durch 17 teilbare Zahl) effektiv (also abgesehen von ausprobieren) finden k\u00f6nnte. <a id=\"x1-26002r26\"><\/a> <\/p> <h4 id=\"z96d0aef8bb52\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.5 <\/span> <a id=\"x1-270005\"><\/a>Weitere Methoden<\/h4> <p class=\"noindent\">Es gibt noch viele weitere Beweismethoden. Beispielsweise gibt es Aussagen, die in verschiedenen F\u00e4llen einfachere (aber verschiedene) Beweise haben. Falls diese F\u00e4lle alle M\u00f6glichkeiten abdecken, haben wir den Beweis der Aussage mittels Fallunterscheidung erhalten. <\/p><p class=\"indent\">Ein anderes Beispiel einer Beweismethode (vor allem aus der Kombinatorik) ist die folgende: Angenommen wir wollen die endliche Kardinalit\u00e4t einer Menge bestimmen. Mit Hilfe einer geschickt gew\u00e4hlten Bijektion von dieser Menge in eine andere kann man dieses Z\u00e4hlproblem an einen Ort transportieren, wo man die Antwort einfacher zu finden ist oder bereits kennt. <\/p><p class=\"indent\">Wir haben auch bereits erw\u00e4hnt, dass manche Beweise sozusagen durch die Definitionen der involvierten Objekte erzwungen werden. Letzteres k\u00f6nnen Sie aber nur bemerken, wenn Sie die bereits besprochenen <span class=\"ecti-1095\">Definitionen im Ged<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">chnis <\/span>haben. Wir werden klare F\u00e4lle derartiger Beweise im eSkript als \ud83e\ude86  Matrjoschkabeweise kennzeichnen, da diese Beweise aus mehreren Schichten bestehen, die genauso wie die russischen Matrjoschkapuppen auf nur eine Art und Weise vern\u00fcnftig zusammengebaut werden k\u00f6nnen. Bei Auffinden der Matrjoschkapuppe im eSkript, empfehlen wir Ihnen den folgenden Beweis eigenst\u00e4ndig nach                                                                                                                                                                           folgendem Schema zu formulieren: Angenommen wir wollen f\u00fcr bereits definierte Aussagen <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>C<\/mi><\/math> zeigen, dass <math display=\"inline\"><mi>A<\/mi> <mo class=\"MathClass-bin\">\u2227<\/mo> <mi>B<\/mi><\/math> die Aussage <math display=\"inline\"><mi>C<\/mi><\/math> impliziert. Wenn sie die Definition von <math display=\"inline\"><mi>C<\/mi><\/math> nachsehen, wird dort \u00fcblicherweise wiederum eine Vorraussetzung \u00fcber die Objekte (Zahlen, Vektoren, Funktionen, \u2026) von Interesse auftauchen. Nun nehmnen sie diese Vorraussetzung und erinnern sich an die Definitionen von <math display=\"inline\"><mi>A<\/mi><\/math> und <span class=\"maperiod\"><math display=\"inline\"><mi>B<\/mi><\/math><\/span><span class=\"period\">,<\/span> mit dem Ziel zu sehen, was sie mit der Vorraussetzung in <math display=\"inline\"><mi>C<\/mi><\/math> zum Beispiel mittels <math display=\"inline\"><mi>A<\/mi><\/math> erhalten k\u00f6nnen. Diese Aussage ist dann aber vielleicht genau die Vorrausetzung in <span class=\"maperiod\"><math display=\"inline\"><mi>B<\/mi><\/math><\/span><span class=\"period\">,<\/span> womit sie eine weitere Aussage \u00fcber die Objekte erhalten. Mit etwas Gl\u00fcck ist dies nun die gew\u00fcnschte Aussage, die in <math display=\"inline\"><mi>C<\/mi><\/math> behauptet wird, und sie haben damit <math display=\"inline\"><mi>A<\/mi> <mo class=\"MathClass-bin\">\u2227<\/mo> <mi>B<\/mi><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>C<\/mi><\/math> bewiesen. Dieses Schema tauchte zum Beispiel im Beweis von Lemma <a href=\"..\/..\/chapter\/mengenlehre-und-abbildungen#x1-13025r40\">1.40<\/a>(i) auf, wobei in diesem Fall <math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>B<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>C<\/mi><\/math> jeweils die Injektivit\u00e4t der Funktionen <math display=\"inline\"><mi>g<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>f<\/mi><mo class=\"MathClass-punc\">,<\/mo><mi>g<\/mi> <mo class=\"MathClass-bin\">\u2218<\/mo> <mi>f<\/mi><\/math> besagten. Mit \u00dcbung werden sie dieses Schema aber auch in deutlich komplizierteren Beweisen zumindest teilweise wiederfinden. <a id=\"x1-27001r27\"><\/a> <\/p> <h4 id=\"z4e0cf2059777\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.6 <\/span> <a id=\"x1-280006\"><\/a>Anspr\u00fcche an Beweise<\/h4> <p class=\"noindent\">Wie bereits angedeutet, gibt es mehrere W\u00fcnsche, die man an einen Beweis stellen k\u00f6nnte. In erster Linie muss dieser nat\u00fcrlich einen vollst\u00e4ndigen Beweis darstellen, doch k\u00f6nnte man sich auch folgende Punkte w\u00fcnschen: Der Beweis k\u00f6nnte eine gute Erkl\u00e4rung f\u00fcr die Aussage liefert, k\u00f6nnte Verallgemeinerungen zulassen oder k\u00f6nnte bereits als Anleitung gelesen werden, wie man aus dem Existenzbeweis einen Algorithmus zum Auffinden des gesuchten Objektes erstellen kann. F\u00fcr all diese Aussagen werden wir viele Beispiele sehen. Das Auffinden eines zweiten Beweises einer Aussage ist zwar logisch gesehen unn\u00f6tig (und f\u00fcr uns aus Zeitgr\u00fcnden oft nicht m\u00f6glich), kann aber mitunter diese weiteren W\u00fcnsche besser abdecken und insgesamt das Verst\u00e4ndnis der Theorie st\u00e4rken. <a id=\"x1-28001r28\"><\/a> <\/p> <h4 id=\"z3c36ca921dd1\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.7 <\/span> <a id=\"x1-290007\"><\/a>Beweise finden<\/h4> <p class=\"noindent\">Sie fragen sich vielleicht bereits, wie man Beweise (wie zum Beispiel f\u00fcr die \u00dcbungen) finden kann. Die Antwort ist mit \u00dcbung, Hartn\u00e4ckigkeit und Gl\u00fcck. Des Weiteren empfehlen wir Ihnen, Beweise aus der Vorlesung, diesem Skript oder anderer Literatur aus dem Ged\u00e4chtnis zu wiederholen. Dadurch bekommen Sie \u00dcbung und ein gewisses Gesp\u00fcr f\u00fcr die inneren                                                                                                                                                                           Mechanismen von Beweisen. Zus\u00e4tzlich erkennen Sie vielleicht, dass viele Beweise \u00e4hnliche Bauformen aufweisen. Wenn sie die fr\u00fchere <span class=\"ecti-1095\">Beweise bereits im Ged<\/span><span class=\"ecti-1095\">\u00e4<\/span><span class=\"ecti-1095\">chnis <\/span>haben, so werden sie diese \u00c4hnlichkeiten schneller sehen und Teile dieser Beweise wiederverwenden k\u00f6nnen. <a id=\"x1-29001r29\"><\/a> <\/p> <h4 id=\"zb94cb1e6bdc9\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.8 <\/span> <a id=\"x1-300008\"><\/a>Beweise aufschreiben<\/h4> <p class=\"noindent\">Nachdem Sie die Idee f\u00fcr den Beweis gefunden haben, wollen Sie diesen kommunizieren und aufschreiben. Auch dazu ist (viel) \u00dcbung n\u00f6tig und Sie m\u00fcssen den Beweis vielleicht umstellen oder komplett neu formulieren, bevor er f\u00fcr andere verst\u00e4ndlich wird (was das Ziel sein sollte). Mitunter ist die Reihenfolge der Argumente, wie man sie gefunden hat, m\u00f6glicherweise komplett anders als die Reihenfolge der Argumente, wie man sie pr\u00e4sentieren sollte. Weiters darf ein Beweis nicht nur aus Formeln bestehen, sondern muss dieser auch die Gedanken enthalten, die diesen Formeln Sinn und Zusammenhang geben. Wir verweisen auf <span class=\"cite\">[<a href=\"#Xschichl-steinbauer\">SS12<\/a>]<\/span> und das Buch \u201e Das ist o.B.d.A. trivial\u201c (<span class=\"cite\">[<a href=\"#Xtrivial\">Beu09<\/a>]<\/span>) von Beutelspacher f\u00fcr weitere Tipps in diese Richtung. <\/p><p class=\"indent\">An dieser Stelle m\u00f6chten wir noch die W\u00f6rter \u201eo.B.d.A.\u201c und \u201etrivial\u201c im obigen Buchtitel kommentieren. Die Abk\u00fcrzung \u201eo.B.d.A.\u201csteht f\u00fcr \u201eohne Beschr\u00e4nkung der Allgemeinheit\u201c. Wir verwenden diese, wenn wir den Beweis einer Aussage auf den Beweis eines Spezialfalls reduzieren. Folgendes Beispiel illustriert dies: <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"zdd2ca80fe4f0\"> <a id=\"x1-30001r88\"><\/a> <span class=\"ecbx-1095\">Beispiel 1.88 <\/span>(o.B.d.A)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Sei <\/span><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">die Aussage <\/span><math display=\"inline\"><msup><mrow><mn>2<\/mn><\/mrow><mrow><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <\/mrow><\/msup> <mo class=\"MathClass-rel\">&gt;<\/mo> <msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup><\/math> <span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">ber ganze Zahlen <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>n<\/mi><\/math><\/span><span class=\"period\">,<\/span> <span class=\"ecti-1095\">die die Eigenschaft <\/span><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d4<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mo class=\"MathClass-bin\">\u2212<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r jede ganze Zahl <\/span><math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">erf<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">llt. Wollen wir die Wahrheit der Aussage <\/span><math display=\"inline\"><mi>A<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>n<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">nachweisen, so reicht es anzunehmen, dass <\/span><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2265<\/mo> <mn>0<\/mn><\/math> <span class=\"ecti-1095\">ist, denn ein m<\/span><span class=\"ecti-1095\">\u00f6<\/span><span class=\"ecti-1095\">gliches Vorzeichen von <\/span><math display=\"inline\"><mi>n<\/mi><\/math> <span class=\"ecti-1095\">wird von der Funktion <\/span><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2124<\/mi><mo class=\"MathClass-rel\">\u21a6<\/mo><msup><mrow><mi>n<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u2124<\/mi><\/math> <span class=\"ecti-1095\">absorbiert. Wir schreiben zu Beginn des Beweises also<\/span> <span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Sei o.B.d.A. <\/span><span class=\"maendquote\"><math display=\"inline\"><mi>n<\/mi> <mo class=\"MathClass-rel\">\u2265<\/mo> <mn>0<\/mn><\/math><\/span><span class=\"endquote\">\u201c<\/span><span class=\"ecti-1095\">.<\/span> <\/p> <\/div> <p class=\"indent\">Das Wort \u201e trivial\u201c (abgeleitet von lat. \u201etrivium\u201c) bedeutet \u201ebekannt\u201c oder \u201eallgemein bekannt\u201c und sollte entgegen dem \u00fcblichen Gebrauch nicht mit dem Wort \u201eoffensichtlich\u201c verwechselt werden. Wenn also \u201e\u2026ist trivial\u201c geschrieben wird, so sollte man dies als Aufforderung verstehen, zu                                                                                                                                                                           verifizieren, wieso genau die Aussage \u201ebekannt\u201c sein sollte. Dennoch werden wir und sollten Sie auf den Gebrauch dieses Wortes komplett verzichten. Selbiges betrifft W\u00f6rter wie <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><p class=\"noindent\">\u201eoffensichtlich\u201c , \u201eevident\u201c, \u201eeinfach\u201c und \u201eleicht\u201c<\/p><\/div> <p class=\"noindent\">oder Phrasen wie <\/p> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><p class=\"noindent\">\u201e\u2026ist klar\u201c und \u201eEs ist leicht zu sehen, dass \u2026\u201c.<\/p><\/div> <p class=\"noindent\">Grund daf\u00fcr ist, dass diese Ausdr\u00fccke aus Sicht des Lesers als Affront aufgefasst werden k\u00f6nnen; es liegt nicht an der Verfasserin oder dem Verfasser, die Schwierigkeit einer Aussage zu beurteilen, die sie oder er selbst hingeschrieben hat. Des Weiteren kann man eine (vermeintlich) einfache Aussage oft auch in wenigen Worten erkl\u00e4ren. <a id=\"x1-30002r30\"><\/a> <\/p> <h4 id=\"zf5ac672a4b38\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.9 <\/span> <a id=\"x1-310009\"><\/a>Beweise lesen<\/h4> <p class=\"noindent\">Ein wichtiger erster Schritt ist die zu beweisende Aussage zu lesen, zu verstehen und zu erkennen, was \u00fcberhaupt zu beweisen ist. Wenn Sie dann den Beweis lesen, dann sollten Sie jeden Schritt hinterfragen und dabei fast so stur wie ein Computer beim Abarbeiten eines Programms vorgehen. Man kann dazu auch das Motto der Royal Society zitieren: <\/p><blockquote class=\"quote\"> <div class=\"center\"> <div class=\"wp-nocaption \"><\/div><p class=\"noindent\"><span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Nullus in verba<\/span><span class=\"ecti-1095\">\u201c<\/span> <span class=\"ecti-1095\">oder<\/span> <span class=\"ecti-1095\">\u201e<\/span><span class=\"ecti-1095\">Take nobody\u2019s word for it<\/span><span class=\"ecti-1095\">\u201c<\/span><span class=\"ecti-1095\">.<\/span><\/p><\/div> <\/blockquote> <p class=\"noindent\">Sollten Sie einen Schritt nicht verstehen oder nicht einsehen, wieso dieser m\u00f6glich sein soll, dann fragen Sie bei Mitstudenten, bei Assistenten oder beim Professor nach, bis Sie eine zufriedenstellende Antwort bekommen haben. Bem\u00fchen Sie sich jetzt, wo die Themen noch nicht so verflochten sind, ein vollst\u00e4ndiges Verst\u00e4ndnis der besprochenen Begriffe und S\u00e4tze zu entwickeln, und warten Sie nicht darauf bis die Themen \u201einteressanter\u201c werden. Denn dann werden diese auch schwieriger und es wird zunehmend schwieriger werden, den Einstieg zu finden.                                                                                                                                                                           <\/p><p class=\"indent\">Umgekehrt sollten Ihre Beweise auch so aufgeschrieben sein, dass auch ein sturer Leser nicht umhin kommt, die von Ihnen bewiesene Aussage zu akzeptieren. Es hilft, wenn Sie Ihren Beweis einen oder zwei Tage sp\u00e4ter nochmals lesen, da es f\u00fcr Sie dann wahrscheinlich leichter ist, bewusst zu vergessen, was Sie sich beim Niederschreiben gedacht haben und dann vielmehr lesen, was Sie tats\u00e4chlich niedergeschrieben haben. <a id=\"x1-31001r31\"><\/a> <\/p> <h4 id=\"z7286dc7e772b\" class=\"subsectionHead\"><span class=\"titlemark\">1.8.10 <\/span> <a id=\"x1-3200010\"><\/a>Pr\u00e4dikatenlogik vs Umgangssprache<\/h4> <p class=\"noindent\">Wir werden unsere Beweise in der Umgangssprache (also in Deutsch anstatt in formalen Symbolen) formulieren, doch empfehlen wir Ihnen, die \u00dcbersetzung zwischen Umgangssprache und Pr\u00e4dikatenlogik zu \u00fcben. Wenn wir die Analogie zur Informatik etwas weiter ziehen, dann sollten Sie die Pr\u00e4dikatenlogik als Maschinensprache der Beweise verstehen und die Umgangssprache als die h\u00f6here Programmiersprache, die es uns Menschen leichter machen wird, Zusammenh\u00e4nge zu sehen, eine Intuition f\u00fcr die Theorie zu entwickeln und Konversationen \u00fcber den Beweis zu f\u00fchren. Der Autor eines Beweises muss also \u201eals Programmierer\u201c sicherstellen, dass die umgangssprachliche Formulierung ohne Zweideutigkeiten in die Pr\u00e4dikatenlogik \u00fcbersetzt werden kann. Genauso sollte der Leser die Rolle des \u201esturen Computers\u201c spielen und \u00fcberpr\u00fcfen, ob der Beweis \u201e ohne Fehler abl\u00e4uft\u201c. <\/p><p class=\"indent\">Wir werden anfangs unsere Diskussionen n\u00e4her an der Pr\u00e4dikatenlogik halten und mitunter (entgegen \u00fcblichen mathematischen Konventionen) auch die Quantoren <math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">,<\/mo> <mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">,<\/mo> <mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">!<\/mo><\/math> in Symbolen verwenden. Doch werden wir sehen, dass weder die Lineare Algebra noch die Analysis sinnlose Formelsammlungen in Buchstaben und den Symbolen <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u00ac<\/mi><mo> <\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-bin\">\u2227<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-bin\">\u2228<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d2<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mspace class=\"thickpace\" width=\"0.28em\" \/><mo class=\"MathClass-rel\">\u21d4<\/mo><mspace class=\"thickpace\" width=\"0.28em\" \/><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2200<\/mi><mo> <\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mi class=\"MathClass-op\">\u2203<\/mi><mo> <\/mo><mo class=\"MathClass-punc\">!<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-rel\">=<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-rel\">\u2208<\/mo><\/math><\/span><span class=\"period\">,<\/span> <span class=\"maperiod\"><math display=\"inline\"><mo class=\"MathClass-rel\">\u2286<\/mo><\/math><\/span><span class=\"period\">,<\/span> \u2026bilden. Vielmehr stellen sie zwei sehr massive Geb\u00e4ude mit vielen Stockwerken, interessanten Verzierungen und Erkern sowie mehreren Br\u00fccken zwischen einander und anderen Geb\u00e4uden dar. Wenn Sie das \u201eGeb\u00e4ude\u201c der Linearen Algebra oder das \u201eGeb\u00e4ude\u201c der Analysis verstehen wollen, dann m\u00fcssen Sie zwar die einzelnen Bausteine (in Form von Definitionen, Lemmata und S\u00e4tzen), aber eben auch den Lageplan des Geb\u00e4udes (das w\u00e4ren die Zusammenh\u00e4nge) kennen. Es sind diese Zusammenh\u00e4nge, die in umgangsprachlich formulierten Beweisen klarer werden.                                                                                                                                                                           <\/p><p class=\"indent\">Wir wollen Ihnen am Ende des Hauptteiles dieses Kapitels noch einen <a href=\"http:\/\/www.bbc.co.uk\/programmes\/b00dshx3\" target=\"_blank\" rel=\"noopener\">Podcast<\/a> der BBC empfehlen, der neben geschichtlichen Informationen auch noch eine Zusammenfassung vieler Themen dieses Kapitels bietet. <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"z4394653ef886\"> <span class=\"ecti-1095\">Bemerkung.<\/span><\/h4> <p class=\"indent\">Eigentlich besch\u00e4ftigt sich obiger Podcast mit G\u00f6del\u2019s Unvollst\u00e4ndigkeitssatz, welcher Teil der mathematischen Logik ist. Dieses Teilgebiet der Mathematik besch\u00e4ftigt sich mit der Theorie des Beweisens und Fragen wie \u201eist die Aussage \u2026&nbsp;aus den Axiomen \u2026&nbsp;beweisbar?\u201c. Interessanterweise gibt es in dieser Theorie nicht bloss einen Unvollst\u00e4ndigkeitssatz, sondern auch einen Vollst\u00e4ndigkeitssatz.  Die  Aufl\u00f6sung  dieses  scheinbaren  Paradox  w\u00fcrde  uns jedoch zu weit vom Thema abbringen. <\/p> <\/div> <a id=\"x1-32001r22\"><\/a> \n","protected":false},"author":1089,"menu_order":8,"template":"","meta":{"pb_show_title":"","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-31","chapter","type-chapter","status-publish","hentry"],"part":23,"_links":{"self":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters\/31","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/users\/1089"}],"version-history":[{"count":0,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters\/31\/revisions"}],"part":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/parts\/23"}],"metadata":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters\/31\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/media?parent=31"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapter-type?post=31"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/contributor?post=31"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/license?post=31"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}