4 Quantificatori universale ed esistenziale

[next] [prev] [prev-tail] [tail] [up]

Capitolo 4
Quantificatori universale ed esistenziale

WEB (Materiali vari)

“

Studia questo capitolo con l’AI: quiz, esercizi e altro

Ripassa con le flashcard

Esercizi auto-generati

Sorgente di questo capitolo

Schede, test e video di matematika.it

Esercizi del prof. De Capoa

La logica matematica differisce dalle altre logiche solo per il fatto di usare i simboli.”

— Giuseppe Peano, Formulario Mathematico (1908)

____________________________________________________________________________________

4.1 Introduzione motivazionale

quiz e materiali con l’AI

Nel capitolo precedente abbiamo introdotto i connettivi $\lnot $, $\land $, $\lor $, $\Rightarrow $, $\Leftrightarrow $, che permettono di combinare proposizioni intere. Ma molte affermazioni matematiche hanno una struttura più fine: non riguardano un singolo oggetto, riguardano tutti gli oggetti di un insieme oppure almeno uno.

“Il quadrato di ogni numero reale è non negativo” è un’affermazione di tipo nuovo: parla simultaneamente di infiniti oggetti. “Esiste un numero naturale maggiore di un milione” è anch’essa diversa da una semplice proposizione: dichiara solo che almeno uno c’è. Questi due modi di parlare — l’“ogni” e l’“esiste” — sono i quantificatori.

Senza quantificatori la matematica resterebbe muta su quasi tutto ciò che le interessa: i teoremi, le definizioni, le proprietà strutturali. In questo capitolo introduciamo i due simboli $\forall $ (“per ogni”) ed $\exists $ (“esiste”), impariamo a leggerli e a scriverli, e soprattutto impariamo a negarli correttamente — operazione tutt’altro che ovvia, e fonte di molti errori per chi inizia.

4.2 Predicati e quantificatore universale $\forall $

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 4.1 — Predicato

Un predicato (o formula aperta) è una frase contenente una o più variabili, che diventa una proposizione (vera o falsa) non appena le variabili vengano sostituite con valori concreti tratti da un insieme di riferimento, detto dominio.

Indichiamo i predicati con $P(x)$, $Q(x,y)$, $\ldots $, mettendo tra parentesi le variabili libere. La frase

\[ P(x): \quad ``x>0'' \qquad \text {(con $x\in \mathbb{R} $)} \]

non è in sé vera o falsa: $P(3)$ è vera, $P(-1)$ è falsa, $P(\sqrt {2})$ è vera. È solo quando $x$ riceve un valore — o quando viene “quantificata” — che si ottiene una proposizione.

Il primo modo di trasformare un predicato in proposizione è dire che il predicato vale per tutti gli elementi del dominio.

Definizione 4.2 — Quantificatore universale

Dato un predicato $P(x)$ sul dominio $D$, la proposizione

\[ \forall x\in D : P(x) \]

si legge “per ogni $x$ in $D$, vale $P(x)$” ed è vera quando $P(x)$ è vera per ciascun elemento $x$ del dominio, falsa quando esiste almeno un elemento del dominio per cui $P(x)$ è falsa.

Il simbolo $\forall $ è una A capovolta (all, “tutti”) e si scrive a sinistra della variabile cui si riferisce. Se il dominio è chiaro dal contesto si scrive semplicemente $\forall x: P(x)$.

Esempio 4.1 — Vero o falso?

Stabilire il valore di verità delle seguenti proposizioni.

$\forall x\in \mathbb{R} :\ x^2\ge 0$ — vera: il quadrato di ogni numero reale è non negativo.
$\forall n\in \mathbb{N} :\ n+1>n$ — vera.
$\forall x\in \mathbb{R} :\ x>0$ — falsa: $x=-1$ è un controesempio.
$\forall n\in \mathbb{N} :\ n^2-n\ge 0$ — vera: per $n=0$ vale $0$; per $n\ge 1$, $n^2-n=n(n-1)\ge 0$.

Nota — Quantificatore universale e congiunzione

Se il dominio è finito, $D=\{a_1,a_2,\ldots ,a_n\}$, allora

\[ \forall x\in D: P(x) \quad \equiv \quad P(a_1)\land P(a_2)\land \cdots \land P(a_n). \]

Il quantificatore universale è dunque una specie di “congiunzione su tutti gli elementi” del dominio. Se $D$ è infinito, la congiunzione diventa infinita e $\forall $ è l’unico modo di esprimerla in modo finito.

Attenzione! — Per smentire un “$\forall $”

Per dimostrare che $\forall x\in D: P(x)$ è falsa basta un singolo elemento $x_0\in D$ per cui $P(x_0)$ è falsa: si chiama controesempio. Trovare un controesempio è sufficiente. Verificare la proposizione su molti casi favorevoli, invece, non è mai sufficiente: il fatto che $P(x)$ valga per i primi cento valori non garantisce nulla sul centunesimo.

[Picture] — Figura 4.1: Il quantificatore universale $\forall x\in D: P(x)$ è vero quando ogni elemento di $D$ soddisfa il predicato $P$: nella figura, tutti i punti sono “verdi” (soddisfano $P$).

4.3 Quantificatore esistenziale $\exists $

quiz e materiali con l’AI

flashcard del paragrafo

Il secondo modo di trasformare un predicato in proposizione è dire che il predicato vale per almeno un elemento del dominio.

Definizione 4.3 — Quantificatore esistenziale

Dato un predicato $P(x)$ sul dominio $D$, la proposizione

\[ \exists x\in D : P(x) \]

si legge “esiste $x$ in $D$ tale che $P(x)$” ed è vera quando almeno un elemento del dominio soddisfa $P(x)$, falsa se nessun elemento del dominio lo soddisfa.

Il simbolo $\exists $ è una E rovesciata (exists). “Esiste” va inteso in senso debole: significa “ce n’è almeno uno”, non “ce n’è esattamente uno”.

Esempio 4.2

$\exists n\in \mathbb{N} :\ n>10^6$ — vera (ad esempio $n=10^6+1$).
$\exists x\in \mathbb{R} :\ x^2=-1$ — falsa: nessun reale ha quadrato negativo.
$\exists x\in \mathbb{R} :\ x^2=2$ — vera ($x=\sqrt {2}$, ma anche $x=-\sqrt {2}$).
$\exists p\in \mathbb{N} :\ p$ è primo e $p>100$ — vera (ad esempio $p=101$).

Nota — Quantificatore esistenziale e disgiunzione

Se il dominio è finito, $D=\{a_1,a_2,\ldots ,a_n\}$, allora

\[ \exists x\in D: P(x) \quad \equiv \quad P(a_1)\lor P(a_2)\lor \cdots \lor P(a_n). \]

L’esistenziale è dunque una “disgiunzione su tutti gli elementi”. Anche qui, se $D$ è infinito, $\exists $ è l’unico modo finito di esprimerla.

Definizione 4.4 — Esistenza unica

Si introduce talvolta il simbolo $\exists !$ per esprimere esistenza e unicità:

\[ \exists !\, x\in D : P(x) \]

significa “esiste un unico $x\in D$ tale che $P(x)$”. Equivale alla congiunzione di due fatti:

\[ \exists x\in D : P(x) \quad \text {(esistenza)} \qquad \land \qquad \forall x,y\in D :\ (P(x)\land P(y)\Rightarrow x=y) \quad \text {(unicità).} \]

Esempio 4.3

$\exists !\, x\in \mathbb{R} :\ 3x-7=2$: esiste un unico reale tale che $3x-7=2$, ed è $x=3$. L’esistenza si prova esibendolo; l’unicità deriva dall’unicità della soluzione di un’equazione lineare a coefficiente non nullo.

Attenzione! — Per smentire un “$\exists $”

Per dimostrare che $\exists x\in D: P(x)$ è falsa bisogna escludere ogni elemento del dominio: equivalentemente, bisogna provare che $\forall x\in D: \lnot P(x)$. Per provarla vera, invece, basta esibirne un esempio.

4.4 Negazione di proposizioni con quantificatori

quiz e materiali con l’AI

flashcard del paragrafo

Negare un’affermazione con quantificatori è una delle operazioni più delicate per chi inizia a fare matematica. La regola, però, è semplice e ricorda da vicino le leggi di De Morgan viste nel capitolo precedente: negando si scambia $\forall $ con $\exists $ e si nega il predicato.

Teorema 4.1 — Leggi di De Morgan per i quantificatori

Per ogni predicato $P(x)$ sul dominio $D$:

\[ \lnot \bigl (\forall x\in D : P(x)\bigr ) \;\equiv \; \exists x\in D : \lnot P(x), \]

\[ \lnot \bigl (\exists x\in D : P(x)\bigr ) \;\equiv \; \forall x\in D : \lnot P(x). \]

Dimostrazione (idea). Dire “non è vero che $P(x)$ vale per ogni $x$” significa dire “c’è almeno un $x$ per cui $P(x)$ non vale”: è la prima legge. Specularmente, dire “non è vero che esiste un $x$ con $P(x)$” significa dire “per ogni $x$, $P(x)$ è falso”: è la seconda. Su dominio finito, la verifica è una applicazione iterata delle leggi di De Morgan per $\land $ e $\lor $ già dimostrate.

\[ \lnot (\forall x : P(x)) \equiv \exists x : \lnot P(x),\qquad \lnot (\exists x : P(x)) \equiv \forall x : \lnot P(x). \]

Procedura — Negare una proposizione quantificata

Per negare un’affermazione che contiene quantificatori:

1.: si scambia ogni $\forall $ con $\exists $ e viceversa, mantenendo lo stesso dominio;
2.: si nega il predicato finale, applicando se serve le regole sui connettivi (in particolare $\lnot (p\Rightarrow q)\equiv p\land \lnot q$).

Esempio 4.4 — Negazione di una frase universale

Negare: “ogni numero primo è dispari”.

Soluzione. Posto $P(p):$ “$p$ è dispari”, la frase è $\forall p\in \mathbb {P}: P(p)$ (dove $\mathbb {P}$ è l’insieme dei primi). La sua negazione è $\exists p\in \mathbb {P}: \lnot P(p)$, ovvero “esiste un primo che non è dispari”, cioè “esiste un primo pari”. Un controesempio esiste: $p=2$. Quindi la frase di partenza è falsa.

Esempio 4.5 — Negazione di una frase esistenziale

Negare: “esiste un numero reale uguale al proprio quadrato e diverso da $0$ e $1$”.

Soluzione. Posto $P(x):$ “$x^2=x \land x\neq 0 \land x\neq 1$”, la frase è $\exists x\in \mathbb{R} : P(x)$. La negazione è $\forall x\in \mathbb{R} : \lnot P(x)$, ovvero “per ogni $x\in \mathbb{R} $, $x^2\neq x$ oppure $x=0$ oppure $x=1$”. (Equivalentemente: “ogni reale che soddisfa $x^2=x$ è $0$ o $1$”.) Quest’ultima è vera: $x^2=x\Leftrightarrow x(x-1)=0\Leftrightarrow x=0\lor x=1$. Quindi la frase di partenza è falsa.

Esempio 4.6 — Negazione di un’implicazione quantificata

Negare: “per ogni $n\in \mathbb{N} $, se $n$ è primo allora $n$ è dispari”.

Soluzione. Posto $p(n):$ “$n$ è primo” e $q(n):$ “$n$ è dispari”, la frase è $\forall n\in \mathbb{N} : (p(n)\Rightarrow q(n))$. Negandola:

\[ \exists n\in \mathbb{N} : \lnot (p(n)\Rightarrow q(n)) \equiv \exists n\in \mathbb{N} : (p(n)\land \lnot q(n)), \]

cioè: “esiste un $n\in \mathbb{N} $ primo e non dispari”, ovvero “esiste un primo pari”. È vera ($n=2$): quindi la frase di partenza è falsa, e $n=2$ è il controesempio.

4.5 Quantificatori multipli

quiz e materiali con l’AI

flashcard del paragrafo

Molte definizioni della matematica usano più quantificatori in cascata. Per esempio, “per ogni numero reale esiste un naturale più grande di esso” contiene un $\forall $ seguito da un $\exists $. La cosa importante da capire è che l’ordine dei quantificatori conta.

Definizione 4.5 — Quantificatori dello stesso tipo

Quantificatori dello stesso tipo, in posizioni adiacenti, commutano:

\[ \forall x\,\forall y : P(x,y) \;\equiv \; \forall y\,\forall x : P(x,y), \qquad \exists x\,\exists y : P(x,y) \;\equiv \; \exists y\,\exists x : P(x,y). \]

Si scrivono spesso in forma compatta: $\forall x,y : P(x,y)$ oppure $\exists x,y : P(x,y)$.

Attenzione! — Quantificatori di tipo diverso non commutano

$\forall x\,\exists y : P(x,y)$ e $\exists y\,\forall x : P(x,y)$ non sono equivalenti.

$\forall x\,\exists y : P(x,y)$ — “per ogni $x$ esiste un $y$ (eventualmente dipendente da $x$) tale che $P(x,y)$”;
$\exists y\,\forall x : P(x,y)$ — “esiste un $y$ unico e indipendente da $x$ tale che $P(x,y)$ valga per tutti gli $x$”.

La seconda è molto più forte: ne segue la prima, ma non viceversa.

Esempio 4.7 — Caso tipico

Sia $P(x,y):$ “$y>x$”, con $x,y\in \mathbb{R} $.

$\forall x\in \mathbb{R} \,\exists y\in \mathbb{R} : y>x$ — vera: per ogni $x$, basta scegliere $y=x+1$.
$\exists y\in \mathbb{R} \,\forall x\in \mathbb{R} : y>x$ — falsa: nessun reale può essere maggiore di tutti i reali (in particolare, non può essere maggiore di sé stesso $+1$).

La differenza è nella dipendenza di $y$ da $x$.

Nota — Negare quantificatori in cascata

La regola si applica passo per passo, da sinistra a destra:

\[ \lnot \bigl (\forall x\,\exists y : P(x,y)\bigr ) \equiv \exists x : \lnot \bigl (\exists y : P(x,y)\bigr ) \equiv \exists x\,\forall y : \lnot P(x,y). \]

Ogni quantificatore si rovescia, e il predicato finale si nega.

Esempio 4.8 — Negazione di una definizione tipica

La definizione di “$0$ è l’unico massimo di $-x^2$ su $\mathbb{R} $” è del tipo $\forall x\in \mathbb{R} : -x^2\le 0$. La sua negazione sarebbe: $\exists x\in \mathbb{R} : -x^2>0$, cioè “esiste un reale con quadrato negativo”, falsa.

Più in generale, la negazione di “$M$ è un maggiorante di $A$”, cioè $\forall x\in A: x\le M$, è $\exists x\in A: x>M$ (“c’è almeno un elemento di $A$ più grande di $M$”). È così che si nega “maggiorante”.

4.6 Esempi svolti

quiz e materiali con l’AI

Esempio 4.9 — Tradurre dal linguaggio naturale

Tradurre in simboli: “ogni numero naturale maggiore di $1$ ha almeno un divisore primo”.

Soluzione. Posto $D(p,n):$ “$p$ divide $n$”, la frase è

\[ \forall n\in \mathbb{N} ,\ n>1\ :\ \exists p\in \mathbb{N} \ (p\ \text {primo}\ \land \ D(p,n)). \]

Il quantificatore universale è ristretto agli $n>1$ (lo si può anche scrivere $\forall n\in \mathbb{N} : n>1 \Rightarrow \cdots $, equivalente). All’interno, l’esistenziale dichiara la presenza di un divisore primo.

Esempio 4.10 — Negare una proposizione complessa

Negare: “per ogni $\varepsilon >0$ esiste un intero positivo $n$ tale che $\tfrac {1}{n}<\varepsilon $”.

Soluzione. La proposizione, in simboli, è

\[ \forall \varepsilon >0\ \exists n\in \mathbb{N} ^*\ :\ \tfrac {1}{n}<\varepsilon . \]

Applicando le regole di negazione due volte:

\[ \exists \varepsilon >0\ \forall n\in \mathbb{N} ^*\ :\ \tfrac {1}{n}\ge \varepsilon . \]

Cioè: “esiste un $\varepsilon >0$ tale che $\tfrac {1}{n}\ge \varepsilon $ per ogni intero positivo $n$”. (La proposizione originale è la cosiddetta “proprietà archimedea” di $\mathbb{R} $: è vera, dunque la sua negazione è falsa.)

Esempio 4.11 — Dipendenza di $y$ da $x$

Dire se le proposizioni

\[ \varphi : \forall x\in \mathbb{R} \ \exists y\in \mathbb{R} \ :\ y^2=x \qquad \psi : \exists y\in \mathbb{R} \ \forall x\in \mathbb{R} \ :\ y^2=x \]

sono vere.

Soluzione. $\varphi $ chiede che ogni reale sia il quadrato di qualche reale: falsa, perché i reali negativi non lo sono. $\psi $ chiede che esista un $y$ tale che $y^2=x$ per ogni $x\in \mathbb{R} $: falsa, perché un $y$ fissato dà un unico valore $y^2$ e non può essere uguale a tutti i reali contemporaneamente. Le due sono diverse anche se entrambe false.

Se restringiamo il dominio a $\mathbb{R} _{\ge 0}$, la prima diventa vera: $\forall x\ge 0\ \exists y\ge 0 : y^2=x$ (basta $y=\sqrt {x}$). La seconda resta falsa.

Esempio 4.12 — Controesempio in un universale

Stabilire se è vera: “per ogni $n\in \mathbb{N} $, $n^2+n+41$ è primo”.

Soluzione. La proprietà vale per $n=0,1,\ldots ,39$ (è la classica “formula di Eulero”): $0+0+41=41$ è primo, $1+1+41=43$ è primo, e così via. Si è tentati di crederla vera. Però per $n=40$:

\[ 40^2+40+41 = 1600+40+41 = 1681 = 41^2, \]

che non è primo. Quindi la proposizione è falsa, e $n=40$ è il controesempio. Conferma del principio: nessuna quantità di casi favorevoli prova un universale; un solo caso sfavorevole lo confuta.

4.7 Esercizi proposti

quiz e materiali con l’AI

Esercizio 4.1

1.: Stabilisci il valore di verità delle seguenti proposizioni e, in caso di falsità, fornisci un controesempio: (a) $\forall x\in \mathbb{R} :\ x^2>0$; (b) $\forall n\in \mathbb{N} :\ n+1>0$; (c) $\exists x\in \mathbb{R} :\ x^2+1=0$; (d) $\exists n\in \mathbb{N} :\ n^2=n+1$; (e) $\forall n\in \mathbb{N} :\ 2n$ è pari.
2.: Traduci in linguaggio simbolico (scegliendo opportunamente i predicati): (a) “il prodotto di due numeri pari è pari”; (b) “esistono due interi distinti con lo stesso quadrato”; (c) “non tutti i numeri primi sono dispari”; (d) “ogni triangolo equilatero è isoscele”.
3.: Scrivi la negazione delle seguenti proposizioni, riformulandola in italiano nel modo più naturale possibile: (a) $\forall x\in \mathbb{R} :\ x^2\ge 0$; (b) $\exists n\in \mathbb{N} :\ n>10^{10}$; (c) “ogni studente della classe ha consegnato il compito”; (d) “esiste almeno un libro non letto sullo scaffale”.
4.: Per ciascuna delle implicazioni quantificate, scrivi la negazione e indica se sei in grado di stabilire chi è vero (l’originale o la negazione): (a) $\forall n\in \mathbb{N} :\ n$ primo $\Rightarrow n$ dispari; (b) $\forall x\in \mathbb{R} :\ x>0\Rightarrow x^2>0$; (c) $\forall n\in \mathbb{N} :\ n^2$ pari $\Rightarrow n$ pari.
5.: Distingui in italiano e in simboli le due proposizioni (a) “per ogni allievo esiste un libro che ha letto”; (b) “esiste un libro che ogni allievo ha letto”. Quale delle due è più forte? Quale implica l’altra?
6.: Sia $P(x,y)$: “$x+y=10$” con $x,y\in \mathbb{Z} $. Stabilisci il valore di verità di: (a) $\forall x\in \mathbb{Z} \ \exists y\in \mathbb{Z} : P(x,y)$; (b) $\exists y\in \mathbb{Z} \ \forall x\in \mathbb{Z} : P(x,y)$; (c) $\exists x,y\in \mathbb{Z} : P(x,y)$; (d) $\forall x,y\in \mathbb{Z} : P(x,y)$.
7.: Sia $\mathbb {P}$ l’insieme dei numeri primi. Traduci in simboli “esiste un primo pari ed è unico”. Riconosci il quantificatore $\exists !$.
8.: (Discussione.) Verifica con due controesempi, presi nel dominio $D=\{1,2,3,4,5\}$, la non commutatività di $\forall \exists $ e $\exists \forall $ per il predicato $P(x,y): y>x$. Confronta poi con il caso $D=\mathbb{R} $.

4.8 Riepilogo del capitolo

quiz e materiali con l’AI

Riepilogo

Un predicato $P(x)$ contiene variabili libere e diventa proposizione solo quando le variabili ricevono un valore o vengono quantificate.
Il quantificatore universale $\forall x\in D : P(x)$ è vero se ogni elemento di $D$ soddisfa $P$. Per smentirlo basta un controesempio.
Il quantificatore esistenziale $\exists x\in D : P(x)$ è vero se almeno un elemento di $D$ soddisfa $P$. Per provarlo vero basta esibire un esempio.
Esistenza e unicità si esprimono con $\exists !\, x\in D : P(x)$, equivalente a esistenza più “due qualunque soluzioni coincidono”.
Leggi di De Morgan per i quantificatori: $\lnot (\forall x:P(x))\equiv \exists x:\lnot P(x)$, $\lnot (\exists x:P(x))\equiv \forall x:\lnot P(x)$.
Per negare un’affermazione quantificata: scambiare ogni $\forall $ con $\exists $ e viceversa, e negare il predicato finale. In particolare $\lnot (p\Rightarrow q)\equiv p\land \lnot q$ (capitolo 3).
I quantificatori dello stesso tipo commutano; quelli di tipo diverso non commutano: $\forall x\,\exists y$ ammette $y$ dipendente da $x$, mentre $\exists y\,\forall x$ pretende un $y$ unico valido per tutti gli $x$.

[next] [prev] [prev-tail] [front] [up]