À propos des quantificateurs
Bonjour
Est-ce que quelqu'un peut me donner une idée sur la démonstration de la permutation des quantificateurs universels entre eux et les quantificateurs existentiels entre eux et aussi concernant de leur négation.
Est-ce que quelqu'un peut me donner une idée sur la démonstration de la permutation des quantificateurs universels entre eux et les quantificateurs existentiels entre eux et aussi concernant de leur négation.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si Ax(AyR(x,y)) alors AyR(t,y) donc R(t,u).
Comme on n'a rien supposé sur t, on considère qu'on peut affirmer [AxR(x,u)]
Comme pour en arriver là on n'a rien supposé sur u on se sent sûr que Ay[AxR(x,y)]
Bon d'un téléphone c'est une horreur de rédaction. Pardon. Mais tu as l'essentiel de la démarche formelle.
Viens-tu de fournir une preuve, une indication, une idée ?
Je sais que tu es du téléphone, alors inutile de t'acharner et de t'énerver sur la technologie ;-).
Ce sont les phrases "on considère qu'on peut affirmer" ou encore "on se sent sûr que" qui ne me permettent pas de comprendre.
Je le répète : pas de réponse trop rapide au téléphone.[/size]
Maintenant, ces arguments se formalisent aussi tout à fait, par exemple dans le calcul des séquents (intuitionniste ou classique, pas d'importance ici).
On part de l'axiome :
$$R(x,y)\vdash R(x,y)$$
(contexte : $\{x,y\}\cup V$ où $V$ est l'ensemble des autres variables libres de la formule $R(x,y)$).
Par la règle d'introduction du $\forall$ à gauche :
$$\forall y\ R(x,y)\vdash R(x,y)$$
(contexte : toujours $\{x,y\}\cup V$).
Encore par la règle d'introduction du $\forall$ à gauche :
$$\forall x\ \forall y\ R(x,y)\vdash R(x,y)$$
(contexte : toujours $\{x,y\}\cup V$).
Puisque la variable $x$ n'a pas d'occurrence libre à gauche du séquent, on peut appliquer la règle d'introduction du $\forall$ à droite, avec élimination de $x$ du contexte :
$$\forall x\ \forall y\ R(x,y)\vdash \forall x\ R(x,y)$$
(contexte : $\{y\}\cup V$).
Puisque la variable $y$ n'a pas d'occurrence libre à gauche du séquent, on peut appliquer la règle d'introduction du $\forall$ à droite, avec élimination de $y$ du contexte :
$$\forall x\ \forall y\ R(x,y)\vdash \forall y\ \forall x\ R(x,y)$$
(contexte : $V$).
Voila une preuve entièrement formalisée. Tu es bien avancé, et Nemya aussi, sans doute ?
Il faut faire attention au symbole $\exists !$ on n'a pas l'équivalence $(\exists!x)(\exists!y)P(x,y)\Leftrightarrow(\exists!y)(\exists!x)P(x,y)$
"j'avais payé les frais"
Je ne connais pas ce langage (séquents, symbole $\vdash $, règle d'introduction du $\forall$, etc.).
Attention, je sais que je dois travailler pour cela et qu'il existe même plein de fils dans ce forum.
Je ne demande pas qu'on fasse le boulot à ma place.
Mon intervention vient du fait que quand je connais le sujet, je trouve certains messages de @cc obscurs (dans le sens "idée", "preuve", autres ?). Tu admettras que "on se sent sûr que" est étonnant.
C'est ainsi que, sans vouloir l'embêter, je lui demande des précisions.
Encore une fois, merci bien, il me reste à travailler.
Dire que $$\forall x\in A\ \ \forall y\in B\ \ R(x,y)$$ est vrai, c'est dire en bon français que quel que soit l'élément $a$ de $A$ et quel que soit l'élément $b$ de $B$, $R(a,b)$ est vrai.
Dire que $$\forall y\in B\ \ \forall x\in A\ \ R(x,y)$$ est vrai, c'est dire en bon français que quel que soit l'élément $b$ de $B$ et quel que soit l'élément $a$ de $A$, $R(a,b)$ est vrai.
N'est-il pas évident pour toi que les deux sont synonymes ? Et toujours synonyme avec "quel que soit le couple $(a,b)$ dans $A\times B$, $R(a,b)$ est vrai" ?
Es-tu d'accord avec http://www.les-mathematiques.net/phorum/read.php?16,1693310,1693378#msg-1693378
J ' ai un contre exemple mais cc m'impressionne des fois avec ces contres exotiques. Je maintiens ma question @cc
Pour ma part, quand on traduit ce « $ \exists !$ » avec les quantificateurs $\forall$ et $\exists$ on s'en rend compte assez bien.
[Inutile de recopier l'avant dernier message. Un lien suffit. AD]
Je ne comprends pas ce que tu veux dire ? Éclaire ma lampe en me précisant cette traduction.
Je tente de traduire avec l'idée suivante :
1) il existe un élément qui satisfait la propriété (l'existence)
$\qquad$ et
2) s'il en existe un autre, alors ils sont égaux (l'unicité)
Expression A :
$\big( \exists !u, P(u) \big) \Leftrightarrow \big( (\exists u, P(u))$ et $(\exists u, P(u), \forall v, (P(v) \Rightarrow u=v)) \big) \qquad$ (A confirmer !)
Hum, les experts confirmeront 8-)
J'ai eu envie dans un premier temps d'écrire cela :
Expression B :
$\big( \exists !u, P(u) \big) \Leftrightarrow \big( (\exists u, P(u))$ et $((\exists v, P(v)) \Rightarrow (u=v)) \big) \qquad$ (Confirmer que ce n'est pas correct)
mais il me semble qu'il y a un problème pour le $u$ qui n'est pas présenté après le "et" (est-ce cela les problèmes de variables liées/libres ?).
Est-ce que ce quantificateur $\exists !$ a une bonne interprétation en "logique d'un point de vue catégorique", de la même manière que $\forall$ et $\exists$ peuvent être vus comme des adjoints (j'ai essayé mais $\exists !$ ne semble pas se prêter au même jeu). (@GaBuZoMeu je crois que tu t'y connais en ce genre de choses.)
@cc@Gabu@logicien
Une question :Trouver la négation de:
$$\forall x\in \mathbb{R},\exists! n\in\mathbb{N}, n\leq x<n+1$$
$$\exists x\ \big(A(x)\text{ et } \forall y (A(y) \Rightarrow y=x)\big)\;.$$
C'est ce qu'a écrit Kramer, sauf que j'ai mis des parenthèses pour qu'il n'y ait pas d'ambigüité sur la portée des quantificateurs.
Par exemple
$$\forall x\in \mathbb{R}\ \exists! n\in\mathbb{N}\ n\leq x<n+1$$
abrège
$$\begin{aligned}
&\forall x\in \mathbb{R}\ \exists n\in\mathbb{N}\\
&\hspace{3cm} \left(n\leq x \text{ et } x<n+1\text{ et }\forall p\in \mathbb N\ \left((p\leq x \text{ et } x<p+1)\Rightarrow p=n\right)\right)
\end{aligned}$$
Pour nier, il n'y a qu'à suivre les règles habituelles.
@Champ-Pot-Lion : Le $\exists!$ ne traduit pas une adjonction (pas comme le $\exists_f$ et le $\forall_f$ adjoints respectivement à gauche et à droite du $f^*$).
On voit quelquefois apparaître un $\exists!$ pour les théories définissables par limites projectives finies, mais ça ne correspond pas à l'usage habituel du $\exists !$ : c'est en fait un $\exists$ ordinaire, mais qu'on a le droit d'écrire uniquement quand on a démontré l'unicité de ce qu'on quantifie (par exemple, comme $\exists y\ xy=1$ dans la théorie des anneaux commutatifs).
Mon expression A est-elle juste ?
Elle est plus longue...
GaBuZoMeu parle d'ambiguïté possible et, très novice avec ces écritures, je suis tombé dedans.
J'imagine qu'on a une règle de syntaxe du type "autour de $\land$ ou $\lor$ on doit redéfinir les lettres" ou un truc de ce genre. Ou des conventions pour éviter des parenthésages pompeux.
C'est dans ce sens que j'ai compliqué les choses dans ma proposition A, plus haut.
@Dom :
$$\exists u, P(u),\color{red}{?}\forall v, (P(v) \Rightarrow u=v)$$
Ta formule ne passe pas l'analyseur syntaxique au ?.
Que veulent dire tes virgules ? Sont elles uniquement décoratives ? Ou alors faut-il les voir comme tantôt décoratives, tantôt signifiant "et" ? Fallait-il lire comme suit ?
$$\exists u\ \left(P(u) \text{ et }\forall v\ (P(v) \Rightarrow u=v)\right)$$
C'est une solution. Pas la seule. Il est équivalent de considérer que $\exists! x\ A(x)$ abrège : $$\Big(\exists x\ A(x)\Big)\text{ et } \Big(\forall x_1 \forall x_2\ \big(A(x_1)\wedge A(x_2)\big) \Rightarrow x_1=x_2\Big)~:$$ la première partie de la conjonction traduit alors l'existence et la seconde partie l'unicité.
Toute ensemble $Q$ de parties de $E$ est un quantificateur sur $E$, qui fournit l'abréviation suivante:
$$ [QxR(x)] := \{x \in E \mid R(x) \} \in Q $$
Le quantificateur $\forall$ n'est autre que $\{E\}$ et le quantificateur $\exists $ n'est autre que $P(E) \setminus \{\emptyset\}$
wikipedia est génial mais à lire avec un esprit critique car je ne t'apprends rien, si tu y regardes bien. (je n'ai d'ailleurs jamais appris ce que je suis en train de te raconter)
Le quantificateur $\exists !$ est $\{ X\subset E\mid card(X)=1 \}$.
Concernant les parenthèses, il est effectivement désolant que la convention internationale ou nationale n'ait pas fixé des pratiques convergentes. Le plus important en tout cas c'est de bien comprendre que quand $Q_1,Q_2$ sont des quantificateurs, $[Q_1xQ_2y P]$ est une abréviation de $[Q_1x(Q_2y P)]$
Tu as raison, je mets des virgules partout, ce ne sont que des séparateurs dans mon esprit.
Je n'ai pas de pratique de ces choses-là et j'imagine que c'est inutile.
Quand je lis une phrase quantifiée à haute voix, je dis plein de "tel que".
Par exemple, je reprends ce que tu as pointé : $\exists u, P(u),\color{red}{?}\forall v, (P(v) \Rightarrow u=v)$
J'ai voulu dire : il existe un $u$ tel que $P(u)$ tel que pour tout $v$, $P(v)$ entraine $u=v$.
Par réflexe, là j'ai mis une seule virgule, pour la lecture en français avant l'implication.
Là encore il faudrait que je me documente et que je travaille.
Je reprends ta proposition de correction : $\exists u\ \left(P(u) \text{ et }\forall v\ (P(v) \Rightarrow u=v)\right)$
En effet, cela veut bien dire : Il existe un $u$ qui vérifie deux choses :
-$P(u)$ 1ère chose
et aussi
-$\forall v (P(v) \Rightarrow u=v)$ 2e chose.
Petite question :
Sans le "et" la phrase $\exists u\ P(u) \forall v\ (P(v) \Rightarrow u=v)\color{red}{)}$ est-elle syntaxiquement juste ?
Edit : je repasse en rouge une parenthèse qui n'aurait pas due être écrite.
Ce n'est pourtant pas difficile. Les formules sont
1) Les formules atomiques
2) Les $A \vee B$, $A \wedge B$, $A \Rightarrow B$, $\neg A$ où $A$ et $B$ sont des formules
3) Les $\forall x A$ et $\exists x A$ où $x$ est une variable et $A$ une formule.
Analyse ce que tu as écrit, tu verras que ça ne peut pas se démonter suivant les règles ci-dessus.
Je tente une justification.
On a cette phrase :
$\exists u\ P(u) \forall v\ (P(v) \Rightarrow u=v)$
L'implication est une formule (entre parenthèses on n'a pas d'autres choix) que je note $F$ .
$\exists u\ P(u) \forall v\ F$
En effet il manque un connecteur (je crois que c'est le bon terme).
Remarque : même sans les parenthèses autour de l'implication on n'a bien un problème au même endroit, je crois que j'ai compris.
$\exists M \in \mathbb R, \forall x \in \mathbb R, f(x)<M \qquad$ (Ne me demandez pas pourquoi je mets des virgules !)
Ici, tout est contracté dans peu de notations et on n'a pas de "$et$".
C'est cela je crois qui m'embrouille...
On lit : "Il existe un réel $M$ tel que pour tout réel $x$, $f(x)$ est strictement inférieur à $M$".
Je tente une traduction avec les règles que tu as données en notant "$R(x)$" la formule "$x$ est réel".
$\exists M \, \left( R(M) \wedge \forall x \, \left( R(x) \Rightarrow f(x)<M \right) \right)$
Est-ce juste ?
J'ai l'impression de mettre trop de parenthèses, est-ce le cas ?
Merci :-)
$$\exists u\ \left(P(u) \ \forall v\ (P(v) \Rightarrow u=v)\right)$$
obtenu par la règle 3) à partir de
$$P(u) \ \forall v\ (P(v) \Rightarrow u=v)$$
Alarme ! Ne relève d'aucune des règles 1) 2) 3).
PS. Tu peux faire l'analyse grammaticale syntaxique de la formule que tu viens d'écrire dans ton dernier message.
Alors j'étudie cette formule : je code en bleu les symboles relatifs aux règles.
$\color{blue}{\exists M} \, \left( R(M) \wedge \forall x \, \left( R(x) \Rightarrow f(x)<M \right) \right)$
règle 3) (il existe)
$R(M) \color{blue}{\wedge} \forall x \, \left( R(x) \Rightarrow f(x)<M \right)$
règle 2) ("et") avec le $R(M)$ et l'autre morceau :
$\color{blue}{\forall x} \, \left( R(x) \Rightarrow f(x)<M \right)$
règle 3) (pour tout)
$ R(x) \color{blue}{\Rightarrow} f(x)<M$
règle 2) (implique)
$R(x)$ et $f(x)<M$ sont bien des formules.
Hum...?
Acquérir ça te fera plaisir ne te prendra que quelques trentaines de minutes de lectures et au moins tu seras "au propre".
Sinon tu seras oblige d'étudier chaque fois comme s'ils étaient ad hoc les programmes qui inspectent une suite.
On est ici devant ce qu'on appelle "une grammaire non ambiguë" mais il y en a qui sont ambiguës, etc. Il y a toute une petite culture sympa à rendre familière pour mieux échanger.
Oui, je sais bien que ce n'est pas long.
Je m'essaye à traduire un truc et surtout je m'interroge : comment en est-on arrivé à écrire un phrase courte et pour moi très claire : $\exists M \in \mathbb R, \forall x \in \mathbb R, f(x)<M \qquad$ ?
Alors qu'avec une "grammaire algébrique" on écrit des phrases "plus dures à lire".
Est-ce une histoire d'implicite ?
c'est à cause de la brise des fondements :-)
Un fil qui peut t’intéresser surtout que gabu était présent et tu peux remarquer qu'il n'utilise jamais les "virgules" ou " tel que" https://www.ilemaths.net/sujet-ecrire-en-quantificateurs-500440.html
Oui, cependant, ça je sais faire (quantifier à la sauce L1).