Je ne sais pas si je pollue le fil en proposant une idée pour le problème 500 mais j'envisage (sans preuve) de répondre par la négative
avec cet exemple :
Je considère un cercle avec la réunion des éléments de l'ensemble $A\cup B$ où $A$ est l'ensemble des droites passant le centre du cercle
et formant un angle $2\pi\alpha$ avec l'axe réel où $\alpha$ est un rationnel et où $B$ est l'ensemble des droites tangentes au cercle en ses points qui ne sont pas
dans un élément de $A$.
Ce n'est qu'une intuition mais je dirais que cette réunion est d’intérieur vide et bien sûr, par construction, elle contient le cercle.
Bien vu Georges Abitbol. Il suffit de faire l'induction jusqu'au premier ordinal non dénombrable.
J'explicite le lemme et je fais remarquer qu'il est possible de le démontrer sans induction ordinale:
Si $A \subseteq \R^X$ est une sous $\R$-algèbre et si $B$ est le plus petit sous-ensemble de $\R^X$ stable par limite simple alors $B$ est également une sous $\R$-algèbre de $\R^X$ (indication: soit $x \in \R^X$, posons $A_x:=\{t \in \R^X|t+x \in B\}$. Si $x \in A$ alors $A_x$ est stable par limite simple et contient $A$, donc $B \subseteq A_x$. Si $y \in B$, par ce qui précède $A \subseteq A_y$ et donc $B \subseteq A_y$, finalement $B$ est stable par somme. Les autres axiomes de $\R$-algèbre sont vérifiés de la même façon. Le lecteur familier de la preuve habituelle du lemme de classe monotone reconnaitra l'idée qui est similaire, le résultat de l'exo en est une version "fonctionnelle").
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Ah ouiii, je reconnais l'idée cette démonstration ! C'est aussi un peu la même idée pour démontrer que si $A$ et $B$ sont deux ensembles de parties, alors $\sigma\left(\{a \times b \mbox{ }\vert \mbox{ } a \in A \mbox{ et } b \in B\}\right) = \sigma(A) \otimes \sigma(B)$, je trouve !
Au sujet de "ma" récurrence transfinie, pourquoi ça se stabiliserait dès le premier ordinal non dénombrable ? Un ami (merci Seirios !) a démontré que c'est stationnaire à partir d'un ordinal de cardinal plus grand que celui de $\mathbb{R}^X$. En effet, ça ferait une "suite" (indexée par l'ordinal en question) de parties de $\mathcal{P}(\mathbb{R}^X)$ strictement croissante, ce qui contredirait l'hypothèse sur le cardinal.
@Georges Abitbol: soit $A_{\emptyset}:= A \subseteq \R^X, A_{\alpha}=\bigcup_{\beta<\alpha} A_{\beta}$ si $\alpha$ est un ordinal limite non vide, et $A_{\alpha+1}$ l'ensemble des limites simples de suites d'éléments de $A_{\alpha}$. Soit $\omega_1$ le premier ordinal non dénombrable et $(x_n)_{n \in \N} \in A_{\omega_1}^{\N}$ convergeant simplement vers $x$. Il existe pour tout $n \in \N$, $\alpha_n \in \omega_1$ tel que $x_n \in A_{\alpha_n}$ et pour une telle suite, soit $\beta\in \omega_1$ un majorant de $\{\alpha_n|n \in \N\}$ (car toute partie dénombrable de $\omega_1$ est majorée). Alors $\forall n \in \N, x_n \in A_{\beta}$ et donc $x\in A_{\beta+1} \subseteq A_{\omega_1}$.
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Ah oui, ok, il me manquait cette propriété de $\omega_1$. Merci pour toutes ces précisions !
EDIT : Et pour la c), je propose : Si $C$ est une partie fermée de $X$, on note $C_n$ la réunion des boules de rayon $\frac{1}{n}$ autour de points de $C$. Si $x\in X$, on note $f_n(x) := \frac{d_{C^c_n(x)}}{d_C(x) + d_{C^c_n}(x)}$. La limite simple de la suite $(f_n)_n$ est $1_C$, et donc on se ramène à la question précédente. La réponse est qu'on obtient l'ensemble des fonctions boréliennes sur $X$.
Je profite de ce qu'on m'offre des numéros de questions gratuits pour proposer un exo qui en plus d'apporter une distraction estivale, a la prétention incroyable d'initier le lecteur à certains théorèmes d'indécidabilité :-D.
Soit $E$ un ensemble, $D \subseteq E^2$, $\Phi$ une application de $E$ dans $D$. Soit $\equiv$ une relation d'équivalence sur $E$. Si $x \in E$ on note $Dom(x):= \{y \in E|(x,y) \in D \}$ et $\Phi_x: y \in D \mapsto \Phi(x,y) \in E$ (en gros les éléments de $E$ sont assimilés, via $\Phi$, à des fonctions partielles).
On suppose que pour tout $x \in E$ il existe $x^* \in E$ tel que $Dom(x^*)=E$ et tel que pour tout $y \in E$, si $y \in Dom(y)$ et si $\Phi(y,y) \in Dom(x)$, alors $\Phi \left [x,\Phi(y,y) \right] \equiv \Phi(x^*,y)$.
Question 692:(édité)(théorème de point fixe) Montrer que pour tout $x \in E$ tel que $Dom(x)=E$, il existe $e \in E$ tel que $\Phi(x,e) \equiv e$.
Question 693: On suppose dans cette question que
(a) pour tous $x,y$ on a $x\equiv y$ si et seulement si $\Phi_x=\Phi_y$ .
(b) pour tous $x,y$ il existe $z$ tel que $\Phi_x \circ \Phi_y=\Phi_z$
(c) pour tous $x_1,x_2,y_1,y_2 \in E$ avec $x_1 \neq x_2$, il existe $a \in E$ tel que $Dom(a)=E$, $\Phi_a(x_1)=y_1$ et $\Phi_a(x_2)=y_2$.
1°) Soient $(\mathfrak v,\mathfrak f)\in E^2$, $r \in E$ tel que $Dom(r)=E, \Phi_r(E) \subseteq \{\frak v,f\}$ et tel que pour tous $v,w \in E$, $v \equiv w \implies \Phi_r(v)=\Phi_r(w)$. Montrer que $\Phi_r$ est constante (théorème de Rice).
2°) (ajout) (édité) soient $x,y,t \in E$ tels que $t \in Dom(y) \backslash Dom(x)$, déduire de 1° qu'il n'existe pas $h\in E$ tel que $Dom(h)=E, \Phi_h(E)=\{\frak v,f\}$, et $\forall z \in E, \Phi_h (z)=\mathfrak v \iff t \in Dom(z)$ (théorème de l'arrêt).
Indications en blanc:
692: considérer $\Phi(x^*,x^*)$
693-1°: Si $\Phi(r,x)=\frak v$ et $\Phi(r,y)=\frak f\neq v$, soit $w\in E$ tel que $Dom(w)=E$, $w(\mathfrak f)=x$, $w(\mathfrak v)=y$,et soit $t \in E$ tel que $\Phi_t=\Phi_w \circ \Phi_r$. Considérer $e\in E$ tel que $te \equiv e$ .
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Les hypothèses et notations sont celles de l'en-tête du post précédent (notamment la conclusion de 692 est vraie ici). $E$ est cette fois un ensemble de "phrases". On suppose qu'il y a des applications $\neg$ de $E$ dans $E$ et $\to$ de $E^2$ dans $E$. Soit $\mathfrak P\subseteq E$ (ensemble des "phrases prouvables")vérifiant, pour tous $x, y\in E^2$, $x \equiv y$ si et seulement si $x\to y\in \frak P$ et $y \to x \in \frak P$. On suppose aussi que pour tous $x,y \in E^2$ , si $x$ et $x\to y$ sont dans $\frak P$ alors $y\in \frak P$ (cela entraîne que $\frak P$ est saturé pour $\equiv$, i.e pour tous $x,y$ tels que $x \equiv y$, si $x$ est dans $\frak P$ alors $y$ aussi ).
On suppose également que pour tous $x,y \in D$, $Dom(x)=Dom(\neg x)$ et $ \neg \Phi(x,y)\equiv \Phi(\neg x,y)$ (*)
Question 694:
1° Soit $\{\frak V,F\}$ une partition de $E$ en deux ensembles saturés pour $\equiv$, telle que $\frak P \subseteq V$ et telle que pour tout $x \in E$, $x \in \frak V$ si et seulement si $\neg x \in \frak F$. Soit $v \in E$ tel que $Dom(v)=E$ et tel que pour tout $x\in E$, si $x \in \frak V$ alors $\Phi(v,x) \in \frak V$. Montrer qu'il existe $y \in E$ tel que $\Phi(v,y)\in \frak V$ mais tel que $y \in \frak F$. (**)
2° Soit $p \in E$ tel que $Dom(p)=E$ et tel que pour tout $t \in E$, $t \in \frak P$ si et seulement si $\Phi(p,t) \in \frak P$. Montrer qu'il existe $x\in E$ tel que $\neg x$ et $x$ sont tous les deux dans $\frak P$, ou bien tel que ni $\neg x$ ni $x$ ne sont dans $\frak P$ (1er théorème d'incomplétude).
[size=x-small](*) moralement, on se donne une bijection $\#:E \to \N$; $D$ est l'ensemble des $(p,q)$ ou $p$ est une formule du premier ordre sur le langage de l'arithmétique à une seule variable libre et (si $x$ est cette variable libre) $\Phi(p,q)=p[x:=\#q]$.
(**) en gros: il n'existe pas d'élément de $E$ qui exprime convenablement ce qu'est une phrase "vraie" (théorème de Tarski)[/size]
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Comme tu m'as permis de poser des ilestfacile en voici un (dont je ne connais ni le numéro...ni la réponse...)
Dans un ensemble ordonné, un orphelin est un élément qui n'est pas la borne supérieure de deux éléments distincts de lui.
Un patriarche est un élément qui a strictement plus de majorant distincts de lui que de non-majorant.
Existe-t-il un ensemble ordonné fini tel que tout orphelin soit patriarche ?
@lesmathspoinclaires: si c'était vrai on aurait une réponse négative à la version "lattice" de https://fr.wikipedia.org/wiki/Conjecture_des_familles_stables_par_unions .
[size=x-small]:-D
Dire que j'ai failli chercher ce truc d'apparence toute simple alors que j'ai des choses à faire aujourd'hui et que je ne peux pas me permettre de procrastiner. Ce sera pour plus tard. L'énoncé plus haut est un problème ouvert depuis 1979.[/size]
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
voici la question dont je t'ai parlé mercredi , Christophe
Soit $A$ une matrice carrée^$n\times n$, réelle à coéfficient positifs, et soit $A^*$ la matrice définie par $A^*_{i,j}=0^{A_{j,i}}$ avec la convention $0^0=1$.
1)Montrer que si $A^*$ est inversible alors il existe $P$ et $Q$ matrice de permutation et $T$ matrice trigonale supérieure, tel que
$(AA^*)^*=PTQ$
2)montrer qu'on a alors que si $T_{i,j}=e_i^t.T.e_j=1$ alors on a $T(e_j)-T(e_i)\in \mathbb R_{+}^n$
@ christophe et foysnc : je le mets ici, car ça a un rapport avec la question précédente et en même temps, la matrice $A^*$ rappelle le "dual" que cc avait défini dans le post où il parlait de degrés ludique du point de vue catégorique.
question 707 : soit f continue de IR dans IR on suppose que pour tout reel w: si f(w) n'est pas egale a w^2 alors f est derivable en w et f'(w)=2w. Peut on en deduire que f est la fonction carree?
remarque: issue d'un fil recent.
MERCI A SIMEON!
EDIT on suppose aussi f(0)=0
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Pour la question 707, on pose $g(w)=f(w)-w^2$. Donc, pour tout $w$, si $g(w)\neq 0$, $g$ est dérivable en $w$ et $g'(w)=0$. Si $g(w) \neq 0$, $g(x)$ différent de $0$ au voisinage d'un tel $w$, donc aussi $g'(x)=0$. Donc $g$ est constante au voisinage de $w$ (si $g(w) \neq 0$). Si il existe un $w$ tel que $g(w)=c\neq 0$, alors $g^{-1}(\{c\})$ est fermé et aussi ouvert car $g$ localement constante sur $g^{-1}(\{c\})$. Donc $g^{-1}(\{c\})= \R$ et donc $g(0)=c\neq 0$. Contradiction. Donc il n'existe pas de $w$ tel que $g(w) \neq 0$. Donc $g=0$ et $f(w)=w^2$ pour tout $w$.
Merci et bravo Marco. Pour donner un petit air lycée à une solution on peut rédiger autrement mais c'est le même argument de fond. Je laisse les très improbables lycéens ou jeunes étudiants qui passeront par là s'y essayer.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Question 709: on considère que $\R$ comme un ev sur $\Q$. Existe-t-il un borélien négligeable $A$ tel que $A+A+A=\R$ et $A+A$ négligeable?
Question 710: on dit qu'une partie $X$ de $\R$ est bleue quand pour toute application borélienne $f: \R\to \R$ l'image réciproque $f^{-1} (X)$ est Lebesgue-mesurable. Est-ce que forcément la somme de deux parties bleues est bleue?
Question 711: existe-t-il $f$ une application continue de $\R^2$ dans $\R$ vérifiant la conjonction des conditions suivantes?
711.1/ pour tout $x\in \R$, les fonctions $y\mapsto f(x,y)$ et $y\mapsto f(y,x)$ sont surjectives
711.2/ Pour toutes parties négligeables $A,B$, l'image directe de $A\times B$ par $f$ est négligeable
négligeable abrège Lebesgue négligeable
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Question 712: on garde le cadre de la question 709. On note $T_0$ la topologie usuelle de $\R$ et pour chaque entier $n$, l'ensemble des parties de $\R$ qui sont ou bien réunions dénombrables ou complémentaire d'éléments de $T_n$.
Quel est le plus petit $n$ qui contient deux sev $A,B$ négligeables du $\Q$-ev $\R$ tels que $A+B= \R$?
(à vue de nez, je dirais 4 ou 5, mais c'est très bâclée comme conviction)
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Pour la 712, en regardant de près, il me semble avoir n=3.
Question 713:soit A un SEV borélien du Q ev IR tel que pour tout SEV borélien B négligeable, A+B est négligeable. A-t-on alors forcément que A est dénombrable?
edit, j'avais écrit X à la place de B, merci à Zéphir pour la correction
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Pourquoi préciser (dans la 709) qu'on considère $\R$ comme un $\Q$-espace vectoriel ?
(est-ce encore pour montrer qu'on peut jeter des trucs à la poubelles ?)
Avec $A$ l'ensemble des réels tels que seulement 0 et 1 apparaissent dans l'écriture en base 3 ça devrait marcher.
Bonsoir Christophe,
Dans la question 713 qui est $B$ ?
La règle de relecture avant envoie s'applique à tous, même aux génie que tu es.
A bon entendeur...
@PE: merci de numéroter les questions, comme ça quand des gens répondent, même 6 mois plus tard, ils peuvent désigner le numéro. Disons que ta question est la numéro 715
Et pour info, la réponse est oui, mais l'usage est de préciser l'ensemble de base (la façon dont on en représente les éléments dans l'ordi) parce que la récursivité est une notion informatique
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Ok, je détaille un peu : 715 : On prend comme fonction de base sur $\Q(\sqrt{2})$ l'addition, multiplication, l'inverse, l'opposé, la partie entière, la fonction identité et les fonctions constantes. On note $f : \Q(\sqrt{2}) \rightarrow \Q$ tel que $\forall a,b\in \Q, f(a+b\sqrt{2})=a$.
a/La fonction $f$ est-elle récursive primitive ? b/Si non, la fonction $f$ est-elle récursive ?
Concernant la 715, @PE: ça ne va toujours pas. On ne fait pas d'informatique en parlant des éléments de $E:=\Q[\sqrt{2}]$. Les éléments de cet ensemble ne sont pas des entités syntaxiques simples et ta question est mal posée. Par exemple, si tu décrètes qu'un élément de $E$ est nommé par un couple $(a,b)\in \Q^2$, alors $f$ n'est rien d'autre que la première projection (la fonction abscisse qu'on dit chez les zenfants). Or ce n'est probablement ce que tu VEUX demander.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
718: il existe des sous-corps de $\C$ denses isomorphes à $\C$ (utiliser des bases de transcendance et le fait que deux corps algébriquement clos de caractéristique nulle et de cardinal $>card(\N)$ égaux sont isomorphes).
Pour régler le cas de $\R$ j'ai besoin de résultats sur le corps des $p$-adiques $\Q_p$.
Soit $K$ une clôture algébrique de $\Q_p$. Il existe sur $K$ une seule valeur absolue prolongeant celle de $\Q_p$ et $K$ n'est pas complet pour cette valeur absolue. On note $\C_p$ le complété de $K$ pour cette valeur absolue: c'est aussi un corps algébriquement clos et on peut montrer que $\C_p$ et $K$ sont isomorphes algébriquement à $\C$ par le même argument de cardinalité. Soit $F$ l'image de $\R$ dans $K$ par un tel morphisme. Alors $F$ n'est pas complet (sinon $K=F\oplus \sqrt{-1} F$ le serait aussi. En fait il s'avère que l'équivalence des normes en dimension finie est vraie pour des ev sur corps munis de valeurs absolues, complets). Donc $F \neq \overline F$ dans $\C_p$.
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
@CC : non, car l'ensemble des fonctions récursives primitives avec comme fonction de base certaines fonctions cela à un sens.
C'est l'ensemble des fonctions, stable par composition et par : si $f,g$ récursives primitives et $g$ à image dans $\N^*$, alors $(x,y)\rightarrow f^{g(x)}(y)$ est une fonction récursive primitive.
La question étant, puis-je reconstruire la projection à l'aide de cette famille de fonction.
Je te laisse le soin de deviner pour le cas de récursive.
Merci à toi foys pour la 718. GBZM avait déjà signalé le cas des corps algébriquement clos dans le fil concerné. Tu as ajouté le cas $\mathbb{R}$.
@PE : ça ne va toujours pas, essaie de formuler une 715 praticable, car pour l'instant ce que tu racontes n'a pas de pertinence au regard de la calculabilité (ou manque de précision si tu penses à quelque chose que tu ne dis pas).
Je pose cette question tout en sachant que la réponse est bien connue en théorie des ensembles, mais ma mémoire est de plus en plus à trous avec les medocs et de toute façon, ça ne lui fait pas de mal de figurer dans ce fil, ça en excitera peut-être quelques uns (de mémoire, il me semble que cet exercice est .. "facile" et sans background).
Existe-t-il un entier $n$ et un ensemble $A$ de parties de $\N$ qui n'est pas dénombrable et vérifie que pour tous éléments différents $X,Y$ de $A: card(X\cap Y) \leq n$?
Remarque, c'est un exercice très simple, et qui peut être rédigé très élégamment (sans lourdeur, calcul, ou cabalisitique et sans qu'aucun lecteur ne peine à lire et adhérer) que de prouver la chose suivante:
il existe une partie $A$ de $P(\N)$ telle que:
1) $card(A)=card(\R)$
2) Pour tous éléments différents $X,Y$ de $A: X\cap Y$ est fini
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Et non, si le terme récursive primitive ne te va pas, tu n'as qu'a dire le plus petit ensemble contenant les fonctions de bases (dont j'ai parlées) et stables par les opérations que j'ai précisées.
Pour récursives, ce sont les fonctions que l'on peut construire avec les instructions de bases (la boucle conditionnelle (while), l'instruction sous condition (if), conjonction disjonction négation (and, or, not )), et avec le =, et les opérations de bases sur un corps, et avec autant de mémoire (fini) que souhaitée, ces fonctions étant définies partout, c'est à dire sans boucle infini.
@PE: puisque tu t'entêtes à ne pas comprendre (en prenant même un ton docte :-D ce qui ajoute à ton charme), on va imposer spécialement pour toi***que $<<f$ est récursive (resp récursive primitive)$>>$ est par convention vrai seulement s'il existe un entier naturel $n>0$ tel que $f$ est une fonction partielle de $\N^n$ dans $\N$. Ca évitera d'avoir à se répéter. Tu as produit 3 posts dans ce fil (qui n'y est pas habitué :-D ) sans jamais avoir lu que ce que je te demandais de corriger étaient les ensembles de départ et d'arrivée.
Si tu souhaites reformuler ta 715 sans utiliser les mots réservés de la logique, tu peux, mais dans ce cas trouve une définition qui n'est pas vérifiée par l'ensemble vide comme l'est ta tentative de gloubiboulga des posts précédents (dont on ne sait pas si le n+1 ième** annule le n ième par ailleurs).
*** Quand on a affaire à des lecteurs "habituels" et un peu pro (ou un peu honnêtes intellectuellement), ils se dépêchent bien vite de retraduire tout de manière à avoir des ensembles d'entiers sans l'exiger du poseur de question qui lui-même a pris soin de ne pas balancer un truc problématique.
** tu parles de $x^y$ et quelques lignes plus loin demande que ça s'applique à $\Q[\sqrt{2}], etc
PS: merci de ne pas te défendre dans ce fil, je ne t'attaque pas, même si c'est un peu un ton lassé que j'utilise, dans ce cas pardon. J'essaie juste de maintenir à ce fil un paradigme de haute précision et formelle-tude des questions posées. Ce n'est pas forcément avec la même exigence de formalisme que j'aborde les autres fils. Par exemple, je ne t'embêterai pas dans un autre fil sur cette question 715, mais ici, ça m'ennuie (pour l'heure ceux qui te répondront seront obligés de la formuler avant d'y répondre, et je voudrais que ça n'ait pas à être nécessaire).
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Réponses
avec cet exemple :
Je considère un cercle avec la réunion des éléments de l'ensemble $A\cup B$ où $A$ est l'ensemble des droites passant le centre du cercle
et formant un angle $2\pi\alpha$ avec l'axe réel où $\alpha$ est un rationnel et où $B$ est l'ensemble des droites tangentes au cercle en ses points qui ne sont pas
dans un élément de $A$.
Ce n'est qu'une intuition mais je dirais que cette réunion est d’intérieur vide et bien sûr, par construction, elle contient le cercle.
Okay, mon idée n'est donc pas la plus courte, après, je serais intéressé de savoir si ma construction fonctionne quand même ou non
si cependant quelqu’un était en mesure de me le dire.
J'explicite le lemme et je fais remarquer qu'il est possible de le démontrer sans induction ordinale:
Si $A \subseteq \R^X$ est une sous $\R$-algèbre et si $B$ est le plus petit sous-ensemble de $\R^X$ stable par limite simple alors $B$ est également une sous $\R$-algèbre de $\R^X$ (indication: soit $x \in \R^X$, posons $A_x:=\{t \in \R^X|t+x \in B\}$. Si $x \in A$ alors $A_x$ est stable par limite simple et contient $A$, donc $B \subseteq A_x$. Si $y \in B$, par ce qui précède $A \subseteq A_y$ et donc $B \subseteq A_y$, finalement $B$ est stable par somme. Les autres axiomes de $\R$-algèbre sont vérifiés de la même façon. Le lecteur familier de la preuve habituelle du lemme de classe monotone reconnaitra l'idée qui est similaire, le résultat de l'exo en est une version "fonctionnelle").
Au sujet de "ma" récurrence transfinie, pourquoi ça se stabiliserait dès le premier ordinal non dénombrable ? Un ami (merci Seirios !) a démontré que c'est stationnaire à partir d'un ordinal de cardinal plus grand que celui de $\mathbb{R}^X$. En effet, ça ferait une "suite" (indexée par l'ordinal en question) de parties de $\mathcal{P}(\mathbb{R}^X)$ strictement croissante, ce qui contredirait l'hypothèse sur le cardinal.
EDIT : Et pour la c), je propose :
Si $C$ est une partie fermée de $X$, on note $C_n$ la réunion des boules de rayon $\frac{1}{n}$ autour de points de $C$. Si $x\in X$, on note $f_n(x) := \frac{d_{C^c_n(x)}}{d_C(x) + d_{C^c_n}(x)}$. La limite simple de la suite $(f_n)_n$ est $1_C$, et donc on se ramène à la question précédente. La réponse est qu'on obtient l'ensemble des fonctions boréliennes sur $X$.
[large]
Soit $E$ un ensemble, $D \subseteq E^2$, $\Phi$ une application de $E$ dans $D$. Soit $\equiv$ une relation d'équivalence sur $E$. Si $x \in E$ on note $Dom(x):= \{y \in E|(x,y) \in D \}$ et $\Phi_x: y \in D \mapsto \Phi(x,y) \in E$ (en gros les éléments de $E$ sont assimilés, via $\Phi$, à des fonctions partielles).
On suppose que pour tout $x \in E$ il existe $x^* \in E$ tel que $Dom(x^*)=E$ et tel que pour tout $y \in E$, si $y \in Dom(y)$ et si $\Phi(y,y) \in Dom(x)$, alors $\Phi \left [x,\Phi(y,y) \right] \equiv \Phi(x^*,y)$.
Question 692: (édité)(théorème de point fixe) Montrer que pour tout $x \in E$ tel que $Dom(x)=E$, il existe $e \in E$ tel que $\Phi(x,e) \equiv e$.
Question 693: On suppose dans cette question que
(a) pour tous $x,y$ on a $x\equiv y$ si et seulement si $\Phi_x=\Phi_y$ .
(b) pour tous $x,y$ il existe $z$ tel que $\Phi_x \circ \Phi_y=\Phi_z$
(c) pour tous $x_1,x_2,y_1,y_2 \in E$ avec $x_1 \neq x_2$, il existe $a \in E$ tel que $Dom(a)=E$, $\Phi_a(x_1)=y_1$ et $\Phi_a(x_2)=y_2$.
1°) Soient $(\mathfrak v,\mathfrak f)\in E^2$, $r \in E$ tel que $Dom(r)=E, \Phi_r(E) \subseteq \{\frak v,f\}$ et tel que pour tous $v,w \in E$, $v \equiv w \implies \Phi_r(v)=\Phi_r(w)$. Montrer que $\Phi_r$ est constante (théorème de Rice).
2°) (ajout) (édité) soient $x,y,t \in E$ tels que $t \in Dom(y) \backslash Dom(x)$, déduire de 1° qu'il n'existe pas $h\in E$ tel que $Dom(h)=E, \Phi_h(E)=\{\frak v,f\}$, et $\forall z \in E, \Phi_h (z)=\mathfrak v \iff t \in Dom(z)$ (théorème de l'arrêt).
Indications en blanc:
692: considérer $\Phi(x^*,x^*)$
693-1°: Si $\Phi(r,x)=\frak v$ et $\Phi(r,y)=\frak f\neq v$, soit $w\in E$ tel que $Dom(w)=E$, $w(\mathfrak f)=x$, $w(\mathfrak v)=y$,et soit $t \in E$ tel que $\Phi_t=\Phi_w \circ \Phi_r$. Considérer $e\in E$ tel que $te \equiv e$ .
On suppose également que pour tous $x,y \in D$, $Dom(x)=Dom(\neg x)$ et $ \neg \Phi(x,y)\equiv \Phi(\neg x,y)$ (*)
Question 694:
1° Soit $\{\frak V,F\}$ une partition de $E$ en deux ensembles saturés pour $\equiv$, telle que $\frak P \subseteq V$ et telle que pour tout $x \in E$, $x \in \frak V$ si et seulement si $\neg x \in \frak F$. Soit $v \in E$ tel que $Dom(v)=E$ et tel que pour tout $x\in E$, si $x \in \frak V$ alors $\Phi(v,x) \in \frak V$. Montrer qu'il existe $y \in E$ tel que $\Phi(v,y)\in \frak V$ mais tel que $y \in \frak F$. (**)
2° Soit $p \in E$ tel que $Dom(p)=E$ et tel que pour tout $t \in E$, $t \in \frak P$ si et seulement si $\Phi(p,t) \in \frak P$. Montrer qu'il existe $x\in E$ tel que $\neg x$ et $x$ sont tous les deux dans $\frak P$, ou bien tel que ni $\neg x$ ni $x$ ne sont dans $\frak P$ (1er théorème d'incomplétude).
[size=x-small](*) moralement, on se donne une bijection $\#:E \to \N$; $D$ est l'ensemble des $(p,q)$ ou $p$ est une formule du premier ordre sur le langage de l'arithmétique à une seule variable libre et (si $x$ est cette variable libre) $\Phi(p,q)=p[x:=\#q]$.
(**) en gros: il n'existe pas d'élément de $E$ qui exprime convenablement ce qu'est une phrase "vraie" (théorème de Tarski)[/size]
pour éviter des lettres dans les numéros.
Dans un ensemble ordonné, un orphelin est un élément qui n'est pas la borne supérieure de deux éléments distincts de lui.
Un patriarche est un élément qui a strictement plus de majorant distincts de lui que de non-majorant.
Existe-t-il un ensemble ordonné fini tel que tout orphelin soit patriarche ?
[size=x-small]:-D
Dire que j'ai failli chercher ce truc d'apparence toute simple alors que j'ai des choses à faire aujourd'hui et que je ne peux pas me permettre de procrastiner. Ce sera pour plus tard. L'énoncé plus haut est un problème ouvert depuis 1979.[/size]
[Inutile de recopier le message précédent. AD]
Soit $A$ une matrice carrée^$n\times n$, réelle à coéfficient positifs, et soit $A^*$ la matrice définie par $A^*_{i,j}=0^{A_{j,i}}$ avec la convention $0^0=1$.
1)Montrer que si $A^*$ est inversible alors il existe $P$ et $Q$ matrice de permutation et $T$ matrice trigonale supérieure, tel que
$(AA^*)^*=PTQ$
2)montrer qu'on a alors que si $T_{i,j}=e_i^t.T.e_j=1$ alors on a $T(e_j)-T(e_i)\in \mathbb R_{+}^n$
@ christophe et foysnc : je le mets ici, car ça a un rapport avec la question précédente et en même temps, la matrice $A^*$ rappelle le "dual" que cc avait défini dans le post où il parlait de degrés ludique du point de vue catégorique.
remarque: issue d'un fil recent.
MERCI A SIMEON!
EDIT on suppose aussi f(0)=0
EDIT : trompé, c'est précisé.
Question 710: on dit qu'une partie $X$ de $\R$ est bleue quand pour toute application borélienne $f: \R\to \R$ l'image réciproque $f^{-1} (X)$ est Lebesgue-mesurable. Est-ce que forcément la somme de deux parties bleues est bleue?
Question 711: existe-t-il $f$ une application continue de $\R^2$ dans $\R$ vérifiant la conjonction des conditions suivantes?
711.1/ pour tout $x\in \R$, les fonctions $y\mapsto f(x,y)$ et $y\mapsto f(y,x)$ sont surjectives
711.2/ Pour toutes parties négligeables $A,B$, l'image directe de $A\times B$ par $f$ est négligeable
négligeable abrège Lebesgue négligeable
Quel est le plus petit $n$ qui contient deux sev $A,B$ négligeables du $\Q$-ev $\R$ tels que $A+B= \R$?
(à vue de nez, je dirais 4 ou 5, mais c'est très bâclée comme conviction)
Question 713: soit A un SEV borélien du Q ev IR tel que pour tout SEV borélien B négligeable, A+B est négligeable. A-t-on alors forcément que A est dénombrable?
edit, j'avais écrit X à la place de B, merci à Zéphir pour la correction
(est-ce encore pour montrer qu'on peut jeter des trucs à la poubelles ?)
Avec $A$ l'ensemble des réels tels que seulement 0 et 1 apparaissent dans l'écriture en base 3 ça devrait marcher.
Dans la question 713 qui est $B$ ?
La règle de relecture avant envoie s'applique à tous, même aux génie que tu es.
A bon entendeur...
La fonction $f : \Q(\sqrt{2}) \rightarrow \Q$ tel que $\forall a,b\in \Q, f(a+b\sqrt{2})=a$ est-elle récursive ?
Bonne soirée.
Et pour info, la réponse est oui, mais l'usage est de préciser l'ensemble de base (la façon dont on en représente les éléments dans l'ordi) parce que la récursivité est une notion informatique
Ok, je détaille un peu :
715 : On prend comme fonction de base sur $\Q(\sqrt{2})$ l'addition, multiplication, l'inverse, l'opposé, la partie entière, la fonction identité et les fonctions constantes. On note $f : \Q(\sqrt{2}) \rightarrow \Q$ tel que $\forall a,b\in \Q, f(a+b\sqrt{2})=a$.
a/La fonction $f$ est-elle récursive primitive ?
b/Si non, la fonction $f$ est-elle récursive ?
Bonne journée.
Concernant la 715, @PE: ça ne va toujours pas. On ne fait pas d'informatique en parlant des éléments de $E:=\Q[\sqrt{2}]$. Les éléments de cet ensemble ne sont pas des entités syntaxiques simples et ta question est mal posée. Par exemple, si tu décrètes qu'un élément de $E$ est nommé par un couple $(a,b)\in \Q^2$, alors $f$ n'est rien d'autre que la première projection (la fonction abscisse qu'on dit chez les zenfants). Or ce n'est probablement ce que tu VEUX demander.
Pour régler le cas de $\R$ j'ai besoin de résultats sur le corps des $p$-adiques $\Q_p$.
Soit $K$ une clôture algébrique de $\Q_p$. Il existe sur $K$ une seule valeur absolue prolongeant celle de $\Q_p$ et $K$ n'est pas complet pour cette valeur absolue. On note $\C_p$ le complété de $K$ pour cette valeur absolue: c'est aussi un corps algébriquement clos et on peut montrer que $\C_p$ et $K$ sont isomorphes algébriquement à $\C$ par le même argument de cardinalité. Soit $F$ l'image de $\R$ dans $K$ par un tel morphisme. Alors $F$ n'est pas complet (sinon $K=F\oplus \sqrt{-1} F$ le serait aussi. En fait il s'avère que l'équivalence des normes en dimension finie est vraie pour des ev sur corps munis de valeurs absolues, complets). Donc $F \neq \overline F$ dans $\C_p$.
@CC : non, car l'ensemble des fonctions récursives primitives avec comme fonction de base certaines fonctions cela à un sens.
C'est l'ensemble des fonctions, stable par composition et par : si $f,g$ récursives primitives et $g$ à image dans $\N^*$, alors $(x,y)\rightarrow f^{g(x)}(y)$ est une fonction récursive primitive.
La question étant, puis-je reconstruire la projection à l'aide de cette famille de fonction.
Je te laisse le soin de deviner pour le cas de récursive.
Bonne journée.
Pour 715 : J'ajoute que dans le a/ comme le b/ les fonctions doivent être définies sur $\Q(\sqrt{2})$ entier.
Bonne journée.
@PE : ça ne va toujours pas, essaie de formuler une 715 praticable, car pour l'instant ce que tu racontes n'a pas de pertinence au regard de la calculabilité (ou manque de précision si tu penses à quelque chose que tu ne dis pas).
Je pose cette question tout en sachant que la réponse est bien connue en théorie des ensembles, mais ma mémoire est de plus en plus à trous avec les medocs et de toute façon, ça ne lui fait pas de mal de figurer dans ce fil, ça en excitera peut-être quelques uns (de mémoire, il me semble que cet exercice est .. "facile" et sans background).
Existe-t-il un entier $n$ et un ensemble $A$ de parties de $\N$ qui n'est pas dénombrable et vérifie que pour tous éléments différents $X,Y$ de $A: card(X\cap Y) \leq n$?
Remarque, c'est un exercice très simple, et qui peut être rédigé très élégamment (sans lourdeur, calcul, ou cabalisitique et sans qu'aucun lecteur ne peine à lire et adhérer) que de prouver la chose suivante:
il existe une partie $A$ de $P(\N)$ telle que:
1) $card(A)=card(\R)$
2) Pour tous éléments différents $X,Y$ de $A: X\cap Y$ est fini
Et non, si le terme récursive primitive ne te va pas, tu n'as qu'a dire le plus petit ensemble contenant les fonctions de bases (dont j'ai parlées) et stables par les opérations que j'ai précisées.
Pour récursives, ce sont les fonctions que l'on peut construire avec les instructions de bases (la boucle conditionnelle (while), l'instruction sous condition (if), conjonction disjonction négation (and, or, not )), et avec le =, et les opérations de bases sur un corps, et avec autant de mémoire (fini) que souhaitée, ces fonctions étant définies partout, c'est à dire sans boucle infini.
Bonne soirée.
Si tu souhaites reformuler ta 715 sans utiliser les mots réservés de la logique, tu peux, mais dans ce cas trouve une définition qui n'est pas vérifiée par l'ensemble vide comme l'est ta tentative de gloubiboulga des posts précédents (dont on ne sait pas si le n+1 ième** annule le n ième par ailleurs).
*** Quand on a affaire à des lecteurs "habituels" et un peu pro (ou un peu honnêtes intellectuellement), ils se dépêchent bien vite de retraduire tout de manière à avoir des ensembles d'entiers sans l'exiger du poseur de question qui lui-même a pris soin de ne pas balancer un truc problématique.
** tu parles de $x^y$ et quelques lignes plus loin demande que ça s'applique à $\Q[\sqrt{2}], etc
PS: merci de ne pas te défendre dans ce fil, je ne t'attaque pas, même si c'est un peu un ton lassé que j'utilise, dans ce cas pardon. J'essaie juste de maintenir à ce fil un paradigme de haute précision et formelle-tude des questions posées. Ce n'est pas forcément avec la même exigence de formalisme que j'aborde les autres fils. Par exemple, je ne t'embêterai pas dans un autre fil sur cette question 715, mais ici, ça m'ennuie (pour l'heure ceux qui te répondront seront obligés de la formuler avant d'y répondre, et je voudrais que ça n'ait pas à être nécessaire).