Pourquoi la diagonalisation ne nécessite-t-elle pas de prendre une limite?

Question

Lorsque nous quantifions les sommes infinies, nous le faisons en prenant la limite comme $ i $ va à l'infini.Par exemple, nous examinons $ \ lim_ {n \ rightarrow \ infty} \ sum_ {n \ in \ mathbb {n}} n $ , puis nous disons queCela diverge et n'a pas de somme.

Lorsque nous effectuons une diagonalisation, nous iTerons une liste infinie tout en indexant chaque élément de liste par un nombre naturel, puis parlez du résultat.Pourquoi pouvons-nous faire cela au lieu de devoir invoquer des limites?

De la même manière, cela irait bien d'affecter une valeur à $ \ sum_ {n \ in \ mathbb {n}} n $ avec la valeur étantune séquence infinie?

Answer 1

Certaines arguments de la diagonalisation peuvent nécessiter des limites pour pouvoir clouer tous les détails (par exemple, s'ils impliquent une somme infinie, ou une expansion décimale infinie, qui est officiellement une somme convergente infinie d'un certains types), mais ils ne nécessitent pas de limites en général.

L'argument de la diagonalisation la plus populaire prouve que $ | \ mathbb {n} | \ neq | \ mathbb {r} | $ . En fonction de la façon dont vous avez vu cela, résoudre certains des détails pourrait finir pour nécessiter des limites en raison de la nature de $ \ mathbb {r} $ . Voyons donc un exemple énormément discret de la diagonalisation à la place:

THEOREM $ | \ MATHBB {N} | \ neq | \ {0, 1 \} ^ \ mathbb {n} | $

nous prenons $ \ {0, 1 \} ^ \ mathbb {n} $ Pour être l'ensemble de toutes les séquences infinies de celles et de zéros (vous pouvez aussi Pensez-y comme l'espace de fonction $ \ mathbb {n} \ to \ {0,1 \} $ ). Donc, par exemple, nous pourrions avoir les séquences $ a= (0, 1, 0, 1, 0, 1, 0, 1, \ CDOTS) $ tel que < SPAN CLASS="MATH-CONTAINER"> $ A_ {2I}= 0 $ et $ a_ {2i + 1}= 1 $

Comme il s'agit d'un argument de la diagonalisation, nous procédons par contradiction. Nous supposons d'abord qu'il est possible d'énumérer tous les éléments de $ \ {0, 1 \} ^ \ mathbb n $ via une fonction $ F $ , de sorte que pour tous $ i \ geq 0 $ , $ f (i) $ est une séquence infinie de 0 et 1s.

Nous construirons une séquence infinie explicite qui ne s'affiche pas dans l'image de $ f $ , ce qui prouve qu'aucun tel $ f $ peut énumérer toutes les séquences infinies de 0s et 1s, ce qui signifie que $ | \ mathbb n | \ neq | \ {0,1 \} ^ \ mathbb n | $ comme vous le souhaitez:

$$ a_i \ triangleq 1 - f (i) _i $$

Et maintenant, nous pouvons voir immédiatement en construction que pour chaque $ i \ geq 0 $ , $ a \ neq f (i) $ , car si $ a= f (i) $ alors pour tous $ k $ < / span>, $ a_k= f (i) _k $ , mais en particulier pour $ k= i $ Nous avons $ a_i= 1 - f (i) _i \ neq f (i) _i $ . $ \ blacksquare $

---

Cette construction n'implique clairement aucune limite - tous les objets sont discrets. La preuve complète équivalente spécifiquement pour $ \ mathbb r $ peut impliquer une limite ou une preuve de convergence (facile et automatique) pour la construction du nombre réel $ a $ , mais il n'y a rien de particulièrement perspicace à propos de cette étape.