ترغب بنشر مسار تعليمي؟ اضغط هنا

Fusible numbers and Peano Arithmetic

129   0   0.0 ( 0 )
 نشر من قبل Gabriel Nivasch
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Inspired by a mathematical riddle involving fuses, we define the fusible numbers as follows: $0$ is fusible, and whenever $x,y$ are fusible with $|y-x|<1$, the number $(x+y+1)/2$ is also fusible. We prove that the set of fusible numbers, ordered by the usual order on $mathbb R$, is well-ordered, with order type $varepsilon_0$. Furthermore, we prove that the density of the fusible numbers along the real line grows at an incredibly fast rate: Letting $g(n)$ be the largest gap between consecutive fusible numbers in the interval $[n,infty)$, we have $g(n)^{-1} ge F_{varepsilon_0}(n-c)$ for some constant $c$, where $F_alpha$ denotes the fast-growing hierarchy. Finally, we derive some true statements that can be formulated but not proven in Peano Arithmetic, of a different flavor than previously known such statements: PA cannot prove the true statement For every natural number $n$ there exists a smallest fusible number larger than $n$. Also, consider the algorithm $M(x)$: if $x<0$ return $-x$, else return $M(x-M(x-1))/2$. Then $M$ terminates on real inputs, although PA cannot prove the statement $M$ terminates on all natural inputs.

قيم البحث

اقرأ أيضاً

106 - Athar Abdul-Quader 2017
Simpson showed that every countable model $mathcal{M} models mathsf{PA}$ has an expansion $(mathcal{M}, X) models mathsf{PA}^*$ that is pointwise definable. A natural question is whether, in general, one can obtain expansions of a non-prime model in which the definable elements coincide with those of the underlying model. Enayat showed that this is impossible by proving that there is $mathcal{M} models mathsf{PA}$ such that for each undefinable class $X$ of $mathcal{M}$, the expansion $(mathcal{M}, X)$ is pointwise definable. We call models with this property Enayat models. In this paper, we study Enayat models and show that a model of $mathsf{PA}$ is Enayat if it is countable, has no proper cofinal submodels and is a conservative extension of all of its elementary cuts. We then show that, for any countable linear order $gamma$, if there is a model $mathcal{M}$ such that $mathrm{Lt}(mathcal{M}) cong gamma$, then there is an Enayat model $mathcal{M}$ such that $mathrm{Lt}(mathcal{M}) cong gamma$.
155 - Tamas Hausel 2005
A Fourier transform technique is introduced for counting the number of solutions of holomorphic moment map equations over a finite field. This in turn gives information on Betti numbers of holomorphic symplectic quotients. As a consequence simple uni fied proofs are obtained for formulas of Poincare polynomials of toric hyperkahler varieties, Poincare polynomials of Hilbert schemes of points and twisted ADHM spaces of instantons on C^2 and Poincare polynomials of all Nakajima quiver varieties. As an application, a proof of a conjecture of Kac on the number of absolutely indecomposable representations of a quiver is announced.
We study notions of genericity in models of $mathsf{PA}$, inspired by lines of inquiry initiated by Chatzidakis and Pillay and continued by Dolich, Miller and Steinhorn in general model-theoretic contexts. These papers studied the theories obtained b y adding a random predicate to a class of structures. Chatzidakis and Pillay axiomatized the theories obtained in this way. In this article, we look at the subsets of models of $mathsf{PA}$ which satisfy the axiomatization given by Chatzidakis and Pillay; we refer to these subsets in models of $mathsf{PA}$ as CP-generics. We study a more natural property, called strong CP-genericity, which implies CP-genericity. We use an arithmetic version of Cohen forcing to construct (strong) CP-generics with various properties, including ones in which every element of the model is definable in the expansion, and, on the other extreme, ones in which the definable closure relation is unchanged.
185 - James H. Schmerl 2019
If $M prec N$ are models of Peano Arithmetic and Lt$(N/M)$ is the pentagon lattice $N_5$, then $N$ is either a cofinal or an end extension of $M$. In contrast, there are $M prec N$ that are models of PA* (PA in a language with countably many new pred icate symbols) such that Lt$(N/M) cong N_5$ and $N$ is neither a cofinal nor an end extension of $M$.
127 - Fei Wei 2018
To study arithmetic structures of natural numbers, we introduce a notion of entropy of arithmetic functions, called anqie entropy. This entropy possesses some crucial properties common to both Shannons and Kolmogorovs entropies. We show that all arit hmetic functions with zero anqie entropy form a C*-algebra. Its maximal ideal space defines our arithmetic compactification of natural numbers, which is totally disconnected but not extremely disconnected. We also compute the $K$-groups of the space of all continuous functions on the arithmetic compactification. As an application, we show that any topological dynamical system with topological entropy $lambda$, can be approximated by symbolic dynamical systems with entropy less than or equal to $lambda$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا