Questions about coverings and some odd question.

  • #1
MathematicalPhysicist
Gold Member
4,294
203

Main Question or Discussion Point

1. i need to show that the set A={x in Q|0<=x<=1}
Q is the rationals set.
can be covered by open intervals I_k (k is natural number) which the total sum of their lengths is smaller than 1/100.
2. an integer number is called simple if you can write it by the letters ),(,1,2,+,* (* is multiplication) when we can use the letters at most 10 times.
i need to show that there exists a natural number N,
1<=N<=10000000000 which isnt simple.

for the first question im not sure,
i need to show that A is a subset of the union of open intervals which their total length is smaller than 1/100, obviously we can dissect A into,
(0,1/1000),(1/1000,2/1000),....(999/1000,1) but then we don't have the end points included.
perhaps the end points should be irrational, cause they anyway cannot be attained in the set A?

for the second question i dont have a clue, i thought perhaps give an ad absurdum proof, suppose every natural number in the interval [1,10000000000] is simple then the number of those numbers is 10000000000, and we have used at most 100000000000,
if we show that the cardinality of the set of letters used is smaller than the cardinality of the set of simple numbers in this interval than we have a contradiction, but im finding it hard to find a one to one function between sets, i dont know how to even to define one.

any help?
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
1. Trying to cover the whole interval [0, 1] cannot possibly work, since it has length one, and thus any collection of intervals that covers [0, 1], or even most of [0, 1], must have total length at least 1. (e.g. the collection you wrote down has total length exactly 1)

Your intervals are allowed to overlap, by the way.



2. I think you're overthinking it; it's just a counting problem.
 
  • #3
MathematicalPhysicist
Gold Member
4,294
203
then how to solve question two?
i think i solved question 1, bacause every x in A is in the interval (x-e/2^k+2,x+e/2^k+2) so the set A is covered by: U(x-e/2^k+2,x+e/2^k+2)
where k is from 1 to infinity, and thus its total length is e/2, so because this is true for all e>0 it's also true for e=1/100 and thus i think ive solved it.
 
  • #4
verty
Homework Helper
2,164
198
Ah, you are adding up an infinite number of infinitesimal subsets so that their union has an arbitrary finite length, am I right?
 
  • #5
matt grime
Science Advisor
Homework Helper
9,395
3
You're taking a union over what index set? I know you've got the answer, but try to write things properly. Is the union indexed by x? By k? What is the relationship between x and k?

Question 2 looks ripe for the pigeonhole principle to me.
 
  • #6
MathematicalPhysicist
Gold Member
4,294
203
the union is indexed by k.
how exactly to use here the pigenhole principle?
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Ah, you are adding up an infinite number of infinitesimal subsets so that their union has an arbitrary finite length, am I right?
No, he's taking the union of an infinite number of intervals, each with a positive length. And the total length is the infinite sum of the lengths which, in this case, is a geometric series.
 
  • #8
EnumaElish
Science Advisor
Homework Helper
2,304
124
the union is indexed by k.
how exactly to use here the pigenhole principle?
If you were allowed to use each character once (I am assuming you meant "character" or "typographical symbol" when you wrote "letter"), then you'd have 5! = 720 permutations. (Just a guess.)
 
  • #9
matt grime
Science Advisor
Homework Helper
9,395
3
the union is indexed by k.
Is it? Then your answer is wrong. Since x doesn't vary at all, all you get is a nested union, i.e. the interval (x-e/2, x+e/2).

As for part 2. How many numbers can you make from those symbols? Try vastly over estimating it. If you can just show there are fewer possible combinations than whatever that large number you wrote is then....
 
  • #10
MathematicalPhysicist
Gold Member
4,294
203
then how should i correct my answer to the first question?
so i shouldv'e indexed over x, for x in A?

enumaelish wrote that there are 5! permutations, but you can use the symbols at least 10 times, so the number of combinations is 10C1+10C2+...+10C5 i think, am i wrong here?
 
  • #12
453
0
Question 1 is best solved by simply observing that the result is true for any countable set.
 
  • #13
HallsofIvy
Science Advisor
Homework Helper
41,833
956
1. i need to show that the set A={x in Q|0<=x<=1}
Q is the rationals set.
can be covered by open intervals I_k (k is natural number) which the total sum of their lengths is smaller than 1/100.
The total sum of their lengths or the length of each one? The latter is easy, the former impossible!

2. an integer number is called simple if you can write it by the letters ),(,1,2,+,* (* is multiplication) when we can use the letters at most 10 times.
i need to show that there exists a natural number N,
1<=N<=10000000000 which isnt simple.
HOW MANY different such formulas are there?
 
  • #14
MathematicalPhysicist
Gold Member
4,294
203
The total sum of their lengths or the length of each one? The latter is easy, the former impossible!
the length of each one.
HOW MANY different such formulas are there?
at least as many as there are simple numbers, but i dont know what's the upper bound.
 
  • #15
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
The total sum of their lengths or the length of each one? The latter is easy, the former impossible!
The former; and it's not impossible, he's essentially solved it, he just needs to dot his i's and cross his t's.

at least as many as there are simple numbers, but i dont know what's the upper bound.
Your goal is to count the simple numbers by counting formulas, not the other way around.
 
Last edited:
  • #16
MathematicalPhysicist
Gold Member
4,294
203
i dont think this is feasible to count all of the simple numbers from 1 to 10000000000.
and anyway, who gurantees that a simple number has only one formula, maybe it can have two formuals which satisfy the condintions.

and what do you mean dot his i's and cross his t's?
what on hell i did wrong there, i shouldn't have indexed on k this i understand, cause then we have a nested interval, then i asked matt if i should have indexed over x, im waiting for his response.
 
  • #17
matt grime
Science Advisor
Homework Helper
9,395
3
then how should i correct my answer to the first question?
so i shouldv'e indexed over x, for x in A?
You wrote

[tex] \cup_{k \in \mathbb{N}} (x-e/2^k, x+e/2^k)[/tex]

that is just (x-e/2,x+e/2). And has length e. You haven't said what x is. That is just an interval ov length e containing x. Unioning that over x isn't going to help you, is it? I mean

[tex] \cup_{x \in A}(x-e/2^k, x+e/2^k)[/tex]

doesn't work, since that is an infinite number of intervals all of length 2e/2^k, whatever k might now mean.



You need to find one interval for each x in A, whose total length is e.
 
Last edited:
  • #18
matt grime
Science Advisor
Homework Helper
9,395
3
i dont think this is feasible to count all of the simple numbers from 1 to 10000000000.
Who told you to count them? I told you to overestimate them. If you can show that there are at most 12 possible simple numbers then you're done right? A simple number is just specified by a string

x_1,..,x_10 where the x_i are in that symbol list. How many such strings are there? Who cares if a number is represented by two different strings - you're not trying to count the number of simple numbers.
 
  • #19
MathematicalPhysicist
Gold Member
4,294
203
but how estimate the number of simple numbers, i have 5 symbols, right?
i can use all of them maximum 10 times, so the maximum number of them would be at least as the number 2222222222.
i really dont know how to estimate their quantity.

and for the first question, didnt i wrote: U(x-e/2^k+2,x+e/2^k+2)?
perhaps, (x-e/2,x+e/2) for every x in A, is it that simple?
 
  • #20
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
but how estimate the number of simple numbers, i have 5 symbols, right?
i can use all of them maximum 10 times, so the maximum number of them would be at least as the number 2222222222.
i really dont know how to estimate their quantity.
Hrm, how did you get 2222222222?

Incidentally, does the question say that a simple number uses up to 10 symbols, or up to 10 of each of the symbols? (p.s. there are 6 symbols)
 
  • #21
MathematicalPhysicist
Gold Member
4,294
203
up to 10 of each symbol, has anyone got hints, cause im really stuck here.
 
  • #22
MathematicalPhysicist
Gold Member
4,294
203
the maximum number i can achieve by 10 of the symbols is 10 time the digit 2, so i thoght bacuase i cannot reach further than that then this is the maximum number of simple numbers, but i might be wrong as usual. )-:
 
  • #23
matt grime
Science Advisor
Homework Helper
9,395
3
and for the first question, didnt i wrote: U(x-e/2^k+2,x+e/2^k+2)?
perhaps, (x-e/2,x+e/2) for every x in A, is it that simple?
As I said before, that is not correct - each element of A lies in an interval of width e, it says nothing about the total size of all the intervals. With that method, the total width of the cover is 1+2e.

Now, let's take you actual answer I misremembered. I presume that +2 is suppposed to be in the superscript. I'll ask again, what relationship has k got to do with x? (That's a hint by the way.)

For the third time: just putting fixed width intervals around each x will do nothing as the total area will be greater than 1. There are an infinite number of elements of A. You need an infinite sum of lengths that can be made arbitrarily small - how many infinite series do you know that converge?
 
Last edited:
  • #24
EnumaElish
Science Advisor
Homework Helper
2,304
124
the maximum number i can achieve by 10 of the symbols is 10 time the digit 2, so i thoght bacuase i cannot reach further than that then this is the maximum number of simple numbers, but i might be wrong as usual. )-:
I think you need to think permutations, along my previous example, but taking into account 10X. To further your thought process, I'll suggest you make up 10 flavors of each of the symbols you are allowed to use. Example: 11, ..., 110. Then )1, ..., )10. Then +1, ..., +10. Etc. If you had 5 symbols originally, now you have 50 symbols (flavors). Now use the perm. formula to calculate the # of simple numbers.
 
  • #25
EnumaElish
Science Advisor
Homework Helper
2,304
124
As for the 1st question, why isn't Length(union of an infinite number of sets) < Sum(lengths of the sets) < 1?
 

Related Threads on Questions about coverings and some odd question.

Replies
5
Views
207
Replies
3
Views
2K
Replies
0
Views
3K
  • Last Post
Replies
3
Views
631
  • Last Post
Replies
1
Views
550
Replies
4
Views
533
  • Last Post
Replies
1
Views
2K
Replies
0
Views
6K
Replies
2
Views
7K
Replies
1
Views
590
Top