m

F Nous contacter

0

Documents  03F60 | enregistrements trouvés : 10

O
     

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-19-850127-5

Oxford logic guides , 0036

Localisation : Colloque 1er étage (VENI)

analyse constructive # analyse récursive # fondement # logique d'ordre supérieur # mathématique constructive # structure logique # système constructif # théorie de la preuve # théorie des types de logique

03-06 ; 03B15 ; 03F50 ; 03F60 ; 03F65

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 316 p.
ISBN 978-1-4020-0152-9

Synthese library , 0306

Localisation : Colloque 1er étage (VENI)

logique mathatique # analyse non standard # analyse constructive # histoire # philosophie # épistémologie # continuum # mathématique constructive # mathématique non standard

00B25 ; 03-06 ; 03F60 ; 03H05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that $\partial\alpha/\partial\beta = 1$ if and only if $\alpha-\beta$ is nonrandom; $\partial\alpha/\partial\beta>1$ if and only if $\alpha-\beta$ is a random left-c.e. real; and $\partial\alpha/\partial\beta<1$ if and only if $\alpha-\beta$ is a random right-c.e. real.

We extend their results to the d.c.e. reals, which clarifies what is happening. The extension is straightforward. Fix a random left-c.e. real $\Omega$ with approximation $\{\Omega_s\}_{s\in\omega}$. If $\alpha$ is a d.c.e. real with d.c.e. approximation $\{\alpha_s\}_{s\in\omega}$, let
\[
\partial\alpha = \frac{\partial\alpha}{\partial\Omega} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\Omega-\Omega_s}.
\]
As above, the limit exists and is independent of the choice of approximations. Now $\partial\alpha=0$ if and only if $\alpha$ is nonrandom; $\partial\alpha>0$ if and only if $\alpha$ is a random left-c.e. real; and $\partial\alpha<0$ if and only if $\alpha$ is a random right-c.e. real.

As we have telegraphed by our choice of notation, $\partial$ is a derivation on the field of d.c.e. reals. In other words, $\partial$ preserves addition and satisfies the Leibniz law:
\[
\partial(\alpha\beta) = \alpha\,\partial\beta + \beta\,\partial\alpha.
\]
(However, $\partial$ maps outside of the d.c.e. reals, so it does not make them a differential field.) We will see how the properties of $\partial$ encapsulate much of what we know about randomness in the left-c.e. and d.c.e. reals. We also show that if $f\colon\mathbb{R}\rightarrow\mathbb{R}$ is a computable function that is differentiable at $\alpha$, then $\partial f(\alpha) = f'(\alpha)\,\partial\alpha$. This allows us to apply basic identities from calculus, so for example, $\partial\alpha^n = n\alpha^{n-1}\,\partial\alpha$ and $\partial e^\alpha = e^\alpha\,\partial\alpha$. Since $\partial\Omega=1$, we have $\partial e^\Omega = e^\Omega$.

Given a derivation on a field, the elements that it maps to zero also form a field: the $ \textit {field of constants}$. In our case, these are the nonrandom d.c.e. reals. We show that, in fact, the nonrandom d.c.e. reals form a $ \textit {real closed field}$. Note that it was not even known that the nonrandom d.c.e. reals are closed under addition, and indeed, it is easy to prove the convergence of [1] from this fact. In contrast, it has long been known that the nonrandom left-c.e. reals are closed under addition (Demuth [2] and Downey, Hirschfeldt, and Nies [3]). While also nontrivial, this fact seems to be easier to prove. Towards understanding this difference, we show that the real closure of the nonrandom left-c.e. reals is strictly smaller than the field of nonrandom d.c.e. reals. In particular, there are nonrandom d.c.e. reals that cannot be written as the difference of nonrandom left-c.e. reals; despite being nonrandom, they carry some kind of intrinsic randomness.
Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that ...

03D28 ; 03D80 ; 03F60 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics. I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of ...

03D25 ; 03D32 ; 03F60 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 466 p.
ISBN 978-0-387-12173-4

Ergebnisse der mathematik und ihrer grenzgebiete 3 folge , 0006

Localisation : Ouvrage RdC (BEES)

logique mathématique et base # théorie de preuve et mathématique constructive # philosophie mathématique

03F65 ; 00A30 ; 03F50 ; 03F55 ; 03F60

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 149 p.
ISBN 978-0-521-31802-0

London mathematical society lecture note series , 0097

Localisation : Collection 1er étage

analyse constructive # constructibilité # intuitivité # logique mathématiques # logique symbolique # mathématiques constructives # mathématiques intuitives

03E45 ; 03F50 ; 03F55 ; 03F60

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-3-540-50035-3

Perspectives in mathematical logic

Localisation : Ouvrage RdC (Pour)

analyse mathematique # informatique # logique # physique # theorie de la recursion

03D80 ; 03F60 ; 46Nxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 467 p.
ISBN 978-0-19-853158-6

Oxford logic guides

Localisation : Ouvrage RdC (DUMM)

formalisation # logique intuitioniste # mathématique intuitioniste # preuve constructive # suite de choix

03F50 ; 03F55 ; 03F60 ; 03F65

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 350 p.
ISBN 978-0-19-856651-9

Oxford logic guides , 0048

Localisation : Ouvrages RdC (From)

logique # théorie des ensembles # analyse constructive # mathématiques constructives # mathématiques intuitives

03-06 ; 00B25 ; 03F55 ; 03F60 ; 03F65

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- x; 219 p.
ISBN 978-0-88385-777-9

Localisation : Ouvrage RdC (HENL)

nombres réels # nombres complexes # théorie des nombres

03-01 ; 03F60 ; 03H05

... Lire [+]

Z