---
Title: Folo - Cours 2\ :\ Logique du 1er ordre (Théorie des ensembles)
tags: folo, cours, MiMos
---
{%hackmd theme-dark %}

# Formalisation Logique - Cours 2: Logique du 1er ordre (Théorie des ensembles)

[`video`](https://web.microsoftstream.com/video/7420c63d-b5c5-42e3-8ace-82b26bfe50a5?channelId=72a2ac7e-b1c9-4e29-9bb0-5c203649f700)
[`slide`](https://moodle.cri.epita.fr/mod/resource/view.php?id=9730)

## Introduction

Extension de la logique classique utilisant la théorie des ensembles.

> **But:** regrouper et manipuler des objets qui ont les mêmes propriétés.

## Définition

### Ensemble $\{x_1, \dots, x_n \}$

- est constitué d'un predicat[^1] dont tous les éléments valide ce **prédicat d'appartenance**.
Soit $P$ le prédicat de l'ensemble $E$ :
$$
\forall x \in E, P(x) \text{ vrai} \\
\forall x \notin E, \neg P(x) \text{ vrai}
$$

- collection d'objet distinct (ne contient pas 2 fois le même objet).

Un ensemble contenant $n$ ($n \in \mathbb N$) éléments $x_1, \dots, x_n$ est noté:

$$
\{x_1, \dots, x_n \}
$$

### Ensemble Vide $\emptyset$

L'ensemble vide est noté:

$$
\emptyset
$$

il ne contient **aucun élément**

$$
x \notin \emptyset \text{ est toujours vrai}
$$

### Singleton $\{x\}$

Un ensemble ne contenent qu'un élément est un **singleton**. Le singleton contenant $x$ est noté:

$$
\{x\}
$$

### Couple $\{x, y\}$

Un couple est un ensemble constitué de 2 éléments (distinct).

Un couple contenant $x$ et $y$ est noté:

$$
\{x, y\}
$$

## Opération

Soit $U$ et $V$ 2 ensembles

### Union $\cup$


$U \cup V$ est **l'union de $U$ et $V$** et est lui-même un ensemble.

$$
x \in U \cup V \equiv (x \in U) \lor (x \in V)
$$

### Intersection $\cap$


$U \cap V$ est **l'intersection de $U$ et $V$** et est lui-même un ensemble.

$$
x \in U \cap V \equiv (x \in U) \land (x \in V)
$$

### Sous-ensemble $\subseteq$


$U \subseteq V$ est une proposition qui est vraie si tous les éléments de $U$ sont dans $V$

$$
U \subseteq V \equiv (x \in U) \implies (x \in V)
$$

### Egalité $=$

$U = V$ est une proposition qui est vrai si tous les éléments de $U$ sont dans $V$ et vise-versa.

$$
U = V \equiv (x \in U) \iff (x \in V)
$$

> #### Preuve
>
> $$
> \begin{align}
> U = V &\iff (x \in U) \iff (x \in V)\ \ (\text{définition de} \iff) \\
> &\iff ((x \in U) \implies (x \in V))
> \land ((x \in V) \implies (x > \in U)) \\
> &\iff (U \subseteq V) \land (V \subseteq U) \\
> \end{align}
> $$
>
> donc pour prouver que $U = V$ on doit prouver la double inclusion.

### Parties d'un ensemble $\mathcal P(E)$

Soit $E$ un ensemble, $\mathcal P(E)$ est l'ensemble des sous-ensemble de $E$.

$$
X \in \mathcal P(E) \iff X \subseteq E. \\
P(E) = \{F | F \subseteq E\}
$$

#### Propriété

$\mathcal P (E)$ contient toujours l'ensemble vide ainsi que lui-même.

$$
\forall E, \emptyset \in \mathcal P(E), E \in \mathcal P(E)
$$

### Complémentation $\complement$


Soit le complementaire de l'ensemble $U$ par apport à $V$ est l'ensemble des éléments qui sont dans $V$ mais pas $U$.

$$
U \subseteq V, x\in U^\complement V \iff (x \notin U) \land (x \in V)
$$

### Produit cartésien $\times$

#### Paire

Une paire de 2 éléments $x$ et $y$ est notée:

$$
(x, y)
$$

Les propriétés des paires sont:
- Strucure ordonnée $(x, y) \neq (y, x)$
- Ne pas confondre avec les [couples](##Couple-span-idMathJax-Element-1363-Frame-classmjx-chtml-MathJax_CHTML-tabindex0-stylefont-size-118-position-relative-data-mathmlxy-rolepresentationxyxyx-y)

#### Définition

Le produit cartésien de 2 ensembles $U$ et $V$ est un ensemble contenent des paires dont le premier élément appartient à $U$ et le deuxième à $V$.

$$
(x, y) \in U \times V \iff (x \in U) \land (y \in V)
$$

### Soustraction $\setminus$

L'ensemble $U \setminus V$ est l'ensemble des éléments qui ne sont dans $U$ mais pas dans $V$.

$$
x \in u \setminus V \iff x
$$

### Quatificateurs

#### Pour tous $\forall$

$$
\forall x \in \mathbb R, x^2 \geq 0
$$

Remarque:
$$
\forall x \in \emptyset, ...
$$
Cette proposition est toujours vraie

Exemple de structure pour prouver avec un $\forall$ :

**Prouver :**

$\forall x \mathbb R^{+\star}$

$$
x + \frac1x \geq 2
$$

**Analyse** :

$$
\begin{align}
x + \frac1x &\geq 2\\
\iff x^2 + 1 &\geq 2x \\
\iff x^2 - 2x + 1 &\geq 0 \\
\iff (x - 1)^2 &\geq 0
\end{align}
$$

**Synthèse** :

$$
(x - 1)^2\geq 0
$$

Condition nécessaire (mais pas forcement suffisante), mais ne veut pas dire que l'hypothèse est vrai, il s'agit juste d'une conséquence possible.

Autre exemple :

$$
\forall \in E, \mathcal P(x)
$$

**hypothese:** cas particulier

$\forall a, b , c \in \mathbb R, P \equiv ax^2 + bx + c = 0$

$$
(\forall x \in \mathbb E, ax^2 + bx + c = 0) \implies (a = b = c = 0)
$$

$$
\begin{cases}
x = 0 &\implies& x = 0 \\
a + b = 0 &\implies& x = 1 \\
a - b = 0 &\implies& x = -1
\end{cases}
$$

#### Il existe $\exists$

Pour dire qu'il existe au moins 1'élément on utilise le symbole:

$$
\exists
$$

Exemple:

$$
\forall x \in E , \mathcal P(x)
$$

**Application:**

$$
\exists x \in E, \mathcal P
$$

#### Unicité $\exists!$

Pour dire qu'il y a que un seul élément on écrit :

$$
\exists!
$$

## Résumé

Soit $U$ et $V$ deux ensembles avec respectivement comme predicat d'appartenance $P$ et $Q$.

| ensemble | prédicat d'appartenance |
| ----------------- | ---------------------- |
| $U \cup V$ | $P \lor Q$ |
| $U \cap V$ | $P \land Q$ |
| $U \subset V$ | $P \implies Q$ |
| $U^\complement V$ | $\lnot P \land Q$ |
| $U = V$ | $P \iff Q$ |
| $U \setminus V$ | $P \land \lnot Q$ |

[^1]: fonction à 1 variable qui renvoie un booléen