Questions about coverings and some odd question.

MathematicalPhysicist

Gold Member
4,027
118
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?
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,829
14
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.
 

MathematicalPhysicist

Gold Member
4,027
118
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.
 

verty

Homework Helper
2,150
197
Ah, you are adding up an infinite number of infinitesimal subsets so that their union has an arbitrary finite length, am I right?
 

matt grime

Science Advisor
Homework Helper
9,392
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.
 

MathematicalPhysicist

Gold Member
4,027
118
the union is indexed by k.
how exactly to use here the pigenhole principle?
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,829
14
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.
 

EnumaElish

Science Advisor
Homework Helper
2,273
123
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.)
 

matt grime

Science Advisor
Homework Helper
9,392
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....
 

MathematicalPhysicist

Gold Member
4,027
118
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?
 

MathematicalPhysicist

Gold Member
4,027
118
C is the binomial coefficient.
 
Question 1 is best solved by simply observing that the result is true for any countable set.
 

HallsofIvy

Science Advisor
41,626
821
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?
 

MathematicalPhysicist

Gold Member
4,027
118
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.
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,829
14
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:

MathematicalPhysicist

Gold Member
4,027
118
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.
 

matt grime

Science Advisor
Homework Helper
9,392
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:

matt grime

Science Advisor
Homework Helper
9,392
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.
 

MathematicalPhysicist

Gold Member
4,027
118
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?
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,829
14
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)
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top