Wikipedia:Reference desk/Archives/Mathematics/2011 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

Infinite Dimensional Spaces

We all know that Rⁿ is the set of sequences (x₁, x₂, …, x_n) where each x_k belongs to R. I'd like to ask about R^∞, which is defined to be the set of infinite sequences (x₁, x₂, x₃, …), where only finitely many of the x_k are non-zero. Why do we need to impose the condition that only finitely many of the x_k are non-zero? I've got a feeling that it's related to the topology, e.g. it would otherwise fail to be Hausdorff, or something like that. — Fly by Night (talk) 00:33, 13 August 2011 (UTC)

You're talking about the difference between the product topology and the box topology. Usually the product topology works out to be more important in practice, because it's the topology in which sequences of functions converge just in case they converge pointwise. --Trovatore (talk) 00:41, 13 August 2011 (UTC)

Hmm, or then again maybe you're not. I am actually not familiar with your definition of R^∞, now that I re-read it. It sounds more like a discretized version of the space of functions with compact support. Where did you happen to see the notation R^∞ for it? --Trovatore (talk) 00:44, 13 August 2011 (UTC)

It's from Milnor, J. W.; Stasheff, J. D. (1974). Characteristic Classes. Princeton University Press. pp. 62−63. ISBN 0691081220.. The space R^∞ is topologised as the direct limit of the sequence R¹ ⊂ R² ⊂ R³ ⊂ …, where each R^k is identified with the sequence (x₁, x₂, …, x_k, 0, 0, …) ∈ R^∞. — Fly by Night (talk) 15:22, 13 August 2011 (UTC)

Ah, well, that's the answer to your question, then. Direct limits are essentially unions. More exactly they're a context general enough to subsume all the things you're taking the limit of, as substructures.

So you're looking at, more or less, the union of all the R^k, in such a way as to be able to compare an element of R^k to an element of R^m even when k is not equal to m.

But for each k, obviously, any element of R^k has only finitely many nonzero coordinates. But any element of R^∞ comes from some R^k, and therefore likewise has only finitely many nonzero coordinates.

Granted this is a bit handwavy, but that's kind of the point of an intuitive justification, which I gather was what you were looking for. Is that satisfying? --Trovatore (talk) 19:35, 13 August 2011 (UTC)

Thanks for the reply. I'm not sure it does cover everything. What you said is true, but it doesn't seem to tell me why. The direct limit is used to give a topology on the space when we've defined it the way we did. But why not define it as to allow arbitrary sequences? If we did then we'd still be able to define a topology. It must be defined the way it is for a reason. — Fly by Night (talk) 01:31, 14 August 2011 (UTC)

I'm guessing now that you're taking the product of infinitely many copies of R considered as an additive group. See product (category theory) for the abstract notion of which that's an instance, and you should be able to work out from that the reason for the finite-support condition. --Trovatore (talk) 00:51, 13 August 2011 (UTC)

(I was waiting for someone to catch me on this, but no one did.) Actually it's the coproduct, not the product. The product of ω-many copies of R considered as an additive group would not have the finite-support condition. The coproduct (aka direct sum) does have it. --Trovatore (talk) 02:07, 13 August 2011 (UTC)

The R^∞ you describe is the vector space over R of countable dimension. If we didn't have the finite support condition, the resulting v.s. would have higher dimension. There's nothing inherently wrong with that, but sometimes people want to talk about the v.s. of countable dimension.

(Incidentally, would the larger space necessarily have dimension continuum (under ZFC)? I can show that ZFC + MA proves it does.)--Antendren (talk) 01:49, 13 August 2011 (UTC)

(1) Why do you think he's talking about vector spaces, where is that mentioned? (Not that it's really much different from the additive-group interpretation, in this case.)

(2) What sort of dimension? --Trovatore (talk) 02:07, 13 August 2011 (UTC)

(1) I'm not sure he is; I'm just giving a context in which the finite support condition would be important.

(2) Smallest cardinality of a spanning subset, where span is defined in terms of finite linear combinations over R.--Antendren (talk) 02:17, 13 August 2011 (UTC)

It is being thought of as a vector space. Sorry for the confusion; I assumed that it would have been a well known idea. The definition comes from vector bundles and Grassmannians. The compact, Hausdorf, topological manifold of k-planes (passing through the origin) in Rⁿ is denoted as Gr_k(Rⁿ). The so-called universal bundle has Gr_k(R^∞) as the base space. It's given by

$\pi :\gamma ^{k}\twoheadrightarrow {\text{Gr}}_{k}\left({\mathbf {\mathbb {R} } }^{\infty }\right),\ {\text{where}}\ \gamma ^{k}:=\{(X,v):X\in {\text{Gr}}_{k}\left({\mathbf {\mathbb {R} } }^{\infty }\right)\ {\text{and}}\ v\in X\},\ {\text{and}}\ \pi (X,v):=X\,.$

— Fly by Night (talk) 15:35, 13 August 2011 (UTC)

Metamath question

I'm having a lot of trouble trying to understand how metamath works. Apparently it's not exactly like traditional FOL, besides the obviously fact that it works with axiom schemes. One thing I don't get is thing with class variables. Aren't proper classes not allowed in ZFC? So what's with all the purple class variables? And if you look [[1]], why do they have x=y as a theorem!? x=y is supposed to be an atomic formula. The worst thing I'm having trouble with is definitions of new symbols. Aren't definitions meant to abbreviate formulas? But then they use the biconditional to define stuff, and some of the definitions just dont make sense to me. Can someone please explain this carefully to me? Thanks. Money is tight (talk) 02:15, 13 August 2011 (UTC)

No expert but my interpretation of what you have there is they they don't have x=y as a theorem in that reference you gave - they have that x=y is a well formed formula is a theorem. It follows from the syntax definition that A=B is a well formed formula if A and B are classes. They haven't really started on axioms yet at that stage, they're just setting up the basic syntax of ZFC so Metamath can deal with it. Dmcq (talk) 12:17, 15 August 2011 (UTC)

what if everyone on facebook friended their friends' friends and they had to accept

Say there is large group of facebook users. like several million. When they first start their account they are assigned, say, 100 friends at random (for the purposes of this question, you can't decline a friend offer). In addition to this first 100 you also have the friends who happened to have been assigned you as a friend and you had to accept.

OK now let's say you are required to add ALL of your friends' friends, and they are required to accept. Then repeat the process until there are no more friends' friends to add and all the possibilities have been exhausted.

At this point what is the statistical likelihood that everyone will be everyone else's friend? Is that the CERTAIN outcome? Is that outcome extremely likely/unlikely?

If you repeated this random trial a whole bunch of times, what is the average % of facebook population one could reasonably be expected to be friends with at the end of the process?--Fran Cranley (talk) 08:26, 13 August 2011 (UTC)

This kind of question is studied in graph theory—more precisely, in the area of random graphs. The particular problem you pose can be modeled (approximately) with the Erdős–Rényi G(n, p) model of random graphs, which is well studied. Such a graph has n vertices (dots) representing all of the people on Facebook. Some of these vertices are connected by edges (lines); each edge connects two people who are friends. In the Erdős–Rényi G(n, p) model, each potential edge (i.e., each potential friendship between two people) is included randomly with probability p (and excluded with probability 1 − p). To model the "100 friends" part of your puzzle, the value of p should be approximately 200/n. In the standard notation, then, this random graph would be written G(n, 200/n). (Please note that this random graph model does not guarantee that each person will be given exactly 100 friends; rather, each possible friendship is decided randomly in such a way that most people will be given close to 100 friends, and on average everybody gets about 100 friends. So this random graph isn't an exact fit for your question. There are other random graph models which would model your question better; I chose the Erdős–Rényi model because it's the one I know the most about.)

Your question is essentially asking whether the random graph you describe is connected or not. The important fact about G(n, p) is that, for large values of n, the random graph G(n, p) is almost surely disconnected if $\textstyle p<{\frac {(1-\epsilon )\ln n}{n}}$. In this case we have $\textstyle p={\frac {200}{n}}$, which is less than $\textstyle {\frac {(1-\epsilon )\ln n}{n}}$ for large values of n. In other words, with high probability (a probability approaching 1 as n grows larger and larger), the random graph G(n, 200/n), which I am using to model your question, will have two or more separate "pieces," where nobody in one "piece" knows anybody in any other "piece," and so it will not turn out that everyone will be everyone else's friend.

Unfortunately I am not sure how well G(n, 200/n) actually models the question you ask, because it is also true that, with high probability, G(n, 200/n) contains an isolated vertex (a vertex that isn't joined by an edge to any other vertex), which would correspond to a Facebook user who is totally friendless. Of course, in your question this can't happen, since everyone is assigned at least 100 friends. —Bkell (talk) 10:18, 13 August 2011 (UTC)

(Two longish replies, this is to the OP.) Perhaps I've misunderstood, but doesn't the reasoning run like this: we have a dot for every user. If we take that dot and randomly join it to 100 others. Unless all those people had only those friends, then there are going to be more people. 100 is quite a lot of people; I can't quite work out if the fact that facebook has millions of users means that a very small chance is plausible, but it seems to me that for a matter of thousands of people the chance that a group exists is very small.

The first probability as I see it is that all 101 people in the group have the same friends. This is clearly very unlikely (additionally since the other people have to not be given people in the group). As there are more people in the group, the chance that the person's friends are all in the group goes up, but the number of people to whom this applies goes up. Grandiose (me, talk, contribs) 10:39, 13 August 2011 (UTC)

Is Yahoo answers correct?

An amateur fisherman throws his takcle(bait) into the river from a pier which stands h metres above the water with an initial velocity of u metres per second at an angle of Ɵ degrees to the horizontal. Determine generalised expressions for the maximum height through the air.

I solve this by considering the maximum height occurs when the projectile is halfway toward the point at which it is again at the same height as the pier. that is, there is a horizontal displacement of zero.

U sin θ T - (1/2)gT^2=0

which gives

T=(2 U sin θ)/g

The projectile will be at its maximum height at T/2

T/2=(U sin θ)/g

So substitute this into the equation for vertical displacement

y(T/2) = U sin θ (T/2) = (U sin θ)(U sin θ)/g = (U^2 sin^2 θ)/g

However I saw this question on Yahoo answers with an answer of (U^2 sin^2 θ)/2g using some other method.

Which is correct? — Preceding unsigned comment added by 118.208.39.138 (talk) 08:35, 13 August 2011 (UTC)

Vertical velocity at time t is

${\dot {y}}=U\sin \theta -gt$

so when vertical velocity is 0, we have

$t={\frac {U\sin \theta }{g}}$

Vertical displacement relative to the starting point at time t is

$y=Ut\sin \theta -{\frac {gt^{2}}{2}}$

so substituting the above value for t into the expression for y gives

$y_{\text{max}}={\frac {U^{2}\sin ^{2}\theta }{g}}-{\frac {gU^{2}\sin ^{2}\theta }{2g^{2}}}={\frac {U^{2}\sin ^{2}\theta }{2g}}$

Your error comes from using T to represent two different times in your working, and getting your two Ts confused. If you want maximum height relative to the water you have to add h to this. Gandalf61 (talk) 10:00, 13 August 2011 (UTC)

Oh now I see the dumbass mistake I made, whoops — Preceding unsigned comment added by 118.208.39.138 (talk) 11:04, 13 August 2011 (UTC)

Monotone functions

1)How many monotone continuous functions on the reals are there? 2)How many smooth monotone functions on the reals are there? 3) If S is the family of smooth monotone functions, can we say that most of S, in category terms, are nowhere analytic? -Rich Peterson199.33.32.40 (talk) 19:15, 13 August 2011 (UTC)

Not being versed in category theory, I'll assume that by "how many" you are talking about cardinality. There are ${\mathfrak {c}}$ continuous functions on the reals (since they are determined by their values on rational numbers). Functions of the form $f(x)=x+a$ are smooth and monotone, and there are ${\mathfrak {c}}$ of them, so the answer to questions 1 and 2 is ${\mathfrak {c}}$. -- Meni Rosenfeld (talk) 19:34, 13 August 2011 (UTC)

• yeah thanks, that was pretty dim of me in 1) and 2). For 3)I did mean Baire category.

I don't think he means category theory, but rather Baire category. I am reasonably sure that the answer to (3) is "yes"; that is, the set of nowhere analytic functions is comeager in the space of smooth monotone functions, assuming the topology of pointwise convergence. I'd have to think about a proof, though. --Trovatore (talk) 19:57, 13 August 2011 (UTC)

Thanks. By the way where this comes from is a note in the march 2000 American math. monthly by Kim & Kwon, showing there exists a monotone, smooth, nowhere analytic, function; so I wondered if "there exists" that can be strengthened to "most of them are." Later they show that a smooth function can have an arbitrary and must have some open subset of R to be its analytic points. I wonder further if a MONOTONE smooth function can have an arbitrary open set for its analytic points?199.33.32.40 (talk)