Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

August 24

Probability

I've got a question on Probability which I found on one of my reference books, which I couldn't figure out. Guys, this is not homework, just an interesting question which I ran into. Say a police officer is investigating a case. He is 60% convinced that X is the culprit. Suddenly, he finds a new piece of evidence, which is a mark on the culprit's face, which 90% of the population don't have. If X has the mark, what is the probability that X is the prisoner ? Actually, though this question looks simple enough, I just can't crack it ! Excuse me if I had asked a very obvious question, but I need some help. Rkr1991 ^{(Wanna chat?)} 10:54, 24 August 2009 (UTC)

Let A be the event "X is the culprit" and B "X has a mark". We have $P(A)=0.6,P(B|A)=1,P(B|A^{C})=0.1\,\!$. By Bayes' theorem the posterior probability of A given that we know B is

$P(A|B)={\frac {P(A)P(B|A)}{P(B)}}={\frac {0.6\cdot 1}{P(A,B)+P(A^{C},B)}}={\frac {0.6}{0.6+0.04}}=0.9375$

-- Meni Rosenfeld (talk) 12:16, 24 August 2009 (UTC)

Either there's a typo in the question or it's a trick question. The probability that X is the prisoner cannot be calculated from the police officer's certainty that X is the culprit and the ratio of people carrying a certain facial mark. We're not told anything about any trial turning a suspected culprit into a prisoner. ~~ Dr Dec (Talk) ~~ 12:24, 24 August 2009 (UTC)

Great, that's the right answer. Thanks a lot !!!! Rkr1991 ^{(Wanna chat?)} 13:25, 24 August 2009 (UTC)

General formula for power sum

Today I am the one who asks about a general formula for the following sum, of integers.

$\sum _{i=1}^{n}i^{k}$

For example, the simple form is given by the arithmetic progression sum, in which k = 1, is given as

$\sum _{i=1}^{n}i={\frac {n+n^{2}}{2}}$

If there exists an article, I'd be glad to be guided to.--Email4mobile (talk) 16:27, 24 August 2009 (UTC)

Have a look at Bernoulli number which answers your question. 129.67.186.200 (talk) 16:39, 24 August 2009 (UTC)

Thank you very much, 129.67.186.200. That is what I need. I did try to find a general solution yesterday, didn't know this formula exists. That's my try, User:Email4mobile/sum of power arithmetic progression.--Email4mobile (talk) 21:46, 24 August 2009 (UTC)

Also: Faulhaber's formula. Michael Hardy (talk) 23:15, 24 August 2009 (UTC)

Conceptually the simplest way to figure out that summation is through the Lagrange interpolation formula. You know that it's obviously a polynomial of degree k+1, so plot some points and then fit the curve through it. 70.90.174.101 (talk) 00:14, 25 August 2009 (UTC)

Greater, lesser or non-comparable

Would it be proper to say that negative numbers are less than positive numbers -- because an angle of -7 is a greater angle than an angle of 5? Or are angles different, because in regard to angles magnitude is all that matters? DRosenbach ^{(Talk | Contribs)} 18:55, 24 August 2009 (UTC)

Yes: the negative numbers are less than the positive numbers, with repect the the usual ordering. What exactly do you mean when you say that "−7 is a greater angle than an angle of 5"? I assume you mean something along the lines of an angle of −7 degrees is larger than an angle of 5 degrees. Well, this is very different. The number −7 is further from 0 than 5 is. This is because |−7| > |5|. It all depends on how you chose to order your set, and once an ordering has been chosen then it doesn't really make any sense to compare orderings. For example, given a natural number k, the metric norm

$||(x,y)||_{k}:=(x^{k}+y^{k})^{1/k}\,$

have very different "unit disks". The unit disk for k = 2 (i.e. in the usual Euclidean metric) is the usual circular Euclidean unit disk. In the case where $k\to \infty$, the unit ball is the Euclidean unit square! ~~ Dr Dec (Talk) ~~ 19:27, 24 August 2009 (UTC)

Wow...I got everything up until your example of "k" -- from then on, I would say it's all Chinese to me. If you insist it's English, then I don't know what I'll say... :) DRosenbach ^{(Talk | Contribs)} 21:59, 24 August 2009 (UTC)

I think it was just an analogy. The real numbers with different orders are completely different things in the same way that the plane with different metrics/norms are completely different things. It doesn't really matter, but basically that formula is a new definition of the distance between two points, so you end up with up different definitions of discs (since a disc is all the points less than or equal to a certain distance from a certain point, so you chance the definition of distance you change the definition of a disc). If it doesn't make sense, just ignore it! The important bit is everything before "For example". --Tango (talk) 22:14, 24 August 2009 (UTC)

Well, there are many ways to measure distance, and to measure the length of something. A metric is something that we use to measure the distance between two points. Let's consider the plane, denoted by $\mathbb {R} ^{2}$, as an example. How do we define the distance between two points, say a and b? Well, if a = (a₁,a₂) and b = (b₁,b₂) then the distance, let us denote it by d(a,b), in the good old fashioned using-a-ruler sense is given by

$d({\mathbf {a} },{\mathbf {b} })={\sqrt {(a_{1}-b_{1})^{2}+(a_{2}-b_{2})^{2}}}\ .$

The idea of distance has some nice properties. Let a, b and c be points in the plane (not nevessarily distinct).

1. The distance from a point to itself is zero, i.e. d(a,a) = 0.
2. The distance between points is always non-negative, i.e. d(a,b) ≥ 0.
3. Informally, the shortest distance between two points is a straight line, i.e. d(a,b) + d(b,c) ≥ d(a,c).

This last one is called the triangle inequality. Well, what we do is to abstract this idea. We say that any function d that satisfies these three conditions is a metric, and gives us some idea of distance. One such metric would be

$d_{4}({\mathbf {a} },{\mathbf {b} })=((a_{1}-b_{1})^{4}+(a_{2}-b_{2})^{4})^{1/4}\ .$

In fact, for any positive integer k we have have a metric given by

$d_{k}({\mathbf {a} },{\mathbf {b} })=(|a_{1}-b_{1}|^{k}+|a_{2}-b_{2}|^{k})^{1/k}\ .$

Good old fashioned distance comes from k = 2. But for all positive integers k we have a metric, i.e. a function that takes any two points in the plane and gives us a number in a way that satisfies our three conditions above. Now, the unit disk, for a metric d, centred at some point a is given by all the points b judged to be at a distance of less than or equal to 1 from a, i.e.

$D_{\mathbf {a} }=\{{\mathbf {b} }\in \mathbb {R} ^{2}:d({\mathbf {a} },{\mathbf {b} })\leq 1\}\ .$

In the case of d₂ the unit disk, centred at the origin is just the set of all points at a distance at most 1 from the origin, i.e. the filled in circle. This matches our idea of equidistance: the points at a fixed distance from you will form a circle - a circle has a constant radius. But the unit disks for the metrics d_k are far from circular disks. In fact, as k gets bigger and bigger, the disks get more and more square shaped. In fact the limiting shape is exactly a square. So, according to the metric d_∞, the points a fixed distance from the origin actually form a square! The point is that there are many ways of talking about size and distance. Some are very natural, like d₂; but some are most counterintuative, like d_∞. You need to use the right metric for the right problem, and be very careful when you're trying to compare answers in one metric to answers in another metric, or else you might start saying that a square is a circle (and it is, topologically speaking... but that's another story). ~~ Dr Dec (Talk) ~~ 22:49, 24 August 2009 (UTC)

With angles it depends on what you are doing. 350 degrees and -10 degrees are often completely equivalent, but have very different magnitudes. Sometimes you want to consider the magnitudes, sometimes you want to consider them modulo 360 degrees, sometimes you want the actually real number itself. --Tango (talk) 20:07, 24 August 2009 (UTC)

To some extent, the original question appears to be a language-usage question rather than a mathematical one. Do we say −1000000 is a bigger or smaller negative number than −1? I'm afraid authors are probably inconsistent on this point. But if you see the phrase large negative number it most likely means "negative number of large absolute value" rather than "negative number far to the right (among negative numbers) in the number line". --Trovatore (talk) 22:54, 24 August 2009 (UTC)

August 25

Topology

Is there a simple English equivalent meaning for the word "topology" (even into a simple sentence)? Because I'd like to make a related meaning in Arabic beside the Arabic use of Latin name. If not it is still Ok. Thanks, --Email4mobile (talk) 08:31, 25 August 2009 (UTC)

To be precise, the word topology is from Greek, not Latin. The Latin expression would be analysis situs (yet with half Greek origin). --79.38.22.37 (talk) 08:37, 25 August 2009 (UTC)

Thanks for the correction, but can you give me an alternative meaning in English?--Email4mobile (talk) 09:02, 25 August 2009 (UTC)

See -ology. "topos" means place, and "logos" means "word". By analogy,

• biology is the study/theory/science of life (more literally, the word or talk about life)
• sociology is the study of society/social structure

so topology is the theory of "place" or "space". As -ology explains, X-ology can also a subject itself, not only its study. See network topology for example.

But please remember that Wikipedia is not a place where words should be invented.

--Aleph4 (talk) 09:37, 25 August 2009 (UTC)

Inner model theorists are topologists, because they study mice.

(It's sort of a pun.) --Trovatore (talk) 09:46, 25 August 2009 (UTC)

In Tuscany there is also a coarser pun, linked to the jargon word "topa" --pma (talk) 10:02, 25 August 2009 (UTC)

(ec) Do you mean, an other meaning of the word "topology"? As far as I know, the word "topology" is used in maths only, with these meanings: a) the branch of maths devoted to the study of topological spaces; b) the family of all open sets of a topological space: "the Euclidean topology of the real line is generated by all open intervals"; c1) sligthly more generally, the complex of all topological properties of a space: "a horned sphere has a weird topology"; c2) sometimes with a point of view of algebraic topology: "a disk has no topology"; "the projective space has a rich topology"; "a non-orientable manifold has no topology at the top level".--pma (talk) 09:52, 25 August 2009 (UTC)

Thank you all for explanation. Though, topology is also used outside Maths fields; for example: network topology. I'm not sure if the term "the study of space" or "the theory of space" would be the nearest meaning). How about "preserved space"?--Email4mobile (talk) 10:43, 25 August 2009 (UTC)

People probably assumed you were asking about the mathematical usage of the term, as this is the Mathematics Reference Desk. For other meanings see Topology (disambiguation). Don't see how you get to "preserved space", but for general translations (rather than mathematical meanings) you could also ask at the Language Reference Desk. Gandalf61 (talk) 11:07, 25 August 2009 (UTC)

Indeed network topology is still in the mathematical sense, even if it is more used in applied maths. "Study of space" is quite ok as informal explanation of "topology". Preserved space apparently has no clear sense. Still it is not clear if you want other meanings of the same word "topology", or other words, sinonyms or phrases with the same meaning. The original question seems to ask for "an equivalent meaning for the word topology" (the answer then would be: "topology" I guess). --pma (talk) 11:12, 25 August 2009 (UTC)

A network topology is more like a graph (in the graph-theory sense) than a topology. I suppose you could code it as a topology, but it takes a bit of work, especially to make sure you can distinguish nodes of degree less than 3. --Trovatore (talk) 19:39, 25 August 2009 (UTC)

Agreeded. Indeed I just meant that network topology is still a mathematical term, but you are very right that graph-theory is a useful category in topology. --pma (talk) 11:14, 27 August 2009 (UTC)

For a lot of uses "connectivity" or "study of connectivity" has a very similar meaning. You could clarify(?) by calling it the "abstracted connectivity"...maybe...83.100.250.79 (talk) 11:40, 25 August 2009 (UTC)

...uhm maybe not, "connectivity" seems a bit obscure as a term of current language, and not quite appropriate here as a mathematical term. --pma (talk) 11:14, 27 August 2009 (UTC)

I used this online translator and got طوبولوجيا. It seems okay, when I translated it back from Arabic to English it came up with topology. It even translated طوبولوجيا from Arabic into Spanish as topología which is correct. ~~ Dr Dec (Talk) ~~ 13:54, 25 August 2009 (UTC)

Indeed if you switch languages from English to Arabic (العربية) at the en.wikipedia page topology, you immediately get طوبولوجيا at the ar.wikipedia page. But I fear this is the information that the OP needs to know the less... --pma (talk) 15:06, 25 August 2009 (UTC)

Sorry, but what's an OP? ~~ Dr Dec (Talk) ~~ 15:14, 25 August 2009 (UTC)

OP=Original post/Original poster. It was clear that طوبولوجيا is a transliteration (and that of course the OP (=Email4mobile) knows it very well) --pma (talk) 15:34, 25 August 2009 (UTC)

The word "طوبولوجيا" already exists in the article but what you aren't aware of is that it is the literal translation of "Topology". "طوبولوجيا" is not an original Arabic word and not even containing a similar word. We use this kind of translation when we can't get any Arabic alternative. For this reason I said in the beginning it would be Ok if there is no alternative. —Preceding unsigned comment added by Email4mobile (talk • contribs) 15:13, 25 August 2009 (UTC)

I see. Well then I doubt very much that there will be an Arabic word for it. In English and all other Eurpoean languages (using the Roman alphabet) the word is a loan word from Greek: Topology in English, Topología in Spanish, Topologie in French, Topologia in Italian, etc. Even in other languages, like Russian, it's a loan word: Топология. They are all more or less just transcriptions of one another. ~~ Dr Dec (Talk) ~~ 15:20, 25 August 2009 (UTC)

You mean transliteration ;) --pma (talk) 15:38, 25 August 2009 (UTC)

I wrote transliterations in the first place, but then after reading the article on transliteration decided that transcription might be better. Oh well... ~~ Dr Dec (Talk) ~~ 15:42, 25 August 2009 (UTC)

"Topology" describes what elements of a set or system are connected to each other, for whatever meaning of "connected" you want to apply to that system. For example, you could describe a topology on the system of Wikipedia articles, in which two articles are connected if any individual editor has edited both of them. Why not look up the Arabic word for topology (I'm sure there is one) and use it? 67.122.211.205 (talk) 05:30, 26 August 2009 (UTC)

"The study of shape" or "the study of shapes" is a good description of topology (as a field studied by mathematicians, rather than as a technical mathematical object). The Oxford English Dictionary has "The branch of mathematics concerned with those properties of figures and surfaces which are independent of size and shape and are unchanged by any deformation that is continuous, neither creating new points nor fusing existing ones". It is related to geometry (هندسة رياضية؟) --- the difference is that in geometry, we worry about exact distances and angles, while in topology, we're allowed to bend things and wiggle them around.

By the way, I took your original question to be asking "I would like to include a short explanation in Arabic of the meaning of the English word 'topology'. If someone can provide me with a short explanation in English, I will translate it into Arabic and be happy." There seems to have been some confusion about this, but I found your request quite clear. Tesseran (talk) 08:55, 27 August 2009 (UTC)

The real numbers and subsets of the natural numbers

The natural numbers are countably infinite and are the smallest infinite set, i.e. they have cardinality ℵ₀. The set of all subsets of the natural numbers has cardinality 2^ℵ₀: assign to each natural number a 0 or a 1 depending on whether the element is in or out of a given subset. Now, we can also show that the cardinality of the real numbers, i.e. the cardinality of the continuum is exactly 2^ℵ₀. The proof I have seen is a proof by contrandiction. Does anyone know of an explicit proof which finds a bijection between the real numbers (or an open subset thereof) and the set of all subsets of the natural numbers? ~~ Dr Dec (Talk) ~~ 11:21, 25 August 2009 (UTC)

I've seen a "proof" that puts a number into binary. Then for each string of 0s and 1s we get a subset of the natural numbers. For example 101 ~ {0,2} and 111101 ~ {0,1,2,3,5}. But this seems to be giving a bijection between the natural numbers and the set of all subsets of the natural numbers... that can't be right! Any ideas?! And besides, what about numbers numbers in the interval [0,1]? Won't we get some overlap? Is it even a bijection? I should stick to my own field and stop playing with fire. My head hurts! ~~ Dr Dec (Talk) ~~ 11:30, 25 August 2009 (UTC)

• When representing natural numbers in binary each natural number is a finite string. So you get a bijection between the natural number and the finite subsets of the natural numbers. Taemyr (talk) 11:37, 25 August 2009 (UTC)
• (ec)You only get finite sets that way. Finite subsets of natural numbers are countable. I suspect what you (miss-)remember is the proof that reals are uncountable (by trying to enumerate binary values from [0,1] and showing via diagonalization that that fails). --Stephan Schulz (talk) 11:45, 25 August 2009 (UTC)

Ah, I think you're right about that one! ~~ Dr Dec (Talk) ~~ 13:36, 25 August 2009 (UTC)

Oh, okay, cool. Do you have any idea of an explicit bijection from the real numbers to the set of all subsets of the natural numbers? ~~ Dr Dec (Talk) ~~ 11:42, 25 August 2009 (UTC)

Well, you can map each real in binary to a set of natural numbers (n is in the set if the nth bit of the binary representation of real number r is 1). Real numbers have infinite representations (the few with finite ones can be extended with zeros to infinity). --Stephan Schulz (talk) 11:59, 25 August 2009 (UTC)

Nice, straightforward idea but sadly not 1-1, as {1} maps to 0.1₂ and {2,3,4...} maps to 0.0111...₂ and these binary expansion represent the same real number, namely 1/2. Gandalf61 (talk) 12:25, 25 August 2009 (UTC)

True, but it is 1-1 if we only consider mapping infinite binary expansions to infinite subsets of natural numbers.

There probably isn't any pretty bijection between an interval of real numbers and the set of all subsets of natural numbers. That doesn't mean it can't be done, though. For instance, let the above bijection be Y=f(X), where X is a real number, and Y is an infinite subset of natural numbers. We define g(X)=f(X) if X cannot be represented as 1/n for some natural number n. For those numbers, letting n range from 1 to infinity, we define g(1/2n)=f(1/n), and g(1/(2n-1)) to be an enumeration of finite subsets of natural numbers. If we define g(0) to be the empty set, then g is a bijection between [0, 1] and the set of all subsets of natural numbers. --COVIZAPIBETEFOKY (talk) 12:50, 25 August 2009 (UTC)

My suggestion above is simple enough. To get around the 0.1*=1 problem, just define a unique representation for each rational number (by forbidding the ones that ends in 1*). Remember, we start with the numbers, not the strings. The problem I found by now, however, is that it does not map R, but only [0;1[ (or equivalent intervals). But it should be possible to get around this somehow by using a bijection from R to [0;1[. I think x->(1/(x+1)+0.5) (if positive or 0), x->(1/(-x+1)) (if negative) should do the job. --Stephan Schulz (talk) 14:14, 25 August 2009 (UTC)

So you represent 1/2 uniquely by 0.1, then map this to {1} - but now you have no real number that maps to {2,3,4,...}. So some subsets of natural numbers do not have a pre-image, and you still don't have a bijection. (Not saying this can't be patched up somehow to make it into a bijection - just saying it's not as simple as you originally said). Gandalf61 (talk) 15:55, 25 August 2009 (UTC)

Point taken. --Stephan Schulz (talk) 15:59, 25 August 2009 (UTC)

Another example: To each infinite subset of the natural numbers, say $0\leq a_{1}<a_{2}<\cdots$ assign the sequence $n_{1}=a_{1},n_{2}=a_{2}-a_{1},n_{3}=a_{3}-a_{2},\ldots$ of positive natural numbers; interpret this sequence as a continued fraction, and you will get a positive irrational number ${n_{1}+{\frac {1}{n_{2}+{\frac {1}{\ddots }}}}}$. Every positive irrational is obtained in this way. This is a (reasonably nice, I think) bijection between the (positive) irrationals and the infinite subsets of the natural numbers.

All that remains is to map the finite subsets of the natural numbers bijectively onto the rational positive numbers. As both these sets are countable, this is easy to do, but it can even be done "nicely", again using continued fractions.

--Aleph4 (talk) 22:08, 25 August 2009 (UTC)

On a different, but related topic. Is there anyway of giving a cananonical example for a set with cardinality ℵ_n for some natural number n? ~~ Dr Dec (Talk) ~~ 16:43, 25 August 2009 (UTC)

More or less by definition, ℵ_n is the cardinality of the set of ordinals of cardinality at most ℵ_n-1. Algebraist 16:46, 25 August 2009 (UTC)

Could you please explain that in a little more detail, if you don't mind? The ordinal article says that an ordinal are is the order type of a well-ordered set. So they are numbers. So the cardinality of an ordinal will be 1. So all ordinals have cardinality less than ℵ₀. ~~ Dr Dec (Talk) ~~ 17:00, 25 August 2009 (UTC)

(if you didn't mean to make a joke) "the cardinality of the ordinal x", refers to x as an ordered set, e.g. the set of all smaller ordinals, according to the von Neumann representation. --79.38.22.37 (talk) 17:18, 25 August 2009 (UTC)

A standard definition for ordinal numbers is very similar to the one for natural numbers, which defines each natural number as the set of all natural numbers less than it (where 0 is the empty set). That is, an ordinal number is often defined as the set of all ordinal numbers less than it. The finite ordinal numbers are natural numbers. The first infinite ordinal number is the set of all natural numbers. The second infinite ordinal number would be the set containing all natural numbers and the set of all natural numbers. And so on. --COVIZAPIBETEFOKY (talk) 17:12, 25 August 2009 (UTC)

Hold on, forgot to make my point (I guess you got it, but I'll put it explicitly anyways). So, the first infinite ordinal number has cardinality equal to ℵ₀, and so do many many many more after that. However, there will eventually be an ordinal number with cardinality ℵ₁, and ℵ₂, and so on. --COVIZAPIBETEFOKY (talk) 17:15, 25 August 2009 (UTC)

I see! ~~ Dr Dec (Talk) ~~ 17:15, 25 August 2009 (UTC)

Two more examples of sets of size aleph1:

• Example 1: Let P the set of all subsets of the rational numbers. (So P has size continuum.)

On the set P define an equivalence relation E by declaring two sets A and B (both subsets of the rationals) to be in relation E if they are order isomorphic (i.e., there is an order preserving bijection from A onto B), or neither of the two is a well-order. (For example, the sets {0,1,2} and {-1, 1/2, 7} are in relation E.)

The set of E-equivalence classes has cardinality aleph1. This is easy to see as each equivalence class (except for the class of non-well-ordered sets) naturally and bijectively corresponds to a countable ordinal. (So this example is just a thinly disguised version of the first uncountable ordinal, mentioned above.)

• Example 2: Let P be the same set as above. Now define a relation L as follows:

(A,B) is in L iff there is an order preserving embedding from A into B, and there is an order-preserving embedding of B into A.

Laver's theorem says that there are exactly aleph1 equivalence classes. ("Fraisse's conjecture"; highly non-trivial.)

--Aleph4 (talk) 21:19, 25 August 2009 (UTC)

Is this correct?

Resolved

 – Accdude92 already has the correct answer

Find F(x)+g(x) F(x)=X/X+2 G(X)=2X=3

I got 2x(squared)+8X+6\X+2 Accdude92 (talk) (sign) 14:12, 25 August 2009 (UTC)

I'm sorry, but I don't understand the problem. Do you mean find F(x) + G(x) when

$F(x)={\frac {x}{x+2}}\ ,$

$G(x)=2x-3?\,$

In that case it's just addition of fractions and some simplification. I get

$F(x)+G(x)={\frac {2(x^{2}+x-3)}{x+2}}\ .$

If x and X are different and g and G are different then I have no idea. ~~ Dr Dec (Talk) ~~ 14:18, 25 August 2009 (UTC)

Oh, I see, you have G(x) = 2x + 3, and in this case you're right:

${\frac {x}{x+2}}+(2x+3)={\frac {2(x^{2}+4x-3)}{x+2}}\ .$ ~~ Dr Dec (Talk) ~~ 14:20, 25 August 2009 (UTC)

Darn keyboard. Its really Find F(x)+g(x) F(x)=X/X+2 G(X)=2X+3 —Preceding unsigned comment added by Accdude92 (talk • contribs) 14:21, 25 August 2009 (UTC)

fibonacci spiral

for what value of $\omega$ does $|z|=re^{\omega arg(z)}$ plot a fibonacci spiral in the argand plane? —Preceding unsigned comment added by 92.1.60.82 (talk) 23:55, 25 August 2009 (UTC)

See Golden spiral. Black Carrot (talk) 06:09, 26 August 2009 (UTC)

August 26

Computer-aided proofs since Appel-Haken

This is less about mathematics than about mathematics history. I'm interested in knowing what notable questions in mathematics there have been whose solution have relied upon an effectively not-by-hand-checkable computer program since Appel and Haken proved the Four-Color Theorem using a computer program in 1976. —Preceding unsigned comment added by Julzes (talk • contribs) 08:22, 26 August 2009 (UTC)

What do you accept as "proved"? The Kepler conjecture has most likely been proved by computer, but nobody is completely sure if that proof is sound. There are several proofs now that have been found by automated reasoning systems - the most famous one is probably the Robbins conjecture proved by EQP. However, that proof was hard to find, but easily checkable. --Stephan Schulz (talk) 09:03, 26 August 2009 (UTC)

I'm mostly interested in the question of exhaustive searches and other sorts of things where the acceptance of effectively uncheckable computer calculations is involved. The Kepler Conjecture is a good example, but the fact that it's controversial sort of goes against what I would have proposed saying about the acceptance of things similar to the proof of the Four-Color Theorem having become somewhat routine.Julzes (talk) 10:08, 26 August 2009 (UTC)

Well, sorry if reality does not support your proposed opinions ;-). If you are interested in searches: The claim that the game-theoretic value of Checkers is 0 comes from exhaustive calculations by the Chinook team, and seems to be widely accepted. --Stephan Schulz (talk) 10:33, 26 August 2009 (UTC)

A lot of work has been done on formalizing proofs that have already been found by humans (the Flyspeck project is an example, as is Gonthier's Coq implementation of the 4-color theorem). There is also lots of exploratory math done with computers--see some of Doron Zeilberger's articles on experimental math for info. But I think not all that much has been done using computers to find proofs of traditional math conjectures. WZ theory might be an example though--a scheme for automatically solving certain hypergeometric sums. Hmm, another example, the Bailey-Borwein-Plouffe formula for computing digits of pi was found with a big computer search involving the PSLQ algorithm (there are related such formulas too, found in similar ways). This page is a reasonable place to look for info about formalized math in general, and there was a special issue of AMS Notices about formalized math, that has several good articles that you might like.[1] —Preceding unsigned comment added by 67.122.211.205 (talk) 23:39, 26 August 2009 (UTC)

I should add that the point of Gonthier's proof of 4CT is that (unlike Appel-Haken's) it can be checked by a program that itself is supposed to be hand checkable (Coq's proof checking core is based on a small, hand checkable kernel, per the de Bruijn criterion). 67.122.211.205 (talk) 00:01, 27 August 2009 (UTC)

Further: OK, I think I understand your question better now. The issue with the Appel-Haken proof is it was done with 1970's computer and software technology, and was a huge complicated set of C assembly language programs that were potentially full of bugs and was too large to be inspected by hand (being small enough for hand verification is called the de Bruijn criterion), so nobody could be sure it was really right. These days, programming itself (at least at this pointy-headed level) is getting more formalized, so in a language like C you can write a program with the intention that it computes X, and make informal arguments that it actually does compute X, but maybe your arguments have a gap and your program has bugs. But in a language like Coq (you can view Coq as a programming language), the programs are stated rigorously enough that you can prove theorems about their properties, and mechanically verify the proofs, using a hand checkable verifier. So you can write a Coq program that computes X, and state what X is, and prove as a theorem (formally verified) that your program really computes X. That is essentially Gonthier's proof of 4CT, I think. (There is an article about it in the AMS issue I linked to). In principle you could repeat Schaffer's calculation of the outcome of checkers, by writing a Coq program that computes the outcome of checkers, proving its correctness, and running it for however long it took (hmm, I guess that involves trusting the compiler, but we are getting closer to having completely verified compilers), and then saying the output is verified. In that way we're getting away from the acceptance gap that the Appel-Haken proof faced. Anything we can compute unverifiably, we can do verifiably with enough extra work. 67.122.211.205 (talk) 00:12, 27 August 2009 (UTC)

Thanks for the thoughtful answers. Aside from helping me help someone else write a short piece on the 4CT, it's a subject of some personal interest, so I will be having a look at what you have offered up.Julzes (talk) 03:56, 27 August 2009 (UTC)

Connect Four has been shown to be a first player win using a computer-assisted search approach. Victor Allis's Master's Thesis contains a very interesting and clearly written account of the investigation. Some people may have the impression that a computer-assisted proof involves writing an enormously complex and poorly understood program which then runs for hundreds of hours before producing a one-line answer. This is not the case. The programs in such proofs are re-written and expanded many times, as the researchers' ideas evolve. Each new version of the proof program can be checked by ensuring it reproduces the partial results of previous versions - indeed, this is a very efficient form of regression testing. In addition, the proof program (or suite of programs - the tasks of generating and evaluating cases may be divided between different programs) can be expected to include a degree of redundancy and internal cross-checking - the equivalent of check sums. It should also store snapshots of intermediate positions or results, which can be checked for internal consistency by independent programs. The algorithms behind the proof programs should be described so that they can, in principle, be implemented independently in entirely different software. And finally, improvements to the original algorithms are often made and tested by later researchers, which provides the ultimate error check. The original Appel-Haken proof of 4CT, for example, has evolved through several subsequent generations, each improving on the efficiency of the previous generation, but all confirming the original result. Gandalf61 (talk) 12:01, 27 August 2009 (UTC)

Definition of Kähler manifolds

From the Wikipedia article about Kähler manifolds, a Kähler manifold is a complex manifold with a Hermitian metric $h=g+i\omega$ where $g$ is a Riemannian metric, $i$ an almost complex structure and $\omega$ a symplectic form, which must satisfy an additional condition.

The article gives two of such equivalent additional conditions:

• $d\omega =0$, the symplectic form is closed.
• Parallel transport induced by the Levi-Civita connection corresponding to $g$ actually induces $\mathbb {C}$-linear mappings of tangent spaces, not only $\mathbb {R}$-linear.

I've been thinking about this for a while now but I can't seem to figure out the equivalence. For example, starting with the second condition, I have no idea how to involve $\omega$.

I'd be very grateful if anyone had a few tips or a good reference. Thanks. -Xedi^Talk 13:52, 26 August 2009 (UTC)

can u solve this

1=19-20=60

one straight line --America vega (talk) 21:23, 26 August 2009 (UTC)

What is the question? You have given a false arithmetic statement and a geometric object, you haven't actually given us anything to solve. --Tango (talk) 21:29, 26 August 2009 (UTC)

I know my brother gave it to me to solve but I can't I think it might be a riddle--America vega (talk) 21:39, 26 August 2009 (UTC)

is it (1,20) (20,60) which is y=40x/19+17+17/19 ? 83.100.250.79 (talk) 21:45, 26 August 2009 (UTC)

How many matchsticks can you move? – b_jonas 11:53, 29 August 2009 (UTC)

Commutivity of addition

Resolved

 – Wow! Good work everybody.

Has anyone any idea how one might prove the commutivity of addition?

• Let's start with a + b = b + a where a and b are real numbers. ~~ Dr Dec (Talk) ~~ 23:14, 26 August 2009 (UTC)

This will depend on your preferred Construction of the real numbers. Algebraist 23:15, 26 August 2009 (UTC)

Good point! Okay, let's list the possible constructions and their respective proofs... ~~ Dr Dec (Talk) ~~ 23:21, 26 August 2009 (UTC)

The reals are a Field (mathematics). The additive operation of a field is commutative by definition. QED. ;-) --Stephan Schulz (talk) 23:24, 26 August 2009 (UTC)

This is a joke, right?! PROVE that addition is commutative! ~~ Dr Dec (Talk) ~~ 23:27, 26 August 2009 (UTC)

Only slightly. The most common definition of the reals is as the essentially unique ordered field satisfying a completeness property (exactly how the completeness property is phrased varies); with this definition, commutativity of + is automatic. Algebraist 23:30, 26 August 2009 (UTC):

There are a great many constructions of the reals, and I doubt we could find them all, let alone list them. For many constructions, the commutativity of addition is a trivial consequence of the commutativity of rational or integer addition; this is the case for every construction listed in our article, for example. Algebraist 23:30, 26 August 2009 (UTC)

Okay, my first example was that of the reals. What about the addition of connexions? What about group rings? (Can you PROVE the commutivity instead of ASSUME it? Can you PROVE it from the properties that are not derived from the assumption itself?) ~~ Dr Dec (Talk) ~~ 23:40, 26 August 2009 (UTC)

I think "prove addition is commutative" makes the most sense when you're discussing addition of the natural numbers. More complicated structures like the reals are constructed and artificial and commutativity of addition is usually taken as an axiom (Archimedean complete ordered field) rather than something to be proved (unless you're discussing a specific construction of reals, such as Dedekind cuts). The basic properties of the natural numbers are usually given as the Peano axioms. They say that every natural number N has a successor S(N), and they define addition by saying A+0=A and A+S(B)=S(A+B), plus a few other things. From these axioms, the commtativity of addition should be provable as a theorem. 67.122.211.205 (talk) 23:49, 26 August 2009 (UTC)

67.122.211.205, you're half way there. Now prove it... ~~ Dr Dec (Talk) ~~ 23:55, 26 August 2009 (UTC)

It needs an inductive proof. Addition is "only" an inductive theorem of the natural numbers. Via induction, the proof is fairly simple. --Stephan Schulz (talk) 23:59, 26 August 2009 (UTC)

Even with the naturals, there are alternative approaches. For example, if we instead define the naturals to be the finite cardinals, then commutativity of addition is a triviality. If we define the naturals to be the nonnegative (or positive, to taste) part of the essentially unique well-ordered integral domain, then commutativity of addition is again true by definition. Algebraist 00:05, 27 August 2009 (UTC)

But that's my hang-up: you're ASSUMING it as a definition. Something doesn't sit very well with me about this axiomatic aproach to mathematics. Lots and lots of assuming makes many many things matters of definition. For example, as the axiom article says: "...non-logical axioms (e.g., a + b = b + a) are actually defining properties for the domain of a specific mathematical theory (such as arithmetic)." So the natural numbers are defined, arithmetic is defined. They are not provable; simply defined and accepted. ~~ Dr Dec (Talk) ~~ 00:22, 27 August 2009 (UTC)

Yes, so? This is the usual way of defining mathematical systems since Hilbert; you define a system by its key properties, and call those properties axioms for the system. It is of course possible to go the other way, and define your system to be some specific object in some other system (usually a set theory of some sort) and prove that the object you've chosen has the key properties you want, but this is rather artifical. After all, if the object you'd decided was the real numbers turned out not to have commutative addition, then that wouldn't say anything interesting about the real numbers. It would just mean you'd picked the wrong object to be them. Algebraist 00:33, 27 August 2009 (UTC)

It may be artificial, yes, but on the flip side, actually constructing the object of interest (set of real numbers, set of natural numbers) in terms of other, well-accepted theory, provides one clear way of proving the existence of that object. Declan does have a point that simply making a list of properties of real numbers is not very satisfying until you can prove that a set of numbers, together with appropriately defined addition and multiplication, actually exists.

Of course, this has been done time and time again with the real numbers, most notably with Dedekind cuts and Cauchy sequences. --COVIZAPIBETEFOKY (talk) 00:45, 27 August 2009 (UTC)

Another point that should perhaps be made is that those constructions do depend on some framework of set theory, so if you don't accept set theory, then these hardly suffice as constructions. The fact is, however, that you have to start somewhere, and in the predominant view, ZFC is accepted as the basis for nearly all of mathematics. --COVIZAPIBETEFOKY (talk) 00:50, 27 August 2009 (UTC)

I didn't mean to disparage embedding things in set theory in general, but rather the relevance of the practice to the question at hand. Implementing real numbers as Cauchy sequences is a worthwhile pursuit for a number of reasons, but it doesn't do much to elucidate the commutativity of real addition, and shouldn't really be considered a proof of said commutativity. Algebraist 00:55, 27 August 2009 (UTC)

I think you're missing Declan's point here. Sure, you can take the synthetic approach to defining real numbers, and then - duh! - addition is commutative. However, the synthetic approach makes the assumption that the set of real numbers satisfying all of those properties exists in the first place. This has to be proven first, which can easily be done by way of Dedekind cuts or Cauchy sequences.

The biggest hurdle in proving commutativity of addition in the set-theoretic constructions of natural numbers, integers, rationals and reals is proving that it is so for the natural numbers, and Carl has outlined that part below. --COVIZAPIBETEFOKY (talk) 01:10, 27 August 2009 (UTC)

From a certain perspective, "constructions" of number systems in set theory do not increase our confidence in the consistency of those number systems. Set theory is important as a foundational system because many systems of interest can be formalized within it. For example, we may argue in favor of set theory because we can formalize the real numbers within it. But this argument presupposes that we already know what the real numbers are, so that we can test whether they can be formalized within set theory. — Carl (CBM · talk) 01:18, 27 August 2009 (UTC)

(edit conflict) I take the point, but I don't think there's any avoiding it. The same applies to constructive approaches: you make up a definition, carefully making sure your definition ensures all the properties you want, and – duh! – addition is commutative. A better question might be "What is it about what we use the real numbers for that makes us want to force addition to commute?". One possible answer would be that a fundamental use of real numbers is to measure physical magnitudes, such as lengths of line segments, and there's a natural geometric way of adding lengths of line segments which is commutative. I have not thought much about this and have no idea if this is a very good answer. Algebraist 01:20, 27 August 2009 (UTC)

Declan, could you clarify exactly what your hang-up is here? If it's that you're assuming that a set of "real numbers" exists that satisfies all of its supposed properties, this can be proven - under the assumption that we accept the axioms of set theory. The fact that we have to assume something is an inescapable fact of mathematics, due to Godel's theorem.

If it's closer to what Algebraist is saying, in that you want justification for the assumption of commutativity of addition, well, you have Algebraist's answer here. --COVIZAPIBETEFOKY (talk) 01:36, 27 August 2009 (UTC)

Wow! I'm amazed by the thought provoking discussion that has taken place while I've been lazily snoozing. I'm not sure how to frame my problem in the language used above. My basic problem is that no-one seems to be able to prove that m + n = n + m for all, let's make it simple, natural numbers m and n. We know that the natural numbers exist: we can count with them! So I'm not sure that the existance of the natural numbers is a problem. My problem is the assumption that the natual numbers have the property that m + n = n + m. It seems that we do have to start with some axioms. I'm not sure how to phrase this, but if we removed any mention of the commutivity of the natural numbers and any properties directly implied by commutivity then could we prove the commutivity of the natural numbers? Can we prove, without first assuming, that m + n = n + m? ~~ Dr Dec (Talk) ~~ 11:58, 27 August 2009 (UTC)

Yes. It is possible (though not exactly easy) to prove, from the axioms of peano arithmetic, that addition is commutative. Carl has already addressed this below.

If we choose to use some particular set-theoretic model of natural numbers, it may turn out to be easier to prove, depending on the model. For example, it is really easy to prove commutativity of addition if we choose to define natural numbers as finite cardinal numbers. --COVIZAPIBETEFOKY (talk) 12:23, 27 August 2009 (UTC)

And now Shahab has also addressed the same problem. --COVIZAPIBETEFOKY (talk) 12:26, 27 August 2009 (UTC)

Declan is this what you want: In what follows I assume ZFC. N (the set of natural numbers) is defined as the smallest successor set. Assume associativity in N has been established. If not that too can be easily proven.) Let $M=\{n\in N:1+n=n+1\}$. Clearly $1\in M$. Suppose that $n\in M$. Then $1+n^{+}=(1+n)^{+}=(n+1)^{+}=(n^{+})^{+}=n^{+}+1$. Thus $n^{+}\in M$ and hence by the principle of induction M=N and so n+1=1+n for all n in N. Let $M'=\{n\in N:n+m=m+n\forall m\in N\}$. We have shown 1 is in M'. Assume n in M'. Then $m+n^{+}=(m+n)^{+}=(n+m)^{+}=n+m^{+}=n+(m+1)=n+(1+m)=(n+1)+m=n^{+}+m$. Thus $n^{+}\in M'$ and so M'=N. Regards--Shahab (talk) 12:19, 27 August 2009 (UTC)

Expanding on what Algebraist said: In the axiomatic approach, we take an object and choose a system of axioms that describe it to a greater or lesser extent. If we can prove some property of the object from those axioms, all that this shows is that the property in question is a logical consequence of those axioms, and thus no additional information about the object is needed, apart from the axioms, for us to know it has the property in question. In a certain sense, however, such a proof does not really tell us anything "new" about the system, because we already knew (or assumed) that the object satisfies the axioms, and thus we had already implicitly assumed that the object has every property that is a consequence of the axioms. In this sense, we only learn "new" things about an object when we learn that some property possessed by the object is not a consequence of the axioms we had been studying. — Carl (CBM · talk) 01:12, 27 August 2009 (UTC)

Maybe I'm misunderstanding what you're saying, but isn't the entire endeavor of mathematics to discover new logical consequences of axioms? Just because a property follows from the axioms doesn't mean it's trivial. Conversely, how can we learn things about an object that aren't predicated on the axioms? If a claim doesn't follow from the axioms, isn't it invalid? Rckrone (talk) 06:32, 27 August 2009 (UTC)

Yes, one part of the endeavor of mathematics is to discover new logical consequences of the axioms, and these consequences can be very non-obvious and difficult to determine. However, from a different viewpoint, once we have made the leap of accepting a certain collection of axioms, we have implicitly also accepted all logical consequences of those axioms, and thus when we prove a new theorem from the axioms we do not need to ask people who already accept the axioms to accept our new theorem as well.

Now, there is a distinction between a mathematical object itself, and the axioms used to study it. Finding proofs from axioms that an object satisfies is one way to discover properties of the object that we didn't already know. But, for example, there are many properties of the natural numbers that are not provable in Peano arithmetic, or even in ZFC. This non-provability doesn't make these properties invalid, it makes them interesting. — Carl (CBM · talk) 10:22, 27 August 2009 (UTC)

A further note that I think may be linked with Declan's doubts about the axiomatic approach, above. It is probably true that axioms do not give a complete or explanatory description of what they are talking about (probably due to a close reason, reading an article is not as clear as talking with the author). But I'd say that the main use of axioms in modern maths is more about recognizing known objects, rather than describing new ones --what makes an object more familiar is using it. That is, they are useful to detect known structures into new ones; in particular, in the middle of the jungle of an unknown problem under study. Your nose sniffs something familiar; you formalize it checking that a certain set of axioms is satisfied, and you immediately have at disposal all theorems and results in a given discipline (this is, by the way, a good reason why, as a mathematician, you can't allow yourself to completely ignore areas outside your field). From this point of view the introduction of the axiomatic method is like the invention of the prêt-à-porter : no more need of clothes made to measure! (oops, unintentional). Indeed, the meaning of "axiom" is not "a self-evident proposition" as sometimes people say; it's from the Greek word ἀξίωμα, and may be explained as "what makes something worth of being given a certain name". --pma (talk) 13:38, 27 August 2009 (UTC)

To prove that addition is commutative in Peano arithmetic, one proceeds in the only way possible, which is by induction. One first proves that addition is associative and that, for all a, 1 + a = a + 1. Then one proves by induction on b that b + a = a + b. The key string of equations is:

$a+(c+1)=a+(1+c)=(a+1)+c=(1+a)+c=1+(a+c)=1+(c+a)=(1+c)+a$

— Carl (CBM · talk) 00:51, 27 August 2009 (UTC)

To get at what I think the point of Declan's question is, we arrive at mathematical axioms through abductive reasoning and I don't know of any escape from that. There are various systems of logic like ludics that try to be somehow more primitive than Hilbert-style deduction but AFAIK that doesn't help at the very bottom. 02:28, 27 August 2009 (UTC) —Preceding unsigned comment added by 67.122.211.205 (talk)

Thanks to everyone for their input. I've enjoyed reading your comments very much. I'll sign of this thread now because I'm satisfied. That doesn't mean that someone can't start a sub-thread. In fact I'd quite like to see one. Thanks again! ~~ Dr Dec (Talk) ~~ 12:30, 27 August 2009 (UTC)

More on the commutivity of addition

Declan Davis asks, "Can we prove, without first assuming, that m + n = n + m?". The answer to this in the naive sense is yes. For example, the axioms of Peano arithmetic do not include the desired theorem as an axiom but do imply the theorem.

But there is a deeper level of analysis at which the answer is "no". If we assume a set of axioms for arithmetic which imply commutativity of addition, then we are at the same time implicitly assuming the commutativity of addition, along with all other the logical consequences of those axioms. One could ask if commutativity of addition is provable from logic alone, with no axioms at all: it is not, because there are many structures with a single binary function symbol interpreted by a non-commutative function. Thus some additional axioms will be required to establish commutativity, and at the moment we assume those axioms to be true we are also committing ourselves to the fact that addition is commutative.

A parallel example uses the axiom of choice (AC) and ZF set theory. In ZF, we can prove many theorems of the form "If Θ then AC". But none of these theorems actually proves that the axiom of choice holds. In order to obtain AC itself as the conclusion of a proof, we must introduce some assumption (Θ) that implies AC, at which point we have implicitly already assumed AC. — Carl (CBM · talk) 14:40, 27 August 2009 (UTC)

Good point, well made. ~~ Dr Dec (Talk) ~~ 15:14, 27 August 2009 (UTC)

Also on proving from axioms not being everything, you might be interested in the opposite endevour - getting axioms from your theorems which is what Reverse mathematics tries to do! Dmcq (talk) 15:12, 27 August 2009 (UTC)

An example of a theorem of commutativity (of multiplication) in algebra is of course Wedderburn's little theorem. --pma (talk) 15:45, 27 August 2009 (UTC)

Associativity of composition

Has anyone any idea how one might prove the associativity of composition?

• Let's start with real valued functions f, g and h. How do we prove that $(f\circ g)\circ h=f\circ (g\circ h)?$ ~~ Dr Dec (Talk) ~~ 23:14, 26 August 2009 (UTC)

This is true essentially by definition: $((f\circ g)\circ h)(x)=(f\circ g)(h(x))=f(g(h(x)))=f((g\circ h)(x))=(f\circ (g\circ h))(x)$. Algebraist 23:18, 26 August 2009 (UTC)

Yeah, I agree. (I was going to leave a note saying that this one was easier, but I was busy reading your post on the addition problem). Good work Algebraist.

...of course, it misses an "for all x" quantifier, and you need to assume Extensionality . --Stephan Schulz (talk) 23:28, 26 August 2009 (UTC)

It's not extensionality that is used but the definition of equality of functions. The proof does not depend on functions being implemented as sets in any particular way, or indeed at all. Algebraist 00:11, 27 August 2009 (UTC)

You do need to assume extensionality, but not in the set theoretic sense. What is ordinarily called "equality of functions" is more precisely extensional equality of functions. In systems with intensional equality, function composition generally not associative in the sense described above. In systems with extensional equality, the proof is immediate, as shown above. — Carl (CBM · talk) 00:43, 27 August 2009 (UTC)

Good point. Algebraist 00:47, 27 August 2009 (UTC)

August 27

A weird thing

Consider the set of all continuous functions f:[0,1]->R in the sup metric, i.e.

d(f,g)=sup{|f(x)-g(x)|}

Show that this space has a countable dense subset and therefore has a countable basis.

The proof is very easy the book gives a hint (which I won't say for those of you who want to do it yourselves), but immediately I noticed something WEIRD.

Since one point sets in hausdorff spaces are closed, there are at least as many open sets as points in the space (x->({x} complement)). Now the above space has a countable base so there are as many continuous function as real numbers. Is this true??? It's totally outrageous!!! Standard Oil (talk) 05:45, 27 August 2009 (UTC)

Why is it outrageous? It seems perfectly reasonable. I feel like there should be a simple elementary proof but I'm spacing on it right now. 67.122.211.205 (talk) 06:18, 27 August 2009 (UTC)

A continuous function on [0,1] is determined by its values at the rational points, so the cardinality of C([0,1],R) is c . There are plenty of relevant countable dense sets of this space, e.g. polynomial functions with rational coefficients, or even simpler, piecewise affine functions with rational entries. --pma (talk) 06:52, 27 August 2009 (UTC)

Oh yea polynomial functions with rational coefficients you mean Stone-Weierstrass theorem right? Sorry I'm not a math Ph.D and I find these new things very interesting. And the proof is indeed the piecewise affine functions with rational entries, if you mean straight lines joining points with both entries being rational Standard Oil (talk) 17:42, 27 August 2009 (UTC)

Uncountability of R

Resolved

I want to find an explicit bijection between $\mathbb {R}$ and $2^{\mathbb {N} }$ so that I can conclude that $\mathbb {R}$ is uncountable. Also what is the procedure to convert an arbitrary real number from its decimal representation to its binary representation. Thanks--Shahab (talk) 09:21, 27 August 2009 (UTC)

For the first question, see #The real numbers and subsets of the natural numbers above. —JAO • T • C 10:07, 27 August 2009 (UTC)

And for the other question check Binary numeral system#Conversion to and from other numeral systems. So let $\scriptstyle x=\sum _{k}2^{k}\epsilon _{k}$, where $\scriptstyle \epsilon _{k}\in \{0,1\}$, and $\scriptstyle \epsilon _{k}=0$ for all positive k but finitely many, and for infinitely many negative k; then, $\scriptstyle \epsilon _{k}=\lfloor 2^{-k}x\rfloor \mod 2$.--pma (talk) 10:29, 27 August 2009 (UTC)

Thanks.--Shahab (talk) 11:05, 27 August 2009 (UTC)

Is .99999999999 repeating=1?

I say it gets infinitely close, but never reaches 1, but then again 9/9=1...so maybe it is=1.Accdude92 (talk) (sign) 13:13, 27 August 2009 (UTC)

What does "9/9=1" have to do with this? 17/17=1, but that doesn't make 0.17171717171717171....17=1? DRosenbach ^{(Talk | Contribs)} 15:39, 28 August 2009 (UTC)

I'd assume the point was .999... = 9 * .111... = 9 * 1/9 = 9/9 = 1. —JAO • T • C 15:46, 28 August 2009 (UTC)

I believe someone asked this question several months ago. The proof I've seen is: X = 0.999..., 10X = 9.999..., 9X = 10X - X = 9.999...-0.999... = 9, X = 1. Wikiant (talk) 13:18, 27 August 2009 (UTC)

Oh, i check the archives, and I found noting.Accdude92 (talk) (sign) 13:20, 27 August 2009 (UTC)

See 0.999... (a Featured Article). -- Coneslayer (talk) 13:29, 27 August 2009 (UTC)

To make a long story short, there is a non-standard representation for every terminating decimal number wherein the final digit is reduced by one and then an infinite string of 9s is appended (after a decimal point if initially dealing with an integer). One of the educational problems here is that the notions of converging sequence and limits are not introduced right alongside the introduction of the number line in elementary school. To say that 0.999... "gets infinitely close" to 1 is to fail to distinguish betweeen a sequence of numbers and simply a number that is the limit of such a sequence. We say that the sequence 0.9, 0.99, 0.999, ... goes to 1 in the limit, while 0.999...=1. —Preceding unsigned comment added by Julzes (talk • contribs) 14:00, 27 August 2009 (UTC)

In formal terms, 0.999... represents a limit. In this case the limit means that as you add another 9 to the decimal expansion you get closer to 1. This is true: 0.99 is closer to 1 than 0.9, 0.999 is closer to 1 than 0.99, 0.9999 is closer to 1 than 0.999, and so on. If a_n is 0.99...9 where there are n 9s after the decimal place then clearly 0 < a_n < a_n+1 < 1 for any positive whole number n. Actually

$a_{n}=1-{\frac {1}{10^{n}}}\ .$

So we are getting closer and closer to 1 as we add more and more 9s. Notice that every a_n has a finite number of 9s after the decimal place. Now, this is just one thing we need when we talk about limits. The next thing we need is that if we choose a really, really small distance, say ε, then we can always find an n so that a_n lies within that distance from 1. Actually we can solve: we want a_n to be within a distance of ε from 1, so we want a_n > 1 - ε (just draw a picture: 0 < a_n < 1 and we want it to be within a distance of ε of 1, well inside the interval [0,1] the point 1 - ε is a distance ε from 1. We want a_n to be closer to 1 so we need a_n > 1 - ε). Solving this gives

$n>\log _{10}\left({\frac {1}{\varepsilon }}\right)=-\log _{10}\varepsilon \ .$

So we can see that 0.999...9 gets closer and closer to 1 as we add more and more 9s, and that we can always add a certain number of 9s so that we get as close to 1 as we like (and if we carry on adding 9s we would get even closer!). All the time we have a finite number of 9s.

The statement 0.999... = 1 is true: I've proven it for you above. All it means is that 0.999...9 gets closer and closer to 1, and that we can get as close as we might like. We never claim that we can add, say ten trillion, 9s and finally get to 1. This is the idea of a limit. ~~ Dr Dec (Talk) ~~ 14:24, 27 August 2009 (UTC)

No, 0.999... is not "a limit", or at least not in the sense you suggest. It's one (infinite) decimal representation of the real number more usually written as 1. Please read the FA linked above. --Stephan Schulz (talk) 14:41, 27 August 2009 (UTC)

... which says, in the section 0.999...#Infinite_series_and_sequences''Infinite series and sequences'':

$0.999\ldots =\lim _{n\to \infty }0.\underbrace {99\ldots 9} _{n}=\lim _{n\to \infty }\sum _{k=1}^{n}{\frac {9}{10^{k}}}=\lim _{n\to \infty }\left(1-{\frac {1}{10^{n}}}\right)=1-\lim _{n\to \infty }{\frac {1}{10^{n}}}=1.\,$

I understand there are various ways of interpreting 0.999..., but surely one entirely reasonable and standard viewpoint is to interpet it as a limit. Gandalf61 (talk) 14:56, 27 August 2009 (UTC)

Exactly! The limit of my a_n is exactly the infinite string of digits of which Stephan speaks. He says that the infinite string of digits is equal to 1, I say that the limit of a_n is 1. We both come to the same final point. The difference is that defining it as a limit gives you something tangable that you can put your finger on. Where's the problem in that? ~~ Dr Dec (Talk) ~~ 15:02, 27 August 2009 (UTC)

Let me quote an authoritative source:

Sure, it's a limit. It's also a number. Why do you think a limit shouldn't be a number, or a number shouldn't be a limit? .

We should make an authomatic link to the article on 0.999.., from all questions containing the string "999..". --pma (talk) 15:13, 27 August 2009 (UTC)

In a certain setting they are interchangable. Given a sequence of real numbers (x_n) the limit, if it is defined, will be a real number. And any real number x is the limit of a sequence, namely the sequence (x_n) where x_n = x for all n. ~~ Dr Dec (Talk) ~~ 15:20, 27 August 2009 (UTC)

Hehe! Correct. But it's quite a bit funny writing here proofs that 1=0,999.. every two weeks or so ;-) (indeed, repetita juvant)--pma (talk) 15:30, 27 August 2009 (UTC)

The statement is true for ordinary real numbers but it's worth reading the 0.999... article for cases where it isn't true. For instance there's a game where each position can be given a value, but the game's value equivalent of 0.9999... is less than that for 1. Dmcq (talk) 14:41, 27 August 2009 (UTC)

It's quite simple to accept that numbers are limits and vice versa. After all, what do people think is going on when a limit is evaluated? —Anonymous Dissident^Talk 15:30, 27 August 2009 (UTC)

Hmmm, that's not exactly correct. Not every well-defined limit is a number; some limits are functions. Let f : R → R be a smooth function then

$\lim _{\varepsilon \to 0}{\frac {f(x+\varepsilon )-f(x)}{\varepsilon }}$

isn't a number; it's a function. ~~ Dr Dec (Talk) ~~ 15:42, 27 August 2009 (UTC)

c'mon... of course everybody here's talking of real numbers  ;) --pma (talk) 15:56, 27 August 2009 (UTC)

Okay, okay... Sorry! :oP ~~ Dr Dec (Talk) ~~ 15:58, 27 August 2009 (UTC)

I never meant to imply all limits are numbers; in saying "that numbers are limits and vice versa" I meant it in the way that one might say "men drink on a Friday night", or "teenagers vandalise the car park" – some do, but not all... if that makes sense. —Anonymous Dissident^Talk 16:02, 27 August 2009 (UTC)

I know what you wanted to say, I was just being silly. But the statment "number are limits and visa versa" means that both numbers are limits and limits are numbers. ~~ Dr Dec (Talk) ~~ 16:08, 27 August 2009 (UTC)

Indeed, you're correct. I hope you don't mind, but I've appended a </small> tag to the end of your comment so the rest of the refdesk is not out of format. —Anonymous Dissident^Talk 16:14, 27 August 2009 (UTC)

Line bundles and cohomology

I've been working on trying to classify line bundles over hypersurfaces. The classification that I'm looking for is more refined than that of the Stiefel–Whitney class. Let M be a real n-dimensional smooth hypersurface embedded in Rⁿ⁺¹. For my purposes, the space of line bundles over M coincides with the quotient space $\Omega ^{1}(M)/\Lambda ^{1}(M)$, where $\Omega ^{1}(M)$ is the space of all differential one-forms on M and $\Lambda ^{1}(M)$ is the space of all exact differential one-forms on M. Now, I want to understand this space a little better.

Let $U\subset V\subset W$ be nested vector spaces, then we construct the formal isomorphism $W/U\cong (W/V)\times (V/U).$ Now, notice that $\Lambda ^{1}(M)\subset \Gamma ^{1}(M)\subset \Omega ^{1}(M)$ where $\Gamma ^{1}(M)$ is the space of closed differential one-forms on M. We get that

$\Omega ^{1}(M)/\Lambda ^{1}(M)\cong (\Omega ^{1}(M)/\Gamma ^{1}(M))\times (\Gamma ^{1}(M)/\Lambda ^{1}(M))=(\Omega ^{1}(M)/\Gamma ^{1}(M))\times H_{dR}^{1}(M)\ ,$

where $H_{dR}^{1}(M)$ denotes the first de Rham cohomology class. We can make sense of the space $\Omega ^{1}(M)/\Gamma ^{1}(M)$ by noting that the exterior derivative d is such that $d:\Omega ^{1}(M)\to \Omega ^{2}(M)$, the kernel of d is given by $\Gamma ^{1}(M)$ and the image is given by $\Lambda ^{2}(M)$, i.e. the space of exact differential two-forms on M. It follows that $\Omega ^{1}(M)/\Gamma ^{1}(M)\cong \Lambda ^{2}(M).$ Finally, our original space $\Omega ^{1}(M)/\Lambda ^{1}(M)$ can be shown to have the following property:

$\Omega ^{1}(M)/\Lambda ^{1}(M)\cong \Lambda ^{2}(M)\times H_{dR}^{1}(M)\ .$

My question falls into two parts:

1. Can anyone construct the isomorphism explicitly, or at least give some clues as to its nature?
2. Can anyone say anything about the topology or geometry of these two spaces?

~~ Dr Dec (Talk) ~~ 13:53, 27 August 2009 (UTC)

1. Since for plain vector spaces there is no natural isomorphism for $\textstyle W/U\cong W/V\times V/U$ I'd say you need an additional structure to define an explicit one, like a scalar product. In your case M is naturally a Riemannian manifold, so I guess you'll use a bit of Hodge theory (which implies changing a bit the functional setting).

2. $\Omega ^{k}(M)$ is a Fréchet space wrto the uniform convergence of derivatives of all orders; you are taking a quotient over a closed subspace, hence you still have a Fréchet space; the same for the RHS.

--pma (talk) 16:31, 27 August 2009 (UTC)

Thanks pma; I'll try to find some details on Fréchet spaces. I had heard of them before, but I've never studied them. On another point: I'm not assuming that M is a Riemannian manifold. There's really no need. My construction only requires that M has a torsion-free connexion. In fact, my work started in the affine setting (where we have a volume form on each tangent space instead of a metric), but that turned out to be too strict. There's really no need for any structure. (Although maybe the isomorphism will, in the end, depend upon the choice of connexion). ~~ Dr Dec (Talk) ~~ 16:50, 27 August 2009 (UTC)

OK, but since you took M embedded in Rⁿ⁺¹, if you want you already have a Riemann structure; and in any case for a finite dimensional manifold M you can always pick one. But I believe you, that you need less! --pma (talk) 17:21, 27 August 2009 (UTC)

What is an axiom?

And yes, I have looked at the relevant Wikipedia article, so I'll be more specific with my confusion...

What is the distinction between an axiom and a definition. For example, if I define a new function $f(x)=x^{2}+x$, have I introduced an axiom? Or, perhaps a slightly different example, do the complex numbers depend on any additional axioms to the reals? Or even, when defining a particular group (as opposed to defining what groups are), am I introducing axioms? The reason I ask is that I heard someone saying that it is a mistake to say that the complex numbers depend on any additional axioms [to the reals] which led me to reconsider what I understood the word to mean.--Leon (talk) 16:06, 27 August 2009 (UTC)

The way I understand it, the key difference between an axiom and a definition is that an axiom is a proposition or base from which other abstractions and definitions stem. Such an axiomatic proposition is seen to be self-proving or -evident; unable to be disproved. I guess axioms are the logical principles that underscore what makes good mathematical sense – what makes 1+1=2. Don't take my word for it, though. —Anonymous Dissident^Talk 16:12, 27 August 2009 (UTC)

That makes sense—to some extent. But it's difficult to see from what a definition does "stem out". And how can definitions be disproved?--Leon (talk) 16:18, 27 August 2009 (UTC)

As my dictionary says: An axiom is "a proposition regarded as self-evidently true". A definition is "a statement of the exact meaning of a word or the nature or scope of something." An axiom gives you (something assumed to be) a fact; a definition gives you meaning. Clearly some all definitions can be axioms, but not all axioms can be definitions. ~~ Dr Dec (Talk) ~~ 16:21, 27 August 2009 (UTC)

Then how are the group axioms "self-evidently true", for instance? And in my above examples, do any of the constructions I speak of introduce new axioms?--Leon (talk) 16:29, 27 August 2009 (UTC)

They would have been four facts about certain mathematical structures which later became known as groups. We've been talking about the problems of axiomatic mathematics above. Your question is a matter of definition. Axioms talk about properties, definitions give definitions: We say that an A is a B if it has the properties {p₁, …, p_n}. (The resulting axiom would be that an A with the properties {p₁, …, p_n} is a B. ~~ Dr Dec (Talk) ~~ 16:37, 27 August 2009 (UTC)

I think there is little, if any, difference in underlying meaning, and use of one term rather than the other is largely dictated by custom and tradition. For example you could define the properties of evenness and primeness on the natural numbers, then you could define an evenprime number as a natural number that is (a) even and (b) prime. In this context, the properties of evenness and primeness are axioms - they are the evenprime axioms. You could then show that only one natural number, namely 2, satisfies the evenprime axioms. Now you can turn this process on its head and define 2 as the unique evenprime natural number - and you have an axiomatic definition of 2. Gandalf61 (talk) 16:42, 27 August 2009 (UTC)

(ec) Leon's objection is right. "A proposition regarded as self-evidently true" is not very good as definition of axiom, with the due respect to OED. I happened to write it above; the word axiom is from the Greek word ἀξίωμα, and may be explained as "what makes something worth (ἄξιος) of being given a certain name". E.g. the axioms of groups explain what properties are needed to be worth of being called a group. There is nothing of self-evident, although of course people try to choose axioms as natural and elementary as possible. A definition is also of more local and particolar use (e.g. like in Leon's example, when one sais : "let us define f(x)=x²+x.."). --pma (talk) 17:09, 27 August 2009 (UTC)

I quoted the OED because I thought that the difference between axiom and definition could be resolved by the use of a dictionary. Axiom, from the Greek axiōma meaning what is thought fitting. The OED translation, IMHO, cuts staight to the heart of the issue. ~~ Dr Dec (Talk) ~~ 17:17, 27 August 2009 (UTC)

Also, you're not going to write down the group axioms unless your have a good idea of what you're about to call a group is. As such, when you write down the group axioms you're going to write down self-evident truths about these structure. People didn't invent groups; they discovered them. Moreover, they didn't invent them by writing down some random axioms and saying "Right, put the kettle on, let's see where these take us." ~~ Dr Dec (Talk) ~~ 17:23, 27 August 2009 (UTC)

Sure, so what? well, no matter...--pma (talk) 18:30, 27 August 2009 (UTC)

Well, if my last comment was so trivial as to require an answer of "so what?", then surely my original point is quite clear. ~~ Dr Dec (Talk) ~~ 19:18, 27 August 2009 (UTC)

First: thanks guys for your help!

Second, in the cases of my particular examples, can you tell me if those constructions constitute invocations of further axioms? By further, I mean ones on top of the real line and/or the group axioms?--Leon (talk) 17:19, 27 August 2009

The way I was taught was that a definition introduces a new term (without the definition a term would be meaningless), whereas an axiom uses all previously defined terms, but puts them together in a way that is not self-evident (provable) from their definitions. -- 128.104.112.102 (talk) 17:29, 27 August 2009 (UTC)

In consumer behavior modeling, we make the distinction between "external validity" and "internal validity." Roughly speaking, a statement is internally valid if it is consistent with truths within the confines of the model. A statement is externally valid if it is consistent with truths external to the model. It appears (to me) that the distinction between axiom and definition is similar. Within the confines of a model, I can define 1+1 to equal 3 and then go on to make other statements that would be true *given* the definition (i.e., I establish internal consistency). However, the definition is not consistent with truths external to the model. Hence, I do not have external consistency. In short, it seems to me that it is sufficient that definitions achieve internal consistency, but necessary that axioms achieve external consistency. Wikiant (talk) 17:25, 27 August 2009 (UTC)

As I understand it, a definition just gives a more succinct label to a concept that we can already express. For example if we define the complex numbers as the quotient space R[x]/(x² + 1), that lets us talk about the concept using the term "complex numbers" instead of having to explain "the quotient space R[x]/(x² + 1)" every time we want to refer to that space. Axioms declare properties of or relations between objects we've already defined that we want to take as true but that don't follow from their definitions. However I don't see why you couldn't lump most axioms about an object into the definition of the object so I'm not really sure how clear the distinction always is. I don't know axiomatic set theory, but from the naive foundations that get you to the real numbers you can get to the complex numbers just with definitions. AFAIK you should be able to get to pretty much all the math we know and love just with definitions once you accept the underlying axioms, which is why those axioms are chosen. I'm not really sure though what would prevent us from "defining" the complex numbers completely from scratch with a definition that includes all the axioms. Rckrone (talk) 19:23, 27 August 2009 (UTC)

DISAMBIGUATION:

• In epistemology, an axiom is a proposition, expressible as a complete sentence, that is self-evidently true, in the sense that you can't understand what it says until you know the fact that it asserts, and that is at the base of knowledge in that other knowledge depends on it. See self-evidence. My statement that I am conscious is a self-evident proposition. Your statement that I am conscious is not a self-evident proposition.
• In mathematics, an axiom is something else entirely. Not unrelated, though.

Michael Hardy (talk) 20:33, 27 August 2009 (UTC)

Part of this is a creep in meaning over time. To Euclid, mathematical (geometric) axioms were indeed self-evident. It is a relatively recent development to call any assumed statement an "axiom". To the Greeks, this would have been absurd. It took at least the development of non-Euclidean geometry in the 19th century before there was general awareness that distinct, reasonable axiom systems could contradict each other. Our current understanding of formal logic is not even that old. — Carl (CBM · talk) 00:06, 28 August 2009 (UTC)

Diophantine variances

For certain pedagogical purposes, I want to fiddle around with some variances of small-integer-valued random variables without getting distracted by the arithmetic involved in actually computing the variances.

For that reason, it could be convenient if simultaneously

• The values of the random variables are small integers;
• The expected values are small integers;
• The variances are small integers. (Don't worry about the standard deviations. In other words, the varinces need not be squares of integers.)

Is there a way—maybe even an algorithm?—for producing such things? Michael Hardy (talk) 20:38, 27 August 2009 (UTC)

If I have this right, you're looking for a sequence of integers whose sum is 0 and whose sum of squares is divisible by the number of elements in the sequence? Are there any other constraints? If not it should be pretty easy to massage the values of an arbitrary sequence to make it work. For example if you had any k numbers with a sum of 0 and a sum of squares n > k, you could tack on n-k zeros to your sequence and you'd be done. Then translate the whole thing if you want some other mean besides zero. Rckrone (talk) 21:15, 27 August 2009 (UTC)

Well, of course there are other "constraints" if you mean things not precisely definable, but recongizable by people with common sense. Just the usual stuff: don't make the whole thing too complicated, don't add coincidences from which naive students may make inductive leaps, don't add things likely to distract attention from where you want it, etc. I'll fiddle with this more and see what I think. Michael Hardy (talk) 02:13, 28 August 2009 (UTC)

....to clarify further: If one had an algorithm that would churn these out by the truckload, then one would look among the results for cases that looked good from the point of view of the other "constraints". So if you can provide such an algorithm, that would take care of everything except what I would need to do myself because only I know the whole story of the context in which I would use these. Michael Hardy (talk) 02:53, 28 August 2009 (UTC)

The probability distribution f(x) = (4−x)/10 for x = 0,1,2,3 has mean value 1 and variance 1. Bo Jacoby (talk) 21:40, 27 August 2009 (UTC).

August 28

Automorphisms

I want to prove the following result: Suppose I have an irreducible factor of the polynomial $x^{n}-1$, say h(x) in $\mathbb {Z} _{p}[x]$ (p prime). Now my first question is: If it is said that the Frobenius automorphism fixes h(x) does it mean that the coefficients of h(x) are permuted. Why does it happen? Secondly supposing we consider a splitting field in which the roots of h(x) exist. Will the Frobenius automorphism (over the splitting field Z_p(a,b,c...)) permute the roots a,b,c... and why? Finally why can't we define a splitting field for a polynomial defined over any general ring as opposed to over fields as the article Splitting field says? Thanks--Shahab (talk) 05:21, 28 August 2009 (UTC)

(I may be misunderstanding your questions, so if you do not find my answers helpful please ask again.) The Frobenius automorphism $\sigma$ on $K=\mathbb {Z} _{p}$ is the identity (there are no non-identity automorphisms of $\mathbb {Z} _{p}$). Therefore $\sigma$ fixes all polynomials over K, including h(x), no matter what h(x) is. Now let L be the splitting field of h over K, and let $\sigma$ be the Frobenius automorphism of L. Since $\sigma$ fixes K (why do we know this?), $\sigma h=h$, so the roots of h and $\sigma h$ in L are the same, and thus $\sigma$ permutes the roots of h; that is, $\sigma$ is in the Galois group of L over K.

Your last question is somewhat subtler. Recall that when we wish to adjoin a root of an irreducible polynomial f to a field K, we construct the field $L=K[X]/(f(X))$. (This is a field because (f(X)) is a prime ideal in the ring K[X], which is true because f is irreducible.) There is nothing really stopping us from doing the same operation to a ring R; fundamentally, the reason why we don't do this is because the results are uninteresting (I haven't verified this myself, but I assume that that is so, otherwise we would talk about splitting rings). However if we try to construct these "splitting rings" we can sometimes lose nice properties. For example, let $R=\mathbb {Z} /4\mathbb {Z}$, the cyclic ring of 4 elements, and let $f(x)=2x+1$. Let $S=R[X]/(f(X))$; then S has only one element, so there is no embedding of R into S anymore. Eric. 98.207.86.2 (talk) 07:48, 28 August 2009 (UTC)

Thanks Eric. I understand that the Frobeinus map over $\mathbb {Z} _{p}$ is the identity due to Fermat's little theorem. My main problem was the second question which is still not clear as it was incompletely asked. What I really want to do is this: Given that $g(x)\in \mathbb {Z} _{p^{r}}[x]$ is such that $g\equiv h(\mod p)$ (which I take to mean that the coefficients of g(x) and h(x) agree mod p) and g(x) is the irreducible factor of $x^{n}-1$ then the Frobenius map permutes the roots of g(x). Now $\mathbb {Z} _{p^{r}}$ is the ring in question and the roots must lie in the splitting field hence my last question. Assuming I have some splitting field F of g(x) I reason like this: (All computations are mod p and $\sigma$ is the Frobenius automorphism) g=h and so $\sigma (g)=\sigma (h)$ (where $\sigma$ is really acting upon the coefficients). But $\sigma (h)=h$ and so $\sigma (g)=h=g$. Now I want to use the fact(?) that automorphisms permute the roots of irreducible polynomials when the coefficients are fixed by the automorphism (I'll apply the Frobenius map on F). My second question is that I want a proof of this. Also please excuse me if some of what I have written is obvious or redundant. Since I am mostly self taught so there are quite a few gaps in my knowledge. Thanks again--Shahab (talk) 09:17, 28 August 2009 (UTC)

Are you trying to understand how to lift polynomial factorizations from Z/pZ to the p-adic integers, as in the algorithm to factor integer polynomials described in the original LLL paper? You can probably do that more easily than by developing a Galois theory for arbitrary commutative rings. JackSchmidt (talk) 14:41, 28 August 2009 (UTC)

Unfortunately I'm confused. I see that are you given an irreducible polynomial g (by "the irreducible factor" of $X^{n}-1\in \mathbb {Z} [X]$ I suppose you mean the one with degree $\phi (n)$, which you then project into $\mathbb {Z} _{p^{r}}[X]$ by taking the coefficients mod $p^{r}$) over $\mathbb {Z} _{p^{r}}$. However you introduce two new polynomials h and f and I don't know what those are. You also mention the Frobenius map on $\mathbb {Z} _{p^{r}}$; however, in general, this map (of raising to the power p) is not a ring homomorphism when $r>1$, so it would be unlikely to permute the roots of g or do anything nice.

Your last fact, that field automorphisms permute the roots of irreducible polynomials when the coefficients are fixed by the automorphism is correct. Eric. 216.27.191.178 (talk) 20:09, 28 August 2009 (UTC)

I made the mistake of writing f when I really meant h. I'll try to explain myself more clearly now. (BTW Theorem 1 of this paper online is the closest thing I could find on the internet to what I am trying to prove). I have some fixed irreducible factor of x^n-1 in Z_p[x] which is h. In Z_p^r[x] the same h goes by the name g. The roots of g lie in some extension field F (I don't know how such a field can be constructed. Perhaps we take the quotient field of Z_p^r and then find the splitting field) of Z_p^r. I want to raise all elements of F to pth power and then show that roots are only permuted. Thanks--Shahab (talk) 08:02, 29 August 2009 (UTC)

How do I prove the fact that that field automorphisms permute the roots of irreducible polynomials when the coefficients are fixed by the automorphism is correct.--Shahab (talk) 08:02, 29 August 2009 (UTC)

(dedent) Ah, that is clear. First I'll address the easy part (namely, the part I know how to prove). Suppose $\sigma$ is an automorphism of the field L, the fixed field of $\sigma$ is K, and f is a polynomial over K that splits completely in L; we wish to prove that $\sigma$ permutes the roots of f. For any polynomial g over L and $\alpha \in L$, we have $\sigma (g(\alpha ))=(\sigma g)(\sigma \alpha )$ (because $\sigma$ is an automorphism of L), so $\sigma$ maps the roots of g bijectively to the roots of $\sigma g$. In the case of f, we know $f=\sigma f$ (since the coefficients of f are fixed by $\sigma$); thus $\sigma$ bijectively maps the roots of f to the roots of f, i.e., permutes the roots of f.

As for what you're trying to prove, we run into difficulties. (The ring $R=\mathbb {Z} _{p^{r}}$ does not have a quotient field for r > 1 because R is not an integral domain; in particular $p\cdot p^{r-1}=0$.) I ran through an example to see if I could find the result you were looking for: take p = 2, r = 2, and $f(x)=x^{2}-x+1\in \mathbb {Z} _{p}[x],g(x)=x^{2}-x+1\in R[x]$. f and g are irreducible, and divide $x^{6}-1$. If we square the coefficients of g, we get another polynomial $x^{2}+x+1\in R[x]$, which being unequal to g, cannot have the same roots (even were we working in a ring where they both had all their roots). Eric. 98.207.86.2 (talk) 11:32, 29 August 2009 (UTC)

The best bet for understanding this is to just work with the p-adics. Use Hensel's lift to get the factorization over the p-adic integers, find the ring of integers A of the splitting field of the p-adic polynomial, the galois group is abelian so you can take an arbitrary factor of (p) as P and then look at A/P^r as the "extension field" of Z/p^rZ. Make sure that n and p are coprime (6 and 2 is naughty) otherwise the factorization can change. The paper you mentioned has a nice reference [2] that explains the LLL Z[x] factorization algorithm. The permutation of the roots happens in A/P^r the same as it does in A and the same as it does in A/P. If you are naughty and take n and p to have common factors, then the number of roots is not stable, and so the permutation actions cannot possibly be equivalent. JackSchmidt (talk) 13:06, 29 August 2009 (UTC)

That sounds quite reasonable to me. I am wondering if you could explain a few details for me. We have $L=\mathbb {Q} _{p}(\zeta _{n})$ is the splitting field of $x^{n}-1$ over $K=\mathbb {Q} _{p}$. I forget why L/K is abelian (cyclic, right?) but I can look that up myself. If n and p are coprime then L/K is unramified, but I don't see what that gets us. If f is a polynomial over $R=\mathbb {Z} _{p}$ we can project it to $R/p=\mathbb {Z} /p$, and that projection should split completely in A/P, where we have a Frobenius automorphism that permutes its roots in A/P, However I don't see how that helps us in A and A/P^r. Also, what do you mean by "the number of roots is not stable"? Eric. 98.207.86.2 (talk) 22:31, 29 August 2009 (UTC)

The Galois action on the field of fractions of A, L, restricts to a nice action on A itself. That action permutes the n roots of x^n-1 in A, and that action is permutation isomorphic to the action of the Galois group of A/P over Z/pZ on the roots of x^n-1. However, if n and p are not coprime, then there is a different number of n'th roots of unity in L versus A/P, so the actions cannot be permutation isomorphic. For example, if n=2 and p=2, then one has that both L=Q_2 and A=Z_2 have 2 square roots of unity, but Z/2Z=A/P has only one, Z/4Z has two, and Z/8Z has four. JackSchmidt (talk) 00:35, 30 August 2009 (UTC)

Thanks. I see my trouble now, I had gotten myself confused about the definition of Frobenius map#Frobenius_for_local_fields. Eric. 98.207.86.2 (talk) 01:35, 30 August 2009 (UTC)

Nonconvex polyhedra

I have a question: why is it the polyhedra {5/2, 3} and {5/2, 5} both exist but {5/2, 4} doesn't? Professor M. Fiendish, Esq. 12:38, 28 August 2009 (UTC)

The article on the four Kepler-Poinsot polyhedra states that "Augustin Cauchy proved the list complete by stellating the Platonic solids, and almost half a century after that, in 1858, Bertrand provided a more elegant proof by facetting them." Therefore, I suppose that from the definition of a regular star-polyhedron it follows directly that its vertices span a Platonic polyhedron as convex hull. If this supposition is correct, making a complete list is just a matter of checking a finite number of cases. (I wrote "I suppose" because I did not look for the exact definition. Of course, one can give apparently weaker definitions, but equivalent a posteriori, that make the proof more difficult and more general.) --pma (talk) 18:05, 28 August 2009 (UTC)

nested gaussian integrals.

First off: This is not for a homework problem

I am doing some work which requires calculation of nested time integrals (which come up in perturbation theory). I was able to work out a nice formula for a second order equation of the form

${\begin{aligned}&\int _{-\infty }^{\infty }dt_{2}\int _{-\infty }^{t_{2}}dt_{1}\exp \left(-{\frac {t_{2}^{2}}{2\sigma _{2}^{2}}}-i\Delta _{2}t_{2}\right)\exp \left(-{\frac {t_{1}^{2}}{2\sigma _{1}^{2}}}-i\Delta _{1}t_{1}\right)\\&\ \ \ \ \ \ =\pi \sigma _{1}\sigma _{2}\exp \left(-{\frac {1}{2}}(\Delta _{1}^{2}\sigma _{1}^{2}+\Delta _{2}^{2}\sigma _{2}^{2})\right)\operatorname {erfc} \left(i{\frac {\Delta _{2}\sigma _{2}^{2}-\Delta _{1}\sigma _{1}^{2}}{\sqrt {2\sigma _{1}^{2}+2\sigma _{2}^{2}}}}\right)\end{aligned}}$ .

Since there are nice efficient ways to calculate the error function, I don't need to do any time-consuming numerical integration for the second-order nested integral. But I am stuck coming up with a similar solution to a third-order nested integral.

$\int _{-\infty }^{\infty }dt_{3}\int _{-\infty }^{t_{3}}dt_{2}\int _{-\infty }^{t_{2}}dt_{1}\exp \left(-{\frac {t_{3}^{2}}{2\sigma _{3}^{2}}}-i\Delta _{3}t_{3}\right)\exp \left(-{\frac {t_{2}^{2}}{2\sigma _{2}^{2}}}-i\Delta _{2}t_{2}\right)\exp \left(-{\frac {t_{1}^{2}}{2\sigma _{1}^{2}}}-i\Delta _{1}t_{1}\right)$

Any help would be greatly appreciated. mislih 20:32, 28 August 2009 (UTC)

I think you can express the triple integral in terms of the erf function [or antiderivatives of it] (and, possibly, even the analog multiple integral). I'll give you some hints here below.

• You want an integral of a function of the form exp(-Ax²-By²-Cz²-2ax-2by-2cz) on the set {x<y<z}. Here A,B,C are positive constant, and a,b,c are actually imaginary numbers. Notice that {x<y<z} is the intersection of two half-spaces, with an angle of 2π/3.
• Since the integral is clearly an entire function of a,b,c, you can do the computation just for all real a,b,c and then extend by analytic continuation the result to all complex a,b,c; the extension will be automatic (recall that erf(z) is an entire function).
• Now complete the square, that is, here, use the identity exp(-(u+k)²)=exp(-u²-2ku)exp(-k²), and then change variable. This way you transform the initial into the integral of exp(-x²-y²-z²) on a suitable domain which is the intersection of two affine half-spaces, whose angle and position wrto the origin, of course, depend on all the initial coefficients (there is also a factor coming from the complete-the-square thing and from the Jacobian of the affine transformation of the variables).
• Thanks to the rotation invariance of exp(-x²-y²-z²), you can rotate the domain of integration so that its edge (i.e. the singular line of the boundary) is a line parallel to the z axis. A partial integration in the z variable gives you a factor sqrt(π) in front of the double integral of exp(-x²-y²) on an angular domain on the x,y plane (that is, the orthogonal section of the previous three-dimensional domain).
• Again by rotation invariance, you may assume that the angular domain is bounded by a half-line parallel to the y-axis, and you are left with the integral of exp(-x²-y²) on this domain. A first integration produces a partial integral of the form erf(αx)exp(-x²), that you still have to integrate in x>β. (I don't see yet a formula for the latter antiderivative of erf(αx)exp(-x²); but if the matter is just about numerics, it certainly has a very fast power series expansion).

I hope it's clear enough; of course to complete the computation you have some work to do in order to write everything in terms of the initial data. In case ask here again and we'll try to answer.--pma (talk) 21:47, 29 August 2009 (UTC)

August 29

Why use Poisson distribution as an approximation to binomial?

I understand that the Poisson distribution can be used as an approximation to a binomial distribution (if n is sufficiently large and p sufficiently small). I've seen it demonstrated, and I think I get the math involved. But why would you want to use this approximation instead of just using the binomial? What is the advantage of using the Poisson? —Preceding unsigned comment added by 118.241.57.8 (talk) 02:03, 29 August 2009 (UTC)

One could just consider it an out-of-date notion, relevant for a time when calculation was more difficult.Julzes (talk) 02:16, 29 August 2009 (UTC)

One reason is you might have no clue how big n is, or p, but you may still have a good estimate of λ = np. Michael Hardy (talk) 02:32, 29 August 2009 (UTC) ...and besides, obviously it's simpler. Michael Hardy (talk) 02:33, 29 August 2009 (UTC)

The last answer is better than mine.Julzes (talk) 03:56, 29 August 2009 (UTC)

• As Michael said, the Poisson distribution is much simpler. Why should you (the mathematician, not the computer) do calculations involving two parameters, and think about the problem in terms of two parameters, when all the relevant information is contained in one?
• The faster computers become, the more difficult the calculations people use them for. Calculating just one value of a distribution is of course easy, but it's not unthinkable a problem would require billions of such calculations. In such cases there may be a significant difference between evaluating a binomial distribution, which requires 3 factorials, and Poisson which only requires one.

-- Meni Rosenfeld (talk) 21:43, 29 August 2009 (UTC)

The binomial distribution is (a limiting case of) the hypergeometric distribution for large populations, and the poisson distribution is (a limiting case of) the binomial distribution for large samples. You may like to study Cumulant#Cumulants_of_some_discrete_probability_distributions to see that the relationship between binomial and poisson distributions are like the relationship between ellipses and parabolas. The parabola can be used as an approximation to an ellipse. But why would you want to use this approximation instead of just using the ellipse? Bo Jacoby (talk) 22:47, 29 August 2009 (UTC).

The prospective user of a quick approximation to something where an exact calculation is possible but may take more time needs to keep in mind that the trade-off may not be a good one because of the need to keep track of errors. If the approximation really is good enough on its face, that's one thing; but where there is uncertainty it may be necessary in very complicated cases to do some sort of prior study of the nature of the trade-off before one decides whether to use the quick approximation.Julzes (talk) 04:00, 30 August 2009 (UTC)

The Tychonoff theorem

There's every reason to believe that the product space X is (in terms of sets) different from all the spaces X(alpha) in the family. Now take the product space X of the collection of all compact spaces. X is compact hence it belongs to the collection, and so X is different from X (in terms of sets). Is this where proper class come in? Standard Oil (talk) 12:35, 29 August 2009 (UTC)

Right. Within the category of (compact) topological spaces you are only allowed to do products of families of spaces indicized by sets. Indeed what you proposed is just a topological version of a paradox that you may repeat in all versions: the sup of all ordinals is not an ordinal; the union of all sets is not a set.. &c. This does not mean that you can't endow a proper category with a structure that mimes the usual "small" structures (a group structure, a topological structure and so on).--pma (talk) 13:10, 29 August 2009 (UTC)

Question about sets

Hey, I've got a logic question relating to sets that I havn't been able to quite figure out. Maybe someone here could help me. OK, here goes:

There are 6 hypothetical sets (some of them are real sets, but some of them are non-standard). These are N, W, Z, Q, I, and R.

${\sqrt {17}}$ belongs to sets R and I,

$0.86$ belongs to sets R and Q,

${\sqrt {64}}$ belongs to sets R, Q, Z, W, and N,

$-10/2$ belongs to sets R, Q, and Z.

I've gathered that set R are all real numbers, set I are irrational numbers, set Q are rational numbers, and set N are natural numbers. I am have some difficulty with sets W and Z, however. Can anyone help? Thanks in advance, --Anonymous —Preceding unsigned comment added by 做工器 (talk • contribs) 19:59, 29 August 2009 (UTC)

$\mathbb {Z}$ is standard notation for the integers (it comes from German). I've never come across "W" as a standard name for a set before and can't guess what it would be from the information provided. --Tango (talk) 20:07, 29 August 2009 (UTC)

Ah, Blackboard bold says it could be "whole numbers". I guess whoever is using this notation uses W to refer to whichever of {0,1,2,...} or {1,2,3,...} isn't being called the natural numbers (definitions vary, you see - some people consider 0 natural, some don't). --Tango (talk) 20:09, 29 August 2009 (UTC)

Average Value of a Function

Hello, someone asked me a question about this and I have been thinking about it ever since. Working only in the reals, the question is to find the average value of a function over a given set. Obviously, if the set has a finite number of points, then using the definition of average, I can just evaluate at each point and then take the average. If the set is a finite interval, then we just integrate over the interval and then divide by the length of the interval. Extending this, if the set is a bounded region in R^n, then I just integrate over the set and then divide by the volume of that region. Here are the questions:

1.To find the average, it is okay to divide by the Lebesgue measure of the underlying set over which we integrate, right? Is it correct to say, for a bounded set, that to find the average value of a function over that set, just integrate over that set and divide by its Lebesgue measure, assuming that its Lebesgue measure is nonzero?

2.If this is correct, then how do we deal with sets that have measure zero? If the set is finite, we are good. But what if the set has an infinite number of points with measure zero, like the Cantor set or the rationals in [0,1]? I don't want to be dividing by zero but I can't simply evaluate at each point and take the average.

3.In addition, how do we deal with sets with infinite Lebesgue measure? I am sure I can't also "divide" by infinity after the integration. For example, what is the average value of $f(x)=e^{(-x^{2})}$ over $[0,\infty ]$?

4.Furthermore, what is meant when we are asked to find the average value of a function without specifying the region? Is it safe to assume that the entire domain of the function is meant or is there some other standard? Thanks!-Looking for Wisdom and Insight! (talk) 20:52, 29 August 2009 (UTC)

#1 is correct not only for bounded sets, but for any set whose measure is finite. In #3, the way it's usually done involves conditional convergence, so you might get different answers depending on how the region of infinite volume is approached. The idea is: take an average of a subset of finite measure, then take a limit as as that subset in some way approaches the whole domain. There's no non-uniqueness problem if the function is everywhere nonnegative, nor if the positvie and negative parts both have finite integrals; it's only when both are infinite that there is such a problem. Simple example:

$\lim _{a\to \infty ,\ b\to -\infty }\int _{b}^{a}{\frac {x\,dx}{1+x^{2}}}.$

If b = −2a, then the limit is (1/2)log(1/4), but if b = −a, then the limit is 0. See also Cauchy principal value. Michael Hardy (talk) 21:19, 29 August 2009 (UTC)

[ec] I don't think the term "average value of a function" is generalizable to the kind of cases you are thinking about. For these cases it may be more useful to consider the expected value of a function of a random variable, where the latter follows a given distribution.

1. This seems correct.
2. There is probably no generic solution. For a countable set you may choose to assign a weight for each point, or choose an enumeration and take $\lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}f(q_{i})$. For a non-countable set you may want to choose a countable subset of "key points" (for the cantor set, a natural choice is the set of interval endpoints).
3. You can choose a weighting function with a finite integral. In some cases (e.g. periodic functions) it is appropriate to consider $\lim _{t\to \infty }{\frac {1}{t}}\int _{0}^{t}f(t)\;dt$ or $\lim _{t\to \infty }{\frac {1}{2t}}\int _{-t}^{t}f(t)\;dt$.
4. It seems safe to assume the entire domain.

-- Meni Rosenfeld (talk) 21:25, 29 August 2009 (UTC)

With periodic functions, I'd just take the average value over one period. Michael Hardy (talk) 02:20, 30 August 2009 (UTC)

Fun little problem

Here's a fun little problem I saw yesterday. Which is bigger $e^{\pi }\,$ or $\pi ^{e}\,$? No calculator, computer, or search engine allowed; just your brain and some paper. Try to find a proof, i.e. no estimations allowed. It took me a little while to think of a proof, but in the end it's not that difficult. I would like to see if anyone can come up with a proof that uses a different method to mine. If this is too easy for you, then after you've posted a proof (which must use a different method to any others that yours follows) then please turn your attention to my serious problem above. ~~ Dr Dec (Talk) ~~ 23:13, 29 August 2009 (UTC)

Consider the inequality $\scriptstyle e^{x}>x^{e}$, that is $\scriptstyle x>e\,lnx$. So we're interested in the sign of $\scriptstyle f(x):=x-e\,lnx$, which is nicely continuous and differentiable for $\scriptstyle x>0$. $\scriptstyle f'(x)=1-e/x$ so the only solution to $\scriptstyle f'(x)=0$ is $\scriptstyle x=e$. $\scriptstyle f(e)=0$, of course, and it's readily seen that this is a minimum. Hence, $\scriptstyle e^{x}>x^{e}$ for all positive $\scriptstyle x$ (except $\scriptstyle x=e$). —JAO • T • C 23:40, 29 August 2009 (UTC)

Essentially the same as the above. Taking logs we see we are comparing $\pi$ to $e\log \pi$. Now, differentiate $x/\log x$ to compare it to $e$. Phils 23:46, 29 August 2009 (UTC)

But I'd like to see a non-log proof, if at all possible. ~~ Dr Dec (Talk) ~~ 23:59, 29 August 2009 (UTC)

It is easy to re-write Jao's proof to not use logs. Let $f(x)=e^{x}x^{-e}$ for x > 0. We have $f'(x)=e^{x}x^{-e}(1-e/x)$. This is zero exactly when x = e, so f has a unique minimum at e. Proceed as before. Eric. 98.207.86.2 (talk) 01:18, 30 August 2009 (UTC)

Declan, you've been posting some interesting topics, but they really aren't Reference Desk questions. Have you thought about starting a blog? 67.122.211.205 (talk) 06:16, 30 August 2009 (UTC)

Fun little macro with a (math) issue...

I posted this here because this is more a math question than a computer question, though it involves both...

Im making a little macro for fun with AutoIt v3 which opens up MsPaint and draws. There are currently values called xMomentum and yMomentum which guide the pen. Basically the program starts with xMomentum = 0, yMomentum = 0, then each step it generates a random number between -2 and 2 and adds that to xMomentum , and does it again seperately to yMomentum, then the mouse is moved that many pixels.

What i am seeming to get is momentums that build up, so the pen starts to fly across the screen in a (non straight) line. Although a few straight bits are cool, id like more changes to happen. My thought is this:

I could have variables xTop and xBottom, where the random number is no longer between -2 and 2 its between xTop and xBottom. I would adjust these based on xMomentum so that the "faster" the pen goes in either X direction, the more likely it is to change direction slightly. (of course, i would do the same for corresponding y values.)

I dont know how to do this mathematically though, any ideas? All thoughts are welcome! Thanks! :)

97.112.117.236 (talk) 23:38, 29 August 2009 (UTC)

There are a lot of ways you could do this. One way would be to subtract k times the momentum from the momentum at each step where k is a small positive constant. This is basically like introducing a frictional force proportional to the velocity.

Another way would be to just cap the momentum. If at any step it exceeds the cap, reduce it to the cap. Rckrone (talk) 00:19, 30 August 2009 (UTC)

I spoke shortly with my father, and he unearthed a problem. Lets say i add a random integer in the set [-2, 2] as i did before. this is added to a momentum, so there are 3 integers which do not decrease the speed, and 2 that do. Thus 0 needs to be removed from my random integers.

I sort of like the frictional thing.... but can i use that and still get the possibility of both increase or decrease? Maybe i should add my random number (-2, -1, 1, or 2) and then do this subtraction? this would have the possibility of speeding up or slowing down, but add the friction as well. am i correct?

97.112.117.236 (talk) 00:26, 30 August 2009 (UTC)

Yeah I meant add the friction part in addition to what you're already doing. With the friction alone it would be pretty dull: just slowing to a stop and then sitting still. Using the set {-2, -1, 0, 1, 2} doesn't cause any problems, although {-2, -1, 1, 2} works fine too. As long as the average is 0 the momentum won't favor one direction or the other. Rckrone (talk) 00:43, 30 August 2009 (UTC)

Perhaps so. I have opted to eliminate 0 just in case :) 97.112.117.236 (talk) 00:49, 30 August 2009 (UTC)