Reihenfolge der Quantoren und Umkehrvariablen

Für die 3. und 4. Frage, eine informelle Art, diese zu verstehen, beachten Sie, dass ein Existenzial als eine Art Disjunktion angesehen werden kann, das heißt, wenn$a,b,c,...$die Objekte in Ihrer Domäne bezeichnen, dann können Sie sich ein Existential wie folgt vorstellen:

$\exists x \: \varphi(x) \approx \varphi(a) \lor \varphi(b) \lor \varphi(c) \lor ...$

ich benutze$\approx$da dies technisch gesehen keine logische Äquivalenz ist, aber wenn Sie die obige Äquivalenz wirklich beweisen wollen, müssen Sie sich mit der formalen Semantik befassen, und das könnte ein bisschen zu viel sein, um nach einem Binner in Logik zu fragen. Aber was Sie dort tun würden, folgt dieser Grundidee, also lassen wir es einfach informeller.

Mit dieser „Äquivalenz“ können Sie also eine Äquivalenz wie zeigen (oder zumindest informell verstehen).$\exists x \exists y \ P(x,y) \Leftrightarrow \exists y \exists x \ P(x,y)$folgendermaßen:

$\exists x \exists y \ P(x,y) \approx$

$\exists y \ P(a,y) \lor \exists y \ P(b,y) \lor \exists y \ P(c,y) \lor ... \approx$

$(P(a,a) \lor P(a,b) \lor P(a,c) ...) \lor (P(b,a) \lor P(b,b)\lor ...) \lor (P(c,a) \lor P(c,b) \lor ...) \lor ... \Leftrightarrow$

$P(a,a) \lor P(a,b) \lor P(a,c) ... \lor P(b,a) \lor P(b,b) \lor ... \lor P(c,a) \lor P(c,b) \lor ... \Leftrightarrow$

$P(a,a) \lor P(b,a) \lor P(c,a) ... \lor P(a,b) \lor P(b,b) \lor P(c,b) ... \lor P(a,c) \lor P(b,c) ... \lor ... \approx$

$\exists x P(x,a) \lor \exists x P(x,b) \lor \exists x P(x,c) \lor ... \approx$

$\exists y \exists x \ P(x,y)$

Sie sehen also, dass wir zwei Existenzielle tauschen können, wenn sie im Grunde nebeneinander stehen, weil die$\lor$ist assoziativ und kommutativ.

Ebenso, indem man ein Universal wie folgt denkt:

$\forall x \: \varphi(x) \approx \varphi(a) \land \varphi(b) \land \varphi(c) \land ...$

Sie können verstehen, warum zwei Universalien, die nebeneinander liegen, vertauscht werden können, da die$\land$ist sowohl assoziativ als auch kommutativ.

Als allgemeines Äquivalenzprinzip gilt:

Austauschen von Quantoren des gleichen Typs

$\forall x \forall y \ P(x,y) \Leftrightarrow \forall y \forall x \ P(x,y)$

$\exists x \exists y \ P(x,y) \Leftrightarrow \exists y \exists x \ P(x,y)$

Nun stelle ich fest, dass Sie in 3) gefragt haben:

$(∃x∃y \space P(x,y)) \rightarrow (∃y∃x \space P(y,x))$

Hier tauschen Sie also nicht nur die Quantoren, sondern auch die Rolle der Variablen in der Formel. Nun, das funktioniert immer, denn Variablen sind nur Dummy-Platzhalter, also haben Sie natürlich immer :

Gebundene Variablen austauschen

$\forall x \ \varphi(x) \Leftrightarrow \forall y \ \varphi(y)$

$\exists x \ \varphi(x) \Leftrightarrow \exists y \ \varphi(y)$

Und insbesondere haben Sie daher:

$\exists x \exists y \ P(x,y) \Leftrightarrow$

$\exists z \exists y \ P(z,y) \Leftrightarrow$

$\exists z \exists x \ P(z,x) \Leftrightarrow$

$\exists y \exists x \ P(y,x)$

Tatsächlich funktioniert dies auch mit gemischten Quantoren, z.

$\forall x \exists y \ P(x,y) \Leftrightarrow$

$\forall z \exists y \ P(z,y) \Leftrightarrow$

$\forall z \exists x \ P(z,x) \Leftrightarrow$

$\forall y \exists x \ P(y,x)$

Schließlich führt das Austauschen von Variablen in einer Formel normalerweise zu einer Aussage, die nicht äquivalent ist, aber es gibt Fälle, in denen sie äquivalent bleibt:

Austausch der Rolle von Variablen

$\forall x \forall y \ P(x,y) \Leftrightarrow \forall x \forall y \ P(y,x)$

$\exists x \exists y \ P(x,y) \Leftrightarrow \exists x \exists y \ P(y,x)$

Und diese können wir aus den früheren Prinzipien ableiten, zB:

$\forall x \forall y \ P(x,y) \Leftrightarrow \text{ (Swapping Quantifiers)}$

$\forall y \forall x \ P(x,y) \Leftrightarrow \text{ (Swapping Bound Variables)}$

$\forall x \forall y \ P(y,x)$

1. Es gibt leider keine allgemeingültigen Konventionen. Unterschiedliche Traditionen, die unterschiedliche Antworten geben. Wenn Sie sich nicht sicher sind, welche Konvention Ihre Leserschaft verwenden wird, erklären Sie Ihre Konvention entweder im Voraus oder machen Sie sie mithilfe von Klammern vollständig eindeutig.

2. Auch das ist von Tradition zu Tradition unterschiedlich.

3. Ja, diese sind immer wahr. Sie können vom Antezedens zum Sukzessiven gelangen, indem Sie die Reihenfolge zweier gleichartiger Quantoren vertauschen (was gemäß 4 zulässig ist) und dann die gebundenen Variablen umbenennen.

4. Ich verstehe die Frage nicht – welche Art von Antwort auf „wie“ etwas wahr ist, erwarten Sie? Ist es „sehr“ wahr oder „sicher“ wahr oder einfach nur wahr?