Wikipedia:Reference desk/Archives/Mathematics/2010 July 24
Mathematics desk | ||
---|---|---|
< July 23 | << Jun | July | Aug >> | July 25 > |
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
editList of Permutations in GAP
editUsing 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>
- 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:
- (at least if we interpret [ ], the result of the identity permutation, as [1, 2, 3]). --Andreas Rejbrand (talk) 23:58, 24 July 2010 (UTC)
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 theAlternatingGroup(n)
, and the odd permutations form theRightCoset( AlternatingGroup(n), (1,2) )
, which is exactly what Rckrone is saying. JackSchmidt (talk) 03:05, 25 July 2010 (UTC)
- 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
- 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)
Cardinality
editA 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.
- What is the cardinality of Ωk(M), i.e. the space of differential k-forms over M?
- What is the cardinality of Ek(M), i.e. the space of exact differential k-forms over M?
- What is the cardinality of the quotient Ωk(M)/Ek(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 . 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 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 , 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 .
- 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)
- OK, this is a bunch of questions; let me see what I can do....
Some off-topic chat sectioned by the OP − Fly by Night
|
---|
|
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 ω1, because if you go past that, then the ordinal ω1 is a point where there is no local homeomorphism with R. And of course in that case the long line still has just cardinality . It's possible that this observation can be generalized to a proof that any connected manifold has cardinality , but I don't immediately see it. --Trovatore (talk) 07:31, 27 July 2010 (UTC)
- The long line as described there is -many intervals [0,1) patched together (in lexicographic order). Replacing by , we get an extremely long line. In the context of separable spaces, all spaces of continuous functions, differential forms, etc will be 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 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 , not . 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, (ω2,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 ω1 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)
- (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)
- 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 ω1 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)
- Still too naive (assuming your "initial element" means what is normally called a limit ordinal). For example, (ω2,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)
- 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)
- 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)
- 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, if you use 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 , not . Algebraist 08:25, 27 July 2010 (UTC)
- The long line as described there is -many intervals [0,1) patched together (in lexicographic order). Replacing by , we get an extremely long line. In the context of separable spaces, all spaces of continuous functions, differential forms, etc will be since such a function (form) is determined by its values on a countable dense subset. Tkuvho (talk) 07:55, 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 ω1, because if you go past that, then the ordinal ω1 is a point where there is no local homeomorphism with R. And of course in that case the long line still has just cardinality . It's possible that this observation can be generalized to a proof that any connected manifold has cardinality , but I don't immediately see it. --Trovatore (talk) 07:31, 27 July 2010 (UTC)
Thanks again everyone! — Fly by Night (talk) 21:06, 27 July 2010 (UTC)