12
$\begingroup$

EDIT: I posted an answer to this question. Can somone check?

Consider set $T_1,T_2,...T_p$ which are subsets of $\mathbb{Q}$

I want to create a new definition of "size" that distinguishes between subsets of $\mathbb{Q}$ that have "significantly" more elements inside of $\mathbb{Q}$ than other subsets. (Note that I want this size to apply to countably dense and countably finite subsets of $\mathbb{Q}$) .

For example, if we compared rational numbers to integers, we know there are significantly more rationals in rationals than integers in rationals. Morover, there are infinite rationals between every integer, further proving the previous statment.

Unfortunately, formal measures, which assigns a weight for each singleton $\left\{x\right\}$ in $T_p$,

$$\mu(T_p)=\sum_{x \in T_p}\mu(\left\{x\right\})$$

would not be meaningful since assigning zero or positive weight would give subsets of $\mathbb{Q}$ zero or infinite measure. This does not distinguish which of those subsets could have significantly more or less elements inside of $\mathbb{Q}$.

Cardinality is also a problem, since it counts the number of elements, rather than determine which subsets $\mathbb{Q}$ have more elements in $\mathbb{Q}$. Morover, the cardinality of any countably infinite set is infinity.

However, informal measures can be used. For example, the asymptotic density of a subset of $\mathbb{N}$ is the number elements the subset "fills" of natural numbers between $[0,b]$ as $b\to\infty$.

How can we create a new definition of "size" that constructs an informal measure of the subsets of $\mathbb{Q}$ and meets the following requirments?

-If $T_1=T_2$ and $\mu(T_1)=\mu(T_2)$

-If $T_1\subseteq T_2$ then $\mu(T_1) \le \mu(T_2)$

$\endgroup$
  • $\begingroup$ If anyone has ideas let me know. $\endgroup$ – Arbuja Apr 3 '17 at 12:38
  • $\begingroup$ Does the post make sense? $\endgroup$ – Arbuja Apr 3 '17 at 15:15
  • 1
    $\begingroup$ This sounds like a problem that might be an application of numerosity, a concept that extends cardinality but retains the archimedian properties you seek. See sciencedirect.com/science/article/pii/S0001870802000129 or arxiv.org/pdf/1212.6201.pdf $\endgroup$ – Hyperplane May 13 '17 at 14:47
  • $\begingroup$ @Hyperplane I know this too much to ask of you but is numerosity the same as the extending asymptotic density to rationals as mentioned in mine and RossMillikan's answer. $\endgroup$ – Arbuja May 13 '17 at 19:05
  • 1
    $\begingroup$ Sorry I don't know that. Numerosity is something I came across by accident since I dealt with some other work of one of the authors; but I hadn't really looked at it in detail. All I know is that it is based on an ultrafilter construction and claims to achieve some of the properties you seek. $\endgroup$ – Hyperplane May 13 '17 at 19:23
2
$\begingroup$

There is a "natural" extension of the natural density to the rationals, but I am not sure how useful it is. The set of rationals in $[-b,b]$ with denominator less than $b$ is finite, so we can compute the fraction of these rationals that are in $T$ and ask if there is a limit as $b \to \infty$. We want to consider the rationals when expressed in lowest terms. This clearly meets your request that the density of a superset is at least as great as that of a subset and that sets which are negatives of each other get the same density.

There are $\phi(k)$ fractions with denominator $k$ in each unit interval. Wikipedia states that $\sum\limits_{i=1}^b \phi(k) \approx \frac 3{\pi^2}b^2$ so we have about $\frac 6{\pi^2}b^3$ rationals in $[-b,b]$ with denominator $b$ or less.
${}{}{}{}$ It seems one density that would be interesting would be the density of rationals with odd numerators. This is all the ones with even denominators and half of the ones with odd denominators. We need the sum of the totient function over the even numbers to get this, but I haven't found one.

$\endgroup$
  • $\begingroup$ The extension does not satisfy the property $\mu(A)\le\mu(B)$ if $A\subset B$. The simplest counterexample is $A=\left\{\frac{m}{2n+1}\right\}$ and $B=\left\{\frac{m}{4n+2}\right\}$. You would find that the density of $A$ is greater than the density of $B$. $\endgroup$ – Arbuja Dec 25 '17 at 15:49
  • $\begingroup$ The density of $A$ can be found using $\frac{\sum\limits_{i=1}^{\left\lfloor{\frac{b-1}{2}}\right\rfloor}\phi(2i+1)}{\sum\limits_{i=1}^{b}\phi(i)}\approx\frac{\frac{2}{\pi}b^3}{\frac{3}{\pi}b^3}=2/3$ and the density of $B$ can be found using $\frac{\sum\limits_{i=1}^{\left\lfloor{\frac{b-2}{4}}\right\rfloor}\phi(4i+2)}{\sum\limits_{i=1}^{b}\phi(i)}\approx\frac{\frac{1}{2\pi}b^3}{\frac{3}{\pi}b^3}=1/6$. Hence $\mu(A)>\mu(B)$ disproving one of my requirments. $\endgroup$ – Arbuja Dec 25 '17 at 16:04
  • $\begingroup$ The only solution I found was to separate the denominator by divisor 2 to get $2^k(2n+1)$, where $k<r$ and $2n+1<b$, and take the rationals in $[-b,b]$. The number of rationals is $\sum\limits_{k=1}^{r}\sum\limits_{n=1}^{\left\lfloor\frac{b-1}{2}\right\rfloor}\phi(2^k n)\approx\frac{4}{\pi^3}b^3(2^r)$ (using $\phi(cd)=\phi(c)\phi(d)$). We then compute the fractions that are in $T$ as $(r,b)\to\infty$ $\endgroup$ – Arbuja Dec 25 '17 at 16:48
2
$\begingroup$

I strongly recommend that you read Mancosu's article on counting principles, as he reviews the interesting literature that has emerged out of this question. In particular, following the work of Benci and Di Nasso (which is the most promising line of attack), he analyzes the question as being equivalent to the existence of a "numerosity" function $v$ from $S$ (the set of sets to be counted) to $N$ (the set which will be used for counting, typically, in the case of countable sets, $\mathbb{N}$) such that:

(1) If $A, B \in S$ are such that $A \subset B$, then $v(A) < v(B)$; (2) If $v(A) = v(A')$ and $v(B) = v(B')$, then $v(A \sqcup B) = v(A' \sqcup B')$ and $v(A \times B) = v(A' \times B')$ (it preserves disjoint unions and products).

Ideally, we would want it to preserve bijections, but we know that is not compatible with (1) for infinite sets. Nevertheless, there may happen that we are able to impose some other restriction on the bijections to make it work, i.e. something like

(3) If $A \simeq B$ (an isomorphism under an appropriate relation), then $v(A) = v(B)$.

In the second article mentioned above, the authors show that the existence of (an interesting example of) such a function is equivalent to the existence of a certain type of ultrafilter on the natural numbers (Ramsey or selective ultrafilters), which incidentally shows that this question is independent of $\mathsf{ZFC}$. If you're familiar with ultrafilters, their appearance in this context is not very surprising, since they typically give rise to a measure. There are also interesting connections to non-standard analysis which are explored in the article.

$\endgroup$
  • $\begingroup$ I will read into this in more detail but I am unsure how effective this will be on subsets of rational number. Anyways, if you have time can you check my answer. $\endgroup$ – Arbuja May 23 '17 at 1:27
  • $\begingroup$ Hopefully, Numerosity is a generalization of asymptotic density and the answer I found. Otherwise, there will be conflict between both ideas. $\endgroup$ – Arbuja May 23 '17 at 18:26
1
$\begingroup$

The theory of sets asserts that sets of integers and rational numbers are countable sets, that is, they have the same cardinality. At the same time, our experience suggests the opposite:

For example, if we compared rational numbers to integers, we know there are significantly more rationals in rationals than integers in rationals. Moreover, there are infinite rationals between every integer, further proving the previous statement.>

To reconcile the theory with common sense helps the particular case of lemma to the theorem of Matiyasevich on the existence of a one-to-one correspondence $$ \left(\mathbb Z^+\right)^2\leftrightarrow \mathbb Z^+,$$ using the functions $$\begin{cases} z(x,y) = \dfrac12\left((x+y)^2 - x - 3y +2\right)\\ x(z) = z-\dfrac12(s(z)-1)(s(z)-2)\\ y(z) = s(z)-x(z), \end{cases}\tag1$$ where $$s(z) = \left[\sqrt{2z-{7\over4}}-{1\over2}\right] + 2\tag2$$

The functions $(1-2)$ realize the Cantor ordering of the set - by increasing the sum $s=x + y$, and if the sums are equal, by increasing $x$ (see also Wolfram Alfa). Therefore, the Cantor's consequence is $$q_i = \left\{ {1\over1}, {1\over2}, {2\over1}, {1\over3}, {2\over2}, {3\over1}, {1\over4}, {2\over3}, {3\over2}, {4\over1}, {1\over5}, {2\over4}, {3\over3}, {4\over2}, {5\over1}, {1\over6}, {2\over5}, {3\over4}, {4\over3}, {5\over2}, {5\over2},\dots \right\}$$

In my opinion, this order can be used as the "natural" order of positive rational numbers.

For example, natural series displayed in consequence of Cantors indexes $$N_n = {1\over2}\left((n+1)^2 - n - 3 +2\right) = {n(n+1)/2},$$ fractions with odd numerator and even denominator - in consequence $$H_n = \left\{2, 7, 9, 16, 18, 20,\dots \right\} .$$

Thus, each infinite subset of rational numbers can be displayed as the increasing sequence of Cantor indexes, allowing to form representative samples of a given volume. Reciprocal to the selective expectancy of $x\over y$, or its limit (when it converges), or some another selective statistics can be used as the required measure of subsets.

At the same time, more informative (and therefore more promising) direction is the construction of empirical probability distributions.

$\endgroup$
  • $\begingroup$ I'm glad you gave me other possible methods but can you check my answer. My username is Arbuja. $\endgroup$ – Arbuja May 23 '17 at 0:00
  • $\begingroup$ I can't find an article on cantor indexes and how does this lead to $N_n$ and $H_n$? I apolgize for my ignorance. $\endgroup$ – Arbuja May 24 '17 at 11:31
  • $\begingroup$ Try it there, page 110 $\endgroup$ – Yuri Negometyanov May 24 '17 at 12:43
0
$\begingroup$

How about $\mu: \mathcal{P}(\mathbb{Q})\to \mathbb{N}\cup \{\infty\}$ defined by $\mu(T)=\limsup_{a<b\in \mathbb{Q}} |T\cap (a,b)|$. It measures the asymptotic behavior of local density and incorporates your requirement.

$\endgroup$
  • $\begingroup$ What does $\mathbb{N}\cup{\left\{\infty\right\}}$ mean? $\endgroup$ – Arbuja May 19 '17 at 12:25
  • $\begingroup$ $\infty$ here is just reserved for the cardinality of any countably infinite object, as made clear from the definition of $\mu$. $\endgroup$ – Jing Zhang May 19 '17 at 14:02
  • $\begingroup$ So if we set $T=\left\{\left.\frac{m}{2n+1}\right|m,n\in\mathbb{Z}\right\}$ what would $\mu(T)$ be? $\endgroup$ – Arbuja May 19 '17 at 14:29
  • $\begingroup$ Can you elaborate in more detail with how you got this equation? $\endgroup$ – Arbuja May 19 '17 at 15:02
  • $\begingroup$ $\mu(T)$ will be infinity, since between any rationals $a<b$, there are infinitely many $m,n\in \mathbb{Z}$ such that $a<\frac{m}{2n+1}<b$. In some sense this measure is really silly. $\endgroup$ – Jing Zhang May 19 '17 at 17:26
0
$\begingroup$

Here is another definition my professor offered.

However, I believe it does not follow my second requirement for an appropriate measure/density.

Requirement 1: If $T_1$ and $T_2$ are subset of $\mathbb{Q}$ and $T_1=T_2$, then $D(T_1)=D(T_2)$

Requirement 2: If $T_1$ and $T_2$ are subset of $\mathbb{Q}$ and $T_1\subset{T_2}$, then $D(T_1)<D(T_2)$

We can turn $\mathbb{Q}$ into a finite set by restricting its numerator and denominator.

$$V(r)=\left\{\left.\frac{m}{n}\right|1<m<r,1<n<r,\gcd(m,n)=1\right\}$$

$$\lim_{r\to\infty}V(r)=\mathbb{Q}$$

We then take the number of elements in $V(r)$ that $T$ intersects with.

$$\frac{\left|T\bigcap{V(r)}\right|}{|V(r)|}$$

As $r$ becomes larger

$$D(T)=\lim_{r\to\infty}\frac{\left|T\bigcap{V(r)}\right|}{|V(r)|}$$

$\endgroup$

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.