Wikipedia:Reference desk/Archives/Mathematics/2010 March 7

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 7

How to do a Recurrence plot

I would like to do a recurrance plot using some time series data I have. I do not understand the deatail of the article's maths. Would anyone like to try to explain to me, a non-mathematician, how to do this simply? Pseudocode if you like, but not computer languages which I don't understand apart from Basic. Thanks 84.13.166.170 (talk) 01:17, 7 March 2010 (UTC)

No answers yet so perhaps I can ask a question of less scope please. In the example Recurrence plot of the Southern Oscillation index, the X axis is from 1880 to 1980, and the Y axis is also from 1880 to 1980.

What determines if a dot is put on the X,Y coordinate or not? Would it mark all years that had the same amplitude as particular years? Thus for 1880 you simply make a mark on the Y axis for years that had the same amplitude as 1880 (within whatever band of tolerance you set)? And then repeat that procedure for all the years along the X axis. Thanks. 89.242.102.148 (talk) 13:29, 7 March 2010 (UTC)

Yes, there is a dot at (X, Y) if the value of the series at time Y is close to that at time X. -- Meni Rosenfeld (talk) 14:38, 7 March 2010 (UTC)

Look at http://www.recurrence-plot.tk/glance.php?show_intro=1 for simple introduction of recurrence plots (a flash animation!).

Simplifying Trig Identities

Given: (cos²x / sin x) + sin x (1)

And

cot²x + 1= csc²x (2)

Then

(1)= cosx cot x + sin x (3)

How to proceed to simplify (1) to the fullest extent? 192.148.117.79 (talk) 05:34, 7 March 2010 (UTC) —Preceding unsigned comment added by 192.148.117.81 (talk) 05:30, 7 March 2010 (UTC)

You don't need the thing you wrote after "and".

${\frac {\cos ^{2}x}{\sin x}}+\sin x=\cos x\left({\frac {\cos x}{\sin x}}\right)+\sin x=\cos x\cot x+\sin x.$

Michael Hardy (talk) 06:06, 7 March 2010 (UTC)

Yes, that's to help as is the simplification after the "then", my question is where to go after (3)? Alternately, ignoring (2) and (3) how to simplify (1) to the fullest extent? 192.148.117.79 (talk) 06:04, 7 March 2010 (UTC)

OK, you're adding fractions, so use a common denominator, which is sin x:

${\frac {\cos ^{2}x}{\sin x}}+\sin x={\frac {\cos ^{2}x}{\sin x}}+{\frac {\sin ^{2}x}{\sin x}}={\frac {\cos ^{2}x+\sin ^{2}x}{\sin x}}={\frac {1}{\sin x}}.$

Michael Hardy (talk) 06:14, 7 March 2010 (UTC)

Undefinability by any "almost-pure identity" formula (of first-order):

Let the domain of discourse be the class of real numbers.

1. Can one prove that there's no definition (even no implicit definition) formulated by a first-order formula which:

• Contains no free variables, and contains logical symbols only (including identity), except for one function-symbol interpreted (in advance) as the Sine function, and another function symbol to be defined by that formula as the Cosine function...?

2. Can one prove that there's no bijection - from the set of (continuous) Arccosine functions - to the set of (continuous) Arctan functions, so that the bijection is induced by a first-order formula which:

• Contains no free variables, and contains logical symbols only (including identity), except for one function-symbol interpreted (in advance) as an Arccosine function, and another function symbol interpreted (in advance) as an Arctan function?

3. Is there any mathematical realm which deals with similar questions?

4. With regard to questions like those mentioned above, is there a specific term for what I've called: "almost-pure identity" formulas (i.e. formulas fulfilling requirements similar to those mentioned above)?

HOOTmag (talk) 09:08, 7 March 2010 (UTC)

The question of definability over the real numbers is exhaustively studied in model theory. It is very sensitive to the language you work in. For example,

cos(x) = sin(x +π/2)

is a perfectly good definition of cosine. If you want to get rid of the π you can do that by defining π as the smallest positive root of the sin function (which you apparently took as a given). If you only want to allow the sin function and equality, but not any of the arithmetical operations, then I have no idea whether it's definable or not. You'd need to work that out on your own; it's unlikely to be in any model theory text because it's not a very natural question from the modern model-theoretic point of view. This is because there's not much point in saying you're studying "real numbers" if you don't include any of the arithmetical operations on them. You're really just studying an infinite set with an infinite-to-one map. — Carl (CBM · talk) 12:04, 9 March 2010 (UTC)

You've probably meant: (x)(cos(x) = sin(π/2-x)), right?

I couldn't figure out what you mean by:

• "there's not much point in saying you're studying 'real numbers' if you don't include any of the arithmetical operations on them".

Of course I do include the arithmetical operations on the real axis, however I don't let my formula include them. To make it clearer why I do think there is much point in asking my original question (whether there is such a formula), notice the difference between a trial to define the cosine function by the sine function, and a trial to define the "ln" function by the "exp" function: In the latter case, there does exist (what I've called): an "almost-pure-identity" formula, namely: "(x)(ln(exp(x))=x)"; Note that this formula involves logical symbols only (except for the symbols for the definiens and the definiendum). Also, notice the difference between a trial to induce a bijection from the set of continuous Arccosine functions to the set of continuous Arctan functions, and a trial to induce a bijection from the set of continuous Arccosine functions to the set of continuous Arcsine functions: In the latter case, there does exist (what I've called): an "almost-pure-identity" formula, namely: "(∃x)(Arcsin(x)=Arccos(x))"; Note that this formula involves logical symbols only (except for the symbols interpreted in advance as the Arcsine and the Arccosine).

Ok, so I see that model theory can't help me. I'm almost convinced that there is a mathematical realm discussing questions similar to mine, but I haven't found it yet.

HOOTmag (talk) 13:47, 9 March 2010 (UTC)

The mathematical realm you are looking for is model theory, it's just that you are imposing strange restrictions on the problem which go a long way towards ensuring that no one has investigated that particular question before. If you don't let your formula use arithmetical operations, your are looking for a formula in the language of the structure consisting of a set of cardinality of continuum with one unary function, and this structure does not include arithmetical operations. This is the meaning of "include" Carl had in mind. If you do that, there's nothing really ensuring that the structure has anything to do with real numbers, it can be an arbitrary set of the same cardinality. Asking whether a function f on the reals is definable using +, ×, and a function g is an interesting question, and therefore a lot of people studied it. Asking whether a function f on a set of particular cardinality is definable from another function g (only) is a much less interesting question.—Emil J. 15:45, 9 March 2010 (UTC)

Anyway, the permutation of R which exchanges π with 2π and leaves other numbers intact is an automorphism of $\langle \mathbb {R} ,\sin \rangle$ (because $\pi ,2\pi \notin \operatorname {ran} (\sin )$ and sin(π) = 0 = sin(2π)), but it is not an automorphism of $\langle \mathbb {R} ,\cos \rangle$. It follows that cos is not first-order definable in $\langle \mathbb {R} ,\sin \rangle$, explicitly or implicitly (and the same holds for second- or higher-order logic, infinitary logic, and in fact pretty much any other logic one can think of).—Emil J. 16:23, 9 March 2010 (UTC)

How about defining surjections by each other? e.g. to prove the undefinability of the function f (where f(x) = x³) - from the function g (where g(x) = x⁵) - using no symbols other than: f,g and the logical symbols? HOOTmag (talk) 17:25, 9 March 2010 (UTC)

The non-surjectivity of sin happened to be convenient in that example, but it's perfectly possible to construct nontrivial automorphisms of surjective functions as well. In this particular case, let h be the bijection such that h(2⁵ⁿ) = 2⁵ⁿ⁺¹ = g(2⁵ⁿ) for every integer n, and h(x) = x for numbers x not of this form. On the one hand, h is a bijection and h(g(x)) = g(h(x)), thus h is an automorphism of $\langle \mathbb {R} ,g\rangle$. On the other hand, 8 = h(f(2)) ≠ f(h(2)) = 32768, thus h is not an automorphism of $\langle \mathbb {R} ,f\rangle$, and f is not definable from g.—Emil J. 18:44, 9 March 2010 (UTC)

To sum up: If I'd like to prove that a given surjection f (on a given domain) is not definable - from a given surjection g (on that domain) - using no symbols other than: f,g and the logical symbols, then I'll have to find a bijection h (on that domain), such that the composition hg is the same as the composition gh, while the composition hf is not the same as the composition fh.

Is this also the case when f has two variables (f being surjective whenever one of its variables becomes a given constant)? Or should I have then to find a corresponding bijection h for every constant which is substituted for a given variable of the function? i.e. have to prove that for every x there is a bijection h and a number y such that hg = gh but h(f(x,y)) ≠ f(x,h(y)), and also to prove that for every y there is a bijection h and a number x such that hg = gh but h(f(x,y)) ≠ f(h(x),y)?

HOOTmag (talk) 20:21, 9 March 2010 (UTC)

They don't have to be surjections, that's completely irrelevant to the issue. In the general case, h has to be an automorphism of the structure, i.e., a bijection of the domain onto itself such that h and h⁻¹ are both homomorphisms (for structures with only functions and no predicates, the condition on h⁻¹ is redundant). For binary functions this means that h is a bijection and h(g(x,y)) = g(h(x),h(y)) for every x, y, but h(f(x,y)) ≠ f(h(x),h(y)) for some x, y. Also, note that this condition is sufficient to prove non-definability, but it is not necessary. It is possible that there is no such automorphism, but f is still not definable from g (one reason being that invariance under isomorphism is a property of a much more general concepts of definability than just first-order definability, as I already mentioned above). Indeed, with more complicated functions it often happens that the structure has no nontrivial automorphism: that's the case of $\langle \mathbb {R} ,+,\cdot \rangle$ for instance.—Emil J. 11:58, 10 March 2010 (UTC)

1. Thank you for your instructive responses, which helped me a lot.
2. In my last posts I've been referring to surjections only (including bijections), and I still am.
3. As you've probably noticed already, I've always been referring to structures containing no predicates.
4. Note that - when referring to non-definablity - I'm interested in proving that no definition is possible, whether explicit or implicit.
5. To sum up what I've learnt from you: even when the functions f,g aren't unary, I simply have to find a bijection h, such that the composition hg is the same as the composition gh, while the composition hf is not the same as the composition fh. Is that correct?
6. How about structures containing more than one function, say, two functions: g,G (and again: no predicates, while f can't be defined from those functions)? What I'm learning from you, is that I simply have to find a bijection h, such that the composition hg is the same as the composition gh, and also the composition hG is the same as the composition Gh, while the composition hf is not the same as the composition fh. Is that correct?
7. What do you mean by "the condition on h⁻¹ is redundant"? Do you mean that once I find such an appropriate bijective homomorphism h - then I'll automatically find out that also h⁻¹ is factually a homomorphism, or you simply mean that even when h⁻¹ is not a homomorphism, still the very existence of the bijective homomorphism h is sufficient for proving non-definability?
8. Is there any 'necessary and sufficient' condition to prove non-definability (for structures containing no predicates)?
9. I think that the most related issue in Wikipedia is this. However, it doesn't deal with non-definability, although it does deal with general structures, including structures which have no arithmetical operations (and no relations).

HOOTmag (talk) 13:47, 10 March 2010 (UTC)

Ad 5: What you write does not make sense. If D is the domain, you have h: D → D and g: D^k → D for some k ≥ 2. The composition gh (or hg if you write composition in postfix order) is thus undefined. You can only compose functions if the codomain of the inner function is the domain of the outer function.

Ad 6: Yes, apart from the composition problem above.

Ad 7: I mean that if h is a bijective homomorphism then h⁻¹ is automatically also a homomorphism (in structures with only functions).

Ad 8: A function (or predicate, it makes no difference) f is not first-order definable in a structure A if and only if there exists an elementary extension $\langle A',f'\rangle$ of the expanded structure $\langle A,f\rangle$ and an automorphism h of A' which does not preserve f'. I think you may even assume that the elementary extension is an ultrapower, but I'm not entirely sure of that.—Emil J. 15:12, 10 March 2010 (UTC)

Thank you again, Emil.

By the composition gh, I of course meant that for every variable of g one substitutes what h returns for that variable. Yes, I know this doesn't fit the regular definition of a composition, however I afforded to use this abbreviation as I was sure you'd figure out what I meant.

Do you think that your claim in #8 can easily be proved by simply using Godel's completeness theorem? If not, then where can I find some information on that (i.e. a proof and the like)? Wikipedia says nothing...

HOOTmag (talk) 17:04, 10 March 2010 (UTC)

I don't recall seeing it formulated in this exact form, but it can be shown easily using standard model theoretic tools. The right-to-left direction follows immediately from the definitions, using the fact that isomorphisms preserve satisfaction. As for the left-to-right direction: first, it is much less messy to work it out for predicates, so let me assume that P is a predicate (the case of f being a function is equivalent to taking its graph as a predicate) undefinable in A. By compactness (or completeness, if you wish), there exists an elementary extension $\langle A',P'\rangle$ of $\langle A,P\rangle$ and sequences ${\vec {a}},{\vec {b}}$ of elements of A' such that $P'({\vec {a}})$, $\neg P'({\vec {b}})$, and $A'\vDash \phi ({\vec {a}})\leftrightarrow \phi ({\vec {b}})$ for every formula in the language L of A. There exists a strongly ω-homogeneous elementary extension A'' of A', hence there exists an automorphism h of A'' such that h(a_i) = b_i for each i. By Robinson's joint consistency theorem, $\langle A'',{\vec {a}},{\vec {b}},h\rangle$ and $\langle A',{\vec {a}},{\vec {b}},P'\rangle$ have elementary extensions whose reducts to $L_{{\vec {a}},{\vec {b}}}$ are isomorphic. These can be combined to a model $\langle A''',P''',h'\rangle$ such that $\langle A''',P'''\rangle$ is an elementary extension of $\langle A',P'\rangle$, and h' is an automorphism of $A'''$ such that h'(a_i) = b_i. The latter guarantees that h' does not preserve $P'''$. You should be able to find the stuff I used in the argument in any model theory textbook, such as Hodges' "A shorter model theory", or the classic Chang&Keisler's "Model theory".—Emil J. 19:18, 10 March 2010 (UTC)

I believe this result, or one very similar, is called "Svenonius' theorem" in the literature. — Carl (CBM · talk) 03:14, 11 March 2010 (UTC)

Thank you for this additional information. HOOTmag (talk) 10:19, 11 March 2010 (UTC)

So, the left-to-right direction isn't so trival; that's interesting!

Back to one of my original questions: Let's take the right-to-left direction, which is trivial - as you've pointed out. As you (and Carl) had indicated, Model Theory uses such tools for proving the impossibility of defining (in a given structure) some given functions / predicates. Intuitively, do you think you can use similar tools for proving the impossibilty of bijecting / surjecting / injecting / mapping (by a first order formula which can be formulated in every language of any structure of a given form) from a given set to another given set (even when their cardinality permits such a correspondence between them), rather than for proving the impossibility of defining (in a given structure) some given functions / predicates?

For example, Let F be the set of all functions f of the form f(x)=x³ⁿ, and let G be the set of all functions g of the form g(x)=x⁵ⁿ, for a natural n. Intuitively, can you think of any tool (e.g. a tool similar to those tools used in Model Theory), which may enable us to prove the impossibilty of surjecting / injecting from F to G, by a first order formula which can be formulated in every language of any structure of the form $\langle \mathbb {R} ,f,g\rangle$? Note that it is just an example, and I'll welcome any simpler example (provided that the functions f,g are total, and the sets F,G have the same cardinality, or any cardinality which permits the very surjection / injection).

HOOTmag (talk) 10:19, 11 March 2010 (UTC)

Here is a much simpler example:

Let S be the set of all polynomials f,g. Note that each one of the function-symbols f,g is to be interpreted as a polynomial. Intuitively, can you think of any tool (e.g. a tool similar to those tools used in Model Theory), which may enable us to prove the impossibilty of surjecting / injecting from S to itself, by a first order formula which can be formulated in every language of any structure of the form $\langle \mathbb {R} ,f,g\rangle$, when ignoring the trivial identity bijection - which of course can be induced by the formula (x)(f(x)=g(x))?

HOOTmag (talk) 16:44, 11 March 2010 (UTC)

Much less interesting? "Interest" is a relative concept: whatever may seem to be boring in your view - may seem to be interesting in other people's view... :)

Back to my original question:

I can ask whether the function ln on the real numbers is definable using logical symbols only - plus a function-symbol interpreted in advance as the exp function; The answer is..."Yes", the implicit definition being: "(x)(ln(exp(x))=x)"; However, when I ask whether the function Cosine on the real numbers is definable using logical symbols only - plus a function-symbol interpreted in advance as the Sin function (on the real numbers), the answer is..."No".

Similarly, I can ask whether any bijection - from the set of continuous Arcsine functions (on the real numbers) - to the set of continuous Arccosine functions (on the real numbers), can be induced using logical symbols only - plus two function-symbols interpreted in advance as the Arcsine function and the Arccosine function; The answer is "Yes", the formula being: "(∃x)(Arcsin(x)=Arccos(x)); However, when I ask whether any bijection - from the set of continuous Arcsine functions (on the real numbers) - to the set of continuous Arctan functions (on the real numbers), can be induced using logical symbols only - plus two function-symbols interpreted in advance as the Arcsine and the Arctan, the answer is..."probably no". My problem is with the "probably"...

HOOTmag (talk) 16:30, 9 March 2010 (UTC)

When EmilJ and I both describe the problem as "not interesting", we're trying to explain why you will find it hard to look up this sort of thing: because, from the point of view of contemporary model theory, the problem is not very interesting. That doesn't stop you from studying it. But it does mean that you won't find much other work on it, and you would need to be able to make a case for your work if you tried to publish it in a model theory journal. — Carl (CBM · talk) 18:58, 9 March 2010 (UTC)

Yeah, I got it, and I realy have an interesting case for my problem (which may seem to be boring in other people's view). HOOTmag (talk) 20:21, 9 March 2010 (UTC)

How many different types of phase-space plot are there?

I'm familar with simple graphs (or "plot" in American-english?) of time against quantity, as in a time series. But I'm not familiar with graphs in what I think is called the phase space.

How many different types of phase-space plot are there please, and what do you do with the data to make them? The simple things you can do with the data must be quite small, so not many different types of plot.

This http://www.springerlink.com/content/5412256211633127/fulltext.pdf?page=1 says "Recurrences were analysed by first return maps, space time separation plots, return time and recurrence time statistics" which lists four or perhaps five different types of plot. Is there anywhere I can see a simple introduction to these plots and how to construct them? Thanks 89.242.102.148 (talk) 15:08, 7 March 2010 (UTC)

See our articles on phase space, Poincaré map and recurrence plot. Space-time separation time plots are described here. Gandalf61 (talk) 14:43, 10 March 2010 (UTC)

Graph of a smooth function is a smooth embedded surface?

Hi all,

is it necessarily true that if you take a smooth function F of 2 variables, defined on some subset of R^2, then the surface given by Z=F(x,y) is necessarily a smooth embedded surface? I can see intuitively why it should be true, but obviously that's hardly a proof.

My axioms for a smooth embedded surface are:

For each point P there exists a map M(u,v) from a subset of R^2 to some open neighbourhood U of P, U in S, such that:

-M is continuous with continuous inverse

-M is smooth (partial derivatives of all orders)

-At each point Q=M(P), the partial derivatives of M w.r.t. u and v are linearly independent.

(I don't know if these are standard, but they're the ones I'm working with!)

Assuming it is true, I haven't got the first clue about how to show this for some general function F. Could anyone help please?

Thanks a lot, 82.6.96.22 (talk) 16:07, 7 March 2010 (UTC)

Yes, it's a general fact: the graph Γ_f of a C^k map f:M→N is a C^k embedded submanifold of M×N, diffeomorphic to the domain; a diffeo h:M→Γ_f is h(x):=(x,f(x)), whose inverse is the restriction to Γ_f of the first projection of the product, sending (x,f(x)) to x. --pma 16:43, 7 March 2010 (UTC)

Fascinating, thankyou :) 82.6.96.22 (talk) 17:25, 7 March 2010 (UTC)

The probability of a normally distributed random variable being a particular value

For example, what is the probability of a normally distributed random variable with mean 3 and standard deviation 2 being exactly 1? One would think that it would be ${\frac {1}{2}}{\Big [}1+\operatorname {erf} {\Big (}{\frac {1-3}{2{\sqrt {2}}}}{\Big )}{\Big ]}-{\frac {1}{2}}{\Big [}1+\operatorname {erf} {\Big (}{\frac {1-3}{2{\sqrt {2}}}}{\Big )}{\Big ]}=0$, so the proability is 0, however one intuitively knows that there is a slight probability of the value being exactly 1 (although the probability is obviously incredibly small) --220.253.247.165 (talk) 23:18, 7 March 2010 (UTC)

It is 0. If your intuition is telling you otherwise, your intuition is seriously mistaken. Algebraist 23:23, 7 March 2010 (UTC)

Why is it 0? And why is it not 0 for a range of values, if the probability for each individual value within that range is 0? --220.253.247.165 (talk) 23:26, 7 March 2010 (UTC)

It is 0 because the random variable will almost surely not be exactly 1. (There is a technical definition of almost surely which is being used here; see the article.) Similarly, for any given value x, the probability is 0 that the random variable will be exactly x. The reason that the probability is not 0 for a range of values is that a range of values contains uncountably many individual values, and you can't add uncountably many probabilities together. This is all pretty counterintuitive, but it follows from the measure-theoretic foundations of probability. —Bkell (talk) 23:36, 7 March 2010 (UTC)

Here's another way to think about it: Consider a random variable that is uniformly distributed on the interval [0, 1]. What is the probability the random variable is exactly 0.5, say? Suppose this probability is some very small but nonzero value ε. Then the probability must also be ε that the random variable is exactly 0.4, and likewise for every other number in the interval [0, 1]. But there are infinitely many numbers in this interval, so when you add up all of those individual probabilities, no matter how small ε is, you will get the nonsensical result that there is an infinite probability that the random variable takes some value in [0, 1]. This is absurd. So there must be a probability of 0 that the random variable is exactly 0.5. Of course, this doesn't mean it's actually totally impossible for the random variable to take that value; after all, it has to take some value in the interval, but beforehand we would have said that such an occurrence had probability 0. So there is a difference between "probability 0" and "impossible", and likewise a difference between "probability 1" and "absolutely certain"—that difference is what is meant by almost surely. Now, this argument doesn't quite work directly for a normal distribution, because it seems that the probabilities of individual values should "vary", and it's possible to imagine that maybe they vary in such a way that their sum adds up to 1. But this isn't possible because there are uncountably many of them. —Bkell (talk) 23:45, 7 March 2010 (UTC)

These results are actually mathematically equivalent to the observation that the "length" of a single point is obviously 0, but a line segment, which is just a bunch of points strung together, has a nonzero length. If you can understand this geometric idea, which may be intuitively paradoxical at first glance, try to apply it to probability in an analogous way. —Bkell (talk) 23:49, 7 March 2010 (UTC)

Check also Continuous probability distribution. --pma 22:30, 8 March 2010 (UTC)