Wikipedia:Reference desk/Archives/Mathematics/2010 July 24

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.

July 24

List of Permutations in GAP

Using GAP, I wish to obtain a list of all even (odd) permutations of the ordered sequence 1, 2, 3, ..., n of the n first positive integers. How do I do that?

For instance, given n = 3, the ordered sequence of the n first positive integers is

1, 2, 3

and the set of all even permutations is

1, 2, 3

3, 1, 2

2, 3, 1

and the set of all odd permutations is

1, 3, 2

3, 2, 1

2, 1, 3.

--Andreas Rejbrand (talk) 13:47, 24 July 2010 (UTC)

gap> n:=3;;Print("\nThe set of all even permutations is:\n"); for
> pi in AlternatingGroup(n) do
> Print(":",JoinStringsWithSeparator(ListPerm(pi,n),", "),"\n"); od; Print("\n");

The set of even permutations:
:1, 2, 3
:3, 1, 2
:2, 3, 1

gap> n:=3;;Print("\nThe set of all odd permutations is:\n"); for
> pi in RightCoset(AlternatingGroup(n),(1,2)) do
> Print(":",JoinStringsWithSeparator(ListPerm(pi,n),", "),"\n"); od; Print("\n");

The set of odd permutations:
:2, 1, 3
:3, 2, 1
:1, 3, 2

This generates output fairly similar to what you wrote here. JackSchmidt (talk) 15:24, 24 July 2010 (UTC)

Thank you for your reply, but it seems not quite to work:

gap> n:=3;;Print("\nThe set of all even permutations is:\n"); for
The set of all even permutations is:
> pi in AlternatingGroup(n) do
> Print(":",JoinStringsWithSeparator(ListPerm(pi,n),", "),"\n"); od; Print("\n");
Function: number of arguments must be 1 (not 2) at
Print( ":", JoinStringsWithSeparator( ListPerm( pi, n ), ", " ), "\n" );
 called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can replace the argument list <args> via 'return <args>;' to continue
brk>

--Andreas Rejbrand (talk) 23:44, 24 July 2010 (UTC)

But this seems to work for the even permutations:

for pi in AlternatingGroup(3) do Print(ListPerm(pi), "\n"); od;

(at least if we interpret [ ], the result of the identity permutation, as [1, 2, 3]). --Andreas Rejbrand (talk) 23:58, 24 July 2010 (UTC)

Sorry, apparently the two argument version of ListPerm is only available in the development branch. You can use:

gap> listPerm := function(pi,n) return List([1..n],i->i^pi); end;;
gap> n:=3;;Print("\nThe set of all even permutations is:\n"); for
> pi in AlternatingGroup(n) do
> Print(":",JoinStringsWithSeparator(listPerm(pi,n),", "),"\n"); od; Print("\n");

etc. to avoid the "[]" type problem with permutations that do not move all the points. If you don't mind cycle notation, then something like AsSet( AlternatingGroup( 3 ) ) is even easier. The main thing is just that the even permutations form the AlternatingGroup(n), and the odd permutations form the RightCoset( AlternatingGroup(n), (1,2) ), which is exactly what Rckrone is saying. JackSchmidt (talk) 03:05, 25 July 2010 (UTC)

If you've got the even ones, you can get the odd ones by picking any single odd permutation (for example swapping the first and second element) and applying it once to each even permutation in the list. Rckrone (talk) 01:11, 25 July 2010 (UTC)

Thanks, now it works! --Andreas Rejbrand (talk) 15:02, 25 July 2010 (UTC)

Resolved

Cardinality

A question I asked earlier raised some questions about cardinality. It seems that the space of all smooth functions between the real numbers and the real number, denoted C^∞(R,R), has cardinality 2^ω. This is the cardinality of the continuum. I was wondering how this cardinality business worked when we had some structure of our sets. For example, if A and B are two vector spaces (possibly infinite dimensional), and their cardinalities are know, then what is the cardinality of the product space A × B? Let U ⊆ V be two real vector spaces. Let us assume that we know the cardinality of U and V. What is the cardinality of the quotient space U/V? I have a couple of explicit questions too. Let M be a real, smooth manifold.

1. What is the cardinality of Ω^k(M), i.e. the space of differential k-forms over M?
2. What is the cardinality of E^k(M), i.e. the space of exact differential k-forms over M?
3. What is the cardinality of the quotient Ω^k(M)/E^k(M)?

FInally, a more general question. If you have two real, smooth manifold X and Y and a smooth map ƒ: X → Y. Let's assume that we know the cardinality of X and Y. Then what is the cardinality of ƒ(X) ⊆ Y? — Fly by Night (talk) 20:09, 24 July 2010 (UTC)

OK, this is a bunch of questions; let me see what I can do....

• For A and B vector spaces (I assume infinite; that is, they're not over some finite field and they're not the trivial vector space), the cardinality of A×B is the greater of the cardinalities of A and B. To see this, note that it's certainly at least that, because if (say) B is larger, then you can project to B. And it's also at most that, because that's the cardinality of the Cartesian product of A and B as sets.
• For the cardinality of the quotient space, it's impossible to say a priori, because for example U might equal V, in which case the cardinality is 1. But if it isn't, then I think you're always going to get at least $2^{\aleph _{0}}$. I'd have to think about how to prove it.
• I don't know enough about differential forms and would have to think more carefully/look up definitions, but I think all your answers are going to be $2^{\aleph _{0}}$ in normal cases (i.e. I suppose you have to assume the manifolds are connected or sigma-compact or something).
• I think the cardinality of any sigma-compact real manifold is $2^{\aleph _{0}}$, so unless you want to generalize past sigma-compact, the X and Y of your final question are always going to have that cardinality, and the range of f is a closed subset, so unless it's a singleton it will also have cardinality $2^{\aleph _{0}}$.
• Finally, there are interesting questions you can ask if you want to know about cardinality with definable witnesses — this is the area of Borel equivalence relations. --Trovatore (talk) 00:33, 25 July 2010 (UTC)

A differential form on R^n is defined by a finite set of functions with respect to a standard basis, so it would have the same cardinality as functions. Tkuvho (talk) 08:31, 25 July 2010 (UTC)

Some off-topic chat sectioned by the OP − Fly by Night

Trovatore, you're right about the quotient of vector spaces. Let W by a proper subspace of V. Take a vector v outside of W. Now take the collection of cosets rv+W for every real number r. These cosets are pairwise distinct; if (r1)v+W=(r2)v+W for some two different real numbers r1,r2, then (r1-r2)v is inside W. But (r1-r2) is not 0, so v is in W, a contradiction. Note that real vector space is essential; rational vector will offer only countably many cosets. Also you should know it's not just the smooth function with continuum cardinality; the metric space of continuous functions is separable hence of continuum cardinality. And for that matter, you might be surprised to know that the product space [0,1]^[0,1] is separable when it has 2^c card. I find the issue of cardinality in differential forms quite dull. Perhaps it's because I don't even know what a differential form is... Lol. Well my point is, that kind of mathematics is very far from set theory and most of the set theory related question may well turn out to be independent of currently accepted axioms.Money is tight (talk) 10:42, 25 July 2010 (UTC) For all those who say that they do not know what a differential form is, or would have to look it up, it is not anything "really special"! Are you familiar with tensors and tensor algebra (for example, "the basic material" including alternating tensors, the wedge product, etc.)? If so, learning about differential forms is not that much of a step up. If not, there are various books on the subject that assume literally no knowledge of mathematics beyond what a vector space is and basic multivariable calculus, so if, for example, you know what a separable space is, it seems that you have more than enough ability to pick up differential forms. (It takes a day, really: just pick up a decent book such as Munkres' Analysis on Manifolds and read the sixth chapter. Bott and Tu also have an excellent book on the subject which assumes little background if you are mathematically mature.) I mean, even if you are specializing in some area (which to do, you need to have ability, which you clearly do have), there are some basic things in math (differential forms, de Rham cohomology, manifolds, tensor algebra etc.) which you should know. (Ideally, you would want to have a solid knowledge the two "A's" and the one "T": algebra (finite groups, noncommutative rings, commutative rings, algebraic number theory, representation theory), analysis (real analysis, numerical analysis, functional analysis, complex analysis, complex geometry, C* algebras) and topology (point-set topology, set-theoretic topology, algebraic topology, differential geometry, differential topology, algebraic geometry); it is a shame that except in a select few universities across the world, they do not require you to learn these areas to a decent extent to qualify for PhD, anymore.) And it really is not that difficult (especially if you are young, a grad. student or have a PhD): you have already seen differential forms when doing ordinary single-variable calculus and line integrals in multivariable calculus! (Saharon Shelah is a prolific set theorist, but he has applied set theory to numerous areas in mathematics; for example, to the Whitehead problem and to Arrow's impossibility theorem. Of course, set theory is a beautiful subject in its own right, and you do not need to provide applications of the theory to show this, but I guess my point is that with even a little knowledge of other areas of mathematics, you can do very good work in a specialized area. And with problems such as the Riemann hypothesis going around (or really any long open problem in mathematics for that matter), who knows what techniques from which areas of mathematics could be used?) PST 02:08, 27 July 2010 (UTC) PST, it's not that I've never encountered differential forms or that I think they're "difficult". It's that I didn't have the precise definitions at the top of my consciousness, and I didn't want to say something stupid just because I'd forgotten some subtlety. --Trovatore (talk) 02:17, 27 July 2010 (UTC) Trovatore, when I was writing my post I was thinking that I was mostly addressing "Money is Tight" (i.e., I had "Money is Tight in mind) (especially with relation to it being "difficult" or not encountering it before, since Money is Tight explicitly mentioned that he had not encountered it before) but for some reason I had you in mind as well for the exact same things I was addressing "Money is Tight". (Essentially, the comments addressed to each individual got mixed up in the same sentences.) I probably should have written separate posts to each individual. I apologize for this confusion and I agree that I should have interpreted what you said in the way you described. PST 02:36, 27 July 2010 (UTC) Thanks for your response PST. I don't know if differential forms are difficult of not and I haven't encountered them yet because I was following one of your suggestions way back; I ask a question in algebraic topology and basically you replied "go do some category theory and this will be a lot easier". Yes as I now look at algebraic topology texts things that looked out of this world are becoming familiar. I think I'll look at differential forms some other time. Money is tight (talk) 03:47, 27 July 2010 (UTC) It is great that you did some category theory! You should definitely continue doing what you are doing! I did not intend to suggest otherwise. Of course, virtually no-one can successfully learn mathematics by always thinking about what they do not know rather than the task at hand. There will always be a time when you are not familiar with at least one branch of mathematics, but of course that will change as you expand your mathematics knowledge. (Of course that is the same for nearly every mathematician on this planet!) I did not mean to say that differential forms would be difficult for you; in fact, quite the contrary, I think that it is something that you can pick up quite easily whenever you wish but you should do algebraic topology and other branches of mathematics at least until you feel that the time is "ripe". (I would definitely recommend Bott and Tu's Differential forms in algebraic topology for this purpose. One of its novel features is its very intuitive introduction to spectral sequences. The idea of the textbook is to approach algebraic topology from a more differential point of view rather than the classical homological algebra/category theory point of view employed in most texts.) I guess my post was written in a hurry and I do not think it conveyed what I wanted it convey and I apologize for that. PST 06:28, 27 July 2010 (UTC)

Thanks for your detailed response Trovatore, it's much appreciated. Tkuvho: I think you're probably right, but there's a very small chance that you're not. Locally all differential forms are as you say: they are given by a Cartesian product of functions. But all fibre bundles are locally product spaces. Is it possible that the fibre bundle of differential forms over a manifold is not trivial? (It must be possible, or de-Rham cohomology would always be trivial). In such as case, the basis argument doesn't hold globally. I guess the question simplifies to this: is cardinality a local property? — Fly by Night (talk) 22:40, 25 July 2010 (UTC)

If M is a connected compact manifold, then it can be covered by a finite number of coordinate patches, where any bundle will be trivial. Since the sum of a finite number of cardinalities cannot exceed what you started with, this takes care of the connected case. Now you can certainly consider non-connected manifolds with as many connected components as you wish, which would make the space of forms correspondingly large. Generally speaking, cardinality does not seem to be a suitable tool to analyze differential forms. Tkuvho (talk) 04:27, 27 July 2010 (UTC)

Well, what I was trying to figure out is what happens if you drop "compact" (or more to the point, "sigma-compact"). There are connected manifolds that are not sigma-compact, the most obvious example being the long line. But if you want the long line to be a manifold, you have to keep it to length ω₁, because if you go past that, then the ordinal ω₁ is a point where there is no local homeomorphism with R. And of course in that case the long line still has just cardinality $2^{\aleph _{0}}$. It's possible that this observation can be generalized to a proof that any connected manifold has cardinality $2^{\aleph _{0}}$, but I don't immediately see it. --Trovatore (talk) 07:31, 27 July 2010 (UTC)

The long line as described there is $\omega _{1}$-many intervals [0,1) patched together (in lexicographic order). Replacing $\omega _{1}$ by $\omega _{2}$, we get an extremely long line. In the context of separable spaces, all spaces of continuous functions, differential forms, etc will be $\omega _{1}$ since such a function (form) is determined by its values on a countable dense subset. Tkuvho (talk) 07:55, 27 July 2010 (UTC)

No, if you use $\omega _{2}$ you don't get a line at all, as Trovatore points out: it's no longer locally homeomorphic to R. And the set of continuous real-valued functions on a separable space typically has cardinality $2^{\aleph _{0}}$, not $\omega _{1}$. Algebraist 08:25, 27 July 2010 (UTC)

Right, sorry, I guess I am out of my depth here. Let's assume CH for simplicity. So the question is to determine the cardinality of the space of continuous functions on the Cartesian product of R (equipped with a well-ordering) by [0,1) (the product being equipped with the lexicographic order)? It seems as though using AC you should be able to get above the continuum, but I am not sure. Tkuvho (talk) 11:36, 27 July 2010 (UTC) Right, you prescribe the function arbitrarily on its midpoint 1/2, and then connect by linearity between it and its predecessor and successor. Does this work? Tkuvho (talk) 11:39, 27 July 2010 (UTC)

No, such a function need not be continuous, since (for example) (ω,0) is the limit of the points (n,1/2). Algebraist 16:12, 27 July 2010 (UTC)

I see, I was thinking of this too naively. What if one limits the possible values at a given "1/2" to lie between 0 and 1/n, where n is the distance to the nearest initial element in the well-order? Tkuvho (talk) 20:23, 27 July 2010 (UTC)

Still too naive (assuming your "initial element" means what is normally called a limit ordinal). For example, (ω²,0) is the limit of the points (ωn+1,1/2), which (if I'm understanding your scheme correctly) can all map to anything between 0 and 1. Algebraist 01:42, 28 July 2010 (UTC)

What if we take all the finite coefficients in the writing of the ordinal, choose the maximal one M, and require the values at the corresponding "1/2" to be at most 1/M ? Tkuvho (talk) 02:12, 28 July 2010 (UTC) I take it one runs into a problem with epsilon nought. I guess what I am asking is, is there a natural integer-valued function f on the ordinals such that an ordinal x is a limit ordinal if and only if f(x)=0? Tkuvho (talk) 03:59, 28 July 2010 (UTC) At any rate, the question of the cardinality of the set of continuous functions on the long line (modulo CH at any rate) seems to be reducible to the following question: does there exist a nonnegative continuous function on the ordinals which vanishes exactly on the limit ordinals? Tkuvho (talk) 08:40, 28 July 2010 (UTC) P.S. I see that it say at order topology that "any continuous function from ω₁ to R (the real line) is eventually constant", based on which I would expect that the set of continuous functions on the long line is no bigger than the continuum. Tkuvho (talk) 08:51, 28 July 2010 (UTC)

(ec) ... I now realize I could've made this a lot easier by actually reading to the end of the article concerned. As I half-remembered, every continuous function from the long line to R is eventually constant, and of course every initial segment of the long line is just homeomorphic to [0,1), which is enough to show that there are only continuum-many continuous functions (with no reliance on CH, but some on AC). Algebraist 09:10, 28 July 2010 (UTC)

Great, thanks! That clarifies things. Tkuvho (talk) 09:37, 28 July 2010 (UTC)

Resolved

Thanks again everyone! — Fly by Night (talk) 21:06, 27 July 2010 (UTC)