6
$\begingroup$

The purpose of my question is trying to understand whether, in some cases, we can achieve greater certainty of reasoning (say when dealing with statements about natural numbers, integers or rational numbers) by using countable subsets of reals instead of using reals as a whole. I will try to explain my question in some detail, because otherwise it might seem completely unmotivated (and perhaps not making much sense).

For concreteness, consider a certain countable subset of real numbers $R$, which we might call the set of $r$-numbers (for the lack of a better word). As one specific case, call $A$ the collection of all "arithmetical functions" (functions computable using some $0^{(n)}$ oracle for some finite ordinal $n$). Some functions within $A$ are accepted as members of the set $R$ (the collection of $r$-numbers). Let's just briefly decide the format when a given function $f:\mathbb{N} \rightarrow \mathbb{N}$ is accepted as an $r$-number:

$\\f(0) \le 1$ (interpreted as sign)

$f(a) \le 9$ when $a \ge 2$ (interpreted as decimal expansion)

Now for $r$-numbers, we define the operations of equality, comparison, addition, subtraction, multiplication and division using appropriate (infinitary) modifications of highschool algorithm. We can also state the "psuedo-completeness" property: "Every non-empty "arithmetical collection" of $r$-numbers, that is bounded above, has a least upper bound which is also an $r$-number." Here a non-empty "arithmetical collection" being defined by a suitable "arithmetical function" of the form $f:\mathbb{N^2} \rightarrow \mathbb{N}$ (each row of the function being interpreted as an $r$-number).


Now it possibly happens often enough that when reasoning about a statement involving naturals,integers or rationals that mathematicians "switch" to some form of reasoning involving continuous objects. After after some reasoning steps, they possibly switch back to the desired result involving naturals, integers or rationals.

Suppose that during some argument (involving $\mathbb{N}$) one switches to real numbers and then back to discrete domain (before completing the argument). My question is, can one give examples where a switch to $\mathbb{R}$ can be "replaced" by a switch to a suitable "countable subset of $\mathbb{R}$" without having to change the argument entirely/substantially. My question is not limited to specific set $R$ I described (it was just meant as an example) .... any bigger countable subset of reals can be used.

P.S. In case the question is received well-enough, I am afraid I am not qualified enough to judge the answers. I can't think of any such examples (possibly due to lack of knowledge or perhaps that finding such examples is little harder).

$\endgroup$
7
$\begingroup$

Suppose that during some argument (involving ℕ) one switches to real numbers and then back to discrete domain (before completing the argument). My question is, can one give examples where a switch to ℝ can be "replaced" by a switch to a suitable "countable subset of ℝ" without having to change the argument entirely/substantially.

A large portion of reverse mathematics consists of doing precisely this (see Simpson's "Subsystems of Second Order Arithmetic"): taking statements which appear to involve the reals (or other equivalent sets, like the power set of the natural numbers) and showing that the same results follow when using only certain axioms about the existence of reals.

Reverse math is usually presented axiomatically, but it's common to think in terms of $\omega$-models: to relate provability in the formal theory $ACA_0$ with those statements which hold when we only use reals which are definable by an arithmetic formula, and so on.

$\endgroup$
9
$\begingroup$

See my paper Analysis in $J_2$, where I explain how core mathematics, particularly abstract analysis, can be developed within a concrete countable set $J_2$ (the second set in Jensen's constructible hierarchy).

$\endgroup$
  • $\begingroup$ Can you highlight/briefly describe a pertinent example? If not, words like "Example 3.2.1.1 on p 56 gives a motivating example B, which is like your A but contained in the complement" might help future readers as well as the original poster. Gerhard "Just Show Me The Spoon" Paseman, 2018.02.19. $\endgroup$ – Gerhard Paseman Feb 19 '18 at 19:05
  • 2
    $\begingroup$ @GerhardPaseman: I'm not sure what you mean by "a pertinent example". My whole paper is about how one can develop a version of core mathematics within $J_2$. Okay, Theorem 3.20 is a $J_2$ version of: a subset of $\mathbb{R}$ is compact iff it is closed and bounded iff it is bounded and closed under convergence of Cauchy sequences iff every sequence has a convergent subsequence. Is that what you're after? I mean the whole paper is a string of such results. $\endgroup$ – Nik Weaver Feb 19 '18 at 20:17
  • $\begingroup$ @NikWeaver While I did not originally mention analysis (I almost included it), the answer is very much in the spirit of my question. Obviously I am not qualified to give any technical comment on this paper of yours (I did read the first few sections in basic detail). Also I read your other essay (for the general reader) introducing your program/philosophy (with some basic parts being more easily understandable than technical ones). I do have some, possibly very naive, observations (in the context of your paper in the answer). I will post them in comments to follow. $\endgroup$ – SSequence Feb 20 '18 at 23:53
  • $\begingroup$ I will follow the terminology in my question. Furthermore I will always use the term "set" in usual/traditional sense (to avoid too much confusion). Consider some countable set $A$ containing functions $f:\mathbb{N} \rightarrow \mathbb{N}$ and similarly consider the corresponding subset of real numbers $R$ (as described in question). Call the numbers in $R$ as $r$-numbers. There are at least three "problems" as I see. Firstly if due to some strong conviction/position one claims that the $r$-numbers actually do represent the reals precisely, then it's fine ..... one can replace (cont.) $\endgroup$ – SSequence Feb 21 '18 at 0:08
  • $\begingroup$ $r$-numbers by real numbers in all claims and be free in their reasoning). But if one's choice of set $A$ is merely taken because of convenience then we have some trouble, because we can't replace $r$-numbers by real numbers in our claims. In this case, we can still freely reason when talking "only" about $r$-numbers. But when we do try to reason about real numbers we will have to be quite careful (and probably very conservative) due to possibility that $\mathbb{R} \supset R$. Secondly clearly there must be some countable ordinal $\alpha$ whose well-order relation isn't contained in $A$ (cont. $\endgroup$ – SSequence Feb 21 '18 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.