10 bizonyítás

Offtopic

Sziasztok.

Tegyük fel, hogy szeretnék 10 bizonyítást összegyűjteni. Olyan tételek bizonyításait amelyek 1, önmagukban is nagyon fontosak 2, a bizonyításuk olyan trükköt tartalmaz ami miatt különösen fontos ismerni őket.

Ki mit tenne fel egy ilyen listára?

Nálam az első néhány ötlet:
- pitagorasz tétele
- gyökkető irracionalitása
- Cantor tétele
- Gödel I-II
- Tarski fixponttétele
- ...

  • 3729 megtekintés

( KG | 2010. 01. 19., k – 19:10 )

Néhány ötlet elsőre:

- Pithagorasz tételéhez kapcsolódóan: Thalész-tétel
- Másodfokú egyenlet megoldásának levezetése, ehhez kapcsolódóan Viéte-formulák
- Szinusz és koszinusz tételek

( NagyZ v | 2010. 01. 19., k – 19:37 )

ki a celkozonseg? szerintem baromira nem lehet egy lapon emliteni egy fixponttetelt (raadasul ahogy neztem, ez a Tarski fele ez topologiai, ami mar azert eleg advanced) egy pitagorasz tetellel:)

( apal v | 2010. 01. 19., k – 19:51 )

infohoz talan jobban kotheto:
- vegtelen sok primszam van
- szamelmelet alaptetele
- kis fermat-tetel
- minden primszamnak van primitiv gyoke (nem tudom milyen te'tel pontosan, de Euler - Gauss kornyeken keresendo")

de persze ahogy a kollega is mondja feljebb, kerdes, hogy mi/ki a celkozononse'g...

( mkristof | 2010. 01. 20., sze – 07:16 )

Kösz a válaszokat.

Pl. a végtelen sok prímszám van az tényleg fontos, nem is tudom hogyan felejthettem ki. :)

Kétfelé osztanám akkor bizonyításokat: az első csoportban az a tíz, ami elemi, minden embernek ismernie kéne, de legalábbis zéró előképzettséggel megérthető, ha valaki leül és szépen elmagyarázza a fogalmakat (ilyen pl. a prímszámok, gyökkető, pitagorasz, Cantor is talán). Ezek úgymond az emberiség "közös kultúrkincséhez tartoznak".

A második csoport pedig lenne az a tíz, ami meg az informatikához/számítástudományhoz létfontosságú. Ide sorolnám mondjuk a negatív választ az eldöntésproblémára vagy a Tarski féle fixponttételt (funkcionális nyelvek denotációs szemantikája ugye).

Így hogyan töltenétek ki ezt a két kategóriát?

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

( daneey | 2010. 01. 23., szo – 13:39 )

Ha informatikánál tartunk, akkor elég sok kisebb/nagyobb tétel tartozik a gráfelmélethez is. Cayley tétel (prüfer-kóddal) és különböző hasznos tételek. (És sok algoritmus is, útkeresésre, útvonaltervezés :D, stb)

( harlequin | 2010. 01. 23., szo – 13:57 )

egy egyszeru : ugyanannyi egesz szam van mint termeszetes

( Tomato | 2010. 01. 23., szo – 14:44 )

Szerintem nem csak a matematika és az informatika jöhetne szóba. De ez csak az én kicsi elfogult véleményem. Szerintem ide illene Newton négy axiómája is.
-Tomato

Akkor már Heisenberg-féle felcserélési relációk és a Maxwell egyenletek is jöhetnének ide, meg néhány népszerűbb fizikai tétel, a kérdés az, hogy milyen bizonyításokat keresünk, mert ezek (és a Newtoni is) méréseken vagy axiómákon alapulnak és nem matematikai értelemben vett bizonyítások.

Az a baj, hogy nem hiszem, hogyha felírod egyenletekkel a Maxwell-egyenleteket, akkor azt mindenki értené. :) Viszont igazad van abban, hogy méréseken alapulnak ezek a dolgok. Bár a fizikában minden azon alapul, mert ugye így bizonyítjuk a feltevéseket. Azt hiszem indukciónak nevezik ezt a módszert. Én csak arra akartam célozni ezzel, hogy ha már a matematikát meg az informatikát így belevesszük az alapműveltségbe, akkor a fizikát is illő volna. Szerény meglátásom szerint a természettudományokat sajnos így is nagyon hanyagolják, pedig több figyelmet kéne rájuk fordítani.
-Tomato

Igen, ilyenre is szükség lenne, de az inkább a "10 fizikai állítás ami nagyon jó predikciókat eredményez és tudnod kéne róla" topikba illik. :)

Amúgy egyetértve az előttem kommentelővel: vagány, mély és fontos - matematikai értelemben vett - bizonyításokat keresünk/sek.

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

( bri | 2010. 01. 23., szo – 22:41 )

a "minden halmazok halmazának" nemlétezése. szép és elegáns bizonyítás, gondolom sokan ismerik. kell kifejtenem?

Szerintem a tétel bizonyítása rossz (megengedem, hogy homályos) mind a magyar mind az angol wikipediában.
Ime:
F2=e U S(a) U S(a^-1) U S(b) U S(b^-1)
Világos, hiszen azt mondja, hogy K2 stringjei kezdődhetnek bármely betűvel.

A következő viszont szerintem nem lehet jó (vagy a lényeg homályban marad):
F2= aS(a^-1) U S(a)
F2= bS(b^-1) U S(b)

mert F2 definíciójában az volt, hogy a és a^-1 nem lehet egymás mellett, tehát aS(a^-1) nem is K2-beli.
Az írás közben jöttem rá, hogy lehet, hogy mégis jó, csak nincs rendesen leírva.
Lehet, hogy arra utazik ezzel, hogy aa^-1 az egységelem az elején és mivel az az üres string elért egyszerűen levágjuk a trükkel az a-t. Ezesetben viszont ezt oda kellene írni, mert csak szívatja a kedves olvasót.

Pont ez a lenyeg, nem a szivatas, hanem az, hogy ezt szimbolikusan megteheted (marmint aS(a^-1) ervenyes kifejezes, jol definialt), emiatt kapod a paradox eredmenyt belole.
Mondjuk szerintem ez nem paradoxon, csak egyszeruen nehez felfogni azt, mit is jelent a kontinuum szamossag, meg a vegtelen, de nullmerteku halmaz, stb.

Az aS(a^-1) ugyan érvényes, de ilyen string nincs a csoportban a csoportműveletének definíciója szerint, mert ott azt mondjuk, hogy az aa^-1 stringeket üresre (egységelem) kell cserélni. Tehát a aS(a^-1) szerepeltetése egy olyan konkatenáció, aminek az értelme pont a string elején levő a^-1 eltüntetése.
Nekem az nem világos, hogy ha ez a cél akkor miért nem írja oda.
Ha meg már ezzel trükközünk akkor sokkal logikusabbnak tűnik nekem az

F2=aS(a^-1) U S(a^-1)

előállítás, mert ez azt mondaná, hogy az F2 előáll mint azonstringek halmaza amiről (trükkösen) levágtuk az elejéről az a^-1-et és azokból amit a^-1-gyel kezdődnek.

Az S(a)-val a végén meg nem is értem, hogy miért jó.

Ha meg nem ez a cél akkor mi.
Nem a végtelent, meg a continuumot nem értem én (nem múlt el nyomtalanul 5 év matek az ELTE-n), hanem a bizonyítás egy technikai részletét.
Általában így szoktam járni, hogy ami nehéz az megy és aztán valami apróság megakad az agyamban és beszorul :-).

Hajrá precíz matematikusok!

en nem ertem miert akadsz fent, szerintem teljesen ertheto ez a dekompozicio. :)

F_2 = aS(a^-1) U S(a).

minek kell bennelenni?
- epszilonak: aa^1 = epszilon - pipa
- a -val kezdodo szavaknak: S(a) miatt pipa

amik nehezebb latszodnak, azok a
- a^1 -el kezdodo szavak
- b -vel kezdodo szavak
- b^-1 el kezdodo szavak.

a trukk az egeszben, hogy S(a^-1) -nek reszhalmaza a fenti halmazok (de mind vegtelen), mert ugye S(a^-1)nek resze a^-1S(b). mivel a -val inditunk, igy aa^-1S(b) = S(b) lesz.

ugyanez igaz a masik dekompoziciora is. remelem igy erthetobb :)

( tttaaa | 2010. 01. 23., szo – 23:03 )

4-nél nagyobb fokszámú polinom gyökképletének nemlétezése

Harr, ez is jó lesz!

Beleillik abba a sorozatba ahol a gyökkettő meg a Gödel I.-II. foglalnak helyet, csak a végén semmi konstruktív nem lesz a listában. :)

Ennyi erővel fel lehetne venni a pi nemszerkeszthetőségének ("körnégyzetesítés") bizonyítását is, csak éppen lehet, hogy már az is nagyon advanced. (most megnéztem a wikipédián és hát...)

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

( persicsb | 2010. 01. 25., h – 12:03 )

Beletennek meg par kombinatorikai, grafelmeleti tetelt, pl. Euler-u/kor letezesenek szukseges es elegseges feltetelenek tetelei. Vagy grafok sikbateritosegerol szolo tetel.

( axt v | 2010. 01. 25., h – 12:14 )

Ha mondjuk 10 helyett 100-as lenne a lista, akkor javasolnám a kínai maradéktételt ... valami modern kori példával :)

( palyesz | 2010. 01. 25., h – 16:48 )

esetleg ez: link

---
Egy jól megállapított probléma félig megoldott probléma.
- Charles Kettering

( rpsoft v | 2010. 01. 25., h – 16:58 )

Szerintem az is fontos lehet, hogy olyan tételeket gyűjtesz-e, ami (vagy aminek a félreértése) erős hatást gyakorolt a filozófiára, vagy olyan tételt, aminek a bizonyítása a matematikára (vagy számítástudományra) gyakorolt erős hatást. A Gödel/Tarski/gyökkettő inkább az előző kategóriába tartozik szerintem. Matematikában, az alkalmazásuk gyakorisága szerint én inkább ilyeneket írnék:

- Pitagorasz-tétel
- Banach-féle fixponttétel (sokmindent bizonyítunk ezzel, kezdve pl. a differenciálegyenletek megoldásának egzisztencia-unicitás-tételével)
- Transzfinit indukció/rekurzió
- Riesz-féle reprezentációs tétel (az alkalmazott "Riesz-trükk a Hilbert-terek elméletében lépten-nyomon előkerül)
- végtelen sok prímszám létezése (számelméleti alkalmazásai nagyon fontosak, és a módszer is)
- implicit- és inverzfüggvénytétel (sok alkalmazás, bizonyítás tipikus "Banach-fixponttételes")
- Spektráltétel (rengeteg alkalmazás, pl. kvantummechanikában; biz. eleje Riesz-féle reprezentációs tétellel)
- Bolzano-Weierstrass-tétel (bizonyítás is tipikus, kompakt halmazok elméletének mintája)
- komplex-függvénytani Cauchy-formula (azaz miért szépek a komplex függvények -- olyan szigorú a struktúra, hogy már nem lehet differenciálható, de nem analitikus függvényt gyártani; ilyen a matematika modernebb ágaiban (pl. Lie-csoportok) is van, szép struktúrák jelentősége)
- mindenütt folytonos, de sehol sem differenciálható függvény létezése (azaz kell precíz analízis)

Egyébként a matematikában nem csak a bizonyításoknak lehet alapvető jelentősége, hanem egy-egy jól eltalált definíció is nagyon sokat alakított a matematika egy-két ágán (és néha legalább annyira nem triviális, mint egy bizonyítás, hogy miért pont így kell csinálni, hogy szépek legyenek majd a tételek és a bizonyítások).
- kompakt halmaz
- nemkorlátos operátor spektruma
- kompakt operátor

( mazursky | 2010. 01. 25., h – 17:06 )

Néhány ötletem lenne, de lehet hogy kicsit offtopic jellegű:

elméleti számítástudomány -> WARNING !!! ;~))

Nerode-Myhill tétel
Mealy és Moore gépek által indukált leképezések, gépek ekvivalenciája
Szekvenciális gépek minimalizálása, Nivat tétele
Parikh-tétel és következményei
Chomsky-Schützenberger tétel
Automaták Gluskov szorzata és kaszkád kompozíciói

szerintem demoralizálásra tökéletesen alkamas ;~)))
pláne ha egy fantasztikus oktató is társul az egészhez

/mazursky 

Love your job but never love your company!
Because you never know when your company stops loving you!