Äquivalenzrelation

04.08.2023, 20:52

Evelyn2003

Auf diesen Beitrag antworten »

Äquivalenzrelation

Frage1: Wie zeige ich das die Vorschrift eine Äquivalenzrelation ist?

Aufgabe:

Die folgenden Vorschriften definieren eine Äquivalenzrelation auf den natürlichen Zahlen $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ :

$\begin{eqnarray*} x \sim y \Leftrightarrow x, y \end{eqnarray*}$ sind beide gerade.
$\begin{eqnarray*} x \sim y \Leftrightarrow x-y \end{eqnarray*}$ gerade.
$\begin{eqnarray*} x \sim y \Leftrightarrow x+y \end{eqnarray*}$ gerade.
$\begin{eqnarray*} x \sim y \Leftrightarrow x-y \end{eqnarray*}$ ungerade.
$\begin{eqnarray*} x \sim y \Leftrightarrow x+y \end{eqnarray*}$ ungerade.

Ich nehme mir jetzt dreii beliebige Werte aus den natürlichen Zahlen als Beispiel heraus:
Sei $\begin{eqnarray*} x=2 \end{eqnarray*}$ , $\begin{eqnarray*} y= 4 \end{eqnarray*}$ $\begin{eqnarray*} z= 6 \end{eqnarray*}$

Frage2: Kann x und y den selben Wert annehmen? also $\begin{eqnarray*} x=2 \end{eqnarray*}$ , $\begin{eqnarray*} y= 2 \end{eqnarray*}$ ? (Zumal eine Relation eine Teilmenge auf ein kartesisches Produkt ist und als Vorraussetzung auch nur wenn die Mengen gleich sind wie z.B bei $\begin{eqnarray*} X \times X \end{eqnarray*}$ ?

reflexiv
$\begin{eqnarray*} 2 \sim 4 \end{eqnarray*}$

symmetrisch
$\begin{eqnarray*} 2 \sim 4 \rightarrow 4 \sim 2 \end{eqnarray*}$

transitiv
$\begin{eqnarray*} 2 \sim 4, 4 \sim 6 \rightarrow 2 \sim 6 \end{eqnarray*}$

Frage3: Was kann ich nachdem ich beliebig gerade natürliche Zahlen in die jeweiligen Eigenschaften der Relation eingesetzt habe daraus schließen? Egal ob Reflexivität Symmetrie, Transitivität. Die Zahlen stehen in relation zueinander da sie trotzdem gerade bleiben?

Und wie zeige ich das bitte formal das es sich um eine Äquivalenzrelation handelt wenn ich kein Gegenbeispiel finde?

04.08.2023, 22:12

Helferlein

Auf diesen Beitrag antworten »

Antwort1: Indem Du die drei Eigenschaften einer Äquivalenzrelation für beliebige natürliche Zahlen nachweist.

Antwort 2: Da wir über eine Relation auf den natürlichen Zahlen reden, dürfen sie selbstverständlich auch identisch sein. Für die Reflexivität ist das sogar zwingend erforderlich.

Antwort 3: Die Frage verstehe ich nicht. Wie man mathematische Schlüsse aus einer Aussage ziehen kann sollte eigentlich bereits im ersten Semester gelehrt werden. Selbst in Schulen sollte einem das Logikprinzip in den Grundzügen gezeigt worden sein.
Fange mit der Definition an und überlege Dir, was daraus folgt.

Nehmen wir mal an, die zu untersuchen Relation wäre x~y wenn x=y. Dann wäre die Relation auf den natürlichen Zahlen reflexiv, da x=x für jedes x gilt. Symmetrisch ist sie auch, da mit x=y auch y=x gilt. Außerdem ist sie auch transitiv und somit eine Äquivalenzrelation.

05.08.2023, 03:12

Evelyn2003

Auf diesen Beitrag antworten »

Wäre das für die erste Relation richtig?

die zu untersuchende Relation:

$\begin{eqnarray*} x \sim y \Leftrightarrow x, y \end{eqnarray*}$ sind beide gerade.

Relation auf den natürlichen Zahlen wäre reflexiv, da $\begin{eqnarray*} x, x \end{eqnarray*}$ beide gerade sind, für alle $\begin{eqnarray*} x \in \mathbb N \end{eqnarray*}$ .

Relation auf den natürlichen Zahlen wäre symmetrisch, da $\begin{eqnarray*} x, y \end{eqnarray*}$ sowie $\begin{eqnarray*} y, x \end{eqnarray*}$ jeweils beide gerade sind, für alle $\begin{eqnarray*} x, y \in \mathbb N \end{eqnarray*}$ .

Relation auf den natürlichen Zahlen wäre transitiv, da $\begin{eqnarray*} x, y \end{eqnarray*}$ sowie $\begin{eqnarray*} y, x \end{eqnarray*}$ und $\begin{eqnarray*} x, z \end{eqnarray*}$ jeweils gerade sind, für alle $\begin{eqnarray*} x,y, z \in \mathbb N \end{eqnarray*}$ .

Somit erfüllt die obige Relation die Eigenschaften einer Äquivalenzrelation.

05.08.2023, 03:48

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein

Bei der zweiten Relation:

$\begin{eqnarray*} x \sim y \Leftrightarrow x-y \end{eqnarray*}$ gerade.

Reflexiv, da $\begin{eqnarray*} x-x=0 \end{eqnarray*}$ gerade für alle $\begin{eqnarray*} x \in \mathbb N \end{eqnarray*}$ .

Nicht symmetrisch, da $\begin{eqnarray*} x-y \end{eqnarray*}$ $\begin{eqnarray*} \rightarrow \end{eqnarray*}$ $\begin{eqnarray*} y-x \end{eqnarray*}$ für alle $\begin{eqnarray*} x, y \in \mathbb N \end{eqnarray*}$ . $\begin{eqnarray*} \rightarrow \end{eqnarray*}$ (Gegenbeispiel) $\begin{eqnarray*} 6-4=2 \end{eqnarray*}$ gerade, aber $\begin{eqnarray*} 4-6=-2 \end{eqnarray*}$ gerade, jedoch $\begin{eqnarray*} -2 \notin \mathbb N \end{eqnarray*}$

zweites Gegenbeispiel $\begin{eqnarray*} 7-4=3 \end{eqnarray*}$ ungerade, $\begin{eqnarray*} 4-7=3 \end{eqnarray*}$ ungerade

Nicht transitiv, da $\begin{eqnarray*} x-y \end{eqnarray*}$ , $\begin{eqnarray*} y-z \end{eqnarray*}$ $\begin{eqnarray*} \rightarrow \end{eqnarray*}$ $\begin{eqnarray*} x-z \end{eqnarray*}$ gerade für alle $\begin{eqnarray*} x, y, z \in \mathbb N \end{eqnarray*}$
(Gegenbeispiel) $\begin{eqnarray*} 6-4=2 \end{eqnarray*}$ , $\begin{eqnarray*} 4-8=-4 \end{eqnarray*}$ $\begin{eqnarray*} \rightarrow \end{eqnarray*}$ $\begin{eqnarray*} 6-8=-2 \end{eqnarray*}$ alle gerade aber $\begin{eqnarray*} -4, -2 \notin \mathbb N \end{eqnarray*}$

Ist das zweite Gegenbeispiel zur symmetrie richtig?

05.08.2023, 07:01

Finn_

Auf diesen Beitrag antworten »

Die Werte der auftretenden Operationen müssen nicht unbedingt für alle Argumente in den natürlichen Zahlen liegen. Jedenfalls geht dies für mich, soweit erkennbar, aus der Formulierung der Aufgabenstellung hervor.

Weiterhin ist $\begin{eqnarray*} x-y \end{eqnarray*}$ keine Aussage. Statt „ $\begin{eqnarray*} x-y\to y-x \end{eqnarray*}$ “ muss es heißen

$\begin{eqnarray*} 2\mid (x-y) \to 2\mid (y-x) \end{eqnarray*}$

für $\begin{eqnarray*} x,y \end{eqnarray*}$ beliebig, aber fest. Der Beweis verläuft in strenger Form folgendermaßen. Man definiert „zwei teilt a“ als

$\begin{eqnarray*} 2\mid a :\leftrightarrow \exists k\in\mathbb Z\colon a = 2k. \end{eqnarray*}$

Die Hypothese $\begin{eqnarray*} 2\mid (x-y) \end{eqnarray*}$ gelte. Dann haben wir irgendein $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} x - y = 2k. \end{eqnarray*}$ Wähle nun $\begin{eqnarray*} k':=-k. \end{eqnarray*}$ Das macht klar, es existiert ein $\begin{eqnarray*} k' \end{eqnarray*}$ mit $\begin{eqnarray*} y - x = 2k', \end{eqnarray*}$ womit auch $\begin{eqnarray*} 2\mid (y-x) \end{eqnarray*}$ gilt.

Dein zweites Gegenbeispiel ist ein Denkfehler. Ist die Hypothese falsch, greift ex falso quodlibet.

05.08.2023, 07:16

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_

Weiterhin ist $\begin{eqnarray*} x-y \end{eqnarray*}$ keine Aussage. Statt „ $\begin{eqnarray*} x-y\to y-x \end{eqnarray*}$ “ muss es heißen

$\begin{eqnarray*} 2\mid (x-y) \to 2\mid (y-x) \end{eqnarray*}$

Habe ich das richtig verstanden das der Ausdruck $\begin{eqnarray*} 2\mid \end{eqnarray*}$ bedeutet "2 teilt"?
Und das hast du hinzugefügt, weil gerade Zahlen durch zwei ohne Rest teilbar sind?

Was mein Gegenbeispiel anbelangt: Meinst du damit das die Annahme $\begin{eqnarray*} 7-4=3 \end{eqnarray*}$ unzulässig ist, weil laut der Relation die Differenz eine gerade Zahl ist?

Wie sieht es zudem bitte mit meinen Beitrag um 03:12 aus?

Anzeige

05.08.2023, 08:20

Helferlein

Auf diesen Beitrag antworten »

Zitat:

Original von Evelyn2003
Wäre das für die erste Relation richtig?

reflexiv, da $\begin{eqnarray*} x, x \end{eqnarray*}$ beide gerade sind, für alle $\begin{eqnarray*} x \in \mathbb N \end{eqnarray*}$ .
st offensichtlich falsch, oder denkst Du 3~3 ist richtig?

Relation auf den natürlichen Zahlen wäre symmetrisch, da $\begin{eqnarray*} x, y \end{eqnarray*}$ sowie $\begin{eqnarray*} y, x \end{eqnarray*}$ jeweils beide gerade sind, für alle $\begin{eqnarray*} x, y \in \mathbb N \end{eqnarray*}$ [/i]
Die Argumentation ist ebenfalls falsch, gleiche Begründung.

Relation auf den natürlichen Zahlen wäre transitiv, da $\begin{eqnarray*} x, y \end{eqnarray*}$ sowie $\begin{eqnarray*} y, x \end{eqnarray*}$ und $\begin{eqnarray*} x, z \end{eqnarray*}$ jeweils gerade sind, für alle $\begin{eqnarray*} x,y, z \in \mathbb N \end{eqnarray*}$ .
Begründung passt auch hier nur, wenn Du die Relation auf die geraden Zahlen beschränkt. Das steht in dem von Dir genannten Text aber nicht!

05.08.2023, 08:57

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein

Zitat:

Original von Evelyn2003
Wäre das für die erste Relation richtig?

Begründung passt auch hier nur, wenn Du die Relation auf die geraden Zahlen beschränkt. Das steht in dem von Dir genannten Text aber nicht!

Wenn ich ungerade Zahlen hinzuziehen kann dann wäre es doch wie bei deinem Gegenbeispiel $\begin{eqnarray*} 3 \sim 3 \end{eqnarray*}$ für sämtliche Eigenschaften unerfüllt?

Wie sehe es denn dann richtig bewiesen bitte aus?

05.08.2023, 09:44

Helferlein

Auf diesen Beitrag antworten »

Etwas zu beweisen, das falsch ist, wird Dir nicht gelingen. Es reicht ein passendes Gegenbeispiel, auf das die Eigenschaft nicht zutrifft, wie von mir bei der Reflexivität gezeigt.
Für die anderen beiden Eigenschaften ist die Implikation zu zeigen:
Wenn x~y dann y~x.
Wenn x~y und y~z, dann x~z.
Hier kannst Du also davon ausgehen, dass die Bedingung der Relation für die gewählten Paare gültig sind und musst daraus geeignete Schlüsse ziehen.

05.08.2023, 09:59

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein

Relation auf den natürlichen Zahlen wäre symmetrisch, da $\begin{eqnarray*} x, y \end{eqnarray*}$ sowie $\begin{eqnarray*} y, x \end{eqnarray*}$ jeweils beide gerade sind, für alle $\begin{eqnarray*} x, y \in \mathbb N \end{eqnarray*}$
Die Argumentation ist ebenfalls falsch, gleiche Begründung.

Ich verstehe nicht wie ich sonst anders bei der Symmetrie argumentieren kann.
Wenn x, y gerade dann y, x gerade?

Oder Kontraposition: wenn y, x ungerade dann x,y ungerade?

Oder muss ich das wie der Finn in seinem vorhergehenden Beitrag mit den 2*k machen?

05.08.2023, 11:26

Helferlein

Auf diesen Beitrag antworten »

Wenn Du streng formell vorgehen willst, dann mache es mit der Variante von Finn.
Ich denke aber dass bei diesem offensichtlichen Fall nicht erforderlich ist.

x~y $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ x und y sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ y und x sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ y~x

05.08.2023, 12:09

Finn_

Auf diesen Beitrag antworten »

Du wolltest die Aussage $\begin{eqnarray*} \forall x,y\colon x\sim y\to y\sim x \end{eqnarray*}$ durch ein Gegenbeispiel widerlegen, hast dazu $\begin{eqnarray*} x_0,y_0 \end{eqnarray*}$ mit $\begin{eqnarray*} \lnot(x_0\sim y_0) \end{eqnarray*}$ gefunden und daraus $\begin{eqnarray*} \lnot (y_0\sim x_0) \end{eqnarray*}$ gefolgert. Abgekürzt sind dir jetzt $\begin{eqnarray*} \lnot A \end{eqnarray*}$ und $\begin{eqnarray*} \lnot B \end{eqnarray*}$ bekannt, womit du $\begin{eqnarray*} A\to B \end{eqnarray*}$ widerlegen willst. In Wirklichkeit ist $\begin{eqnarray*} A\to B \end{eqnarray*}$ allerdings bereits eine Konsequenz von $\begin{eqnarray*} \lnot A. \end{eqnarray*}$

Es gelten hierzu $\begin{eqnarray*} \lnot A,A, \end{eqnarray*}$ woraus wir $\begin{eqnarray*} B \end{eqnarray*}$ schließen wollen. Nun führt die Voraussetzung von sowohl $\begin{eqnarray*} \lnot A \end{eqnarray*}$ als auch $\begin{eqnarray*} A \end{eqnarray*}$ zur Kontradiktion. Aus der Kontradiktion folgt per ex falso quodlibet jede beliebige Aussage, also erst recht $\begin{eqnarray*} B. \end{eqnarray*}$ q.e.d.

Die erste Teilaufgabe könnte man unter Umständen auch deuten als

$\begin{eqnarray*} x\sim y\Leftrightarrow (2\mid x \leftrightarrow 2\mid y), \end{eqnarray*}$

also $\begin{eqnarray*} x,y \end{eqnarray*}$ seien gemeinsam gerade, oder aber gemeinsam ungerade. Etwaige Zweideutigkeiten kannst du im wissenschaftlichen Stil bearbeiten, beispielsweise Deutung der ersten Teilaufgabe als A. Dann verhält es sich so und so. Deutung der ersten Teilaufgabe als B. Dann verhält es sich so und so.

05.08.2023, 21:36

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein
Wenn Du streng formell vorgehen willst, dann mache es mit der Variante von Finn.
Ich denke aber dass bei diesem offensichtlichen Fall nicht erforderlich ist.

x~y $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ x und y sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ y und x sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ y~x

Frage1: Musstest du das jetzt in beide Richtungen zeigen? Da du in dem Beitrag zuvor erwähnt hast man müsse nur die Implikation zeigen und nicht die Äquivalenz? verwirrt

verwirrt

Frage2: bedeutet das Komma zwschen $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ , also $\begin{eqnarray*} x, y \end{eqnarray*}$ dasselbe wie $\begin{eqnarray*} x \wedge y \end{eqnarray*}$ ?
$\begin{eqnarray*} x \sim y \Leftrightarrow x, y \end{eqnarray*}$ sind beide gerade.

Frage3: Müsste man das dann wie folgt für die Transitivität zeigen
$\begin{eqnarray*} x \sim y \end{eqnarray*}$ $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} x \wedge y \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \wedge z \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} x \wedge z \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \sim x \end{eqnarray*}$

Frage4: Was die Reflexivität zur ersten Teilaufgabe angeht. So steht auf meinem Lösungsblatt (wo ausschließlich die Lösungen stehen (ohne Rechenweg bzw. Beweis) das die Relation reflexiv ist. Sowie symmetrisch und transitiv? verwirrt

verwirrt

Frage5: Würde das dann auch analog für die zweite Teilaufgabe (nicht streng formell) gemacht werden?

$\begin{eqnarray*} x \sim y \Leftrightarrow x-y \end{eqnarray*}$ gerade.

Reflexivität
da $\begin{eqnarray*} 2 | x-x= 0 \rightarrow \end{eqnarray*}$ dann setzen wir $\begin{eqnarray*} 0=k \end{eqnarray*}$ mit $\begin{eqnarray*} k \in \mathbb{Z} \end{eqnarray*}$ und folgern daraus $\begin{eqnarray*} \rightarrow x-x= 2 \cdot k \end{eqnarray*}$ gerade für alle $\begin{eqnarray*} x \in \mathbb N \end{eqnarray*}$ .

Symmetrie
$\begin{eqnarray*} x \sim y \end{eqnarray*}$ $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} x - y \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y - x \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \sim x \end{eqnarray*}$

Transitivität
$\begin{eqnarray*} x \sim y \end{eqnarray*}$ $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} x - y \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y - z \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} x - z \end{eqnarray*}$ sind gerade $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \sim x \end{eqnarray*}$

05.08.2023, 23:32

Finn_

Auf diesen Beitrag antworten »

Besteht das Axiom nur aus einer Implikation, genügt der Beweis der Implikation. Trotzdem darf man im Beweis Äquivalenzumformungen unternehmen.

Es ist „ $\begin{eqnarray*} x\land y \end{eqnarray*}$ sind gerade“ keine wohlgeformte Formel. Wohlgeformte Formeln sind „ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \land \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“ und „ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“.

Der Beweis der Transitivität geht so:

$\begin{eqnarray*} \dfrac{\dfrac{\dfrac{\dfrac{x\sim y}{2\mid x\land 2\mid y}{\scriptsize\text{laut Def.}}}{2\mid x}\qquad \dfrac{\dfrac{y\sim z}{2\mid y\land 2\mid z}{\scriptsize\text{laut Def.}}}{2\mid z}}{2\mid x\land 2\mid z}}{x\sim z}{\scriptsize\text{laut Def.}} \end{eqnarray*}$

06.08.2023, 02:40

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_

Es ist „ $\begin{eqnarray*} x\land y \end{eqnarray*}$ sind gerade“ keine wohlgeformte Formel. Wohlgeformte Formeln sind „ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \land \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“ und „ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“.

Der Beweis der Transitivität geht so:

$\begin{eqnarray*} \dfrac{\dfrac{\dfrac{\dfrac{x\sim y}{2\mid x\land 2\mid y}{\scriptsize\text{laut Def.}}}{2\mid x}\qquad \dfrac{\dfrac{y\sim z}{2\mid y\land 2\mid z}{\scriptsize\text{laut Def.}}}{2\mid z}}{2\mid x\land 2\mid z}}{x\sim z}{\scriptsize\text{laut Def.}} \end{eqnarray*}$

Sind die von dir genannten wohlgeformten Formeln gleich?
„ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \land \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“ $\begin{eqnarray*} = \end{eqnarray*}$ „ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“.

Wenn man den Beweis der Transitivität ausschreiben und nicht in abgestufter Form darstellen soll, würde man das wie in der nachfolgenden Zeile machen?

$\begin{eqnarray*} x \sim y \Leftrightarrow 2 \mid x\wedge 2\mid y \end{eqnarray*}$ und $\begin{eqnarray*} y \sim z \Leftrightarrow 2 \mid y\wedge 2\mid z \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow 2\mid x\wedge 2 \mid z \Leftrightarrow x \sim z \end{eqnarray*}$

06.08.2023, 08:10

Finn_

Auf diesen Beitrag antworten »

Zitat:

Sind die von dir genannten wohlgeformten Formeln gleich?
„ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \land \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“ $\begin{eqnarray*} = \end{eqnarray*}$ „ $\begin{eqnarray*} x \end{eqnarray*}$ ist gerade $\begin{eqnarray*} \leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} y \end{eqnarray*}$ ist gerade“.

Den Junktoren $\begin{eqnarray*} \land,\leftrightarrow \end{eqnarray*}$ kommt eine semantische Interpretation zu, sie stehen für Wahrheitsfunktionen, die entsprechend ihrer Wahrheitstafeln definiert sind. Der Wahrheitswert von $\begin{eqnarray*} \text{falsch}\land\text{falsch} \end{eqnarray*}$ ist falsch. Dagegen hat $\begin{eqnarray*} \text{falsch}\leftrightarrow\text{falsch} \end{eqnarray*}$ den Wahrheitswert wahr. Es ist $\begin{eqnarray*} A\leftrightarrow B \end{eqnarray*}$ wie eine Gleichung zu verstehen; solange auf beiden Seiten der gleiche Wahrheitswert herauskommt, ist sie erfüllt.

Zitat:

Wenn man den Beweis der Transitivität ausschreiben und nicht in abgestufter Form darstellen soll, würde man das wie in der nachfolgenden Zeile machen?

$\begin{eqnarray*} x \sim y \Leftrightarrow 2 \mid x\wedge 2\mid y \end{eqnarray*}$ und $\begin{eqnarray*} y \sim z \Leftrightarrow 2 \mid y\wedge 2\mid z \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow 2\mid x\wedge 2 \mid z \Leftrightarrow x \sim z \end{eqnarray*}$

Für das Grundstudium wird das wohl als schlechter Stil angesehen, weil zu knapp. Das $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ darin solltest du zumindest durch es folgt oder ergo oder ähnlich ersetzen. Rigorose Fassung der Beweisführung ginge so:

Beweis. Es seien $\begin{eqnarray*} x,y \end{eqnarray*}$ beliebig(, aber fest). Es gelte $\begin{eqnarray*} x\sim y \end{eqnarray*}$ und $\begin{eqnarray*} y\sim z. \end{eqnarray*}$ Laut Definition sind diese Aussagen äquivalent zu $\begin{eqnarray*} 2\mid x\land 2\mid y \end{eqnarray*}$ und $\begin{eqnarray*} 2\mid y\land 2\mid z. \end{eqnarray*}$ Folglich gilt erst recht sowohl $\begin{eqnarray*} 2\mid x \end{eqnarray*}$ als auch $\begin{eqnarray*} 2\mid z, \end{eqnarray*}$ mithin die Konjunktion $\begin{eqnarray*} 2\mid x\land 2\mid z, \end{eqnarray*}$ die äquivalent zu $\begin{eqnarray*} x\sim z \end{eqnarray*}$ ist. q.e.d.

06.08.2023, 08:55

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_

für $\begin{eqnarray*} x,y \end{eqnarray*}$ beliebig, aber fest. Der Beweis verläuft in strenger Form folgendermaßen. Man definiert „zwei teilt a“ als

$\begin{eqnarray*} 2\mid a :\leftrightarrow \exists k\in\mathbb Z\colon a = 2k. \end{eqnarray*}$

Frage1: Hätte man die im obigen Zitat einfach V nennen können statt "zwei teilt a", oder welchen Sinn hatte es bitte genau sie so zu benennen?

Und ich muss die folgende Frage leider nochmal stellen, da es mir noch nicht ganz klar ist:
Frage2: bedeutet das Komma zwschen $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ , also $\begin{eqnarray*} x, y \end{eqnarray*}$ = $\begin{eqnarray*} x \wedge y \end{eqnarray*}$ ?
$\begin{eqnarray*} x \sim y \Leftrightarrow x, y \end{eqnarray*}$ sind beide gerade.

Zitat:

Original von Finn_
Du wolltest die Aussage $\begin{eqnarray*} \forall x,y\colon x\sim y\to y\sim x \end{eqnarray*}$ durch ein Gegenbeispiel widerlegen, hast dazu $\begin{eqnarray*} x_0,y_0 \end{eqnarray*}$ mit $\begin{eqnarray*} \lnot(x_0\sim y_0) \end{eqnarray*}$ gefunden und daraus $\begin{eqnarray*} \lnot (y_0\sim x_0) \end{eqnarray*}$ gefolgert. Abgekürzt sind dir jetzt $\begin{eqnarray*} \lnot A \end{eqnarray*}$ und $\begin{eqnarray*} \lnot B \end{eqnarray*}$ bekannt, womit du $\begin{eqnarray*} A\to B \end{eqnarray*}$ widerlegen willst. In Wirklichkeit ist $\begin{eqnarray*} A\to B \end{eqnarray*}$ allerdings bereits eine Konsequenz von $\begin{eqnarray*} \lnot A. \end{eqnarray*}$ Es gelten hierzu $\begin{eqnarray*} \lnot A,A, \end{eqnarray*}$ woraus wir $\begin{eqnarray*} B \end{eqnarray*}$ schließen wollen. Nun führt die Voraussetzung von sowohl $\begin{eqnarray*} \lnot A \end{eqnarray*}$ als auch $\begin{eqnarray*} A \end{eqnarray*}$ zur Kontradiktion. Aus der Kontradiktion folgt per ex falso quodlibet jede beliebige Aussage, also erst recht $\begin{eqnarray*} B. \end{eqnarray*}$ q.e.d.

Frage3: Kannst du bitte außerdem das fett gedruckte nochmal etwas vereinfachter erklären?
Wieso gilt jetzt $\begin{eqnarray*} \lnot A,A \end{eqnarray*}$ ?? und $\begin{eqnarray*} \lnot A,A \Rightarrow B \end{eqnarray*}$ ??
Was heißt außerdem ex falso quodlibet?

06.08.2023, 10:51

Helferlein

Auf diesen Beitrag antworten »

Zu Frage 2:
Für mich ist die Formulierung "sind beide gerade" nur sinnvoll, wenn x und y gleichzeitig gemeint sind.
Wenn dein Lösungszettel aber keinen Fehler enthält, ist wohl eher Finns Interpretation ( Beide gerade oder beide ungerade) gemeint. Ansonsten wäre die Relation nur auf den Geraden Zahlen reflexiv.

Für die weitere Beantwortung deiner Fragen überlasse ich Finn das Feld.

06.08.2023, 12:49

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein
Zu Frage 2:
Für mich ist die Formulierung "sind beide gerade" nur sinnvoll, wenn x und y gleichzeitig gemeint sind.
Wenn dein Lösungszettel aber keinen Fehler enthält, ist wohl eher Finns Interpretation ( Beide gerade oder beide ungerade) gemeint. Ansonsten wäre die Relation nur auf den Geraden Zahlen reflexiv.

Für die weitere Beantwortung deiner Fragen überlasse ich Finn das Feld.

Was war dann bitte genau deine Interpretation? "wenn x und y gleichzeitig gemeint sind." klingt für mich dasselbe wie "beide gerade oder beide ungerade" ? verwirrt

verwirrt

06.08.2023, 14:33

Finn_

Auf diesen Beitrag antworten »

Logisches Schließen läuft, obgleich in Worten formuliert, nach streng festgelegten Regeln ab. Es sei $\begin{eqnarray*} \Gamma \end{eqnarray*}$ eine Liste oder Menge von Aussagen. Wir schreiben $\begin{eqnarray*} \Gamma\vdash A \end{eqnarray*}$ für „die Aussage $\begin{eqnarray*} A \end{eqnarray*}$ ist unter Annahme der Aussagen aus $\begin{eqnarray*} \Gamma \end{eqnarray*}$ beweisbar“.

Für beliebige Aussagen $\begin{eqnarray*} A,B, \end{eqnarray*}$ das dürfen auch mit Junktoren zusammengesetzte Aussagen sein, gelten die Schlussregeln

$\begin{eqnarray*} \dfrac{}{\Gamma\vdash A}{\small (A\in\Gamma)},\qquad\dfrac{\Gamma\vdash \lnot A\qquad\Gamma\vdash A}{\Gamma\vdash\bot},\qquad\dfrac{\Gamma\vdash\bot}{\Gamma\vdash B},\qquad\dfrac{\Gamma,A\vdash B}{\Gamma\vdash A\to B}. \end{eqnarray*}$

Das sind die Grundregel, die Einführung der Kontradiktion, ex falso quodlibet, und die Einführung der Implikation. Vermittels dieser Regeln findet sich der Beweis:

$\begin{eqnarray*} \dfrac{\dfrac{\dfrac{\dfrac{}{\lnot A,A\vdash\lnot A}\qquad\dfrac{}{\lnot A,A\vdash A}}{\lnot A,A\vdash\bot}}{\lnot A,A\vdash B}}{\lnot A\vdash A\to B} \end{eqnarray*}$

06.08.2023, 19:58

Helferlein

Auf diesen Beitrag antworten »

Zitat:

Original von Evelyn2003
Was war dann bitte genau deine Interpretation? "wenn x und y gleichzeitig gemeint sind." klingt für mich dasselbe wie "beide gerade oder beide ungerade" ? verwirrt

verwirrt

Eben nicht. Die Definition besagt, dass x in Relation zu y steht dann und nur dann wenn x,y beide gerade sind.
Da ist nirgends etwas von ungerade gesagt. Diese Sichtweise habe ich übrigens inzwischen auch in einem anderen Forum bereits vor fast 20 Jahren bestätigt gefunden.

07.08.2023, 09:03

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein

Zitat:

Original von Evelyn2003
Wäre das für die erste Relation richtig?

reflexiv, da $\begin{eqnarray*} x, x \end{eqnarray*}$ beide gerade sind, für alle $\begin{eqnarray*} x \in \mathbb N \end{eqnarray*}$ .
st offensichtlich falsch, oder denkst Du 3~3 ist richtig?

Wäre dann so wie ich es für die Reflexivität geschrieben habe, richtig? Da dein Gegenbeispiel ja dann nur unter der Annahme beruhte das beide gerade oder beide ungerade sind? verwirrt

verwirrt

Falls der Beweis für die Reflexivität nicht so gültig wäre - Wie würde dann bitte der Beweis aussehen?

08.08.2023, 14:27

Evelyn2003

Auf diesen Beitrag antworten »

Kann mir jemand bitte zu der Teilaufgabe b im Bezug auf die Transitivität die rot markierte Stelle erklären?

Angenommen, wir haben $\begin{eqnarray*} x \sim y \end{eqnarray*}$ (d.h. $\begin{eqnarray*} x - y \end{eqnarray*}$ ist gerade) und $\begin{eqnarray*} y \sim z \end{eqnarray*}$ (d.h. $\begin{eqnarray*} y - z \end{eqnarray*}$ ist gerade). Unser Ziel ist es, zu zeigen, dass dann auch $\begin{eqnarray*} x \sim z \end{eqnarray*}$ gilt (d.h. $\begin{eqnarray*} x - z \end{eqnarray*}$ ist gerade).

Da $\begin{eqnarray*} x - y \end{eqnarray*}$ gerade ist, können wir es als $\begin{eqnarray*} 2m \end{eqnarray*}$ ausdrücken (für eine ganze Zahl $\begin{eqnarray*} m \end{eqnarray*}$ ):

$\begin{eqnarray*} x - y = 2m \end{eqnarray*}$

Ebenso können wir $\begin{eqnarray*} y - z \end{eqnarray*}$ als $\begin{eqnarray*} 2n \end{eqnarray*}$ ausdrücken (für eine ganze Zahl $\begin{eqnarray*} n \end{eqnarray*}$ ):

$\begin{eqnarray*} y - z = 2n \end{eqnarray*}$

Nun betrachten wir die Differenz $\begin{eqnarray*} x - z \end{eqnarray*}$ :

$\begin{eqnarray*} x - z = (x - y) - (y - z)= 2m - 2n = 2(m - n) \end{eqnarray*}$

Da die Differenz von zwei geraden Zahlen wieder gerade ist (hier $\begin{eqnarray*} m - n \end{eqnarray*}$ ist eine ganze Zahl), haben wir gezeigt, dass $\begin{eqnarray*} x - z \end{eqnarray*}$ gerade ist. Dies bedeutet, dass $\begin{eqnarray*} x \sim z \end{eqnarray*}$ erfüllt ist, und die Transitivität der gegebenen Äquivalenzrelation ist somit bewiesen.

x - z = (x - y) - (y - z)

Wieso kann man aus $\begin{eqnarray*} x-z \end{eqnarray*}$ folgern das es gleich $\begin{eqnarray*} (x - y) - (y - z) \end{eqnarray*}$ ist?

08.08.2023, 16:15

URL

Auf diesen Beitrag antworten »

Da hat sich einfach jemand mit den Vorzeichen vertan. Gemeint war vermutlich $\begin{eqnarray*} x-z=x-y+y-z=(x-y)+(y-z)=2m+2n=2(m+n) \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »