Beweisansatz

09.01.2013, 22:58

Ploki

Beweisansatz

Meine Frage:
[attach]27747[/attach]

Meine Ideen:
Ich bekomm keinen wirklichen Ansatz hin. Könnt ihr mir bitte auf die Sprünge helfen? =)

lg Ploki

10.01.2013, 01:13

RavenOnJ

Auf diesen Beitrag antworten »

Nimm an, es gebe zwei Lösungen und führe das zu einem Widerspruch.

10.01.2013, 02:52

Ploki

Auf diesen Beitrag antworten »

Danke für deine Antwort!

Also meine Annahme ist:
Es gibt mindestens 2 (verschiedene) Lösungen. Also existiert ein $\begin{eqnarray*} q_{1},q_{2} \in N_{0} \end{eqnarray*}$ und ein $\begin{eqnarray*} r_{1},r_{2} \in \left\{ 0,1,...,m-1\right\} \end{eqnarray*}$ mit $\begin{eqnarray*} n= m \cdot q_{1} +r_{1} \wedge n= m \cdot q_{2} +r_{2} \end{eqnarray*}$

Ich will doch un irgendwie darauf kommen, dass q1 =q2 bzw r1 = r2 sein muss, um einen Widerspruch zu erhalten.
Nur wie schaffe ich das? Muss ich nun Fallunterscheidung machen?

10.01.2013, 08:51

RavenOnJ

Auf diesen Beitrag antworten »

Nein, das Beweisverfahren ist anders: Es gelte die Grundannahme, also $\begin{align*} q_1\ne q_2\lor r_1\ne r_2 \end{align*}$ . Dies muss jetzt auf einen Widerspruch führen. Daraus folgt dann, dass die Annahme falsch sein muss, dass es also nur ein solches $\begin{align*} (q,r) \end{align*}$ -Tupel geben kann. Eigentlich ist das recht einfach, man könnte z.B. die beiden Gleichungen voneinander abziehen:

$\begin{eqnarray*} \Rightarrow m(q_1 -q_2) = r_2 -r_1 \end{eqnarray*}$

Daraus kann man jetzt weiter schlussfolgern und einen Widerspruch konstruieren.

Edit: Nach Hinweis von HAL geändert

10.01.2013, 09:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von RavenOnJ
Es gelte die Grundannahme, also $\begin{align*} q_1\ne q_2\land r_1\ne r_2 \end{align*}$ .

Na die ist eher $\begin{eqnarray*} \neg(q_1=q_2\wedge r_1=r_2) \end{eqnarray*}$ bzw. auch $\begin{eqnarray*} q_1\neq q_2 {\color{red}\vee} r_1\neq r_2 \end{eqnarray*}$ geschrieben.

10.01.2013, 10:50

RavenOnJ

Auf diesen Beitrag antworten »

@HAL
stimmt natürlich, ändert aber am Folgenden nichts.

10.01.2013, 12:29

Ploki

Auf diesen Beitrag antworten »

Zitat:

Original von RavenOnJ
$\begin{eqnarray*} \Rightarrow m(q_1 -q_2) = r_2 -r_1 \end{eqnarray*}$

Wie du auf diese Gleichung kommst ist mir klar.
Nur ob meine Schlussfolgerung so stimmt ist mir ungewiss.

Weiters umgeformt ergibt sich:

$\begin{eqnarray*} m = \frac{r_2 -r_1}{q_1 -q_2} \end{eqnarray*}$

Für den Fall m = 0, erhalten wir einen Widerspruch zu der Grundannahme.
Muss ich nun noch Fallunterscheidung machen?

Fall 1: $\begin{align*} q_1= q_2\wedge r_1\ne r_2 \end{align*}$
Fall 2: $\begin{align*} q_1\ne q_2\wedge r_1= r_2 \end{align*}$
Fall 3: $\begin{align*} q_1\ne q_2\wedge r_1\ne r_2 \end{align*}$

10.01.2013, 12:57

RavenOnJ

Auf diesen Beitrag antworten »

Einen Fall m=0 musst du gar nicht berücksichtigen, da m > 0 vorausgesetzt wurde.

Ansonsten argumentiere einerseits damit, dass $\begin{align*} 0\le |r_2-r_1| < m \end{align*}$ gelten muss, und dass andererseits, falls $\begin{align*} r_1\ne r_2 \end{align*}$ , eine Teilerbeziehung zwischen $\begin{align*} m \end{align*}$ und $\begin{align*} r_2 - r_1 \end{align*}$ gelten muss. Damit kannst du schon mal den Fall $\begin{align*} r_1\ne r_2 \end{align*}$ erschlagen. Die Folgerung für $\begin{align*} q_1\ne q_2 \end{align*}$ ist dann praktisch trivial.

10.01.2013, 14:38

Ploki

Auf diesen Beitrag antworten »

Achja, dachte m sei aus N_0.

Also eine Teilerbeziehung kann es nicht geben, da $\begin{align*} |r_2-r_1| < m \end{align*}$ .

Außerdem gilt: $\begin{align*} 0 \le |q_1-q_2| < m \end{align*}$ .
Für den Fall $\begin{align*} q_1\ne q_2 \end{align*}$ ist $\begin{align*} (r_2 - r_1) \end{align*}$ ein Vielfaches von m, was ein Widerspruch zu $\begin{align*} |r_2-r_1| < m \end{align*}$ ist.

Hab ich somit richtig argumentiert?

10.01.2013, 15:14

RavenOnJ

Auf diesen Beitrag antworten »

genau, da $\begin{align*} 0\le r_i <m \end{align*}$ , muss $\begin{align*} |r_2-r_1|<m\Rightarrow m \nmid (r_2-r_1) \Rightarrow r_2-r_1 =0 \land q_2-q_1 = 0 \end{align*}$

10.01.2013, 15:31

Ploki

Auf diesen Beitrag antworten »

Danke vielmals!

lg Ploki

10.01.2013, 15:43

Ploki

Auf diesen Beitrag antworten »

Ui, mir ist noch was aufgefallen.

Hab ich damit nur gezeigt, dass es nicht mehr als eine Lösung geben kann?

Muss ich nicht noch zeigen, dass es überhaupt eine Lösung gibt? Oder ist das beim Widerspruchsbeweis miteinbezogen?

10.01.2013, 15:48

RavenOnJ

Auf diesen Beitrag antworten »

ja, das musst du natürlich noch zeigen. Es steht ja nicht da: "zeigen Sie, dass es höchstens eine Lösung gibt", dann wäre das natürlich hinfällig.

10.01.2013, 22:31

Ploki

Auf diesen Beitrag antworten »

Ok, also ich hab den Beweis mit Induktion geführt.

Es gibt 2 Fälle:

1.Fall: $\begin{align*} 0 \leq n < m \end{align*}$
2.Fall: $\begin{align*} n \geq m \end{align*}$

IA:
$\begin{align*} 0 \leq n < m \end{align*}$ mit $\begin{align*} n=0 \cdot m +n \end{align*}$

$\begin{align*} \Rightarrow q=0, r=n \end{align*}$

IS:
$\begin{align*} n \geq m \end{align*}$ für $\begin{align*} n_{*} \leq n - m \end{align*}$ bewiesen.

$\begin{eqnarray*} n-m = q \cdot m + r \Rightarrow n = m+q \cdot m+r = (q+1) \cdot m + r \end{eqnarray*}$

Also gibt es für n mindestens eine Darstellung. Zusammen mit beweis nr.1, gibt es genau eine Darstellung.

Passt das so?

lg Ploki

Neue Frage »

Antworten »

Beweisansatz

Verwandte Themen