Die Mathe-Redaktion - 24.08.2019 06:56 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 433 Gäste und 4 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » Kann sowas durch einen Computer bewiesen werden?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Kann sowas durch einen Computer bewiesen werden?
reneeeee
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 19.11.2011
Mitteilungen: 310
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-03-22


Angenommen ich habe Folgendes Programm:

Eingabe: Eine natürliche Zahl n>=2.
Das Programm testet dann ob mehrere Gleichungen (endlich viele) in den natürlichen Zahlen gelten. Als konkretes Beispiel sei hier genannt:
(m+n)^2=n^2+2mn+m^2 für 1<=m<=n.



Ausgabe: true wenn diese Gleichungen richtig sind und false else.


Nun kann ich ein festes n eingeben und das Programm sagt mir, ob für dieses feste n true or false rauskommt.

Frage:
Gibt es mittlerweile auch "intelligente Programme" die sowas für alle n>=2 beweisen können? (also ein problem in den natürlichen Zahlen und Gleichungen darin)


Ich gebe einem High-tech program oder was auch immer es ist also meinen code und er sagt mir, ob es für alle n>=2 stimmt also eine wahre Aussage ist.



Hintergrund: Ein komplexes Problem wurde auf ein solch elementares Problem reduziert. Das elementare Problem ist aber etwas lästig und von Hand scheint es keine ganz kurze/schöne Lösung zu geben.
Kann ich das elementare Problem irgendeinem Computer geben, der es für mich beweist? Wird so ein Beweis in (guten) Journals der Mathematik akzeptiert?



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2651
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-03-22


en.wikipedia.org/wiki/Proof_assistant

So was?

In Coq (z.B.) kannst du so ein Problem eingeben. Ob er einen Beweis findet, ist die andere Frage. Die binomische Formel findet er bestimmt, aber dein Problem ist ja vermutlich deutlich schwieriger. Üblicherweise ist es eher so, dass man als Mensch den Beweis schon kennt und das Programm anstupsen muss ("Tactics"). Anders ist es, wenn man ein Problem vorher auf viele, aber endlich viele, Fälle verteilt hat, die man als Mensch nicht alle durchprobieren kann.

Ich habe ein bisschen mit Coq herumgespielt, bin aber kein Experte.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5090
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-03-22


Hallo reneeeee,

um welche Art von Gleichungen geht es? Ausschließlich um Polynomgleichungen in zwei Variablen?



  Profil  Quote  Link auf diesen Beitrag Link
reneeeee
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 19.11.2011
Mitteilungen: 310
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-03-22


Danke für die Antworten.
Ok, ich schreibe hier mal das konkrete Problem (auf englisch):

For $n \geq 2$ and $a \geq 2$ define the list $N_{n,a,s}$ as $[a,a,...,a,a+1,a+1,...,a+1]$, which has $n$ entries and $a$ appears $s \geq 1$ times and $s<n$ (so a and a+1 both appear at least once).

We use the convention that two lists are isomorphic (=get identified) in case they are a cyclic shift of eachother and we look at lists only up to isomorphism in the following.

For $n \geq 2$, we define $Z_{n,0}$ as the list $[2,2,2,...,2,1]$.
Given $1 \leq m \leq n-1$ and $n \geq 2$, define the list $\mathcal{Z}_{n,m}$ as $N_{n,a,s}$, where
$$a:=[\frac{2n-1}{n-m}],$$ in case $n \equiv m$ mod 2 and
$$a:=[\frac{2n}{n-m+1}],$$ in case $n \neq m$ mod 2 together with the convention that
$$s= n(a+1)- \frac{(-a^2+3a+2)n+(a^2+a)m-2a)}{2},$$ in case $n+m-1$ is odd and
$$s= n(a+1)- \frac{(-a^2+3a+2)n+(a^2+a)m-a^2+a-2)}{2},$$
in case $n+m-1$ is even.

Example:
$\mathcal{Z}_{n,1}=[2,2,....,2,3]$ and $\mathcal{Z}_{n,n-1}=[n,n+1,n+1,...,n+1]$.
$\mathcal{Z}_{8,m}$ for $m=1,...,7$ are given as follows:
[ 2, 2, 2, 2, 2, 2, 2, 3 ], [ 2, 2, 2, 2, 3, 3, 3, 3 ], [ 2, 3, 3, 3, 3, 3, 3, 3 ], [ 3, 3, 3, 4, 4, 4, 4, 4 ],  [ 4, 4, 4, 4, 4, 5, 5, 5 ], [ 7, 7, 7, 7, 7, 7, 7, 8 ], [ 8, 9, 9, 9, 9, 9, 9, 9 ].


We define a operation $\chi$ on the lists of the form $N_{n,a,s}$ for $a \leq n-1$ as follows:

For $N_{n,a,s}=[c_0,c_1,...,c_{n-1}]$, define $\chi(N_{n,a,s})= [r_0,r_1,...,r_{n-2}]$ with $r_i=c_i- \phi(i)$, where $\phi(i)=1$ when $c_i \geq n-i$ and $\phi(i)=0$ else for $i \in \{0,1,..., n-2 \}$.

Proposition:
Let $A=N_{n,a,s}$ with $a \leq n-1$, then the following holds for $m \leq n-2$:
-$\chi(\mathcal{Z}_{n,m})= \mathcal{Z}_{n-1,m-1}$.
- In case $\chi(N_{n,a,s})= \mathcal{Z}_{n-1,r}$ for some $r$ then $A=\mathcal{Z}_{n,r+1}$.



Ich habe zwar einen Beweis aber er ist nicht hübsch. Ich würde in einem Artikel es am liebsten dem Leser überlassen mit dem Hinweis dass es von einem Computer programm für allgemeine n bestätigt wurde (und ich denke sowas ist OK in einem Journal sofern es so ein Computer programm gibt).



Im Grund geht alles durch elementares Umformen innerhalb der natürlichen Zahlen und ich würde denken bei der heutigen Technik gibt es vielleicht Computerprogramme wo man so elementare Dinge  beweisen lassen kann.



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-03-23


Hallo reneeeee,

ich habe ein Verständisproblem bei deiner Funktion $\chi$. Es sollte doch z.B. gelten

$\chi (\mathcal{Z}_{8,5})=\mathcal{Z}_{7,4}$

oder verstehe ich das falsch?




  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2651
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-03-23


Du müsstest ja irgendwie dem Leser die Möglichkeit geben, nachzuvollziehen, dass es so ein Programm, bzw. so einen maschinellen Beweis, gibt, also z.B. den Quellcode anhängen. Ich bezweifle, dass das in Summe übersichtlicher ist als den handgeschriebenen Beweis anzuhängen.

Außerdem hängt der Beweis dann von der Korrektheit des entsprechenden Provers oder Beweisassistenten, irgendwelcher Compiler und der Hardware ab. Ein Opfer, das m.E. nicht gerechtfertigt ist, wenn man bereits einen Beweis hat.



  Profil  Quote  Link auf diesen Beitrag Link
reneeeee
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 19.11.2011
Mitteilungen: 310
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-03-23


Hallo,
danke für den Hinweis, querin. Ich habe vergessen zu sagen, dass Listen up to cyclic shifts nur betrachtet werden. Hab es oben ergänzt.
[4,4,4,4,4,5,5,5] wird also auf [4,4,4,4,3,4,4] geschickt, was gleich [3,4,4,4,4,4,4] ist.

@darkhelmet: Deine Meinung kann ich gut nachvollziehen. Trotzdem würde mich interessieren ob es Computerprogramme gibt, die sowas beweisen können.


2019-03-23 11:10 - querin in Beitrag No. 4 schreibt:
Hallo reneeeee,

ich habe ein Verständisproblem bei deiner Funktion $\chi$. Es sollte doch z.B. gelten

$\chi (\mathcal{Z}_{8,5})=\mathcal{Z}_{7,4}$

oder verstehe ich das falsch?





  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-03-23


Hallo reneeeee, ich sehe noch ein Problem:

$\chi (\mathcal{N}_{8,6,0})=\chi (\mathcal{N}_{8,7,8})=\mathcal{Z}_{7,5}$ aber $A \ne \mathcal{Z}_{8,6}$



  Profil  Quote  Link auf diesen Beitrag Link
reneeeee
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 19.11.2011
Mitteilungen: 310
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-03-23


Hallo,
n>s>=1. Habe es jetzt explizit dazugeschrieben.
Danke für die Bemerkung.



  Profil  Quote  Link auf diesen Beitrag Link
reneeeee hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]