Questions about coverings and some odd question.

[MathematicalPhysicist]

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 isn't simple.

for the first question I am 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 don't 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 I am finding it hard to find a one to one function between sets, i don't know how to even to define one.

any help?

 

[Hurkyl]

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]

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 I've solved it.

 

[verty]

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]

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]

the union is indexed by k.
how exactly to use here the pigenhole principle?

 

[Hurkyl]

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]

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]

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]

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]

C is the binomial coefficient.

 

[DeadWolfe]

Question 1 is best solved by simply observing that the result is true for any countable set.

 

[HallsofIvy]

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 isn't simple.

HOW MANY different such formulas are there?

 

[MathematicalPhysicist]

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 don't know what's the upper bound.

 

[Hurkyl]

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 don't know what's the upper bound.

Your goal is to count the simple numbers by counting formulas, not the other way around.

 

[MathematicalPhysicist]

i don't 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, I am waiting for his response.

 

[matt grime]

then how should i correct my answer to the first question?
so i shouldv'e indexed over x, for x in A?

You wrote

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

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

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

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.

 

[matt grime]

i don't 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]

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 don't 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]

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 don't 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)

 

[MathematicalPhysicist]

up to 10 of each symbol, has anyone got hints, cause I am really stuck here.

 

[MathematicalPhysicist]

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. )-:

 

[matt grime]

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?

 

[EnumaElish]

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: 1₁, ..., 1₁₀. Then )₁, ..., )₁₀. Then +₁, ..., +₁₀. Etc. If you had 5 symbols originally, now you have 50 symbols (flavors). Now use the perm. formula to calculate the # of simple numbers.

 

[EnumaElish]

As for the 1st question, why isn't Length(union of an infinite number of sets) < Sum(lengths of the sets) < 1?

 

[MathematicalPhysicist]

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?

every x in A is also in (x-e/2,x+e/2), we can number A because it's countable: {x1,x2,...} so x1 is in (x1-e/2,x1+e/2) x2 is in (x2-e/4,x2+e/4),...
and so forth.
so k is indicating the number in A we are counting.
is this correct or am iwrong again?


enumaelish, so it should be 6! the answer?
cause first i can use one letter, and i have 6 options, afterwards i can choose another 6 options for the second option, so it means it should be 10*6!, is this correct, is this the maximum number?

 

[matt grime]

every x in A is also in (x-e/2,x+e/2), we can number A because it's countable: {x1,x2,...} so x1 is in (x1-e/2,x1+e/2) x2 is in (x2-e/4,x2+e/4),...
and so forth.
so k is indicating the number in A we are counting.
is this correct or am iwrong again?

what do you think? Is every element of A in some interval? What is the total length of all the intervals?

I don't follow either your answer, nor some of the advice you've been gettting for the other question.

So, I'll repeat myself. How many strings of ten symbols can be made? That is all you need to work out. Sure, not all of them even correspond to allowable strings, but that doesn't matter. This factorial stuff is completely irrelevant.

 

[MathematicalPhysicist]

yes, idefined it such that x1 is in(x1-e/2,x1+e/2) and so forth.
what's wrong with that?

and for the second question, only to count the number of strings that can be made out of ten symbols.
in order to choose the first symbol we have 6 options, and thus it follows up until the tenth symbol, overall we have 10*6!, so why do you say the factorial stuff is irrelevant?
the number of strings that can be made must include factorial, is it not?

 

[MathematicalPhysicist]

but the total length isn't e, so i could squeeze such that (x1-e/4,x1+e/4)
(x2-e/8,x2+e/8)...
so the total length is e/2+e/4+...=e/2(1/1-1/2)=e
but surely that's not your problem from what i wrote, is it?

 

[EnumaElish]

yes, idefined it such that x1 is in(x1-e/2,x1+e/2) and so forth.
what's wrong with that?

and for the second question, only to count the number of strings that can be made out of ten symbols.
in order to choose the first symbol we have 6 options, and thus it follows up until the tenth symbol, overall we have 10*6!, so why do you say the factorial stuff is irrelevant?
the number of strings that can be made must include factorial, is it not?

I may have misinterpreted your OP, which led to some confusion: when you wrote

we can use the letters at most 10 times

I interpreted it as

use each symbol at most 10 times.

I think that was incorrect, what you meant was

use at most 10 symbols.

If that is the case (as I now am guessing is), please ignore my post immediately prior to this. Instead, you might think of 10 boxes, and each box can hold anyone of the symbols you are allowed to use. How many strings of symbols can you write this way? E.g., the first box can hold any of the 6 symbols. Same with the 2nd box. And so on...

 

[matt grime]

yes, idefined it such that x1 is in(x1-e/2,x1+e/2) and so forth.
what's wrong with that?

Nothing - just tidy it up. I.e. put in proper subscripts, notation, and don't use 'and so forth' after *one* example.

and for the second question, only to count the number of strings that can be made out of ten symbols.
in order to choose the first symbol we have 6 options, and thus it follows up until the tenth symbol, overall we have 10*6!, so why do you say the factorial stuff is irrelevant?
the number of strings that can be made must include factorial, is it not?

No. Why would it? Let's say we can only use the symbols 0,1,2,..,9. Now, how many numbers can be made from strings of length n in those symbols. Let's say n=2, so we have 00,01,02,03,04,..,99. Hmm, does 100=2*10!, which is what you've said it does by the above reasoning?

 

[matt grime]

but the total length isn't e, so i could squeeze such that (x1-e/4,x1+e/4)
(x2-e/8,x2+e/8)...
so the total length is e/2+e/4+...=e/2(1/1-1/2)=e

No, the total length is *less* than e; the intervals are not necessarily disjoint.

but surely that's not your problem from what i wrote, is it?

What are you referring to with 'my problem'?

 

[EnumaElish]

I think what the 1st question is getting at Cantor's argument that the measure of rationals (on the real line) is zero. Imagine you can visualize each rational point on the real line (and there are infinitely many of them, to be sure). Suppose a tiny creature wants to walk on the real line from 0 to 1 in infinitely tiny steps, and that each point corresponding to a rational number holds a landmine. So your advice to the creature is to avoid those points, but to make extra sure that it doesn't blow off a leg, you decide to cover each rational point with a tiny piece of red paper. Although your Xmas gifts are wrapped in miles of red paper, what you really need is a tiny, tiny, piece of red paper to cover all the rationals. Why? Suppose you have a piece of red paper with length L (which is tiny, e.g., 1/"zillion"). You use half of it to cover the first rational point that you see (and to be sure, even the tiniest bit of paper will cover more than just the point with a landmine, i.e. it will also cover some safe [i.e. irrational] points which are very near the rational point you'd like to cover, but there is no way to avoid this, and that's okay anyway, as long as each landmine is covered in the end, along with some safe points). For the next rational point, you use half of the remaining half, or 1/4ths. Use 1/8ths for the next rational. And so on. Question: can you cover all the rationals this way? Why (or why not)? Supposing that you can, what is the total length of paper that you'll ever need to cover all the rationals?

 

[EnumaElish]

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,

1. Why do you need the +2 after each 2^k?
2. Don't you need an argument or a sentence as to why these intervals would cover all the rationals?

 

[EnumaElish]

#33 is almost verbatim from

Everything and More: a Compact History of ∞