3
$\begingroup$

Define a set $S$ as the smallest subset of the set of positive rational numbers satisfying the following rules:

  • (i) $1$ is in $S$

  • (ii) If $a/b$ is in $S$, where the fraction is written in irreducible form (that is, $a$ and $b$ have greatest common divisor 1) then $\frac b{2\cdot a}$ is in $S$ (in other words, $q\in S$ implies $\frac1{2\cdot q}\in S$).

  • (iii) If $a/b$ and $c/d$ are in $S$, where they are written in irreducible form then $(a+c)/(b+d)$ is in $S$.

Can you describe which numbers are in $S$?

Improve this question
$\endgroup$
10
  • $\begingroup$ Sorry in the second condition I wrote a is written in lowest terms it will be ----- a/b is written in the lowest terms $\endgroup$
    – user542993
    Commented Mar 20, 2018 at 10:48
  • 2
    $\begingroup$ Previously posted to (and closed at) m.se, math.stackexchange.com/questions/2692249/… $\endgroup$
    – Gerry Myerson
    Commented Mar 20, 2018 at 11:36
  • 1
    $\begingroup$ Well you don’t get 1/0 and 0/1. However, you get 1/1 and 1/2, and thus using mediants you get the part of the tree between 1/2 and 1/1, i.e., $\mathbb Q\cap[1/2,1]$. And that’s all, by Joel’s observation. $\endgroup$
    – Emil Jeřábek
    Commented Mar 20, 2018 at 12:24
  • 1
    $\begingroup$ By (i), $(-1)/(-1)$ (which is equal to $1/1$) is in $S$. By (iii), it follows that $(1+(-1))/(1+(-1))=0/0$ is in $S$. But $0/0$ does not represent any real number. Therefore there is no set $S$ satisfying your conditions. $\endgroup$
    – Steven Landsburg
    Commented Mar 20, 2018 at 15:53
  • 2
    $\begingroup$ Steven, it would be charitable to interpret the question as insisting, say, that denominators should be positive, in which case $S$ does exist. $\endgroup$
    – Joel David Hamkins
    Commented Mar 20, 2018 at 16:21

4 Answers 4

Reset to default
7
$\begingroup$

It is indeed true that $S=\mathbb{Q}\cap [1/2,1]$. The inclusion $S\subseteq \mathbb{Q}\cap [1/2,1]$ is observed in the answer by Joel David Hamkins. The opposite inclusion $\mathbb{Q}\cap [1/2,1]\subseteq S$ follows from the fact that $\{1/2,1\}\subset S$ and basic properties of Farey sequence.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Isn't this maybe a comment on @JoelDavidHamkins's answer rather than a separate answer? $\endgroup$
    – LSpice
    Commented Mar 22, 2019 at 0:29
  • $\begingroup$ @LSpice possibly. But my general experience is that the comments often remain much less read than the answers, and people proceed thinking on something already written in the comments. $\endgroup$
    – Fedor Petrov
    Commented Mar 22, 2019 at 0:40
  • 3
    $\begingroup$ I think this should remain an answer, not a comment, because it provides the complete answer to the question. $\endgroup$
    – Andreas Blass
    Commented Mar 22, 2019 at 14:16
6
$\begingroup$

To start things off, here is a simple observation: the set $S$ is contained in the rational interval $\mathbb{Q}\cap[\frac 12,1]$, the rational numbers $\frac ab$ where $0<a\leq b\leq 2a$.

The reason is that $1/1$ has this form and your transformations preserve the property of being in this interval. If $a\leq b\leq 2a$, then $b/2a$ obeys the requirement, since $b\leq 2a\leq 2b$. And if $a/b$ and $c/d$ obey the requirement, then so does $(a+c)/(b+d)$, since $a+c\leq b+d\leq 2a+2c=2(a+c)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sir, I do not understand your statement as you said 0<a≤b≤2a. If I take 1/4 from [1/2,1] the inequality is not obeyed $\endgroup$
    – user542993
    Commented Mar 20, 2018 at 15:03
  • $\begingroup$ For positive integers, $a\leq b$ means $\frac ab\leq 1$, and $b\leq 2a$ means $\frac 12\leq \frac ab$. So $0<a\leq b\leq 2a$ is satisfied by exactly the fractions in the interval from $\frac 12$ to $1$. $\endgroup$
    – Joel David Hamkins
    Commented Mar 20, 2018 at 15:09
  • 4
    $\begingroup$ @user542993, note that $1/4$ is not in $[1/2, 1]$. $\endgroup$
    – LSpice
    Commented Mar 22, 2019 at 0:28
1
$\begingroup$

Once you have 1/2, you don't need Rule (ii) anymore. In other words, the problem could read as follows:

The set S contains some real numbers, according to the following three rules.

(i) 1/1 is in S (ii) 1/2 is in S, and (iii) If a/b and c/d are in S, where they are written in the lowest terms then (a+c)/(b+d) is in S.

These rules are exhaustive: if these rules do not imply that a number is in S, then that number is not in S. Can you describe which numbers are in S?

The answer will still be the same: S=Q∩[1/2,1]

Improve this answer
$\endgroup$
0
$\begingroup$

Way-way more is true than stated by the OP's Question (or even the earlier answers).

Let notation $\ a/b\ $ stand for an ordered pair $ a\ $ and $\ b\ $ of non-negative integers that are relatively prime.

Such pairs $\ a/b\ $ are interpreted as positive rational numbers except for the single case of $\ 1/0\ $ that is interpreted as $\ \infty.\ $

Let two such pairs, $\ A/B\ $ and $\ a/b\ $ be called neighbors (in this order!) $\ \Leftarrow:\Rightarrow\ $ their determinant is $\ 1,\ $ i.e. $$ A\cdot b-B\cdot a\ =\ 1. $$

For instance $$ \frac11\quad\frac12 $$ are neighbors.

Let's start with an arbitrary pair of neighbors as the top row of table $\ T(A/B\,\ a/b),\ $ and lets obtain the next rows of the table (in a Pascal triangle manner) by applying the median operation in order to obtain a new row from the last row by:

$$ A/B\quad a/b $$ $$ A/B\quad(A+a)/(B+b)\quad a/b $$ $$ A/B\quad(2\!\cdot\! A+a)/(2\!\cdot\! a+b)\quad(A+a)/(B+b) \quad (A+2\!\cdot\! a)/(B+2\cdot b)\quad a/b $$ etc.

Obviously, each two consecutive elements of arbitrary row of the table are neighbors. The following two basic theorems hold (have you seen the second one in print?):

  • Let $\ X/x\ $ be a pair of relatively prime non-negative integers such that $\ A/a\ge X/x\ge B/b,\ $ i.e. $\ A\cdot x\ge a\cdot X\ $ and $\ X\cdot b\ge x\cdot B.\ $ Then $\ X/x\ $ appears in a row of the table (hence in allm next rows too).

  • Arbitrary pair of neighbors, $\ X/x\quad Y/y\ $, such that $$ A/a\ \ge\ X/x\ >\ Y/y\ \ge\ B/B $$ appears as consecutive elements of a row in the table exactly one time.

Remarks

  • Table $\ T(A/a\,\ B/b)\ $ is a subtable of table $\ T(1/0\,\ 0/1).\ $ This last table represents all non-negative rational numbers as well as $\ \infty:=1/0.$
  • Table $\ T(1/0\,\ 0/1)\ $ corresponds to the general special monoid generated by the two "two by two" 0-1 triangular matrices; it immediately tells you that it is a free monoid in two generators, and it tells you about everything there is about this monoid. Indeed, given a pair of neighbors, the median produces two pairs of neighbors that can be equivalently defined by applying the two triangular matrices to the given pair of neighbors. (I am not able to recall the name of the author of table $\ T(1/\, 0/1).\ $ I seem to remember that this name was mentioned in a small monograph by Knuth)
  • Table $\ T(1/0\,\ 0/1)\ $ may serve as a foundation for the elementary diophantine (rather better than the otherwise impressive Farey sequence) -- this table is in a simple way directly related to the continued fractions.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .