Forum:  Logik, Mengen & Beweistechnik
Thema: Kann sowas durch einen Computer bewiesen werden?
Themen-Übersicht
reneeeee
Senior
Dabei seit: 19.11.2011
Mitteilungen: 310
Aus:
Themenstart: 2019-03-22 18:27

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?


darkhelmet
Senior
Dabei seit: 05.03.2007
Mitteilungen: 2631
Aus: Bayern
Beitrag No.1, eingetragen 2019-03-22 18:48

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.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5035
Aus: Milchstraße
Beitrag No.2, eingetragen 2019-03-22 19:12

Hallo reneeeee,

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


reneeeee
Senior
Dabei seit: 19.11.2011
Mitteilungen: 310
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2019-03-22 20:53

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.


querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 192
Aus:
Beitrag No.4, eingetragen 2019-03-23 11:10

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?



darkhelmet
Senior
Dabei seit: 05.03.2007
Mitteilungen: 2631
Aus: Bayern
Beitrag No.5, eingetragen 2019-03-23 12:25

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.


reneeeee
Senior
Dabei seit: 19.11.2011
Mitteilungen: 310
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2019-03-23 13:54

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?




querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 192
Aus:
Beitrag No.7, eingetragen 2019-03-23 15:48

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}$


reneeeee
Senior
Dabei seit: 19.11.2011
Mitteilungen: 310
Aus:
Beitrag No.8, vom Themenstarter, eingetragen 2019-03-23 16:50

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




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=240965=17
Druckdatum: 2019-07-21 23:19