Wikipedia:Reference desk/Archives/Mathematics/2008 March 22

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 22

Uncountable Sets of Measure Zero

To a beginner (in measure theory that is) it seems that a set having (Lebesgue) measure zero is equivalent to that set being denumerable (countable or finite) but I just found out that the Cantor ternary set is both uncountable and it has measure zero. My question is, does anyone know of any other uncountable sets that have measure zero? What about an example of a real set which is not measurable at all? Thanks!
A Real Kaiser (talk) 03:37, 22 March 2008 (UTC)

For uncountable sets of measure 0, a bunch of copies of the Cantor set would work, of another set similarly constructed. As for non-measurable sets, see Vitali set. -GTBacchus^(talk) 03:48, 22 March 2008 (UTC)

The Cantor set already gives you lots of uncountable sets of measure zero: since Lebesgue measure is complete, any uncountable subset of the Cantor set will do. There are 2^c of them, which is already far more than, say, the number of Borel sets. Algebraist 12:53, 22 March 2008 (UTC)

What about another example of an uncountable set with measure zero? Something "different" than the Cantor ternary set? In addition, is there another example of a nonmeasurable real set besides a Vitali set, something that can perhaps be described explicitly (you know something like "all irrational numbers between one and two", which I know is measurable)?
A Real Kaiser (talk) 19:27, 23 March 2008 (UTC)

So for the first question, you might be interested in something like this: almost all real numbers are normal, but certainly uncountably many real numbers are not normal. In fact, to be more explicit, consider the real numbers whose decimal expansions follow some slight predictable bias; say, 11% of their digits are 7 (instead of 10%), and only 9% of their digits are 8. It's "obvious" that there are just as many numbers like that as there are normal numbers, but because almost all numbers are normal, the set of all numbers with this bias (none of which are normal) must have measure zero.

For the second question, it depends a little on what you mean by "described explicitly", but the short answer is that for any explicit description you're likely to think of, unless you know quite a bit of set theory, the set of reals so described is measurable. --Trovatore (talk) 22:09, 23 March 2008 (UTC)

Cool, thanks everyone!A Real Kaiser (talk) 01:03, 24 March 2008 (UTC)

a question for econs nerds

cost function c(y) = y^3 - 2y^2 + 6y + 6.

need to derive the supply curve.

figured out that the shutdown point is where p = 5 (AVC = y^2 - 2y + 6, MC = 3y^2 - 4y +6; when y = 1, the two are both equal to 5, and because profit maximization occurs when MC = p, then the smallest price is 5).

so when p < 5, y = 0; when p > 5, p = 3y^2 - 4y + 6. I have to write this in terms of y, however - wtf I do this?

also, the firm makes positive profits when the price is higher than the average cost ofc, right? AlmostCrimes (talk) 18:18, 22 March 2008 (UTC)

Well to get $p=3y^{2}-4y+6$ in terms of y, just subtract p from both sides and then treat p as part of the constant term c, in ax^2+bx+c. So to be a little more clear once you've moved p to the right side, a=3 b=-4 and c=(6-p). A math-wiki (talk) 21:43, 22 March 2008 (UTC)

After you follow AMW's suggestion, you may find two solutions (functions y(p)) using the quadratic formula; of these two solutions, you must choose the increasing one (satisfying the second-order condition of profit maximization). And yes, AlmostCrimes, you are right in that positive profits happen when price is higher than the average (total) cost, for then the average income (price) is greater than the average cost, which implies that total income is greater than the total expenditures. Pallida  Mors 06:27, 25 March 2008 (UTC)

Error in the Total order article?

I'm not all that proficient at mathematics, but I do enjoy to be dazzled by the shiny notation of set theory, so I often find myself reading articles in that subject and saying "Ohh, pretty!". I happened just now to come across the Total order article, and saw something which I'm fairly certain is an error, but I thought I'd check with you guys first. Under the "Example" heading, this is stated:

"The set of real numbers ordered by the usual less than (<) or greater than (>) relations is totally ordered, hence also the subsets of natural numbers, integers, and rational numbers."

This is not true, right? Both "less than" and "greater than" fails the totality criterion since they are not reflexive (statements like "42 < 42" are most certainly not true). Shouldn't that sentence be:

"The set of real numbers ordered by the usual less than or equals operator (≤) or the greater than or equals operator (≥) relations is totally ordered, hence also the subsets of natural numbers, integers, and rational numbers."

Right? 83.250.207.154 (talk) 19:35, 22 March 2008 (UTC)

A (weak) total order and its associated strict total order are interchangeable for most purposes. The orders don't satisfy the same axioms, but each is obtained from the other in a straightforward way, by adding or removing the diagonal. That is, the strict total order is obtained from the weak total order by the rule x < y if and only if x ≤ y and x ≠ y, while the weak total order is obtained from the strict total order by the rule x ≤ y if and only if x < y or x = y. Michael Slone (talk) 20:11, 22 March 2008 (UTC)

True, but strictly speaking, I think the anon is right - it should say ≤. The ordering is the same, but to be consistent with the way its defined at the top of the article, the weak order should be given. --Tango (talk) 20:26, 22 March 2008 (UTC)

weak order? Taemyr (talk) 01:10, 24 March 2008 (UTC)

Sorry, weak *total* order. I think someone needs to come up with better names for orderings... this is far too confusing. --Tango (talk) 02:12, 24 March 2008 (UTC)

Chicken, fox, and grain problem

Here is the traditional problem, both question and answer. Question: A farmer is standing on one bank of a river, with a fox, a chicken, and a bag of grain. He needs to get to the other side of the river, taking the fox, the chicken, and the grain with him. However, the boat used to cross the river is only large enough to carry the farmer and one of the things he needs to take with him, so he will need to make several trips in order to get everything across. In addition, he cannot leave the fox unattended with the chicken, or else the fox will eat the chicken. And he cannot leave the chicken unattended with the grain, or else the chicken will eat the grain. The fox is not particularly partial to grain, and may be left alone with it. How can he get everything across the river without anything being eaten? Answer: The farmer takes the chicken across first, leaving the fox and grain together on the other side. He returns and gets the fox, but when he deposits the fox on the other side, he takes the chicken BACK across, so that the fox and chicken aren't left alone together. He drops the chicken off back on the other side, picks up the grain, and takes it across to deposit with the fox. Finally, he returns to retrieve the chicken and takes it to the other side. At no time were the fox and chicken left alone together, nor were the chicken and grain. At no time was more than one of them in the boat with the man simultaneously.

My question #1 is: Is there any generalized mathematical formula / set-up / algorithm that essentially explains and solves this problem? And, thus, could be extended into more complex similar problems (e.g., the farmer now has 7 items -- or 24 or whatever -- to carry over with various restrictions upon the 7 -- or 24 -- items, etc.) ...?

My question #2 is: (related to question #1 above) Generally speaking, how would one know that the given scenario is indeed "able" or "impossible" to be executed? So, for example, in the traditional problem above ... how would I know at the onset that this can in fact be effectuated (or not) without going through umpteen "trial and error" attempts first? Thanks. (Joseph A. Spadaro (talk) 21:48, 22 March 2008 (UTC))

I can't answer your question, but that won't stop me posting a link to the definitive discussion of the original problem. AndrewWTaylor (talk) 21:55, 22 March 2008 (UTC)

I'm not sure about question 1. For question 2, I would expect the easiest way to confirm it's possible is to find a solution. If it's impossible, there is probably a way to prove that without testing every possible combination. Whether there's a general method, or you just have to do it on a case-by-case basis, I don't know. --Tango (talk) 21:57, 22 March 2008 (UTC)

Actually, on second thoughts, I can partially answer a restricted version of question 1. If the restrictions on the items are all of the same form as in the original question (ie. items x and y cannot be left alone together), then it will be impossible in all but a small number of cases. Unless there is an item which is included in all the restrictions (in the original problem, the chicken), then it's impossible because there is no available first move. If there are more complicated restrictions (x and y can only be together if z is there too, for example), then it gets more complicated. --Tango (talk) 22:02, 22 March 2008 (UTC)

I suppose you can express the constraints in Linear temporal logic. Maybe this article is of interest to you? Phaunt (talk) 10:00, 25 March 2008 (UTC)

I assumed we must have an article on this puzzle, but I can't find it (anyone ?). Anyway, this type of puzzle can be solved algorithmically by constructing a graph of allowed states and transitions between them.

• We start in state {F,f,c,g | } with Farmer, fox, chicken and grain all on one side of the river. We want to get to state { | F,f,c,g}.
• Initially we have sixteen states (each object can be on either side of the river, so number of states is 2^4) - but once we disallow states such as {F,g | f,c} (fox eats chicken) and {c,g | F,f} (chicken eats grain) and {F | f,c,g} (fox eats well-fed chicken) we are left with 10 allowed states. Each of these states is a vertex in the graph.
• Transitions take F and possibly one other object from one side of the river to the other, so we draw an edge from {F,f,c,g | } to {f,g | F,c}, and an edge from {f,g | F,c} to {F,f,g | c} etc. In this case each transition is reversible, so we have an undirected graph. If transitions were not reversible, we could draw a directed graph.
• Once we have drawn the graph, we look for a route from our initial state {F,f,c,g | } to our final state { | F,f,c,g}.

In the F,f,c,g case the routes (there are two of them) are obvious. For larger problems, some sort of search algorithm could be used to find a solution. Gandalf61 (talk) 10:37, 25 March 2008 (UTC)

That approach works, but because the number of nodes is equal to $k^{n}$ (where n is the number of items, and k is the number of states each item may be in), it is only tractable for relatively moderate values of these parameters (especially n). Phaunt (talk) 10:46, 25 March 2008 (UTC)

Finally found our article on this puzzle, in a different guise - it is the fox, goose and bag of beans puzzle. Gandalf61 (talk) 10:37, 27 March 2008 (UTC)

The Riemann Zeta Function

The Wikipedia article on the Riemann Zeta Function lists Specific Values. One of them says that the Riemann Zeta Function of zero is -1/2. Can anyone explain why this is? I know it should probably be obvious, but I just can't seem to figure it out. Digger3000 (talk) 23:07, 22 March 2008 (UTC)

This can be easily obtained from the infinite product expansions listed under Hadamard product. Now why these hold...  --Lambiam 00:35, 23 March 2008 (UTC)

Sorry, but that all looks like Greek to me. (And some of it really is.) If it's not too much trouble, could someone dumb it down a little (a lot) for me? Digger3000 (talk) 01:34, 23 March 2008 (UTC)

I guess we're talking about the formula:

$\zeta (s)={\frac {e^{(\log(2\pi )-1-\gamma /2)s}}{2(s-1)\Gamma (1+s/2)}}\prod _{\rho }\left(1-{\frac {s}{\rho }}\right)e^{s/\rho }\!$,

where the product is over the non-trivial zeros ρ of ζ and the letter γ again denotes the Euler-Mascheroni constant. (from Riemann zeta function#Hadamard product)

This formula can be useful for calculating the zeta function at certain values where the usual infinite series representation fails to converge. The idea is to just plug 0 in for s in that equation...

• Now, in the numerator of the big fraction, there's a long expression in the exponent that's multiplied by s, so that whole exponent becomes 0, and we have e⁰=1, so the numerator equals 1.
• The denominator is going to equal 2 times -1 times Г(1), where that last function is the gamma function. It's a matter of calculating an integral to evaluate Γ(1)=1. That gives us a denominator of -2.
• Now there's the thing over to the right of the fraction, which is a product - the capital pi (Π) notation for products is a lot like the capital sigma (Σ) notation for sums, but we're multiplying instead of adding. This particular product will consist of one factor for each non-trivial zero of the zeta function, ρ. When s=0, it doesn't really matter what any of the values are for ρ, because each term in that product will just equal 1.

Thus, when we plug in 0 for s, we obtain $\zeta (0)={\frac {1}{-2}}\cdot 1=-{\frac {1}{2}}.$ Does that help? -GTBacchus^(talk) 02:43, 23 March 2008 (UTC)

Well, technically, that shows that it either equals -1/2 or 0 - if it's 0, the product is undetermined, so anything can happen. Presumably there is an alternative way of showing it's non-zero. --Tango (talk) 02:48, 23 March 2008 (UTC)

How's that? Aren't all the factors in the product equal to 1? -GTBacchus^(talk) 02:57, 23 March 2008 (UTC)

If 0 is a zero of the function, then one of the factors will have a 0/0 in it. (Although, I note you said the product is over the non-trivial zeros, I'm not quite sure what trivial means in this context.) --Tango (talk) 03:16, 23 March 2008 (UTC)

After looking it up, trivial means negative even integers, so 0 presumably wouldn't count as trivial. --Tango (talk) 03:17, 23 March 2008 (UTC)

Ah, I see. Thank you. -GTBacchus^(talk) 03:20, 23 March 2008 (UTC)

Well, I still have a lot to learn about things like integrals and such, but that does make it a lot clearer. Thank you. Digger3000 (talk) 03:26, 23 March 2008 (UTC)