Wikipedia:Reference desk/Archives/Mathematics/2009 August 13

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.

August 13

Absolute continuity

Assume f is a real-valued continuous of bounded variation on [0, 1], and f is absolutely continuous on every interval [a, 1] for 0 < a < 1. Prove f is absolutely continuous on [0, 1]. Can any one help me out a bit? Thanks StatisticsMan (talk) 00:19, 13 August 2009 (UTC)

This may be overkill, but any function of bounded variation on the line is decomposable as the sum of an absolutely continuous function, a continuous function whose derivative is 0 almost everywhere but is not constant, and a collection of jump discontinuities. Since your function is continuous of bounded variation, it must be the sume of an absolutely continuous function and a continuous function whose derivative is 0 almost everywhere but is not constant. The latter function is 0, so therefore the function itself must be absolutely continuous. (see, for example, Stein's Real Analysis, Chapter 3). Ray^Talk 02:33, 13 August 2009 (UTC)

How can the latter function be 0 if you have specified that it is not constant? --Tango (talk) 02:43, 13 August 2009 (UTC)

Oops. Amend to "not necessarily." Ray^Talk 03:21, 13 August 2009 (UTC)

You can argue that the total variation of f on the interval [0, a] goes to zero as a goes to zero. That said, for any ε>0, choose a so that the total variation on [0, a] is less than ε/2, and choose a δ like you normally would on [a, 1] for ε/2. I think that should work. Rckrone (talk) 02:46, 13 August 2009 (UTC)

Actually, I have a solution for the method you are talking about Rckrone (as in someone else's solution). And, I think I understand everything after what you just said. But, showing that the total variation goes to zero as a goes to zero is the part I don't get. All this solution says is since f is continuous at 0, $\sum _{i=1}^{n}|f(x_{i})-f(x_{i-1})|$ goes to 0 as a goes to 0 (where the x_i's come from some partition of [0, a] of course). But, I don't get that. StatisticsMan (talk) 03:02, 13 August 2009 (UTC)

Well if the total variation g is bounded and continuous on [0, 1], then the limit of g(x) as x goes to 0 must be g(0). Rckrone (talk) 03:35, 13 August 2009 (UTC)

Okay, Royden doesn't define the total variation as a function, though I have seen this in other books. So, I will check that out. Thanks! StatisticsMan (talk) 16:12, 13 August 2009 (UTC)

Hmm, okay, so I only found such a function in one of my undergrad books (not in my two graduate books) and it doesn't say that the total variation function is continuous. It does say that if the total variation function is continuous at a point, then the function itself is continuous at that same point... but nothing about the other way around. And, what you say makes sense that it would be true, but I don't understand exactly why. StatisticsMan (talk) 01:15, 15 August 2009 (UTC)

RMK: for a BV function f on [a,b] it is true that the total variation of f on [a,x] is continuous at x if and only if f is continuous at x. For an elementary proof see e.g. G.Choquet's "Cours d'Analyse" (t.2, Topologie). I do not have in mind an English reference in this moment. Another way to prove the original statement is via the fundamental theorem of calculus for AC functions: you can rephrase the original problem in terms of the (a.e.) derivative g of the function f. It translates into the easy: "If g is measurable on [0,1] and $\scriptstyle \int _{a}^{1}|g(x)|dx\leq M<+\infty$ for 0 < a < 1, then g is integrable on [0,1]". --pma (talk) 14:43, 15 August 2009 (UTC)

I'll just take your word on $T_{a}^{x}(f)$ being continuous at x if and only if f is. Thanks! As far as your translation, it does look like it's pretty much immediate to prove. But, I don't see exactly where it comes from. Hmm, maybe I'm beginning to get it. I'll try to work it out the first way and keep thinking about the second! Thanks. StatisticsMan (talk) 17:53, 15 August 2009 (UTC)

The fact behind is that for an absolutely continuous $\scriptstyle f:[a,b]\to \mathbb {R}$ one has $\scriptstyle T_{a}^{b}(f)=\int _{a}^{b}|f'(x)|dx$. (By the way, this formula holds true for Rⁿ valued functions, and any given norm $\scriptstyle |\ |$ on Rⁿ). --pma (talk) 19:03, 15 August 2009 (UTC)

I think I get that, but showing g is integrable is equivalent to showing f is absolutely continuous? StatisticsMan (talk) 20:43, 15 August 2009 (UTC)

Sure. A function $\scriptstyle f$ is AC on [a,b] if and only if it is of the form

$\scriptstyle f(x):=\int _{a}^{x}g(t)dt+c$ for all x in [a,b], for some $\scriptstyle g$ in L¹([a,b]), in which case $\scriptstyle g(x)$ is unique a.e., in fact $\scriptstyle g(x)=f'(x)$ a.e., and $\scriptstyle c=f(a$). Here, changing a bit the hypotheses into:

"Assume $\scriptstyle f$ is a real-valued continuous of bounded variation on [0,1], and $\scriptstyle f$ is absolutely continuous on every interval [0,a] for 0<a<1, we have immediately that

$\scriptstyle f(x):=f(0)+\scriptstyle \int _{0}^{x}g(t)dt$ for all $\scriptstyle 0\leq x<1$;

moreover $\scriptstyle \int _{0}^{x}|g(t)|dt=T_{0}^{x}(f)\leq T_{0}^{1}(f)<+\infty$ for all $\scriptstyle 0\leq x<1$. This implies (by Beppo Levi's theorem) that $\scriptstyle g$ is in L¹([0,1]), that is what we had to show (well, the last point is proving the equality

$\scriptstyle f(x):=f(0)+\scriptstyle \int _{0}^{x}g(t)dt$ for x=1 too, but that follows because it holds true for x<1 and by continuity of both sides: the LHS by hypothesis, the RHS because g is in L¹([0,1]) ). --pma (talk) 12:13, 16 August 2009 (UTC)

Well, that solution is much nicer, easier, simpler than the other one! Thanks. StatisticsMan (talk) 15:54, 16 August 2009 (UTC)

What's Beppo Levin's Theorem? I could also just say that since $f\in BV[0,1]$, then $f'$ exists a.e. and is measurable (this is true for monotone functions), and $\int _{0}^{1}|f'|\leq T_{0}^{1}<\infty$, so $f'$ is integrable. Then the function $\int _{x}^{1}f'(t)\,dt$ is absolutely continuous. StatisticsMan (talk) 16:13, 16 August 2009 (UTC)

Yes you can. Like this it's even better and more clear because $\scriptstyle \int _{0}^{1}|f'|\leq T_{0}^{1}<\infty$ is true for any BV[0,1] function (the equality holds iff the function is also AC). Beppo Levi's theorem: aka Lebesgue monotone convergence theorem --pma (talk) 17:50, 19 August 2009 (UTC)

Radius and Volume

A pizza with radius z and a thickness of a has a volume of pi*z*z*a. Is that right? I just read it, and I'm not a mathematician, I'm a linguist. --KageTora - (영호 (影虎)) (talk) 01:57, 13 August 2009 (UTC)

If the pizza's cylindrical, yes. Algebraist 02:00, 13 August 2009 (UTC)

Yum, I could go for a nice slice of $\pi z^{2}a$ right now... 70.90.174.101 (talk) 08:28, 13 August 2009 (UTC)

ordered sets and order types

For well-ordered sets we say the set has an "order type" which we label with an ordinal number. So the natural numbers with the usual order have order type $\omega$, the set of pairs of natural numbers has order type $\omega ^{2}$ etc. But ordinals are all about well-ordering so we can do induction over the sets.

What about just ordinary ordering as opposed to well-ordering? I.e. is there something we'd call an "order type" for the reals and the standard < ordering? What about pairs of reals, etc.? We're not trying to support induction over the whole set, just comparisons between two elements.

I guess this is a question more of terminology than actual math. The objects I want to order are somewhat complicated tree structures with real numbers and some other things stuck in them. I'd like some nomenclature analogous to "order type" that identifies the order relation on a given set of these trees.

Thanks 70.90.174.101 (talk) 08:25, 13 August 2009 (UTC)

I think I've seen the term "order type" applied more generally than to well-orderings. There's no "standard" ordering of pairs of reals; there are many different ways in which they can be ordered. Michael Hardy (talk) 10:38, 13 August 2009 (UTC)

(e/c) In general, an order type of a partial order is an object which identifies the order up to isomorphism. This is somewhat vague description since the actual representation does not matter, but for definiteness you may define the order type of P to be the set of all posets isomorphic to P of minimal rank. — Emil J. 10:42, 13 August 2009 (UTC)

This is Scott's trick. Algebraist 12:40, 13 August 2009 (UTC)

Isn't this talk of "vagueness" and a need for "representation" (which does not matter!) and "definiteness" and "defining" the thing as a particular "set" (chosen to be of minimal rank...) just a consequence of trying to fit the idea into a particular, not necessarily sacred, theory of sets? It seems to me it's a perfectly good concept that people have qualms about because they feel a need to fit it into that particular theory, and the fact that it takes some work to make it fit should really be viewed as clearly indicating that that particular theory really isn't the last word. Michael Hardy (talk) 14:17, 14 August 2009 (UTC)

I agree. However, the fact that Scott's trick always works for such questions shows that ZF, if not canonical, is at least good enough for this sort of thing. Algebraist 00:53, 15 August 2009 (UTC)

So "order type" is fine for non-wellordered sets, and as Michael notes, we needn't trouble ourselves excessively about details of representation except when we need to for technical reasons. However, there are a couple of reasons that the original poster might not have come across this usage. First, order types of general linear orders don't tell you as much. If two wellorderings have the same order type, then you know not merely that there's an order isomorphism between them, but that this isomorphism is unique.

Secondly, the ordinal numbers are much more important than order types of general linear orders. They're used all over the place; even the intended interpretation of set theory, the von Neumann hierarchy, starts with ordinals before it gets to sets (although it is later shown that ordinals may be represented as sets). Ordinals are in some sense the most concrete sort of object that set theory deals with, this ultra-rigid structure that sticks up like a spine through the set-theoretic universe. As soon as you can pin something down by an ordinal, you feel you have about as good a grasp on it as it is possible to have. --Trovatore (talk) 02:09, 15 August 2009 (UTC)

Vogel's approximate method

The transportation algorithm is applicable to the problem of moving goods from suppliers to customers at least total cost, by determining how much should go on each possible route. The algorithm is akin to the Simplex method of linear programming, but takes advantage of the special structure of a transportation problem by carrying out successive iterations of improvement in a simple table whose rows/columns represent the suppliers/customers and whose cells represent the routes. It is important to get a good initial solution, which Vogel's approximate method does by considering the opportunity cost of not using the cheapest-cost route in each row and column, then allocating as much material as possible to the route which has the highest such value. My question is, who was Vogel and when and where was the method first described? It seems too obvious an idea to have a particular name attached to it, but someone must have thought it worthwhile to do this, and since then the label has stuck.→86.148.186.112 (talk) 16:14, 13 August 2009 (UTC)

The standard reference text seems to be Reinfeld, N V and W R Vogel (1958). Mathematical Programming. Englewood Gliffs, New Jersey: Prentice-Hall. I haven't been able to find any biographical information yet. MuDor (talk) 01:16, 14 August 2009 (UTC)

Sudoku Puzzles

I am curious to determine how many possible ways this digits from 1-9 can be placed in a 9x9 square such that they follow the rules of a sudoku puzzle; i.e., no digits repeated in any 3x3 square, row, or column. How could this be calculated?CalamusFortis 21:50, 13 August 2009 (UTC)

6,670,903,752,021,072,936,960, as stated in Sudoku. Algebraist 22:22, 13 August 2009 (UTC)

This is more thoroughly covered in Mathematics of Sudoku, sections Enumerating Sudoku solutions and Enumeration results. --COVIZAPIBETEFOKY (talk) 22:26, 13 August 2009 (UTC)

Note that this enumeration is a complete enumeration; it considers two grids as different if they have different values in any of their 81 pairs of corresponding cells. Given one grid, you can trivially produce 9! similar grids by permuting the digits 1 to 9. You can also create more grids by rotating, reflecting, permuting horizontal and vertical bands, permuting rows within a horizontal band, and permuting columds within a vertical band. Each of these "similar" grids is counted as different in the complete enumeration. Gandalf61 (talk) 12:14, 14 August 2009 (UTC)

If similar grids are counted as the same, the number of solutions is 5,472,730,538. — Emil J. 12:18, 14 August 2009 (UTC)