Jump to content

Wikipedia:Reference desk/Mathematics: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Line 270: Line 270:
::After reading the above more carefully, I realize that you are referring to the fact that <math>\sin x = O(f(x))</math> implies <math>\liminf |f| >0</math>, i.e. the function to tested is in the <math>O(\cdot)</math>. In that case <math>1 = O(f(x))</math> works just as well. My remark about absolute value still holds. [[User:Phils|Phil]]<span style="font-weight: bold;">[[User_talk:Phils|s]]</span> 16:26, 30 August 2009 (UTC)
::After reading the above more carefully, I realize that you are referring to the fact that <math>\sin x = O(f(x))</math> implies <math>\liminf |f| >0</math>, i.e. the function to tested is in the <math>O(\cdot)</math>. In that case <math>1 = O(f(x))</math> works just as well. My remark about absolute value still holds. [[User:Phils|Phil]]<span style="font-weight: bold;">[[User_talk:Phils|s]]</span> 16:26, 30 August 2009 (UTC)


In computer science when we want to be precise, for a given function f, we define O(f) as the set of functions h for which there exists a constant K such that for sufficiently large x, <math>h(x)/f(x)<K</math>. So we would then say <math>\sin\in O(1)</math> where we are abusing notation and writing "1" to denote the [[constant function]] <math>x\mapsto 1</math>. [[Special:Contributions/67.122.211.205|67.122.211.205]] ([[User talk:67.122.211.205|talk]]) 01:52, 31 August 2009 (UTC)
In computer science when we want to be precise, for a given function f, we define O(f) as the set of functions h for which there exists a constant K such that for sufficiently large x, <math>h(x)/f(x)<K</math>. So we would then say <math>\sin\in O(1)</math> where we are abusing notation and writing "1" to denote the [[constant function]] <math>x\mapsto 1</math>. Re Declan: big O notation in the treatment I'm accustomed to is insensitive to additive constants. I don't think it would be used in the way you are asking. [[Special:Contributions/67.122.211.205|67.122.211.205]] ([[User talk:67.122.211.205|talk]]) 01:52, 31 August 2009 (UTC)


== What mathematics things are vs. what mathematical things do ==
== What mathematics things are vs. what mathematical things do ==

Revision as of 01:57, 31 August 2009

Welcome to the mathematics section
of the Wikipedia reference desk.
Select a section:
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.



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:



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)[reply]

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)[reply]
Thanks for the correction, but can you give me an alternative meaning in English?--Email4mobile (talk) 09:02, 25 August 2009 (UTC)[reply]
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)[reply]
Inner model theorists are topologists, because they study mice.
(It's sort of a pun.) --Trovatore (talk) 09:46, 25 August 2009 (UTC)[reply]
In Tuscany there is also a coarser pun, linked to the jargon word "topa" --pma (talk) 10:02, 25 August 2009 (UTC) [reply]
(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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
...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)[reply]

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)[reply]

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)[reply]
Sorry, but what's an OP? ~~ Dr Dec (Talk) ~~ 15:14, 25 August 2009 (UTC)[reply]
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) [reply]
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 (talkcontribs) 15:13, 25 August 2009 (UTC)[reply]
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)[reply]
You mean transliteration ;) --pma (talk) 15:38, 25 August 2009 (UTC)[reply]
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)[reply]
"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)[reply]
"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)[reply]

The natural numbers are countably infinite and are the smallest infinite set, i.e. they have cardinality 0. The set of all subsets of the natural numbers has cardinality 20: 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 20. The proof I have seen is a proof by contrandiction[1]. 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) [reply]

  1. ^ Penrose, R (2005), The Road to Reality: A Complete guide to the Laws of the Universe, Vintage Books, ISBN 0-099-44068-7
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)[reply]
  • 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)[reply]
  • (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)[reply]
Ah, I think you're right about that one! ~~ Dr Dec (Talk) ~~ 13:36, 25 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
Nice, straightforward idea but sadly not 1-1, as {1} maps to 0.12 and {2,3,4...} maps to 0.0111...2 and these binary expansion represent the same real number, namely 1/2. Gandalf61 (talk) 12:25, 25 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
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)[reply]
Point taken. --Stephan Schulz (talk) 15:59, 25 August 2009 (UTC)[reply]
Another example: To each infinite subset of the natural numbers, say assign the sequence of positive natural numbers; interpret this sequence as a continued fraction, and you will get a positive irrational number . 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)[reply]

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)[reply]

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)[reply]
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 ℵ0. ~~ Dr Dec (Talk) ~~ 17:00, 25 August 2009 (UTC)[reply]
(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)[reply]
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)[reply]
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 ℵ0, and so do many many many more after that. However, there will eventually be an ordinal number with cardinality ℵ1, and ℵ2, and so on. --COVIZAPIBETEFOKY (talk) 17:15, 25 August 2009 (UTC)[reply]
I see! ~~ Dr Dec (Talk) ~~ 17:15, 25 August 2009 (UTC)[reply]
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)[reply]

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)[reply]

I'm sorry, but I don't understand the problem. Do you mean find F(x) + G(x) when
In that case it's just addition of fractions and some simplification. I get
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)[reply]
Oh, I see, you have G(x) = 2x + 3, and in this case you're right:
~~ Dr Dec (Talk) ~~ 14:20, 25 August 2009 (UTC)[reply]

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

fibonacci spiral

for what value of does plot a fibonacci spiral in the argand plane? —Preceding unsigned comment added by 92.1.60.82 (talk) 23:55, 25 August 2009 (UTC)[reply]

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


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 (talkcontribs) 08:22, 26 August 2009 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]
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)[reply]
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)[reply]
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)[reply]

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)[reply]

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)[reply]

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 where is a Riemannian metric, an almost complex structure and a symplectic form, which must satisfy an additional condition.

The article gives two of such equivalent additional conditions:

  • , the symplectic form is closed.
  • Parallel transport induced by the Levi-Civita connection corresponding to actually induces -linear mappings of tangent spaces, not only -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 .

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

can u solve this

1=19-20=60

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

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)[reply]

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)[reply]

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)[reply]
How many matchsticks can you move? – b_jonas 11:53, 29 August 2009 (UTC)[reply]

Commutivity of addition

Resolved
 – Wow! Good work everybody.

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

This will depend on your preferred Construction of the real numbers. Algebraist 23:15, 26 August 2009 (UTC)[reply]
Good point! Okay, let's list the possible constructions and their respective proofs... ~~ Dr Dec (Talk) ~~ 23:21, 26 August 2009 (UTC)[reply]
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)[reply]
This is a joke, right?! PROVE that addition is commutative! ~~ Dr Dec (Talk) ~~ 23:27, 26 August 2009 (UTC)[reply]
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):[reply]
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)[reply]

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)[reply]

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)[reply]

67.122.211.205, you're half way there. Now prove it... ~~ Dr Dec (Talk) ~~ 23:55, 26 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
(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)[reply]
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)[reply]
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)[reply]
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)[reply]
And now Shahab has also addressed the same problem. --COVIZAPIBETEFOKY (talk) 12:26, 27 August 2009 (UTC)[reply]
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 . Clearly . Suppose that . Then . Thus and hence by the principle of induction M=N and so n+1=1+n for all n in N. Let . We have shown 1 is in M'. Assume n in M'. Then . Thus and so M'=N. Regards--Shahab (talk) 12:19, 27 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]


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:

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

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)[reply]

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)[reply]

Good point, well made. ~~ Dr Dec (Talk) ~~ 15:14, 27 August 2009 (UTC)[reply]
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)[reply]

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)[reply]

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 ~~ Dr Dec (Talk) ~~ 23:14, 26 August 2009 (UTC)[reply]
This is true essentially by definition: . Algebraist 23:18, 26 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
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)[reply]
Good point. Algebraist 00:47, 27 August 2009 (UTC)[reply]


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)[reply]

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)[reply]
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)[reply]
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)[reply]

Uncountability of R

Resolved

I want to find an explicit bijection between and so that I can conclude that 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)[reply]

For the first question, see #The real numbers and subsets of the natural numbers above. —JAOTC 10:07, 27 August 2009 (UTC)[reply]
And for the other question check Binary numeral system#Conversion to and from other numeral systems. So let , where , and for all positive k but finitely many, and for infinitely many negative k; then, .--pma (talk) 10:29, 27 August 2009 (UTC)[reply]
Thanks.--Shahab (talk) 11:05, 27 August 2009 (UTC)[reply]

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)[reply]

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)[reply]
I'd assume the point was .999... = 9 * .111... = 9 * 1/9 = 9/9 = 1. —JAOTC 15:46, 28 August 2009 (UTC)[reply]
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)[reply]
Oh, i check the archives, and I found noting.Accdude92 (talk) (sign) 13:20, 27 August 2009 (UTC)[reply]
See 0.999... (a Featured Article). -- Coneslayer (talk) 13:29, 27 August 2009 (UTC)[reply]
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 (talkcontribs) 14:00, 27 August 2009 (UTC)[reply]

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 an is 0.99...9 where there are n 9s after the decimal place then clearly 0 < an < an+1 < 1 for any positive whole number n. Actually

So we are getting closer and closer to 1 as we add more and more 9s. Notice that every an 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 an lies within that distance from 1. Actually we can solve: we want an to be within a distance of ε from 1, so we want an > 1 - ε (just draw a picture: 0 < an < 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 an to be closer to 1 so we need an > 1 - ε). Solving this gives

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)[reply]

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)[reply]
... which says, in the section Infinite_series_and_sequences (cmd-click)">Infinite_series_and_sequences (cmd-click)">0.999...#Infinite_series_and_sequences''Infinite series and sequences'':
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)[reply]
Exactly! The limit of my an 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 an 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)[reply]


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)[reply]
In a certain setting they are interchangable. Given a sequence of real numbers (xn) 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 (xn) where xn = x for all n. ~~ Dr Dec (Talk) ~~ 15:20, 27 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
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 DissidentTalk 15:30, 27 August 2009 (UTC)[reply]
Hmmm, that's not exactly correct. Not every well-defined limit is a number; some limits are functions. Let f : RR be a smooth function then
isn't a number; it's a function. ~~ Dr Dec (Talk) ~~ 15:42, 27 August 2009 (UTC)[reply]
c'mon... of course everybody here's talking of real numbers  ;) --pma (talk) 15:56, 27 August 2009 (UTC) [reply]
Okay, okay... Sorry! :oP ~~ Dr Dec (Talk) ~~ 15:58, 27 August 2009 (UTC)[reply]
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 DissidentTalk 16:02, 27 August 2009 (UTC)[reply]
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)[reply]
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 DissidentTalk 16:14, 27 August 2009 (UTC)[reply]

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 Rn+1. For my purposes, the space of line bundles over M coincides with the quotient space , where is the space of all differential one-forms on M and is the space of all exact differential one-forms on M. Now, I want to understand this space a little better.

Let be nested vector spaces, then we construct the formal isomorphism Now, notice that where is the space of closed differential one-forms on M. We get that

where denotes the first de Rham cohomology class. We can make sense of the space by noting that the exterior derivative d is such that , the kernel of d is given by and the image is given by , i.e. the space of exact differential two-forms on M. It follows that Finally, our original space can be shown to have the following property:


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)[reply]


1. Since for plain vector spaces there is no natural isomorphism for 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. 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)[reply]
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)[reply]
OK, but since you took M embedded in Rn+1, 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)[reply]

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 , 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)[reply]

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 DissidentTalk 16:12, 27 August 2009 (UTC)[reply]
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)[reply]

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)[reply]

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)[reply]
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 {p1, …, pn}. (The resulting axiom would be that an A with the properties {p1, …, pn} is a B. ~~ Dr Dec (Talk) ~~ 16:37, 27 August 2009 (UTC)[reply]
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)[reply]


(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)=x2+x.."). --pma (talk) 17:09, 27 August 2009 (UTC)[reply]
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)[reply]
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)[reply]
Sure, so what? well, no matter...--pma (talk) 18:30, 27 August 2009 (UTC)[reply]
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)[reply]
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)[reply]

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)[reply]

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]/(x2 + 1), that lets us talk about the concept using the term "complex numbers" instead of having to explain "the quotient space R[x]/(x2 + 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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]
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)[reply]
....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)[reply]
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).[reply]

August 28

Automorphisms

I want to prove the following result: Suppose I have an irreducible factor of the polynomial , say h(x) in (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)[reply]

(I may be misunderstanding your questions, so if you do not find my answers helpful please ask again.) The Frobenius automorphism on is the identity (there are no non-identity automorphisms of ). Therefore 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 be the Frobenius automorphism of L. Since fixes K (why do we know this?), , so the roots of h and in L are the same, and thus permutes the roots of h; that is, 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 . (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 , the cyclic ring of 4 elements, and let . Let ; 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)[reply]
Thanks Eric. I understand that the Frobeinus map over 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 is such that (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 then the Frobenius map permutes the roots of g(x). Now 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 is the Frobenius automorphism) g=h and so (where is really acting upon the coefficients). But and so . 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)[reply]
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)[reply]
Unfortunately I'm confused. I see that are you given an irreducible polynomial g (by "the irreducible factor" of I suppose you mean the one with degree , which you then project into by taking the coefficients mod ) over . However you introduce two new polynomials h and f and I don't know what those are. You also mention the Frobenius map on ; however, in general, this map (of raising to the power p) is not a ring homomorphism when , 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)[reply]
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)[reply]
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)[reply]

(dedent) Ah, that is clear. First I'll address the easy part (namely, the part I know how to prove). Suppose is an automorphism of the field L, the fixed field of is K, and f is a polynomial over K that splits completely in L; we wish to prove that permutes the roots of f. For any polynomial g over L and , we have (because is an automorphism of L), so maps the roots of g bijectively to the roots of . In the case of f, we know (since the coefficients of f are fixed by ); thus 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 does not have a quotient field for r > 1 because R is not an integral domain; in particular .) I ran through an example to see if I could find the result you were looking for: take p = 2, r = 2, and . f and g are irreducible, and divide . If we square the coefficients of g, we get another polynomial , 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)[reply]

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)[reply]
That sounds quite reasonable to me. I am wondering if you could explain a few details for me. We have is the splitting field of over . 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 we can project it to , 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)[reply]
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)[reply]
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)[reply]

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)[reply]

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)[reply]

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

.

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.

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


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(-Ax2-By2-Cz2-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 π/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)2)=exp(-u2-2ku)exp(-k2), and then change variable. This way you transform the initial into the integral of exp(-x2-y2-z2) 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(-x2-y2-z2), 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(-x2-y2) 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(-x2-y2) on this domain. A first integration produces a partial integral of the form erf(αx+β)exp(-x2), that you still have to integrate in x>0. (I don't see yet a formula for the latter antiderivative of erf(αx+β)exp(-x2); but if the matter is just about numerics, it certainly has a very fastly convergent 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)[reply]

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)[reply]

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)[reply]

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)[reply]

The last answer is better than mine.Julzes (talk) 03:56, 29 August 2009 (UTC)[reply]
  • 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)[reply]

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).[reply]

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)[reply]
Some folk here might be interested to check out Stein's method, which is one way of generalizing the binomial -> poisson limit. HTH, Robinh (talk) 08:29, 30 August 2009 (UTC)[reply]

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)[reply]

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)[reply]

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.

belongs to sets R and I,

belongs to sets R and Q,

belongs to sets R, Q, Z, W, and N,

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 做工器 (talkcontribs) 19:59, 29 August 2009 (UTC)[reply]

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)[reply]
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)[reply]
The sets in the order presented are contained within the next one - so N would be {1,2,...} and W is {0,1,2,...}. Acb314 (talk) 10:55, 30 August 2009 (UTC)[reply]
... maybe, but Q (whatever it is) cannot be contained in I (whatever it is) since Q contains at least three given members that are not in I. Logically, there is no way to infer the entire contents of these hypothetical sets from a few members. We can, however, say that a minimal solution is R={√17, 0.86, 8, -5}; I={√17}; Q={0.86, 8, -5}; Z={8, -5}; W=N={8}. Gandalf61 (talk) 12:06, 30 August 2009 (UTC)[reply]
I think "the order presented" means the order in the statement " belongs to sets R, Q, Z, W, and N". That makes Acb314's argument as good as any, but it's of course true that we can't know much about these sets. —JAOTC 12:17, 30 August 2009 (UTC)[reply]

That was lack of reading comprehension on my part -indeed Q will not be contained in I! Assuming N, Z, Q, R have the usual meanings, which they seem to, N is inside Z inside Q inside R, so my logic was that N would also be inside W from the order they were written in - not mathematically rigorous I know. I throws a spanner in the works unfortunately, although I is "bigger" than Q and contained within R. I agree that there isn't enough information in the examples to tell what N and W are just from those. Acb314 (talk) 14:31, 30 August 2009 (UTC)[reply]

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 over ?

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)[reply]

#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:
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)[reply]
[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 . 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 or .
  4. It seems safe to assume the entire domain.
-- Meni Rosenfeld (talk) 21:25, 29 August 2009 (UTC)[reply]

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

Fun little problem

Here's a fun little problem I saw yesterday. Which is bigger or ? 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)[reply]

Consider the inequality , that is . So we're interested in the sign of , which is nicely continuous and differentiable for . so the only solution to is . , of course, and it's readily seen that this is a minimum. Hence, for all positive (except ). —JAOTC 23:40, 29 August 2009 (UTC)[reply]
Please. It's , not . The backslash BOTH prevents italicization and provides proper spacing. Michael Hardy (talk) 06:24, 30 August 2009 (UTC)[reply]
Oops, of course. I thought my spacing problems were somehow due to \scriptstyle, so I just thought it weird instead of thinking myself stupid. Thanks for setting me straight on that; I fixed those uglies now.JAOTC 08:59, 30 August 2009 (UTC)[reply]
Essentially the same as the above. Taking logs we see we are comparing to . Now, differentiate to compare it to . Phils 23:46, 29 August 2009 (UTC)[reply]
But I'd like to see a non-log proof, if at all possible. ~~ Dr Dec (Talk) ~~ 23:59, 29 August 2009 (UTC)[reply]
It is easy to re-write Jao's proof to not use logs. Let for x > 0. We have . 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)[reply]
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)[reply]
Really? I know that this one is boarderline, but all of my other threads have been perfectly valid reference desk question. My latest questions have been The real numbers and subsets of the real numbers, Commutivity of addition, Associativity of composition and Line bundles and cohomology. I've just read them all again, and they seem perfectly valid reference desk question. I don't know, what do other people think of these five questions? ~~ Dr Dec (Talk) ~~ 09:54, 30 August 2009 (UTC)[reply]
I think Dr Dec's questions are entirely appropriate for the Mathematics Reference Desk, and I welcome him as a new regular contributor here. But this is off-topic so if any further discussion is required. let's take it to Wikipedia talk:Reference desk. Gandalf61 (talk) 11:55, 30 August 2009 (UTC)[reply]
I agree. I'll admit that this thread is a very unusual RD thread, posing a problem the OP has already solved. But as the goal was not to see if others can solve it, but rather to see if there are other ways to solve it, I took it as a sincere fragment of a pursuit of deeper understanding. Which, after all, is what the RD is intended for, isn't it? (Dec's questions have also certainly been more interesting than the typical homework questions, but I don't think that is disputed.)JAOTC 12:04, 30 August 2009 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

Resolved

August 30

Principle of mathematical induction

Please solve this problem of mathematical induction

sinx + sin3x + ... +sin(2n-1)x =sin^2nx/sinx —Preceding unsigned comment added by Tipusultan11 (talkcontribs) 07:08, 30 August 2009 (UTC)[reply]

If you can tell us where you are getting stuck in solving this problem maybe we can help you with it. What have you tried to do so far? Do you understand induction? Eric. 98.207.86.2 (talk) 07:47, 30 August 2009 (UTC)[reply]
Have you to use trig identities? You can do it easily using Euler's formula‎‎ Dmcq (talk) 11:37, 30 August 2009 (UTC)[reply]
...and powers thereof. ~~ Dr Dec (Talk) ~~ 11:43, 30 August 2009 (UTC)[reply]

As an induction problem it seems simpler than taking powers of the Euler formula, expanding, then comparing terms in the binomial expansion. The base case would be when n = 1, i.e.

and this is clearly true. Next, assume that P(k) is true and prove that this implies that P(k+1) is also true. Well for the case P(k) we have

We assume that this equality holds. To prove that P(k) implies P(k+1) we simply need to show that

which I won't do because I'm not going to do all of your homework for you ;oP ~~ Dr Dec (Talk) ~~ 12:30, 30 August 2009 (UTC)[reply]

...and this last step isn't too hard if you use the formula ~~ Dr Dec (Talk) ~~ 12:42, 30 August 2009 (UTC)[reply]
Maybe I'm a stickler for detail, but the conjecture, as written, is false for x=kπ, k integer. --Stephan Schulz (talk) 12:44, 30 August 2009 (UTC)[reply]
It's not false, it's true for all x. I assume your problem is that the RHS has a zero denominator for x = (m an integer). Well there's no problem: it's perfectly well defined. The limit of the RHS exists, and is equal to zero. See the article on L'Hôpital's rule. (In fact you don't even need that: just completing the inductive steps that I have outlined above show you that the singularities at x = are removable.) ~~ Dr Dec (Talk) ~~ 12:50, 30 August 2009 (UTC)[reply]
Sure, the function can be steadily continued at the undefined points, as limits from both sides agree. But as written, it is not so continued. Even your base case is, strictly, wrong. As I wrote, stickler for details ;-) --Stephan Schulz (talk) 13:15, 30 August 2009 (UTC)[reply]
Why is the base case wrong? It has a removable singularity - there is no problem! The base case doesn't require steadily continuing anything. We are canceling functions. I've not tried to evaluate the numerator and denominator before canceling. Would you argue that x/x = 1? I hope not! Well, you're trying to say that there's a problem with the statment that x/x = 1 by saying that the base case isn't well defined. In fact the expression x/x is perfectly well defined; its value at x = 0 is indeterminate, but can be calculated as a limit. Where did I evaluate anything above? ~~ Dr Dec (Talk) ~~ 13:18, 30 August 2009 (UTC)[reply]

To make Stephan happy, let's rephrase the problem. Show, using mathematical induction, that for any positive integer n, and any real number y:

I always tacitly assume the idea of a limit when I evaluate a function. I'm sure most other mathematicians do too. ~~ Dr Dec (Talk) ~~ 13:30, 30 August 2009 (UTC)[reply]

I suspect you're missing a negation somewhere above. But yes, for me (the function defined over the reals by the formula) x/x is different from (the function defined over the reals by the constant formula) 1. In set notation, 1 is , and x/x is . The one is a proper subset of the other (and so can of course be extended), and hence they are not the same. --Stephan Schulz (talk) 13:54, 30 August 2009 (UTC)[reply]
...and this helps to answer Tipusultan11's question, how? (p.s. So what if I haven't not missed no negatives?) ~~ Dr Dec (Talk) ~~ 14:02, 30 August 2009 (UTC)[reply]

Stephan, let's stop this now. You can carry on worrying about the validity of expressions like x/x, so that I can try to help answer people's questions here on the RD. Maybe Tipusultan11 should just hand his homework in with the solution: Question not well defined? ~~ Dr Dec (Talk) ~~ 14:08, 30 August 2009 (UTC)[reply]

For OP's interest, it will probably help him get full marks if he puts sin x != 0 somewhere. --91.145.89.58 (talk) 16:28, 30 August 2009 (UTC)[reply]

...meaning? ~~ Dr Dec (Talk) ~~ 16:39, 30 August 2009 (UTC)[reply]
In the case OP has to compose math test answers, it will steer him away from all trouble if he mentions that there's no equality when sin x = 0; x = pi * n. Forgive if my english is bad. --91.145.89.58 (talk) 16:52, 30 August 2009 (UTC)[reply]
Dr Dec. You write: "I always tacitly assume the idea of a limit when I evaluate a function. I'm sure most other mathematicians do too". How can you be that sure after meeting a mathematician who do not tacitly assume the idea of a limit? Your tacit assumption may lead you into trouble. Stephan's objection is perfectly valid. Bo Jacoby (talk) 17:29, 30 August 2009 (UTC).[reply]
Even if Stephan were a mathematician, the statement "most other" does not mean "all". Besides that, Stephan is a computer scientist and not a mathematician and as such does not count when it comes to qualifying the valididity of statements involving mathematicians (exhaustive or not). One is not going to go very far with one's mathematical thinking if one stops at the first problem. If one were to be presented with a problem that involved indeterminate forms, then one may stop if one chose. However, I might prefer to proceed with common sense. ~~ Dr Dec (Talk) ~~ 19:01, 30 August 2009 (UTC)[reply]

Big O of sin x

Can anything meaningful be said about f(x)? SpinningSpark 13:13, 30 August 2009 (UTC)[reply]

Could you please qualify your notation. I know as a function ring. Do you mean O(f)? ~~ Dr Dec (Talk) ~~ 13:19, 30 August 2009 (UTC)[reply]
Sorry, I meant Big O notation. I copied the style from sorting algorithm so someone should take a look at that article if it's wrong. SpinningSpark 13:34, 30 August 2009 (UTC)[reply]

Well the notation means that, for sufficiently large x, for some fixed positive constant k. This isn't very illuminating. The Big O notation is usually used to describe growth, but since the sine function doesn't grow it's a bit of a non-starter. For example, if then we know that the infimum of , for very large x, grows like the infimum of . But the infimum of is zero: as small as it gets; so this doesn't tell us anything. Why did you ask the question? Can you give us more information and context? ~~ Dr Dec (Talk) ~~ 13:58, 30 August 2009 (UTC)[reply]

(ec) Saying sin(x) = O(f(x)) means that there is some k such that for x sufficiently large we have |sin(x)| ≤ k|f(x)|. This will always be satisfied provided that 1 ≤ k|f(x)|, which is the same as 1/k ≤ |f(x)|. So sin(x) = O(f(x)) means that the values of f(x) will eventually stay outside of some interval around 0. That is, there is some ε such that ε ≤ |f(x)| for x sufficiently large. It's not hard to see that this condition is equivalent to sin(x) = O(f(x)). Another way to say this is that the lim inf of f(x) as x goes to infinity is not zero. Staecker (talk) 14:05, 30 August 2009 (UTC)[reply]
Is this true? will become zero infinitly many times, not matter how large x is. For example, try Clearly for all x (where k = 1), but f is zero infinitly many times and does not have a well-defined limit. I guess that the statement might be that If a limit exists then it will not be zero. ~~ Dr Dec (Talk) ~~ 14:18, 30 August 2009 (UTC)[reply]
While does not exist, certainly does; it is –2. But shouldn't it be (which is 2 in your example) that should not be 0? —JAOTC 14:30, 30 August 2009 (UTC)[reply]
Good point! I missed the inf. In that case then
as Staecker quite rightly says. ~~ Dr Dec (Talk) ~~ 14:42, 30 August 2009 (UTC)[reply]

I think Dec's objection is valid- |f(x)| = |2sinx| does have lim inf equal to zero, but it is certainly the case that sin(x) = O(f(x)). So there are more possibilities for f. Perhaps the correct weaker condition is that: or for all a being an integer multiple of π. (Or something like that.) Staecker (talk) 17:38, 30 August 2009 (UTC)[reply]

Sorry Dr. Dec, there is no context, it just arose out of some idle scribblings on scrap paper. SpinningSpark 14:38, 30 August 2009 (UTC)[reply]

Just to check that I am following this, would it be right to say,

SpinningSpark 15:29, 30 August 2009 (UTC)[reply]
That's correct. To say that a function f is such that f(x) = O(1) means that, for sufficiently large x, f is bounded, i.e. |f(x)| ≤ k for all sufficiently large x. Like I said: the big O notation is used to describe the growth of a function. Say that f(x) = O(g(x)) then what does that mean? Well consider the cone given by y = ±g(x). Then f(x) will, for sufficiently large x, always stay inside a cone of that shape. So, e.g., if f(x) = O(x) then, for sufficiently large x, f(x) will always lie inside a cone given by the two straight lines y = ±kx, for some k (i.e. f(x) ≤ k|x|). ~~ Dr Dec (Talk) ~~ 15:50, 30 August 2009 (UTC)[reply]

The usefulness of sine and cosine

So, let's assume that sine and cosine haven't been invented. We want to try to express, in big O notation, the statement that the limit of the infimum of some smooth function f is non-zero (whilst also, theoretically, being able to take any other real value). How could that be done if we didn't know about sine or cosine? (If we don't know about sine or cosine then we couldn't use a power series for them either!) ~~ Dr Dec (Talk) ~~ 14:51, 30 August 2009 (UTC)[reply]

That's . The big-Oh notation says something about absolute size. You cannot separate statements about the liminf and limsup. Besides, only implies an upper bound. There is a corresponding notation for lower bounds (, see Big Oh notation), although it's not as commonly seen. The definition also has absolute values. I don't think it is worthwhile trying to express non-quantitative statements in big-Oh notation. Phils 16:16, 30 August 2009 (UTC)[reply]
After reading the above more carefully, I realize that you are referring to the fact that implies , i.e. the function to tested is in the . In that case works just as well. My remark about absolute value still holds. Phils 16:26, 30 August 2009 (UTC)[reply]

In computer science when we want to be precise, for a given function f, we define O(f) as the set of functions h for which there exists a constant K such that for sufficiently large x, . So we would then say where we are abusing notation and writing "1" to denote the constant function . Re Declan: big O notation in the treatment I'm accustomed to is insensitive to additive constants. I don't think it would be used in the way you are asking. 67.122.211.205 (talk) 01:52, 31 August 2009 (UTC)[reply]

What mathematics things are vs. what mathematical things do

Is only the latter important? It seems to me like defining 'dog' as something that barks, bites, etc. But not telling what a 'dog' is. On the other hand, the only way of defining 'division' I can thing of is over its output.Quest09 (talk) 16:50, 30 August 2009 (UTC)[reply]

...so are you suggesting we define a dog by its output? YUK! :oP ~~ Dr Dec (Talk) ~~ 17:01, 30 August 2009 (UTC)[reply]
But surely all objects are defined by their interaction with obsevers anyway? The "are" is only assessed by interaction with the world. --Leon (talk) 19:18, 30 August 2009 (UTC)[reply]
Here's an interesting example of this problem (borrowed from a book, but I've forgotten which one EDIT maybe the one in the OUP very short intro series by Gowers). What "is" the king in chess? It's not a particular piece in your chess set, because if you've lost your king you can use any old bit of junk lying around. Is a king anything more than "something which can move only a single square in one direction except for castling, and...."? 87.194.213.98 (talk) 19:25, 30 August 2009 (UTC)[reply]
If you can find a difference between the two then perhaps you can find a scientific explanation of Transubstantiation ;-) Dmcq (talk) 19:53, 30 August 2009 (UTC)[reply]

Mathematicians are concerned with the fact that the reals form a complete ordered field (what they do), and often impatient with things like the fact that the reals can be regarded as equivalence classes of Cauchy sequences or as Dedekind cuts, etc. (what they (supposedly?) are).

The analogy to the king in chess is on the mark.

But this might be argued about philosophically. Michael Hardy (talk) 01:35, 31 August 2009 (UTC)[reply]

The fact that you have mentioned two completely different constructions of the reals that are both very popular shows how unimportant constructions are to the vast majority of mathematics. "The reals are the completion of the field of fractions of a set with at least one element and a successor function." is the most useful definition (albeit lacking a few key details for the sake of conciseness). --Tango (talk) 01:43, 31 August 2009 (UTC)[reply]

PUZZLING PUZZLE

Guys I have been trying to solve this for a long time but I am not able to..please help me with this puzzle.(Thot it would fit in here better rather than the misc. desk)

The diagram shows a 4 x 5 grid with some filled cells. Find the numbers in the remaining cells according to the following rules: a) Each number can only take values from 1 to 5. There are 4 such full sets(1-5). b) Sum of each row is same. c) Sum of each column is same. d) Adjacent numbers cannot be the same.

- - - 1 5
- - - - 1
2 4 - - -
4 - - - -

thanks —Preceding unsigned comment added by 117.193.136.45 (talk) 16:53, 30 August 2009 (UTC)[reply]

An impractical but possible way to solve any such problem is to formulate and solve it as an Integer Programming Problem. There are softwares which automatically solve IPP's and you could use those.--Shahab (talk) 17:46, 30 August 2009 (UTC)[reply]
But, I would hope, 117.193.136.45 wants some kind of mathematical algorithm to solve the problem. I know that computers use algorithms, but that's just no fun! I was trying to find a connexion with sudoku. ~~ Dr Dec (Talk) ~~ 18:28, 30 August 2009 (UTC)[reply]
1 3 5 1 5
5 2 4 3 1
2 4 2 5 2
4 3 1 3 4
Just used good old fashioned trial and error. It's clear that the row and column sums must be 15 and 12 respectively.--RDBury (talk) 19:33, 30 August 2009 (UTC)[reply]
My solution was
2 4 3 1 5
4 2 3 5 1
2 4 3 1 5
4 2 3 5 1
which has a more obvious pattern. I can't see how it could have taken any length of time at all. Dmcq (talk) 19:41, 30 August 2009 (UTC)[reply]
Umm Dmcq, what about the constraint: d) Adjacent numbers cannot be the same? -hydnjo (talk) 19:49, 30 August 2009 (UTC)[reply]
Oops sorry, I should have read through to the end. Silly me Dmcq (talk) 20:09, 30 August 2009 (UTC)[reply]
I found the same solution as RDBury, also by trial and error. Note that since the column sums must be 12, there are only three ways to complete column 1 and three ways to complete column 5. That gives you 9 starting points, most of which quickly lead to dead ends. Gandalf61 (talk) 19:58, 30 August 2009 (UTC)[reply]
Damn. I followed this from Science to Miscellaneous, but didn't realize (didn't read) that is had also been moved here. However, under the premise that it is better the teach a man to fish than to give him a fish, I'll copy my answer here. -- Tcncv (talk) 23:59, 30 August 2009 (UTC)[reply]
There is a solution (and only one), but it would spoil the fun for me to give it outright. One way to find it is to use a backtracking approach, which is a way to solve many logic problems like this. (See also the Ariadne's thread article.) First, make a choice and see where that takes you. Fill in other cells that can be derived from that choice. When you cannot fill in any more, make another choice. If you come to a dead end, backtrack to your most recent choice and select another. If you run out of options at that point back up further and select another option for the previous choice.
This puzzle has a couple of good places to start. For ease of reference, I'll refer to the cells by row and column – (1,1) through (4,5). First you need to figure out the needed row and column sums. Since the sum of all of the available numbers is 4 × (1 + 2 + 3 + 4 + 5) = 60, the rows must each total 15 and the columns 12. Take a look at column 1. You have two numbers already whose sum is 6, so the remaining two numbers in cells (1,1) and (2,1) must also equal 6 (giving a column total of 12). Your options are 1 & 5, 2 & 4, and 5 & 1. The combination 3 & 3 would be an immediate adjacency violation; so would 4 & 2, given the existing value in cell (3,1). Tentatively select one pair and fill them in, keeping track of the other options in case you have to backtrack.
Now take a look at row 1. You already have three of five values, so you can apply the same logic. After that, look at column 2, then row 2, then column 3 etc. As you consider numbers, you can immediately eliminate any that cause adjacency violations. You can also watch for cases where the same number is used more than the allotted four times. That would also prompt you to back track.
Good luck. -- Tcncv (talk) 23:20, 30 August 2009 (UTC)[reply]

Sudoku boards and groups with 9 elements

Think about a completed sudoku board: it's a 9 × 9 board where we must fill the board with the numbers {1,…,9} in such a way that the same number can't appear in the same colomn, the same row, or in any of the 3 × 3 sub-squares that make up the 9 × 9 total board. Now, for me, the first two conditions (i.e. the same number can't appear in the same colomn or the same row) remind me of a group table for a group, say G, with nine elements. Is there a correspondence between completed Sudoku boards and groups with nine elements? It's been about five years since I did any finite group theory or number theory, so please forgive my ignorance. But I seem to rememeber subgroups forming little blocks in the table like the 3 × 3 blocks we have on sudoku boards. Is there a 1-1 correspondence between group tables and sudoku boards (I doubt it, but I'm so rusty that I forget). Although, I seem to remember some enumeration results from representation theory of finite groups, but again; it's so long ago that they're nothing more than quiet little bells ringing ~~ Dr Dec (Talk) ~~ 18:51, 30 August 2009 (UTC)[reply]

There are only two groups of order 9: the cyclic group and the direct product of two groups of order 3, so no such correspondence exists. If you draw the Cayley table of a group, that is, a grid whose rows and cols correspond to the group elements and whose ij entry is the product of the corresponding elements, a subgroup doesn't look like a "sub-square" in which every element (of the big group) occurs once, so this is also not like the small squares in a sudoku grid. You might be interested in Latin square, a correct sudoku grid is a special kind of Latin square. As for rep thy, you might have character tables in mind perhaps.87.194.213.98 (talk) 19:21, 30 August 2009 (UTC)[reply]
I already know about Latin squares, but I thought a group theoretical approach might be interesting. I know, from Lagrange's theorem, that the order of any subgroup must divide the order of the group, so subgroups of order 1, 3 and 9 are all possible. Could you please say a few words as to why there aren't any order 9 groups with subgroups of order 3? ~~ Dr Dec (Talk) ~~ 19:29, 30 August 2009 (UTC)[reply]
There are, all groups of order 9 have subgroups of order 3. If <g> is cyclic of order 9 then g^3 generates a subgroup of order 3, and if a group G is the direct product of two groups of order 3 then it has several subgroups of order 3. Have a look at the Mathematics_of_sudoku article, they mention that not-Burnside's lemma can be used to enumerate solutions up to a notion of equivalence. That article also talks about Cayley tables and sudoku grids.87.194.213.98 (talk) 19:40, 30 August 2009 (UTC)[reply]
Excellent! I'd seen the maths of sudoku section in the sudoku article, but had some how managed to miss the fact that there was an entire article. I know what I'll be doing for the next half hour... ~~ Dr Dec (Talk) ~~ 21:15, 30 August 2009 (UTC) [reply]
There are 2 non-isomorphic groups of order 9. The actual number of Cayley tables that form groups is a lot more than that. The problem is that groups require associativity which puts way more structure on the array than is applicable for Sudoko squares.--RDBury (talk) 19:51, 30 August 2009 (UTC)[reply]
If we restrict ourselves to the set {1,...,9} then the only isomorphisms are permutations of the symbols and you can permute the symbols in a completed Sudoko board without breaking it, so I don't think that makes much difference (although rigour requires we mention it). What if we consider quasigroups instead? According to the article there is (modulo permutation of symbols) a 1-1 correspondence between quasigroups and Latin squares. Is there anything interesting to say about those quasigroups that correspond to a Suduko board? --Tango (talk) 01:35, 31 August 2009 (UTC)[reply]
As an aside note that all groups of order p2 (p prime) are abelian and the converse of Lagrange's theorem holds for all abelian groups.--Shahab (talk) 19:55, 30 August 2009 (UTC)[reply]

Random trig question

I know that it is possible to perform inverse trigonometric functions with a calculator. I have been told that it is not possible by hand. However, trigonometry existed centuries before calculators were invented. So, is it possible to perform these function by hand? If not, how did the ancient mathematicians do it? Intelligentsium 23:21, 30 August 2009 (UTC)[reply]

It is possible, it just depends how much time you have on your hands. For example, in the olden days people used log tables to evaluate logarithms. These were basic grids that once you knew the base of the log (say n) and the value of the variable (say x), would give you the answer (say logn(x)). Well, in that case, finding a number in the middle of the table that was close to the number you wanted to find the inverse of would tell you to which base, and of which value, it was the inverse of. I assume that trig' functions were the same. It's just like a group table: find the number in the group table and you know what's the inverse of what. ~~ Dr Dec (Talk) ~~ 00:13, 31 August 2009 (UTC)[reply]

Well, obviously, when you see a table of values of sine and cosine in a book published in 1908, or 1650, that tells you something. Maybe what was meant was that the methods needed in order to do it efficiently by hand cannot be taught at the very elementary level at which instruction in trigonometry takes place today.

As for log tables, where you looked up logn(x) if you knew n and x, that's not how it was done because it's not an efficient way to do it. Base-10 log tables were commonplace. If you wanted log2(3), you used a base-10 log table and found (log10(3))/log10(2). Tables of base-e logarithms also existed, but were not in an appendix to every book. Michael Hardy (talk) 01:28, 31 August 2009 (UTC)[reply]

Of course you can compute inverse trig functions by hand, for example with Padé approximants. Stupendous amounts of research went into developing methods to minimize the amount of labor required by those computations. In practice you would look your number up in a table and use linear or quadratic interpolation on the nearest values you could find to the one you wanted. But somebody had to prepare the tables, and they did it without computers... 67.122.211.205 (talk) 01:42, 31 August 2009 (UTC)[reply]

August 31

Empty set and phi

So, in my topology class last year, a student referred to the empty set as phi. Then, this past week, one of my professors did the same thing. It seems to me that is more like a 0 with a line through it than , and the 0 would match up symbolically as well. Is it related at all to or are these two people incorrect in calling it ? StatisticsMan (talk) 01:04, 31 August 2009 (UTC)[reply]

I've not heard "phi" for the empty set, and calling it that is incorrect or at least not standard. However is a common variant on that looks a good bit like . Eric. 98.207.86.2 (talk) 01:16, 31 August 2009 (UTC)[reply]
Nor have I. People mis-reading the symbol me thinks. ~~ Dr Dec (Talk) ~~ 01:21, 31 August 2009 (UTC)[reply]
Ditto. It is an easy mistake to make, but I've always heard it pronounced as "the empty set" or just "empty". --Tango (talk) 01:26, 31 August 2009 (UTC)[reply]