Wie beweist man Surjektivität mit Allquantoren und Existenzquantoren?

26.10.2020, 05:01

Enomine

Wie beweist man Surjektivität mit Allquantoren und Existenzquantoren?

Die Definition von Surjektivität lautet:

code:

1:
2:
3:
4:
5:
6:
7:
8:

Nur für die, die nicht wissen was das ist. Wer es weiß weiter nach dem Code-Block.
Jedes Element aus dem Wertebereich einer Funktion muss von mindestens einer Eingabe 
des Definitionsbereiches dieser Funktion erreicht werden.

Sage ich also z.B. der Wertebereich einer Funktion ist [latex]\mathbb{N}[/latex], dann muss 
ich beweisen, dass jede Zahl zwischen 0 und unendlich Ergebnis der Funktion sein kann - oder 
umgekehrt, dass zu jeder dieser Zahlen y ein x existiert, aus dem sich das y errechnet:

$\begin{eqnarray*} \forall_{y\in\mathbb{N}} \exists_{x\in\mathbb{Z}} \left(f\left(x\right)=y\right) \end{eqnarray*}$

Wie beweißt man eine solche Aussage?

Vom Professor haben wir eine Beweisformtabelle:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

zu bew. Satz (log.) |    Beweisform   |      to do
----------------------------------------------------------------
       V => K       | direkter Beweis | V => ... => K
----------------------------------------------------------------
       V => K       | Kontraposition  | ¬K => ¬V
----------------------------------------------------------------
      Aussage A     |   Widerspruch   | ¬A => false
----------------------------------------------------------------
      ¬&#8704;x A(x)      |  Gegenbeispiel  | &#8707;x ¬A(x)
----------------------------------------------------------------
      &#8704;x&#8712;&#8469; A(x)     |vollst. Induktion| Lektion 2
----------------------------------------------------------------

[attach]52046[/attach]
Nun gibt es dort keine Existensquantoren.
Meine Kommulitonen haben etwas gemacht, was sie "direkter Beweis" genannt haben. Jedoch haben wir ja in der obigen Aussage gar keine Implikation ( => ). Deswegen sehe ich nicht, wie ich "sauber" von V nach K kommen soll. Also was soll dieses K überhaupt sein?

Ich hab schon über den Widerspruchsbeweis nachgedacht, indem ich die obige Aussage negiere und hoffe, dass etwas durch die Negation herauskommt, mit dem ich etwas anfangen kann. Aber auf https://de.wikibooks.org/wiki/Mathe_f%C3...ln_zum_Negieren habe ich leider keine Negationsregel für kombinierte Allquantoren mit Existensquantoren gefunden.

PS: bei uns ist $\begin{eqnarray*} f(x) = code_{\mathbb{Z}}(x) \end{eqnarray*}$
wobei $\begin{eqnarray*} code_{\mathbb{Z}}(x) = 2x \qquad \qquad , falls \qquad x >= 0 \end{eqnarray*}$
sowie $\begin{eqnarray*} code_{\mathbb{Z}}(x) = -2x-1 \qquad , sonst \end{eqnarray*}$

Danke - Enomine

26.10.2020, 07:56

Leopold

Auf diesen Beitrag antworten »

Um zu zeigen, daß eine Funktion $\begin{align*} f: X \to Y \end{align*}$ surjektiv ist, gibt man sich ein beliebiges $\begin{align*} y \in Y \end{align*}$ vor und zeigt, daß man genau zu diesem $\begin{align*} y \end{align*}$ ein $\begin{align*} x \end{align*}$ finden kann, so daß $\begin{align*} f(x) = y \end{align*}$ gilt.

So ist jedenfalls das Grundmuster. Gerade die Analysis stellt aber Regeln und Sätze zur Verfügung, wie man die Surjektivität auch aus anderen Eigenschaften einer Funktion schließen kann. Aber hier geht es wohl um die Grundlagen. Nehmen wir ein einfaches Beispiel:

$\begin{align*} f: \mathbb{R} \to \mathbb{R} \, , \ \ x \mapsto y = 2x \end{align*}$

Wir geben uns nun irgendein $\begin{align*} y \in \mathbb{R} \end{align*}$ vor und müssen zeigen, daß dieses durch $\begin{align*} f \end{align*}$ erreicht wird. Da $\begin{align*} f \end{align*}$ verdoppelt, nehmen wir den halben Wert von $\begin{align*} y \end{align*}$ als unser $\begin{align*} x \end{align*}$ , also $\begin{align*} x = \frac{1}{2}y \end{align*}$ , und rechnen nach:

$\begin{align*} f(x) = f \left( \frac{1}{2} y \right) = 2 \cdot \left( \frac{1}{2} y \right) = y \end{align*}$ .

Wir haben uns zwar ein festes $\begin{align*} y \end{align*}$ vorgegeben, aber uns nicht konkret auf seinen Wert festgelegt. Letztlich haben wir also zu jedem $\begin{align*} y \end{align*}$ ein $\begin{align*} x \end{align*}$ gefunden mit $\begin{align*} f(x) = y \end{align*}$ .

Bei deiner code-Funktion fehlt sowohl die Angabe des Definitions- als auch die des Zielbereichs. Du hast lediglich die Funktionsvorschrift angegeben. Damit kann aber die Frage der Surjektivität nicht entschieden werden.

26.10.2020, 08:46

Dopap

Auf diesen Beitrag antworten »

RE: Wie beweist man Surjektivität mit Allquantoren und Existenzquantoren?

Zitat:

Original von Enomine
$\begin{eqnarray*} \forall_{y\in\mathbb{N}} \exists_{x\in\mathbb{Z}} \left(f\left(x\right)=y\right) \end{eqnarray*}$

Freaks:_Aussagen_negieren#Umformungsregeln_zum_Negieren[/URL] habe ich leider keine Negationsregel für kombinierte Allquantoren mit Existensquantoren gefunden

meinst du so etwas wie:

$\begin{eqnarray*} \lnot \big( \bigwedge_{y\in \mathbb N} \bigvee_{x \in \mathbb Z} f(x)=y \big)= \bigvee_{y\in \mathbb N} \bigwedge_{x \in \mathbb Z} f(x)\neq y \quad \end{eqnarray*}$ verwirrt

26.10.2020, 09:08

Leopold

Auf diesen Beitrag antworten »

@ Dopap

Was soll das? Die Ersetzung der Quantoren durch ihre Booleschen Entsprechungen trägt doch nun wirklich nichts zur Aufklärung bei. Statt zu helfen überschüttest du den Fragesteller mit einem neuen, ihm vermutlich unbekannten Bezeichnungssystem. unglücklich

26.10.2020, 10:12

Dopap

Auf diesen Beitrag antworten »

@ Leopold: deshalb steht ein Fragezeichen dahinter.
Die Schreibfiguren sind synonym und die Letztere einfach zu verstehen.

26.10.2020, 15:53

Enomine

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
@ Dopap: deshalb steht ein Fragezeichen dahinter.

Du hast nirgends ein "?" getippt Augenzwinkern

Zitat:

Original von Dopap
Die Schreibfiguren sind synonym und die Letztere einfach zu verstehen.

@Leopold hat recht - es war nicht gerade nötig das so zu schreiben, vorallem da der Unterschied für dich nur bei einem

code:
1:	\forall sowie \exists

statt

code:
1:	\bigwedge sowie \bigvee

gewesen wäre. Und du hattest mein Latex zitiert, hattest dort also eine Kopiervorlage.

Nichts desto trotz hatte ich es verstanden, weil ich die Symbole schoneinmal gesehen hatte.

===== ===== ===== ===== ===== ===== ===== ===== ===== =====

@ Leopold: Könntest du mir noch erläutern, warum das kein Zirkelschluss ist?
https://mathphys.info/vorkurs/inhalt/logik/Logik2_Skript.pdf Seite 11

Zitat:

Original von Leopold:
Bei deiner code-Funktion fehlt sowohl die Angabe des Definitions- als auch die des Zielbereichs. Du hast lediglich die Funktionsvorschrift angegeben. Damit kann aber die Frage der Surjektivität nicht entschieden werden.

=>

Für alle $\begin{eqnarray*} x\in\mathbb{Z} \end{eqnarray*}$ definieren wir $\begin{eqnarray*} code_{\mathbb{Z}} : \mathbb{Z} \mapsto \mathbb{N} \end{eqnarray*}$ als
$\begin{eqnarray*} code_{\mathbb{Z}}(x) = _{def} \begin{cases}2x & x \geq 0 \\-2x-1 & \, \text{sonst}\end{cases} \end{eqnarray*}$

Ich habe verstanden, dass wir es auf deine gezeigte Art Beweisbar ist. Vorbehaltich deiner Erklärung, warum es kein Zirkelschluss ist.

===== =====

$\begin{eqnarray*} \exists_{y\in \mathbb N} \forall_{x \in \mathbb Z} f(x)\neq y \quad \end{eqnarray*}$
wäre doch jetzt der Anfang eines Widerspruchbeweises - oder? Denn die Aussage A ist ja negiert worden. Kann man hier weiter machen?

Dankeschön

Enomine

26.10.2020, 16:16

Leopold

Auf diesen Beitrag antworten »

Bei der Funktion $\begin{align*} \operatorname{code}_{\mathbb{Z}} \end{align*}$ würde ich dir empfehlen, eine Wertetabelle zu erstellen, etwa $\begin{align*} -5 \leq x \leq 5 \end{align*}$ . Schau dir die Werte an. Kommt jede natürliche Zahl unter den Werten von $\begin{align*} \operatorname{code}_{\mathbb{Z}} \end{align*}$ vor? Versuche, die Sache umzukehren: Wie findest du zu einem Wert sein Urbild (oder seine Urbilder)? Und dann hast du die Surjektivität ja schon. Du mußt das dann nur abstrahieren: Wie findest du zu einem $\begin{align*} y \in \mathbb{N} \end{align*}$ ein $\begin{align*} x \in \mathbb{Z} \end{align*}$ mit $\begin{align*} \operatorname{code}_{\mathbb{Z}}(x) = y \end{align*}$ ?

Worauf du mit deiner Zirkelschlußfrage anspielst, verstehe ich nicht. In dieser Aufgabe sollst du die Surjektivität einer Funktion belegen oder widerlegen. Wo da der Zusammenhang zum Thema Widerspruchsbeweis ist, kann ich nicht erkennen.

26.10.2020, 17:26

Luftikus

Auf diesen Beitrag antworten »

Bei deiner Funktion musst du nachweisen, dass jede natürliche Zahl ein Urbild hat.
Dazu kannst du eine Fallunterscheidung machen (k natürlich):

i) n=2k

ii) n=2k-1

Jetzt musst du nachweisen, dass
2m [m>=0] bzw -(2m+1) [m<0] dieses Urbild für jeden Fall liefert.

26.10.2020, 18:39

Enomine

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Bei der Funktion $\begin{align*} \operatorname{code}_{\mathbb{Z}} \end{align*}$ würde ich dir empfehlen, eine Wertetabelle zu erstellen, etwa $\begin{align*} -5 \leq x \leq 5 \end{align*}$ . Schau dir die Werte an. Kommt jede natürliche Zahl unter den Werten von $\begin{align*} \operatorname{code}_{\mathbb{Z}} \end{align*}$ vor? Versuche, die Sache umzukehren: Wie findest du zu einem Wert sein Urbild (oder seine Urbilder)? Und dann hast du die Surjektivität ja schon. Du mußt das dann nur abstrahieren: Wie findest du zu einem $\begin{align*} y \in \mathbb{N} \end{align*}$ ein $\begin{align*} x \in \mathbb{Z} \end{align*}$ mit $\begin{align*} \operatorname{code}_{\mathbb{Z}}(x) = y \end{align*}$ ?

Ja also Bestandteil der Aufgabe ist es auch $\begin{eqnarray*} code_{\mathbb{Z}}^{-1} \end{eqnarray*}$ mathematisch anzugeben, was ich mit
$\begin{eqnarray*} code_{\mathbb{Z}}^{-1}(y) = _{def} \begin{cases} \frac{y}{2} & y \quad gerade \\ -\frac{(y+1)}{2} & y \quad ungerade \end{cases} \end{eqnarray*}$
getan habe.

Kann ich eigentlich auch durch zeigen der Injektivität von $\begin{eqnarray*} code_{\mathbb{Z}}^{-1} \end{eqnarray*}$ die Surjektivität von $\begin{eqnarray*} code_{\mathbb{Z}} \end{eqnarray*}$ zeigen? Muss ich dann nicht auch beweisen, dass $\begin{eqnarray*} code_{\mathbb{Z}}^{-1} \end{eqnarray*}$ wirklich die Umkehrfunktion von $\begin{eqnarray*} code_{\mathbb{Z}} \end{eqnarray*}$ ist? Wie mache ich das?

Injektivität könnte ich meiner Annahme nach über einen Direkten Beweis beweisen, da die Definition von Injektivität ja eine Implikation beinhaltet.

Zitat:

Worauf du mit deiner Zirkelschlußfrage anspielst, verstehe ich nicht. In dieser Aufgabe sollst du die Surjektivität einer Funktion belegen oder widerlegen. Wo da der Zusammenhang zum Thema Widerspruchsbeweis ist, kann ich nicht erkennen.

Ich weiß auch nicht wie ich darauf komme, und das ist ja das Problem. Angst etwas falsch zu machen, ohne es zu merken, was z.B. beim Zirkelschluss der Fall wäre.

Dankeschön

Enomine

30.10.2020, 10:36

Enomine

Auf diesen Beitrag antworten »

Ich hab das mal auf zwei Wege bewiesen.

1. "Üblicher Weg"
Auf die Art und und Weise, wie du es mir gezeigt hast, und wie es auch Videos zur Surjektivität aus dem Internet zeigen.

2. Ich hatte ja oben eine Definition von Surjektivität mit All-Quantor angegeben. Diese wollte ich gerne über einen Widerspruchsbeweis beweisen. Am Ende landete ich deshalb bei der Unmöglichkeit eines Gegenbeispieles, welches wiederrum auf den "Üblichen Weg" zurückgreift.

Meine Frage ich zum 2. Fall, ob man das trotzdem so machen kann und der Beweis in sich so schlüssig und okay ist.

Danke - Enomine

[attach]52060[/attach]
[attach]52061[/attach]
[attach]52062[/attach]

Neue Frage »

Antworten »

Wie beweist man Surjektivität mit Allquantoren und Existenzquantoren?

Verwandte Themen