Wikipedia:Reference desk/Archives/Mathematics/2010 August 3

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 3

The Stone-Cech Compactification of a topological space

Hi, I am trying to figure out the topology on that space. If I understand correctly' the clopen sets in this topology are A={F | A is in F}. My question is this: suppose that a point x is in A in the original topology of the space X. Does the clopen set A we defined on the Stone-Cech Compactification perform an open neighborhood for the principal filter of x? Is this the idea of this compactification? And if so, then what is the meaning of convergence in this space? Thanx! —Preceding unsigned comment added by Topologia clalit (talk • contribs) 09:13, 3 August 2010 (UTC)

I presume you're building the Stone-Cech compactification via ultrafilters here? Since filters are closed upwards, the principle filter at $x$ contains $A$, and thus is contained in the clopen set $[A]$.

Given a sequence ${F_{i}}$, saying that this sequence converges to $F$ means that any closed set $X\in F$, there is an $n$ such that for all $i>n$, $X\in F_{i}$.--203.97.79.114 (talk) 09:56, 3 August 2010 (UTC)

Thanks this is very helpfull. From what you have said, I see now, that for every infinite sequence of ultrafilters there exists an open set that contains an infinite number of ultrafilters from that sequence, since for every A in the original topological space X, either A is in infinite number of ultrafilters or the complement of A is in infinite number of ultrafilters. But, How can I show that every sequence of ultrafilters has a convergence subsequence in this Stone-Cech topology. In other words, I guess, how can I show or be convinced that the Stone-Cach compactification is indeed compact? Thanx! —Preceding unsigned comment added by Topologia clalit (talk • contribs) 10:54, 3 August 2010 (UTC)

number of total order relations

If A is a set with 10 elements how many total order binary relations are possible on A. Thanks -Shahab (talk) 13:56, 3 August 2010 (UTC)

The number of total orders on an n-element set A is equal to the number of bijections from A to {1, 2, 3, ..., n}, which is equal to the number of permutations of {1, 2, 3, ..., n}, which is n!. Algebraist 14:00, 3 August 2010 (UTC)

Thanks Algebraist, but can you also tell me the proof of this. Clearly a bijection is not always a total order, so the proof cant be that total order and bijections are identical, and hence we have this result. Thanks-Shahab (talk) 14:14, 3 August 2010 (UTC)

There's a natural bijection between the set of bijections from A to {1, 2, 3, ..., n} and the set of total orders on A: the bijection f corresponds to the order where a<b iff f(a)<f(b) (where the second < is the natural order on {1, 2, 3, ..., n}. Algebraist 14:17, 3 August 2010 (UTC)

Ambiguity in Number Theory

Here is the discussion moved from above:

Do any reputable mathematicians actually believe there is any ambiguity in what we mean when we ask whether a statement in number theory is True or False?

Of course, Gödel tells us that you can't possible complete the axiomatic system of natural numbers, which is to say, no matter how many axioms you add, there will always be statements that are independent of your set of axioms. However, backing away from the limited scope of axiomatic systems, my question is this: is it conceivable that there could be two models of the natural numbers, both "standard" in a sense that can't quite be stated fully in a purely axiomatic sense, that have different truth values for a given statement? I think the answer is no.

In contrast, set theory seems to be quite ambiguous in the sense that it is certainly conceivable that we could have two perfectly reasonable models of set theory, in one of which the Continuum hypothesis is true, and in the other of which it is false, and we have no clear reason from a purely set theoretic standpoint to prefer one or the other (of course, I could pick any other independent statement in place of the Continuum hypothesis, if it turns out someone demonstrates in the future that there is a clear ironclad reason that the continuum hypothesis ought to be true or false). I emphasize that I don't mean this in the sense that one is more or less useful than the other, but rather, in the sense that one might represent "true" set theory and the other might clearly not be what we intend to mean when we say "set theory". --COVIZAPIBETEFOKY (talk) 16:10, 2 August 2010 (UTC)

OK, I have to jump in here. No, in fact that is not possible. Any two "reasonable" models of set theory must agree on the truth value of CH. Conditions for the models to be "reasonable" in this sense: First, both should be wellfounded models (that is, not just neither thinks there is an infinite descending epsilon chain, but there really isn't an infinite descending epsilon chain in either model). Second, both models, after taking their Mostowski collapses (so that they have the true natural numbers), should contain all sets of natural numbers, and all sets of sets of natural numbers.

If you have two models like that, they agree on the truth value of CH, and the value they agree on is the correct truth value. --Trovatore (talk) 07:46, 5 August 2010 (UTC)

Are you saying that in a "reasonable" model, CH is necessarily true? Tkuvho (talk) 08:35, 5 August 2010 (UTC)

No, not at all. I'm saying that all such models agree on the truth value of CH. Which way they agree, we don't know at the current time. --Trovatore (talk) 16:35, 5 August 2010 (UTC)

This is very intriguing. Is this your own work? How does one prove this sort of result? Tkuvho (talk) 11:27, 6 August 2010 (UTC)

It's actually trivial. CH is equivalent to a sentence of third-order arithmetic ($\Sigma _{1}^{2}$ in fact: "there exists a linear order on P(ω) whose every proper initial segment is countable"), and Trovatore's condition says exactly that the parts of the two models corresponding to third-order arithmetic are the same. What I don't understand is why on earth should this condition be considered "reasonable".—Emil J. 11:45, 6 August 2010 (UTC)

The point I'm really getting at is that there's a certain rather ill-conceived point of view that attempts to maintain a version of realism (there is a model of this or that) while maintaining that propositions like CH are not determinate. If there are models, then we should be able to ask questions of them like "does such and such a model have all subsets of its naturals?". And you don't even have to go all the way to P(P(omega)) to see that CH must be determinate; all you need to do is interrogate wellfounded models that contain all of P(omega). If all such models agree on the truth value of CH, then they are correct. On the other hand, if there are two such models that disagree, then CH is true. --Trovatore (talk) 15:27, 6 August 2010 (UTC)

In an attempt to understand these arguments better, I read through continuum hypothesis but was unable to find anything relevant to the question of simulataneous truth or falsity of CH in various models. Could such information be added? Is there another page that may have relevant information? Tkuvho (talk) 07:10, 8 August 2010 (UTC)

Do you believe reasonable models of set theory should agree on every proposition that can be expressed in the language of set theory? --COVIZAPIBETEFOKY (talk) 21:58, 5 August 2010 (UTC)

Even in number theory you can get things like Goodstein's theorem which cannot be proved just with Peano's axioms and first order logic. It is quite possible for new axioms to be set up that are perfectly acceptable and prove more than can be done now. Dmcq (talk) 16:56, 2 August 2010 (UTC)

Wow, er... that wasn't my question at all. Did I not state it clearly enough? I even linked to Gödel's theorem, which should indicate that I already know there are unprovable propositions in any system of natural numbers that includes both addition and multiplication (and I did know about that particular example, although the example is irrelevant to the general principle). --COVIZAPIBETEFOKY (talk) 18:04, 2 August 2010 (UTC)

Do any reputable mathematicians actually believe there is any ambiguity in what we mean when we ask whether a statement in number theory is True or False? Yes, for example ultrafinitists. Or this guy: [1]. 67.122.211.208 (talk) 18:08, 2 August 2010 (UTC)

I'm very ignorant on this topic but I would like to ask the logicians: if somehow someone managed to "prove" ZFC is consistent/inconsistent, how do you know the framework he got his metaproof from is consistent? You could try metameta proofs but then how do you know that's correct? This obviously goes on forever. And also, if we adopt formalism, we don't believe in any models what not but there's truth about the sentences etc in the realist sense, for example if you metaproof an infinite collection of formulas are theorems, so can we call that formalistic realism? Money is tight (talk) 04:55, 3 August 2010 (UTC)

I don't know much about proofs of the consistency of an axiomatic system, except for: while such a proof cannot be obtained from within the system unless the system turns out to be inconsistent after all, it doesn't necessarily have to occur from a strictly stronger system either. Of course, that doesn't mean the system that proves the consistency can be known for certain to be consistent; there will never be complete certainty.

As for "proofs" of inconsistency of a system, there is only one kind as far as I am aware, and they are quite indisputable: prove a statement and its negation. --COVIZAPIBETEFOKY (talk) 14:49, 3 August 2010 (UTC)

ZFC proves that there is a minimal model of first order arithmetic. All other models are tail extensions of this one. So in this sense (fixing your universe of set theory), there's a "proper" model of elementary number theory, and you could take Truth to be as interpreted in this model. —Preceding unsigned comment added by 203.97.79.114 (talk) 08:57, 3 August 2010 (UTC)

Thanks for the responses, guys. I have some follow-up questions, but unfortunately I also have other priorities, so it'll take me a while to compile them together. Feel free to add any further contributions in the meantime. --COVIZAPIBETEFOKY (talk) 14:37, 3 August 2010 (UTC)

Thanks for your respone COVIZAPIBETEFOKY. As I said I'm not at all familiar with this subject (did a tiny bit a while ago but I'm too busy doing math I need for research) so let me tell you a simple and weird philosophical problem of mine. Say we have a theory with one binary relation R, and we have the axioms (1) for all x xRx and (2) (for all x xRx) implies (for all x not related to x), so we see a contradiction by using modus pendus. But by modus pendus we reasoned, and I know this kind of "reasoning" is just the mechanical deduction and not "intuitive reasoning", but still how do we know that obviously-correct-reasoning is correct? I know you must be like wtf, and I know this is really weird. Perhaps when I have time I'll think about the philosophical side more Money is tight (talk) 15:09, 3 August 2010 (UTC)

Well, in the context of an axiomatic system, what's "correct" is irrelevant to what's valid within the system. We lay out very explicit rules for what's valid and what's not valid, in the form of rules of inference and axioms. In most systems, Modus ponens is a rule of inference, and therefore valid as a step in a proof. It is, however, perfectly conceivable to produce a system in which MP is not a rule of inference. That doesn't change its validity within most of the systems that we speak of in normal mathematical discourse. --COVIZAPIBETEFOKY (talk) 02:48, 4 August 2010 (UTC)

Correct me if I'm wrong, but I'm pretty sure both of the examples that 67.122.211.208 gave are not quite what I'm asking for; they are people who believe that number theory is either outright inconsistent or that it is nonsense not worth studying. My question refers to people who believe in the inherent concept of number theory, but don't believe that there is only one platonic ideal of what a model of number theory should look like exactly. Of course, this is well outside the bounds of mathematical discourse and quite blatantly into philosophy, so possibly it is a question not worth discussing too much. I'm not entirely sure how to justify my own belief that number theory ought to only have one reasonable model, except to say that it's obvious, because in number theory, we can name every object, at least in theory (starting with 0, then S0, SS0, SSS0, and so on).

203.97.79.114's point seems silly to me, since having a reasonable model of set theory is clearly quite a stronger statement than having a reasonable model of number theory (in the sense that it must include a reasonable minimal inductive set containing the empty set, serving as our set of natural numbers, and much more). Maybe there's some merit to it that I don't see, though. --COVIZAPIBETEFOKY (talk) 11:43, 6 August 2010 (UTC)

matrix maximizing algorithm

I saw this problem in a computer programming competition and while I found it trivial to write a program to perform the task, I would like to know if this is a named problem in mathematics so I can see if there are better well-known algorithms. The problem:

Given an mxn matrix of positive integer values from zero to 2^7. Alter the matrix by converting non-zero values to zero such that no column row contains more than one non-zero number and no column contains more than one non-zero number and the total sum of all numbers in the matrix is maximized. There may be more than one maximum solution for a given matrix.

I did it two ways. The first, which I know will not work in special cases, is to remove the lowest number in any row/column with more than one value until there is no row/column with more than one value. That passed the test in the competition. I wrote another version which attempted removing each number, one at a time, in a breadth-first search until it tried all combinations of removals and picked one of the maximized solutions. That works, but is obviously very cost-intensive. Therefore, I am interested in reading about better solutions. -- kainaw™ 14:53, 3 August 2010 (UTC)

This is the Assignment problem.

There's a typo in your problem description, you have "column" twice. -- Meni Rosenfeld (talk) 15:14, 3 August 2010 (UTC)

Thanks. I just checked the index of my discrete math book (where 99% of programming competition problems come from) and this isn't in there. Looks like the Hungarian algorithm is what I was expected to write. -- kainaw™ 16:07, 3 August 2010 (UTC)

Correction... Searched my PDF copy and it is briefly mentioned in the marriage problem section - which is also a good reference for this particular problem except that the marriage problem uses a nxn matrix, not an mxn matrix. -- kainaw™ 16:51, 3 August 2010 (UTC)

Tensor product

Ok the definition of "linear in each variable" is a little dodgy when we talk about infinite tensor products. How about this:

Given a collection Mi of R modules, call a map L defined on their direct product linear in i (index/variable) if for every two tuple x,y such that x(j)=x(j) for every j not equal to i, then L(z)=L(x)+L(y), where z(j)=x(j) for j different from i and z(i)=x(i)+y(i). And for every tuple x and scalar a in R, L(z)=aL(x), where z(i)=ax(i) and same as x everywhere else. L is called multilinear if it's linear in every index.

The relations to make the tensor product in the free module generated by the direct product can be done in similar ways. Am I correct? I find "linear in each variable" in the usual sense quite hard to interpret when the direct product is infinite Money is tight (talk) 14:56, 3 August 2010 (UTC)

Polychora

In terms of side length, what's the hypervolume of each of the regular polychora? --138.110.25.31 (talk) 19:51, 3 August 2010 (UTC)

I assume that you refer to the four-dimensional regular polyhedra, or convex regular 4-polytopes; and I assume that the side length is 1. The tesseract has volume 1 (proof omitted:-); actually, by definition). For the others, you just extrapolate the ordinary methods from (euclidean) geometry in calculating the volumes; with the important observation that the four-dimensional volume of a four-dimensional pyramid is  (base volume) × height / 4 .

The easiest (non-trivial) one to calculate is the volume of the pentachoron. As you hopefully know, the tetrahedron has volume ${\frac {\sqrt {2}}{12}}$, and the distance between its barycentre (let us call it B) and any vertex (V, say) is ${\sqrt {\frac {3}{8}}}$. Now, imagine the tetrahedron as a "basis body" in a pentachoron, with its fifth vertex, say W, outside it. We have a right angle at VBW, and VW has length 1; whence and by the pythagorean theorem, the height of the pentachoron is

$|BW|={\sqrt {|VW|^{2}-|VB|^{2}}}={\sqrt {\frac {5}{8}}}$; whence its volume is

${\frac {\sqrt {2}}{12}}\cdot {\sqrt {\frac {5}{8}}}\cdot {\frac {1}{4}}={\frac {\sqrt {5}}{96}}$

if I calculated correctly (check it by yourself!).

The remaining four volumes are somewhat more complicated to calculate by this method, since the polytopes must be divided into several four-dimensional pyramids each. I think that the easiest way to do this is to let all pyramids be congruent, with the boundary polyhedra for bases, and a common "top" at the barycentre of the respective polytope. JoergenB (talk) 17:41, 8 August 2010 (UTC)

A more general question

Should we add the volumes to the data in tables and boxes for these six "Platonic bodies", and for the three corresponding larger dimensional families? JoergenB (talk) 17:41, 8 August 2010 (UTC)

LaTeX, more than one line of stuff underneath something

Resolved

Okay, what I mean is I want to be able to type a sum with two lines of description, such as for an Eisenstein series

$E_{k}(z)=\sum _{\stackrel {m,n\in \mathbb {Z} }{(m,n)=1}}{\frac {1}{(mz+n)^{k}}}$.

I used \stackrel there but note that the top line is smaller. I see in books often where they do it and the two lines are same size font. Thanks. StatisticsMan (talk) 21:28, 3 August 2010 (UTC)

There is a command "\substack" which does exactly what you want in AMS-LaTeX, but it isn't available on Wikipedia, it seems. --Tango (talk) 03:08, 4 August 2010 (UTC)

\substack is indeed the proper way to do it. On Wikipedia, one can emulate it with matrices:

$E_{k}(z)=\sum _{\begin{smallmatrix}m,n\in \mathbb {Z} \\(m,n)=1\end{smallmatrix}}{\frac {1}{(mz+n)^{k}}}$

—Emil J. 12:09, 4 August 2010 (UTC)

Sweet, thanks a lot both of you. StatisticsMan (talk) 13:10, 4 August 2010 (UTC)