Domanda di base sulle prove con l'obiettivo $\exists x P(x)$

Aug 22 2020

In Velleman, How To Prove It ?, impariamo a dimostrare un obiettivo della forma $\exists x P(x)$ estraendo il quantificatore esistenziale dall'obiettivo, assegnando un valore a una variabile arbitraria x e quindi derivando $\exists x P(x)$dal presupposto introdotto. Nell'esempio seguente, per provare$\exists y[y+2x=0]$ (1), assumiamo $y$ e assegnargli il valore $-2x$ (2) e ricavare l'obiettivo da questo assunto (3).

  1. $\exists y[y+2x=0]$
  2. $ [y=-2x] \rightarrow [y+2x=0]$
  3. $ [y=-2x] \space \land \exists y[y+2x=0] \rightarrow [y+2x=0]$

Non capisco davvero come sia possibile assumere l'assegnazione del valore a y come uno dei dati nella dimostrazione. Un'uguaglianza matematica è logicamente trattata come una tautologia, in modo che possa essere assunta senza restrizioni in qualsiasi prova?

Risposte

2 EricTowers Aug 22 2020 at 04:44

"assumiamo $y$ e assegnargli il valore $−2x$"probabilmente non significa quello che stai pensando. Non assumiamo $y$ - $y$non è una proposizione quindi non siamo in grado di assumerla. Non assumiamo la proposizione$[y]$, o. Quello che stiamo facendo è dire: "Sai, se$y$ sono stati impostati su questo valore speciale, $y = -2x$, allora funziona tutto ".

Quindi supponiamo "$y = -2x$"Questo non è automatico. Abbiamo dovuto fare un po 'di algebra dietro le quinte per scoprire quale valore speciale ha $y$fa funzionare tutto questo. Quell'algebra non viene mostrata. Devi solo iniziare dalla corretta scelta del valore di$y$. Quindi supponiamo$y = -2x$, cioè, assumiamo la proposizione "$[y = -2x]$" (è vero).

Questa ipotesi ha delle conseguenze. In particolare, dovresti essere in grado di derivare $$ [y = -2x] \rightarrow [y+2x = 0] $$ lungo $$ y + 2x = (-2x) + 2x = 0 \text{.} $$ Ciò richiede un uso dell'algebra, non c'è modo di eseguire questa addizione usando solo la logica: devi conoscere i fatti algebrici sugli inversi additivi.

Quindi ottieni $[y = -2x] \rightarrow [y+2x = 0]$. Questo ti permette di dedurre$\exists y [y+2x=0]$, perché in realtà sai di quale specializzazione $y$ rende questo vero, vale a dire $y = -2x$.

La tua linea 3 sembra un po 'strana. Quello che abbiamo in realtà è $$ \left( [y = -2x] \rightarrow [y+2x = 0] \right) \rightarrow \exists y[y+2x = 0] \text{.} $$ Cioè, "dalla specializzazione $y = -2x$ fa $y + 2x = 0$, concludiamo che esiste un file $y$ tale che $y+2x = 0$." Quella $y$ è $-2x$.

Come si scrive questo? Nota che abbiamo prodotto una dichiarazione condizionale: "if$y$ è $-2x$, poi $y+2x = 0$. "Questa sarà una prova secondaria.

... blah blah blah ...

Permettere $y = -2x$. Osservare$y+2x = (-2x)+2x = 0$. Quindi deduciamo$\exists y [y+2x = 0]$.

... blah blah blah ...

Qual è la forma della discussione?

  • Permettere $y = \{\text{a value that works}\}$. Troviamo quel valore usando l'algebra in questo esempio.
  • Si osservi che l'espressione nel predicato che è stata quantificata esistenzialmente è resa vera dall'assegnazione della variabile $y$ al valore nel passaggio precedente.
  • Concludere che esiste un valore di $y$ciò rende vero il predicato esistenzialmente quantificato. (Vale a dire, quello che hai mostrato nel primo passaggio.)

Mi viene in mente che potrebbe esserci un po 'di confusione causata dai due usi distinti di "$y$"nella dichiarazione del modulo di prova, $$ \left( [y = -2x] \rightarrow [y+2x = 0] \right) \rightarrow \exists y[y+2x = 0] \text{.} $$ A destra, la variabile $y$è vincolato dal quantificatore esistenziale; ha portata sintattica solo fino alla fine della clausola quantificata. Potremmo semplicemente sostituirlo con un'altra variabile e ottenere un'istruzione semanticamente equivalente: $$ \left( [y = -2x] \rightarrow [y+2x = 0] \right) \rightarrow \exists z[z+2x = 0] \text{.} $$ Questa è ancora un'inferenza valida.

Sul lato sinistro, $x$ e $y$appaiono non quantificate, quindi sono variabili libere (antonimo di vincolato). Le variabili libere sono implicitamente quantificate universalmente nel campo di applicazione più ampio. Se rendiamo esplicita tale quantificazione, dobbiamo modificare la variabile legata sul lato destro per mantenere la validità sintattica. (Cioè, è un errore di sintassi avere un'istruzione con$y$ vincolati due volte in clausole annidate. $y$ può essere vincolato in due clausole disgiunte, ma si dovrebbe tenere presente che le due $y$s non deve necessariamente avere lo stesso valore.) Quindi, con le quantificazioni implicite, $$ \forall x \forall y \left( \left( [y = -2x] \rightarrow [y+2x = 0] \right) \rightarrow \exists z[z+2x = 0] \right) \text{.} $$

Ne discuto perché nei commenti mi hai proposto $$ \left( [y = -2x] \rightarrow [y+2x = 0] \right) \rightarrow \left( [y = -2x] \rightarrow \exists z[z+2x = 0] \right) \text{.} $$ Questo è molto più debole del modulo di prova descritto sopra e il motivo per cui ha a che fare con l'uso illimitato di$y$ e $x$nell'implicazione tra parentesi a destra. L'implicazione tra parentesi a sinistra dice:

Se, in qualche prova, hai il fatto "$y = -2x$"già stabilito, allora si può dedurre il fatto"$y + 2x = 0$".

Ciò richiede che lo stato delle variabili implicitamente quantificate universalmente nel proprio contesto lo contenga o lo implichi $y = -2x$al fine di ottenere il conseguente. Allo stesso modo, l'implicazione tra parentesi a destra dice:

(Supponendo che l'antecedente, l'implicazione tra parentesi a sinistra, sia già stabilita), se in qualche prova hai il fatto "$y = -2x$"già stabilito, allora si può dedurre il fatto"$\exists z [z + 2x = 0]$".

Questa implicazione di destra non fa la semplice affermazione "$\exists z [z + 2x = 0]$ è vero ". Rende l'affermazione molto più debole" lo stato delle variabili implicitamente quantificate universalmente $x$ e $y$ nel tuo contesto deve contenerlo o implicarlo $y = -2x$e poi puoi dedurre$\exists z [z + 2x = 0]$ è vero".

Ma "$\exists z [z + 2x = 0]$" dovrebbe essere indipendente dalla variabile free$y$. (Equivalentemente, "$\exists y [y + 2x = 0]$" dovrebbe essere indipendente dalla variabile free$y$, poiché la variabile free $y$ non è menzionato in questa clausola quantificata.)

La versione che hai prodotto è più debole perché asserisce solo il risultato esistenzialmente quantificato in contesti (variabili libere) dove $y = -2x$. Ma$\exists z [z+2x = 0]$dovrebbe essere vero in qualsiasi contesto (in cui il materiale ha la relazione$[y = -2x] \leftrightarrow [y+2x=0]$), indipendentemente dai valori delle variabili non associate $x$ e $y$.