Les logiques : notes en vrac

Voir aussi ce sujet, surtout le troisième message : Énigme : zéro divisé par zéro, égal ….

Just for the fun: Logicians find a genie (existentialcomics.com).

Le caractère Unicode « ∎ », U+220E, s’appel End of proof.

Il existe un autre caractère Unicode réciproque, qui se dessine à l’envers, « ∵ », U+2235, et s’appel Because.

Avant de se demander comment trouver une preuve d’une proposition, il faut penser à savoir comment vérifier une preuve quelconque de cette proposition.

Ça doit être dit explicitement …

Pour être correcte, une proposition ne doit pas contenir de variables libres. Ça ne signifie pas qu’il ne peut pas y avoir de variables, et ça ne signifie pas que la valeur des variables soit exactement connue. Si une proposition ne peut pas contenir de variables libres, c’est parce qu’il est nécessaire qu’une proposition ait une valeur de vérité.

Ce sera plus clair avec des exemples :

1) Ceci est une fonction : f ≝ λn . n + n ≥ n
2) Ceci est une proposition : P ≝ ∃x ∈ ℕ. x + x = x
3) Ceci est aussi une proposition : P ≝ ∀x ∈ ℕ. f(x)
4) Ceci est une proposition : P ≝ ∀x. x = x
5) Ceci est aussi une proposition : x = 5 , P ≝ x = 6
6) Ceci n’est pas proposition : x ∈ ℕ, P ≝ x + x ≥ x
7) Ceci est une proposition : ∀x. x = x

Dans le premier cas, la variable x est libre, l’expression n’a pas de valeur de vérité, bien que ce soit le type de la fonction, c’est à dire le type de son application, elle n’est précisément pas appliquée.

Dans le second cas, la valeur de x n’est pas exactement connue — on peut lui substituer n’importe quel élément d’un ensemble —, mais x n’est pas une variable libre, elle est liée par un quantificateur.

Dans le troisième cas, la variable x n’est pas libre, et la fonction f est appliquée, la variable n’est donc pas libre dans f ; l’expression est donc une proposition.

Dans le quatrième cas, même si x n’appartient pas à un ensemble, la variable n’est pas libre non‑plus, comme elle est quantifiée.

Le cinquième cas aussi est une proposition, que j’ajoute pour souligner que les quantificateurs ne sont pas toujours requis pour faire une proposition. Cette exemple souligne aussi qu’il n’est pas obligatoire pour une proposition d’être vraie : une proposition n’est pas une conclusion.

Le sixième cas n’est pas une proposition, que j’ajoute pour souligner qu’une contrainte ne suffit pas à lier une variable. On sait que x appartient à ℕ, mais ça n’en fait pas une variable liée, à moins que par x ∈ ℕ on signifie implicitement ∀x ∈ ℕ ou ∃x ∈ ℕ, mais ça doit alors être clairement posée par une règle syntaxique, et ce serait assez non‑habituel, comme l’omission habituelle serait plutôt de dire ∀x ou ∃x tout court, pour dire ∀x ∈ S ou ∃x ∈ S, quand l’ensemble est implicite.

Le septième cas est une proposition aussi, que j’ajoute pour souligner qu’une proposition n’as pas besoin d’être nommée, pour être proposition.

Une subtilité à ne pas perdre de vue avec les fonctions.

f : A → B doit être lu comme « le domaine de f est égal à A, le codomaine de f est inclus dans B ».

Personnellement, je l’avais oublié, j’avais tendance à le lire comme «  …, le codomaine de f est égal à B ».

À propos de la définition des ensembles essentiels, une différence culturelle importante, mais qui ne produit pas d’ambiguïté, comme un standard de l’ISO a opté pour un choix en particulier.

Pour les Anglophones, l’ensemble des naturels, N, ne comprends pas zéro. C’est à dire que pour eux, il est égal à ce qu’on écrirait N*.

À coté, ils définissent un ensemble qui ne contient que zéro, puis définissent un ensemble qu’ils appellent Whole Numbers, comme étant l’union de leur ensemble des naturels et de leur ensemble zéro.

Leur ensemble des rationnels diffère aussi. Ils définissent d’abord un ensemble qu’ils appellent celui des fractions, qui est comme le notre, modulo que les numérateurs et dénominateurs sont restreints à l’ensemble des naturels. Puis ils définissent un ensemble des rationnels identique au notre, à partir de leur ensemble des fractions et de l’ensemble des entiers.

En résumé, ils définissent Ν* qu’ils notent Ν, puis {0}, puis définissent un W = Ν ∪ {0}, puis définissent ℤ à côté duquel ils définissent F = {p, q ∈ Ν | p/q}. Puis ils définissent ℚ = {p, q ∈ ℤ | p/q} à moins que ce ne soit ℚ = {a ∈ ℤ; p, q ∈ Ν | a ⋅ (p/q)}. Au delà, leurs définitions sont les mêmes que les nôtres.

Je ne trouve pas leurs définitions bêtes, je les trouve même intéressantes. Ceci dit, le standard ISO 80000-2, un standard international, stipule que l’ensemble Ν contient zéro et que l’ensemble Ν sans le zéro, se note Ν*. Après, on peut toujours définir un ensemble explicitement, ça n’a d’importance que pour les notations et les implicites avec lesquels on les lit ; ça n’empêche pas d’écrire exactement ce qu’on veut.

Anecdote : certaines gens considèrent que -0 (zéro négatif), est un nombre rationnel, et le distinguent donc de 0 (zéro tout‑court). J’ignore si ces gens font de même une distinction entre +0 et 0.

Ce que nos amis Anglophones appellent field, est ce qu’en français on appellerait un corps commutatif (un type d’ensemble).

C’est étrange, parce que le nom en français et le nom en Anglais, n’évoquent pas les mêmes choses. Field, désigne un champs, en Anglais, un champs au sens large.

Attention : le mot field apparaît aussi en physique, mais n’y a pas le même sens qu’en maths.