Versuchen, Fragen in der Übung über Beziehungen zu verstehen

Question

Versuchen, Fragen in der Übung über Beziehungen zu verstehen

mmm3

Ich arbeite alleine durch How to Prove It von Daniel J. Velleman und versuche zu verstehen, was für Übung 9 in Abschnitt 4.4 gefragt wird:

Vermuten $R$ liegt eine Teilbestellung vor $A$ Und $S$ liegt eine Teilbestellung vor $B$ . Definiere eine Beziehung $L$ An $A \times B$ folgendermaßen: $L = \{ ((a,b),(a',b')) \in (A \times B) \times (A \times B) ~ | ~ aRa', ~ \text{and if} ~ a = a' \text{then} ~ bSb'\}$ .

Insbesondere versuche ich, die Definition der Beziehung zu verstehen $L$ .

Muss $a = a'$ für jedes Paar geordneter Paare, zu denen es gehört $L$ ?

Als konkretes Beispiel lassen Sie $A = \{1, 2\}$ Und $B = \{3, 4\}$ . Deshalb, $A \times B = \{(1,3), (1,4), (2,3), (2,4)\}$ . Lassen $R = \{(1,1), (2,2), (1,2) \}$ Und $B = \{ (3,3), (4,4), (3,4) \}$ .

Nun in diesem speziellen Beispiel ist $L = \{ ((1,3), (1,3)), ~((1,4),(1,4)), ~ ((1,3),(1,4)), ~ ((2,3),(2,3)), ~ ((2,4),(2,4)), ~ ((2,3),(2,4))\}$ ?

Update: Danke an alle für die hilfreichen Antworten auf meine Frage.

Etwas mehr Kontext zu meiner Frage:

Einer der Gründe, warum ich Schwierigkeiten mit der Definition von habe $L$ ist, wenn man versucht, es zu benutzen, wenn man das zeigt $L$ liegt eine Teilbestellung vor $A \times B$ .

Die Definition von $L$ hat eine logische Form von $P \land (O \implies Q)$ , Wo $P$ Ist $aRa'$ , $O$ Ist $a = a$ , Und $Q$ Ist $bSb'$ .

Nun, um zum Beispiel das zu zeigen $L$ ist eine reflexive Beziehung auf $A \times B$ das müssen wir zeigen $\forall (a, b) \in A \times B ((a,b),(a,b)) \in L$ . Lassen Sie dazu $(a,b)$ willkürlich sein und annehmen $(a,b) \in A \times B$ . Daher, $a \in A$ Und $aRa$ . Dies zeigt die $P$ Teil von $P \land (O \implies Q)$ von oben.

Das müssen wir jetzt zeigen $a = a \implies bSb$ . Die Methode, die uns in diesem Buch gezeigt wird, besteht darin, den Vordersatz anzunehmen und den Nachsatz zu beweisen. Vermute also $a = a$ , aber das sagt uns nichts über $bSb$ . Ich bin mir also nicht sicher, was ich von hier aus tun soll.

Vielleicht sollte ich eine neue Frage für das Zeug im Update-Teil dieser Frage öffnen?

Nachdem Sie die Kommentare unten gelesen und mehr darüber nachgedacht haben, ist hier ein weiterer Versuch, dies zu zeigen $L$ ist eine reflexive Beziehung auf $A \times B$ :

Lassen $(a,b)$ willkürlich sein und annehmen $(a,b) \in A \times B$ . Daher $a \in A$ und weil $R$ liegt eine Teilbestellung vor $A$ , Dann $aRa$ . Nun nehme an $a = a$ . Das wissen wir seitdem $(a,b) \in A \times B$ Dann $b \in B$ . Seit $S$ liegt eine Teilbestellung vor $B$ , Dann $bSb$ . Daher, wenn $a = a$ Dann $bSb$ . Seit $aRa$ und wenn $a = a$ Dann $bSb$ , Dann $((a,b),(a,b)) \in L$ . Seit $(a,b)$ willkürlich war, können wir schließen $L$ ist eine reflexive Beziehung auf $A \times B$ . $\square$

Dan Vellemann

Vielleicht würde es helfen, etwas Motivation zu haben. Denken Sie darüber nach, wie Sie Wörter alphabetisch sortieren. Zuerst vergleicht man die Anfangsbuchstaben. Wenn die Anfangsbuchstaben gleich sind, geht es weiter mit den zweiten Buchstaben und so weiter. Sehen Sie, dass die Definition von

L

$L$ basiert auf einer ähnlichen Idee?

mmm3

@DanVelleman danke für den Kommentar. Ich glaube, ich sehe den Zusammenhang, von dem Sie sprechen. Einer der Gründe, warum ich Probleme mit der Definition von habe

L

$L$ versucht, es zu verwenden, um das zu zeigen

L

$L$ liegt eine Teilbestellung vor

A \times B

$A \times B$ . Ich habe der Frage einige weitere Informationen hinzugefügt, um dies genauer zu erläutern.

Eric Türme

"Die Definition von

L

$L$ hat eine logische Form von

P \land (R ⟹ Q)

$P\wedge (R \implies Q)$ , Wo

P

$P$ Ist

a R a'

$aRa′$ ,

R

$R$ Ist

a = a

$a=a$ , Und

Q

$Q$ Ist

b S b'

$bSb′$ ." Das ist falsch. Erstens haben Sie wiederverwendet "

R

$R$ " mit unterschiedlicher Semantik, gehen wir also mit "Die Definition von

L

$L$ hat eine logische Form von

P \land (O ⟹ Q)

$P\wedge (O \implies Q)$ , Wo

P

$P$ Ist

a R a'

$aRa′$ ,

O

$O$ Ist

a = a

$a=a$ , Und

Q

$Q$ Ist

b S b'

$bSb′$ ." Sie beweisen die Definition einer Menge nicht . Sie erhalten die Definition der Menge – dieses Prädikat gilt für jedes Mitglied der Menge.

Dan Vellemann

Im Update sagen Sie: „Das müssen wir jetzt zeigen

a = a \Rightarrow b S b^{'}

$a=a \Rightarrow bSb'$ ." Das ist nicht richtig, was Sie zeigen müssen, ist das

a = a \Rightarrow b S b

$a=a \Rightarrow bSb$ .

mmm3

@EricTowers Ja, habe ich verwendet

R

$R$ auf zwei verschiedene Arten. Danke für den Hinweis. Ich habe es jetzt umgestellt auf

P \land (O ⟹ Q)

$P \land (O \implies Q)$ . Zu zeigen, dass ein Paar geordneter Paare in der Relation steht

L

$L$ wir müssen zeigen, dass sie die Definition von erfüllen

L

$L$ Rechts? Das habe ich im Update-Bereich versucht.

mmm3

@DanVelleman Ja, du hast Recht. Das muss ich zeigen

a = a ⟹ b S b

$a = a \implies bSb$ darin, das zu zeigen

L

$L$ ist eine reflexive Beziehung auf

A \times B

$A \times B$ . Ich habe das im Update-Bereich korrigiert. Das habe ich auch noch in einem weiteren Beweisversuch ergänzt

L

$L$ ist eine reflexive Beziehung auf

A \times B

$A \times B$ . Sieht es richtig aus?

Dan Vellemann

@mmm3: Ja, der neue Beweis dafür

L

$L$ ist reflexartig sieht gut aus.

Antworten (3)

Versuchen, Fragen in der Übung über Beziehungen zu verstehen

Vielleicht würde es helfen, etwas Motivation zu haben. Denken Sie darüber nach, wie Sie Wörter alphabetisch sortieren. Zuerst vergleicht man die Anfangsbuchstaben. Wenn die Anfangsbuchstaben gleich sind, geht es weiter mit den zweiten Buchstaben und so weiter. Sehen Sie, dass die Definition von $L$ basiert auf einer ähnlichen Idee?
@DanVelleman danke für den Kommentar. Ich glaube, ich sehe den Zusammenhang, von dem Sie sprechen. Einer der Gründe, warum ich Probleme mit der Definition von habe $L$ versucht, es zu verwenden, um das zu zeigen $L$ liegt eine Teilbestellung vor $A \times B$ . Ich habe der Frage einige weitere Informationen hinzugefügt, um dies genauer zu erläutern.
"Die Definition von $L$ hat eine logische Form von $P\wedge (R \implies Q)$ , Wo $P$ Ist $aRa′$ , $R$ Ist $a=a$ , Und $Q$ Ist $bSb′$ ." Das ist falsch. Erstens haben Sie wiederverwendet " $R$ " mit unterschiedlicher Semantik, gehen wir also mit "Die Definition von $L$ hat eine logische Form von $P\wedge (O \implies Q)$ , Wo $P$ Ist $aRa′$ , $O$ Ist $a=a$ , Und $Q$ Ist $bSb′$ ." Sie beweisen die Definition einer Menge nicht . Sie erhalten die Definition der Menge – dieses Prädikat gilt für jedes Mitglied der Menge.
Im Update sagen Sie: „Das müssen wir jetzt zeigen $a=a \Rightarrow bSb'$ ." Das ist nicht richtig, was Sie zeigen müssen, ist das $a=a \Rightarrow bSb$ .
@EricTowers Ja, habe ich verwendet $R$ auf zwei verschiedene Arten. Danke für den Hinweis. Ich habe es jetzt umgestellt auf $P \land (O \implies Q)$ . Zu zeigen, dass ein Paar geordneter Paare in der Relation steht $L$ wir müssen zeigen, dass sie die Definition von erfüllen $L$ Rechts? Das habe ich im Update-Bereich versucht.
@DanVelleman Ja, du hast Recht. Das muss ich zeigen $a = a \implies bSb$ darin, das zu zeigen $L$ ist eine reflexive Beziehung auf $A \times B$ . Ich habe das im Update-Bereich korrigiert. Das habe ich auch noch in einem weiteren Beweisversuch ergänzt $L$ ist eine reflexive Beziehung auf $A \times B$ . Sieht es richtig aus?
@mmm3: Ja, der neue Beweis dafür $L$ ist reflexartig sieht gut aus.

Travis Bemrose · Answer 1

Lassen $x := ((a,b)\times(a',b'))$ . Ob $x \in L$ , hängt davon ab, ob $aRa'$ und ob $bSb'$ . Für die beiden letzteren gibt es 4 Möglichkeiten. Lass uns einen Tisch machen.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline aRa' & & \\ \lnot aRa' \end{array}$

Die Definition für $L$ ist eine and- Bedingung, die mit beginnt $aRa'$ , also können wir das ausschließen $\lnot aRa'$ Fälle.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline aRa' & & \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Weiterhin ist die Definition für $L$ besagt, dass in dem Fall, wo $aRa'$ , müssen wir auch überlegen, ob $a=a'$ , also müssen wir die aufteilen $aRa'$ Fall.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline a=a',aRa' & & \\ a \ne a',aRa' & & \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Der zweite Teil der Bedingung sagt if $a=a'$ Dann $bSb'$ , damit wir die obere Zeile ausfüllen können.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline a=a',aRa' & x\in L & x \notin L \\ a \ne a',aRa' & & \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Schließlich ist die if-Bedingung wahr, wenn die Hypothese falsch ist, das heißt, wenn $a \ne a'$ , So $aRa'$ macht die erste Hälfte der Bedingung wahr und $a \ne a'$ macht die zweite Hälfte wahr, und wir beenden die Tabelle.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline a=a',aRa' & x\in L & x \notin L \\ a \ne a',aRa' & x\in L & x\in L \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Guenterino · Answer 2

Guenterino

Ich würde es wie folgt interpretieren: Die Beziehung lautet wie folgt ((a,b),(a',b')) wobei aRa', außer wenn a= a'. Wenn a = a', dann existieren nur die folgenden Relationen ((a,b), (a',b')) mit aRa' und bSb'.

Guenterino

Ich habe die Antwort ein wenig geändert - es tut mir leid, dass ich seltsame Formulierungen verwendet habe. Ich habe mir nicht die Zeit genommen, Ihre Notation zu verstehen. Jetzt sollte es stimmig sein.

mmm3

Danke, das ergibt für mich jetzt mehr Sinn.

mmm3

Eine kleine Korrektur - ich denke, der allerletzte Teil Ihrer Antwort sollte sein

b S b^{'}

$bSb'$ , nicht

b R b^{'}

$bRb'$ .

Guenterino

@mmm3 Du hast Recht! Ich habe es korrigiert.

Alvaro P. · Answer 3

Muss 𝑎=𝑎′ sein, damit jedes Paar geordneter Paare zu 𝐿 gehört?

Nein. Sie können Paare haben $(a,b)\times (a',b')$ Wo $a\neq a'$ so lange wie $aRa'$ .

Anhand Ihres Beispiels, da $(1,2)\in R$ , dann (1,3)x(2,4) $\in L$ .

Hallo Alvaro, danke für die Antwort. Um auf Ihrer Antwort aufzubauen, da $(1,2) \in R$ Dann $((1,3),(2,3)) \in L$ Und $((1,4),(2,4)) \in L$ ?
Exakt. Allgemein gesagt, wären es alle Paare der Form $(1,b)\times(2,b')$ .

Versuchen, Fragen in der Übung über Beziehungen zu verstehen

mmm3

Dan Vellemann

mmm3

Eric Türme

Dan Vellemann

mmm3

mmm3

Dan Vellemann

Antworten (3)

Travis Bemrose

Guenterino

Guenterino

mmm3

mmm3

Guenterino

Alvaro P.

mmm3

Alvaro P.

Finden eines geeigneten Universums für eine gegebene Struktur

Gegenteile der Transitivität

Mengenbeziehungen (symmetrische und transitive, aber nicht reflexive Beziehung)

Analyse I (Terence Tao) – Freie und gebundene Variablen

Ist die Theorie regulärer formaler Sprachen endlich axiomatisierbar?

Ist diese Intervallnotation zur Lösung eines Ungleichungsproblems korrekt?

Was passiert, wenn sich der Kopf einer Infinite Time Turing Machine ganz links befindet und das Programm vorschreibt, den Kopf nach links zu bewegen?

Prinicpal 1-Typen scheinbares Paradoxon

Ist die Beziehung R=∅R=∅R = \emptyset auf {1,2,3}{1,2,3}\{1, 2, 3\} reflexiv, symmetrisch, transitiv?

Wie wird die vollständige Semantik von SOL und HOL spezifiziert?