TD3 : Relations d’équivalence, Chaînes

TD 3

EX 1

Non, pour qu’une relation d’équivalence sur $E$ puisse être associée de manière biunivoque à une partition de $E$, on a besoin :

  • de la réflexivité :
    • les parties de la partition sont non vides, et leur union fait $E$
  • de la symétrie
  • de la transitivité
    • parties sont deux-à-deux disjointes (en utilisant la transitivité et la symétrie)

NB :

  • Dès qu’il y a plus de deux éléments, la transitivité et la symétrie impliquent le réflexivité, s’il n’y a pas de points isolés.
  • Transitivité + Réfl : $(ℕ, ≤)$
  • Sym + réfl

EX 2

1) Mq que l’ensemble des éléments qui ne sont pas point fixe est de cardinal pair, par réc sur $\vert E\vert $ :

M1 : Si $f$ est l’identité : c’est évident.

Sinon : $f$ est d’ordre 2 dans $𝕾(E) ≃ 𝕾(⟦1,n⟧)$

\(f ≝ \prod_i 𝛾_i ⟹ id = f^2 = \prod_i 𝛾_i^2 ⟹ ∀i, 𝛾_i^2= id \\ \text{(cycles à supports disjoints, qui sont donc des transpositions)}\) ⟹ Si $E$ est de card impair, au moins élément est point fixe (cet élément n’est pas dans les supports des $𝛾_i$)

M2 :

En remarquant que $∀x\neq y, y=f(x) ⟹ x=f(y)$ l’ensemble des non points fixes est de cardinal pair.

2) Impossible d’en avoir $0$, car $0$ est pair.

3) En notant $E$ l’ensemble des racines complexes de $P$ avec multiplicité, et $f$ la conjugaison.

EX 3

La matrice doit être symétrique, n’avoir que des $1$ sur la diagonale, et vérifier \(∀i\neq j \neq k ∈ ⟦1,n⟧, M_{i,j} = M_{j,k} = 1 ⟹ M_{i,k} = 1\)

EX 4

  • Réflexivité, Symétrie : triviales
  • Transitivité : si $(m,n) \sim (p,q)$, et $(p,q) \sim (r,s)$ : on montre facilement que $(m,n)\sim (r,s)$, en multipliant la première relation par une variable qui va nous permettre d’utiliser la deuxième.

L’addition et la multiplication sont définies de manière traditionnelle.

  • Structure d’anneau immédiate
  • Corps : tout $(m,n)$ tq $m\neq 0$ est inversible, et d’inverse $(n,m)$.

EX 5 : équivalence de Nerode

$𝒜 ≝ (Q, 𝛴, 𝛿, i_0, F)$

a) $𝒜_{\sim} ≝ (Q/\sim, 𝛴, 𝛿_{\sim}, C(i_0), F/\sim)$ : l’automate est bien complet, car s’il existait un chemin bloquant, ce chemin serait aussi bloquant pour $𝒜$ (impossible, car complet), et bien déterministe, car deux représentants d’une même classe, s’envoient, par $𝛿$, dans une même autre classe.

  • $𝛿_{\sim}(C,a) = C(𝛿(p,a))$ a bien un sens, car :
    • $∀ q, p ∈ C, 𝛿(p,a) \sim 𝛿(q,a)$, d’où $∀ q, p ∈ C, C(𝛿(p,a)) = C(𝛿(p,a))$

b)

  • $L(𝒜) \supset L(𝒜_{\sim})$ (clairement, car les classes sont non vides)
  • Pour tout mot $w$, $w ∈ L(𝒜_{\sim})$ ssi il existe un chemin qu’il étiquète de $C(i_0)$ dans $C(F)$ ssi il existe un chemin qu’il étiquète d’un état initial dans un état final ssi $w ∈ L(𝒜)$

2) a) trivial. b) Mq qu’il existe un entier $n$ tq : \(∀p, ∈Q, p\sim_n q ⟹ p\sim_{n+1} q\) Pour $n$ le nombre d’états de $Q$, par le pumping lemma. c)

M1 : Il y a $𝜋(n)$ (nombre de Bell) relations d’équivalence sur $Q$, donc deux sont nécessairement égales par le lemme des tiroirs.

M2 :

la fonction qui à $n$ associe $\sim_n$ est à valeurs dans l’ensemble fini ${0,1}^{Q\times Q}$.

EX 6

$E$, dans les deux cas puisque \(∀x∈E, ∀y ∈ ∅, x≤y\) et
\(∀x∈E, ∀y ∈ ∅, x≥y\)

EX 7

\[Successeur(\overline{a_1 ⋯ a_n}) = \begin{cases} \overline{a_1 ⋯ a_{i-1} \bar{a_i} ⋯ \bar{a_n}} \text{, où $a_i$ est le premier chiffre (en partant de la droite) égal à $0$, si } \overline{a_1 ⋯ a_n} \neq \overline{1 ⋯ 1} \\ \overline{1 0 ⋯ 0} \text{ sinon} \end{cases}\]

EX 8

1)

a) Pour tout $k ∈ ⟦0, \lfloor n/2 \rfloor - 1⟧$, mq :

\[\binom{n}{k} < \binom{n}{k+1}\]

Preuve : $n(n-1)⋯(n-k+1)\times (k+1)! < n(n-1)⋯(n-k)\times k!$, car \((k+1) < (n-k)\) (en divisant par $n(n-1)⋯(n-k+1)\times k!$).

Les autres inégalités viennent de : \(\binom{n}{k} = \binom{n}{n-k}\)

b) Les $𝒫_k(X)$, puisque toute inclusion impliquerait l’égalité (cardinal égal).

3)

a)

On pose $X ≝ {x_i}_{i∈⟦1,n⟧}$

À toute permutation $𝜎∈𝕾(X)$, on associe de manière bi-univoque la chaîne \(X_0 ≝ ∅ ⊊ X_1 ≝ \{𝜎(x_1)\} ⊊ X_2 ≝ \{𝜎(x_1), 𝜎(x_2)\} ⋯ ⊊ X_n ≝ \{𝜎(x_1), 𝜎(x_2), ⋯, 𝜎(x_n)\}\)

b) Idem : les $X_0, ⋯, X_s$ ont des éléments de $S$, les $X_{s+1}, ⋯, X_n$ ont des éléments de $S^c$ (et on fait l’union, pour tous, avec $X_s$)

c) On note $E_{cc}$ l’ensemble des chaînes croissantes :

\[E_{cc} \supset \bigsqcup\limits_{k=0}^n \bigsqcup\limits_{P ∈ A; \vert P\vert = k} \{X_0 ≝ ∅ ⊊ X_1 ⋯ ⊊ X_n = E; X_k = P\}\]

Les unions sont disjointes, car il y a au plus un $X_i$ dans $A$.

\[\begin{align*} n! = \vert E_{cc}\vert &≥ \sum\limits_{k=0}^n \sum\limits_{P ∈ A; \vert P\vert = k} k! (n-k)! \\ &≥ \sum\limits_{k=0}^n a_k k! (n-k)! \\ \end{align*}\]

Donc \(1 ≥ \sum\limits_{k=0}^n a_k \frac{1}{\binom{n}{k}}\)

5) On utilise les minorations de la question 1, puis, on trouve : \(\sum_k a_k ≤ \binom{n}{\lfloor n/2 \rfloor}\)

a) Regarder ${(n-k, n+k), k ≤ n}$.

b) Soit $U_i = (x_i, y_i)$ une suite de $ℕ^2$, mq ${U_i}_i$ n’est pas une antichaîne.

  • Cas 1 : Si ${x_i, i∈ℕ}$ est fini, par le lemme des tiroirs : $x_i = x_j$, et $U_i, U_j$ sont comparables.
  • Cas 2 : Sinon, on peut extraire un sous-suite $(x_{𝜑(i)})$ strictement croissante. Pour que $U_i$ soit une antichaîne, il faut que $(y_{𝜑(i)})$ soit str. décroissante : impossible.

6) Expression rationnelle : $b\sum_i a^i b$

Leave a comment