Show that a certain set of positive real numbers must be finite or countable

Question

Let $B$ be a set of positive real numbers with the property that adding together any finite subset of elements from $B$ always gives a sum of $2$ or less. Show that $B$ must be finite or at most countable.

$B$ = {$x \in R:x>0\}$, $x_1,x_2...x_n \in B$ such that $x_1+x_2+...+x_n \le 2$.

Question: for any $a,b$ $(a,b)$~$R$, but $B$ is $(0,+\infty)$ so why $B$ is not uncountable (taking as $a = 0$, and letting $b$->$\infty$)?

And why for $B$ being countable doesn't contradict: for any $a,b$ $(a,b)$~$R$?

P.S. I read Showing a set is finite or countable and understood it.

It sounds like you are confused about what the question is asking. It is not saying that B is the set of positive real numbers; it is a set of positive real numbers. This means that B is a subset of the set of all positive real numbers. — Leonard Blackburn, Aug 08 '18 at 17:23
@LeonardBlackburn So $B$ is not$ B = {x∈R:x>0}$ but it is some $(0,a)$, where $a > 0$, $a \in R$? some finite subset of its elements add up to $1$ — user13, Aug 08 '18 at 17:26
No. B is some unspecified subset of the positive real numbers such that if you add up a finite number of the elements of B the sum is always less than 2. For example, B could be {0.1, 0.2, 0.5, 1.1} or B could be the infinite set {1, 1/2, 1/4, 1/8, 1/16, ...}. Note that B cannot be {1, 1.4, 1.8} and B cannot be {1, 1/2, 1/3, 1/4, ...} — Leonard Blackburn, Aug 08 '18 at 17:47
B does not have to be an interval (0,a). In fact, it cannot be such an interval. Your job is to prove that B must be finite or countable. Intervals are uncountable. — Leonard Blackburn, Aug 08 '18 at 17:49
@LeonardBlackburn Finally, that is the point. Please, don't go away. I know that $(0,a)$ is uncountable, but don't see why $B$ the way it is defined can not be represented as an interval. Can you clarify why? (Please, don't write about the union of countable sets. I see that too) — user13, Aug 08 '18 at 17:52
Well, I'm just trying to help clarify the question. I haven't given a solution. I think the hints and discussion below do that for you. But the point is you cannot assume anything about B except: 1. its elements are all positive real numbers and 2. if you take a finite number of elements from B and add them up then you get a sum less than two. Given any such B you have to prove that B is either finite or countable. — Leonard Blackburn, Aug 08 '18 at 17:59
Here is a proof that B cannot be the open interval (0,1). If it were then these numbers would be in B: 0.5, 0.51, 0.52, and 0.53. These numbers add up to more than 2. Do you see? You could do something similar to show that B cannot be (0,a) for any positive a. But you have to show more than that. You have to show B is finite or countable. — Leonard Blackburn, Aug 08 '18 at 18:00
According to wikipedia, "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set." So saying "countable or finite" is redundant, although I suppose it does dispel any question as to whether it includes the possibility of finiteness. — Acccumulation, Aug 08 '18 at 18:01
@LeonardBlackburn I summed up exactly this numbers too as an illustration for me. Thank you. You are the best! Your contribution is bigger than others for my understanding of the question!! — user13, Aug 08 '18 at 18:03
Glad to help. @acccumulation: good point. I think some classes/books use "countable" to mean "countably infinite" in contrast to wikipedia. — Leonard Blackburn, Aug 08 '18 at 18:06
@Acccumulation As Leonard Blackburn, some books will define a "countable" set to be one that is in bijective correspondence the the natural numbers, meaning that a countable set is infinite. Saying "countable or finite" may be redundant in some circumstances, but it has the advantage of being unambiguous. — Xander Henderson, Aug 08 '18 at 21:34

score 18 · Answer 1 · answered Aug 08 '18 at 17:04

18

Hint 1: How many elements of $B$ can be in the set $[2,\infty)$?

Hint 2: How many elements of $B$ can be in the set $[1,2)$?

Hint 3: How many elements of $B$ can be in the set $[0.5,1)$?

answered Aug 08 '18 at 17:04

vadim123

82,796

26

At this rate you are going to need countably many hints :) – Arnaud Mortier Aug 08 '18 at 17:04
9

@ArnaudMortier Can't he give a hint schema? – saulspatz Aug 08 '18 at 17:07
One $x = 2$, 2) set $x_1=1$ so one for sure, then I don't know how many $x_2,x_3,...x_n$ to choose so that they sum up to $1$. 3) The same, I don't know.

user13

Aug 08 '18 at 17:10

Where for me "I don't know" = "infinitely many" – user13 Aug 08 '18 at 17:16

4

Obviously $B\cap[1,\infty)$ has at most two elements, because if $x,y,z\ge1$ then $x+y+z>2$. Similarly $B\cap[2/n,\infty)$ has at most $n$ elements. (So $B$ is the union of countably many finite sets...) – David C. Ullrich Aug 08 '18 at 17:17

@DavidC.Ullrich Ok, I got the point. But why it does not contradict? – user13 Aug 08 '18 at 17:28

??? Why what does not contradict what? – David C. Ullrich Aug 08 '18 at 17:36

@DavidC.Ullrich To the fact that $(a,b)$ ~ $R$, since we can wrote down $B$ as $(0,a)$, $a>0,a \in R$ – user13 Aug 08 '18 at 17:41

@saulspatz A simplified hint schema is "Hint $n$: How many elements of $B$ can be in $[\frac1n,\infty)$" :) – Hagen von Eitzen Aug 08 '18 at 17:42

@DavidC.Ullrich Why it is not uncountable too that is my question, I see that it is a union of countable sets so it must be countable, but I think it can be rewritten in a form $(0,a)$ so it must be uncountable – user13 Aug 08 '18 at 17:43

That is my question – user13 Aug 08 '18 at 17:44

But they are explaining to you that it must be countable. You ask "why it is not uncountable too." That is a strange thing to ask because "uncountable" means "not countable." A set cannot be both countable and uncountable. I think you are still confused about the question. See me comments to your question above. – Leonard Blackburn Aug 08 '18 at 17:52

1

No, we certainly can't write $B$ as $(0,a)$. If $B=(0,a)$ then there are finite subsets of $B$ with sum larger than $2$. – David C. Ullrich Aug 08 '18 at 18:56

score 4 · Accepted Answer · answered Aug 08 '18 at 18:25

Not only can we show that it's countable, it's not too difficult to construct an enumeration: given an element $b$, just count how many other elements of $B$ are larger. This has to be a finite integer, since if there were an infinite number of elements greater than $b$, then the sum of $n$ such elements would be greater than $nb$, so picking an $n>2/b$ would give a sum greater than 2.

Matt · Answer 3 · 2018-08-09T11:06:31.460

3

For any $a\in B$, define $B_a\equiv\{b\in B:a<b\}$. The cardinality of $B_a$ must be less than $\lceil2/a\rceil$, otherwise the sum of any $\lceil2/a\rceil$ elements of $B_a$ would exceed 2. That is, $\sum_{i=1}^{\lceil2/a\rceil}x_i>\sum_{i=1}^{\lceil2/a\rceil}a=a\lceil2/a\rceil\ge2$ for any sequence $x_i$ in $B_a$, contradicting the requirements on $B$.

Define the function $f:B\rightarrow\mathbb{N}$ as $f(a)=\left|B_a\right|$.

Homework: If you can show that $f$ is one-to-one then you can conclude that $|B|\le|\mathbb{N}|$. That is, $B$ is either finite or countable.

Credit goes to Acccumulation for the outline of this proof.

edited Aug 09 '18 at 11:06

answered Aug 09 '18 at 03:13

Matt

730
5
14

What if $a =$ sup$B$? Then $B_a $ is the empty set. If $B_a \equiv {b \in B: a \leq b }$, then the sum of any $\lceil r/a \rceil$ for $r > 2$ elements of $B_a$ would exceed 2. – hiroshin Jul 18 '19 at 23:08

Show that a certain set of positive real numbers must be finite or countable

3 Answers3