Wikipedia:Reference desk/Archives/Mathematics/2009 November 6

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.

November 6

Counterexample

Could anyone suggest a nice example of a continuously differentiable function on R^2 which has only 1 stationary point - a local minimum (or maximum), but which is not a global minimum (or maximum)?

I keep looking for functions with minimum at 0,0 but I can't seem to find anything which increases locally in all 4 directions, i.e. along both axes, and yet doesn't produce any more stationary points when it eventually decreases somewhere. I found one in a paper by Ash and Sexton but it was quite unpleasant and I was hoping to find something nice and neat. Any ideas?

Thanks. 82.6.96.22 (talk) 00:50, 6 November 2009 (UTC)

I think (x³ - x)e^y + e^2y works. Rckrone (talk) 01:31, 6 November 2009 (UTC)

As an aside, increasing along both axes doesn't guarantee a local min. For example x⁴ + y⁴ - (x+y)⁴/4 - (x-y)⁴/4 has only a saddle point at (0, 0). Rckrone (talk) 02:02, 6 November 2009 (UTC)

In polar coordinates: unless I misunderstand your question or am not thinking straight, try

$f(r,\theta )=r^{2}\,\cos \,r$

That should have a local minimum at the origin but oscillate unboundedly as you get further away. 69.228.171.150 (talk) 06:10, 6 November 2009 (UTC)

A further note. Consider a diffeo h of Rⁿ with an open subset A of Rⁿ itself, for instance a ball, h:Rⁿ→A. If f: Rⁿ→R is any differentiable function, the composition g(x):=f(h(x)) is a differentiable function whose critical set has the same structure (same number, index, nullity, level) of the critical points of f in A. Of course, the latter may be whatever. If the global max and min points of f belongs to the boundary of A, then g has also the same sup/inf as f. So for instance there is a function on Rⁿ with critical points of prescribed level, index, and cardinality, and the interval f(Rⁿ) may also be prescribed. --pma (talk) 09:35, 6 November 2009 (UTC)

With regards to :$f(r,\theta )=r^{2}\,\cos \,r$, would that not have more than 1 stationary point though? 82.6.96.22 (talk) 14:23, 6 November 2009 (UTC)

Oh yes, I did misunderstand. Hmm, I'll think about whether I can fix it by suitably twisting up the shape while keeping the equations reasonably neat. 69.228.171.150 (talk) 22:50, 6 November 2009 (UTC)

Try this section of the maxima and minima article. It says that ƒ : R² → R given by ƒ(x,y) = x² + y²(1 − x)³ has its only critical point at x = y = 0 but that this isn't a global minimum because ƒ(4,1) = −11 < ƒ(0,0) = 0. ~~ Dr Dec (Talk) ~~ 15:44, 6 November 2009 (UTC)

Polynomials

When you say R[x]/<x^2+1> is isomorphic to the complex numbers, do you mean that because [x]^2+[1]=[0], where the brackets denotes the respective equivalence classes, and x is the polynomial f(x)=x? Is the following correct: [x]^2=[x^2] and hence [x]^2+[1] = [x^2+1] = [0], so [x] is like the imaginary unit? Najor Melson (talk) 05:38, 6 November 2009 (UTC)

If R is a ring and if I is an ideal of R, the map sending r to the coset r + I is a surjective ring homomorphism. In particular, using your notation, [x]² = [x²] is true, as well as your other assertions. Consider the surjective homomorphism defined on R[x] that sends a polynomial f to its image at i (the imaginary unit). Since R[x] is a principal ideal domain, and since x² + 1 is irreducible over the real numbers, the kernel of this homomorphism is generated by x² + 1. In particular, $\mathbb {C} \simeq \mathbb {R} [X]/(X^{2}+1).$. Furthermore, since the image of x under this isomorphism is i, x does indeed "act like i" in the given quotient ring (ismorphisms preserve the behaviour of elements). Hope this helps. --PST 05:53, 6 November 2009 (UTC)

It means not only that [x]^2+[1]=[0], but more generally there is a one-to-one correspondence between these equivalence classes and the complex numbers, such that multiplication and addition of equivalence classes correspond exactly to multiplication and addition of complex numbers. Michael Hardy (talk) 16:58, 6 November 2009 (UTC)

ordinal strength

The ordinal strength of PA is ε₀. How does one figure it out for PA+Con(PA)? Thanks. 69.228.171.150 (talk) 08:36, 6 November 2009 (UTC)

It depends on the particular way you choose to measure ordinal strength. There is a trivial answer for measures based on computable functions, such as the smallest ordinal α such that every provably total computable function is β-recursive for some β < α: since the set of p.t.c.f. of a theory is unaffected by addition of true $\Pi _{1}^{0}$-sentences, PA + Con(PA) has the same ordinal as PA, ε₀, in this measure. I'm afraid the answer is more complicated for measures sensitive to the $\Pi _{1}^{0}$-fragment of the theory. For example, the $\Pi _{1}^{0}$-ordinal measure by Beklemishev[1][2] gives ε₀·2 for PA + Con(PA). — Emil J. 16:03, 7 November 2009 (UTC)

Thanks, that's interesting. I am naive about this stuff and thought that Gentzen had shown that PA couldn't prove ε₀ was well-ordered, but that adding TI(ε₀) was enough to prove Con(PA), so the ordinals had to be different. The Beklemishev article looks informative and I'll try to read it. 69.228.171.150 (talk) 21:06, 7 November 2009 (UTC)

It is true that PA cannot prove ε₀ was well-ordered, and that primitive recursive arithmetic plus transfinite induction on ε₀ proves PA is consistent. The thing that is not obvious (or perhaps non-intuitive) is that if you add Con(PA) to PA as an axiom, you obtain no new provable ordinals. This is because the two measures of logical strength, namely:

1. T is stronger than S if T proves Con(S)
2. T is stronger than S if the proof-theoretic ordinal of T is higher than the proof theoretic ordinal of S

are not actually equivalent. I do not even know if there is a theorem that (2) implies (1) for some broad class of theories. — Carl (CBM · talk) 13:35, 9 November 2009 (UTC)

TI(ε₀) is a second-order statement. While one often encounters it mentioned sloppily in the context of PA, it only makes sense in second-order arithmetic, or at least arithmetic with an extra uninterpreted predicate, so properly speaking it gives an ordinal analysis of ACA₀ or PA(X) rather than PA. Having said that, this is basically $\Pi _{1}^{1}$-ordinal analysis, which is even less sensitive to additional axioms than the computable functions approach (i.e., $\Pi _{2}^{0}$-analysis) I mentioned above. ACA₀ + Con(PA), as well as ACA₀ + T for any r.e. set T of arithmetical sentences of bounded complexity consistent with PA, has the same ordinal ε₀ as PA in this setting. The reason is that TI(ε₀) implies not only Con(PA), but in fact the full uniform reflection principle for PA. — Emil J. 14:08, 9 November 2009 (UTC)

You can also consider restricted forms of TI as a schema for classes of arithmetical formulas, this works already in the first-order language. If I got the subscripts right, $\Sigma _{n}^{0}$-TI(ε₀) is not provable in any consistent extension of PA by a set of $\Sigma _{n+1}^{0}$-sentences, in particular PA + Con(PA) does not prove $\Sigma _{1}^{0}$-TI(ε₀). — Emil J. 17:06, 9 November 2009 (UTC)

I did get the subscripts wrong, or rather, badly suboptimal. The (hopefully) correct property is that for any n ≥ 0, $\Sigma _{n}^{0}$-TI(ε₀) is equivalent to $\Pi _{n+1}^{0}$-TI(ε₀), which is in turn equivalent to $\Pi _{n+3}^{0}$-RFN(PA), and consequently is not provable in any consistent extension of PA by a set of $\Sigma _{n+3}^{0}$-sentences (whereas it is easy to see to be expressible as a single $\Pi _{n+3}^{0}$-sentence). In particular, already $\Delta _{0}^{0}$-TI(ε₀) is unprovable in PA + Con(PA) (or in any consistent extension of PA by $\Sigma _{3}^{0}$-sentences). — Emil J. 13:05, 10 November 2009 (UTC)

Thanks, I just spotted the after-Nov-7 posts. I didn't realize that PA and PA+X could have the same ordinal if PA doesn't prove X. It is counterintuitive because of the natural picture of these theories being well-ordered as you add or take away axioms. I also hadn't thought much about how to formalize TI(ε₀). The book I was reading [3] may have handwaved it, but I'll go back and see if I can figure it out. 69.228.171.150 (talk) 03:51, 12 November 2009 (UTC)

Birth and Death Chain - Markov Processes

Hi all :)

I asked this a while ago but never got an answer, hopefully someone might be able to help me this time. For a fairly simple birth-death chain (1D, with probabilities $p_{i}=({\frac {i+1}{i}})^{k}q_{i}$, $p_{01}=1$, $p_{i}+q_{i}=1\forall \,i$ of moving in each direction at node i), what's the easiest way to find (*) P(X_n-> infinity as n -> infinity) - e.g. should I be looking at the expected time of something as n tends to infinity, or P(X_n<k) as n tends to infinity, or the transition matrix P^n etc? Hopefully once I know a sensible way to show (*), the actual question will be fairly simple.

Thanks a lot, Otherlobby17 (talk) 16:28, 6 November 2009 (UTC)

Could you describe the problem in more words? For example, what is k? 69.228.171.150 (talk) 23:00, 6 November 2009 (UTC)

I want to find it for values of k in $(0,\infty )$ - is there a general formula of any sort? Initially I want to show that the probability is 1 for k=2, but then I've been asked to find the formula for a general k in the positive reals - why, is that not feasible? Other than the $p_{i}=({\frac {i+1}{i}})^{k}q_{i}$, $p_{01}=1$, $p_{i}+q_{i}=1\forall \,i$ formulae, I don't really have anything else to explain unfortunately, I mean it's a markov chain along a line (natural numbers, say) with probabilities p_ij of moving from i to j. Sorry but that's pretty much the whole problem! Otherlobby17 (talk) 15:06, 7 November 2009 (UTC)

It seems you'll have to explain your notation even further. Specifically, your formula for $p_{i}$ has no mention of $j$, and your $q_{i}$ is not given any meaning. Is $k$ one of the states, or some constant? What exactly do all of these labels mean? Nm420 (talk) 18:44, 7 November 2009 (UTC)

I'm pretty sure what the OP means is that when the state is currently at i, p_i is the probability of it moving to i+1, and q_i is the probability of it moving to i-1. No other moves are allowed. Referring to the notation in Birth-death process, p_i = λ_i and q_i = μ_i. k is just a constant as the OP said. The answer to the question presumably depends on k. Sorry I don't have any insight into solving the problem. Rckrone (talk) 19:20, 7 November 2009 (UTC)

That makes some sense, though I'm afraid there's little aid I can provide in this problem as well. Since the chain is irreducible, all states are either transient or recurrent; that is, the probability that $X_{n}\to \infty$ is either 0 or 1. If you can show under what conditions state 0 (say) is transient, then you will be done. 97.83.155.87 (talk) 20:54, 7 November 2009 (UTC)

Apologies, I assumed this was fairly standard notation but was obviously mistaken. Yes, at state i (i=0,1,2,...) we may move left by 1 state with probability q_i (or P_i,i-1 if you prefer to talk about the transition matrix) and right by 1 state with probability p_i (P_i,i+1) - p_i+q_i=1, so we have only these 2 options at each stage. The relation between p_i and q_i is the one given above involving k, and I want to find a solution based on the value of k, which is somewhere in (0,infinity) (I am first asked to prove the result is P(X_n-> infinity as n -> infinity)=1 for k=2, and then asked for general k, but obviously the general case would solve my first problem anyway, unless you need the result at k=2 to prove the general case) - when I mentioned p_i,j above, what i meant was the probability of moving from i to j - nonzero iff j=i±1, in this case. Does that make sense?

Also, I follow what you say about all states being either transient or recurrent, but how does that necessarily imply that the probability that $X_{n}\to \infty$ is either 0 or 1? Thanks very much all :) Otherlobby17 (talk) 20:59, 7 November 2009 (UTC)

If a state were recurrent, then the probability of the process returning to it in a finite amount of time is 1; obviously the process cannot return to any particular state if it is growing without bound. That is the intuitive idea behind it anyhow. 97.83.155.87 (talk) 22:06, 7 November 2009 (UTC)

If a state is recurrent then the probability of the sequence going to infinity is zero, but if all the states are transient, couldn't the probability of the sequence going to infinity still be less than 1? I don't see why it would have to be restricted to 0 or 1 either. Rckrone (talk) 05:57, 8 November 2009 (UTC)

If all the states are transient, meaning that for any j in N the set $\scriptstyle \{n\in \mathbb {N} \ :\ X_{n}=j\}$ is finite almost surely, then (by sigma-additivity) $X_{n}$ is almost surely a sequence of naturals that takes each value finitely many times, therefore diverges to $\scriptstyle +\infty$. Following 97.83 directions, I guess one should start by computing or bounding the probability to go back to 0 after the time n; it's the corner coefficient $p^{(n)}(0,0)$ in the n-fold power of the associated infinite matrix

$M:={\begin{bmatrix}0&1&0&0&\quad 0&\cdots \\1-p_{1}&0&p_{1}&0&\quad 0&\cdots \\0&1-p_{2}&0&p_{2}&\quad 0&\cdots \\0&0&1-p_{3}&0&\quad p_{3}&\cdots \\\cdot &\cdot &\cdot &\cdot &\cdot \end{bmatrix}}.$

However it seems difficult to do it for the given $p_{j}$. But for instance, if one finds $\scriptstyle \sum _{n\geq 1}p^{(n)}(0,0)<1,$ then 0 has to be transient, as the latter value is a bound for the probability that $X_{n}=0$ for at least one n>0 (a more precise bound may be obtained via the inclusion-exclusion formula also). In the lack of better ideas, I'd suggest to make some numerics with various choices of the parameter k (note that $\scriptstyle p^{n}(0,0)$ only depends on the first n/2 values of $p_{j}$ or so) . --pma (talk) 15:28, 8 November 2009 (UTC)

Help with Logic Problem

I think i've made progress, but I'm stuck--I was hoping for a nudge in the right direction

I'm only allowed to use the 18 valid argument forms.

Here's what I have so far

1. A≣B (premise)
2. ~(A ⋅ ~R) ⊃ (A ⋅ S) (premise) /∴ ~(B ⋅ S) ⊃ ~(A ⋅ R)
3. (A ⊃ B) ⋅ (B ⊃ A) 1 EQUIV
4. A ⊃ B 3 SIMP
5. (A ⋅ ~R) v (A ⋅ S) 2 IMP
6. A ⋅ (~R v S) 5 DIST
7. A 6 SIMP
8. B 7, 4 MP
9. ~R v S 6 SIMP

but now i'm completely stuck! I have a sneaking suspicion that ADD might help......UGH, any thoughts?

sorry for the double post, i fixed the formatting209.6.48.226 (talk) 18:41, 6 November 2009 (UTC)

Well, "the 18 valid argument forms" doesn't really ring a bell — you should know that which inference rules are taken as basic is something that varies by presentation. There's a good chance that the specific list of inference rules and their names/acronyms is particular to, perhaps, even just the one professor from whom you're taking the course. It's also possible that this is some more widely recognized list that someone else can help you with, just not me. But it's very far from universal, and you should be aware of that. --Trovatore (talk) 20:24, 6 November 2009 (UTC)

I hadn't heard of 18 valid argument forms either, but there are a few ghits. 69.228.171.150 (talk) 20:40, 6 November 2009 (UTC)