Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorDavid Tanzer
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: David Tanzer
   Format: TextHi, I am a visitor to the Nforum, from the Azimuth project. I have a couple of math questions that I have always found curious. Here is the first one. Let S be an infinite set, and consider the power set 2^S, viewed as a vector space over 2. Addition of sets is symmetric difference. For countable S, we could use this equivalent representation: take all sequences of binary digits, with component-wise addition modulo 2, and scaling by 0 and by 1. Since it is a vector space, using the axiom of choice, we know that it must have a basis. I am not able to visualize such a basis. It must be some collection of sets, from which any set can be uniquely expressed as the symmetric difference of a finite number of sets in the collection. The answer would be trivial if we took, instead of 2^S, the collection of _finite_ subsets of S: then the basis would be the collection of all singleton subsets of S. Can anyone provide a constructive description of a basis for 2^S? Or is this another example of a queer implication of the axiom of choice, where it must exist but we don't know how to describe it?

   Hi, I am a visitor to the Nforum, from the Azimuth project. I have a couple of math questions that I have always found curious. Here is the first one.
   
   Let S be an infinite set, and consider the power set 2^S, viewed as a vector space over 2. Addition of sets is symmetric difference. For countable S, we could use this equivalent representation: take all sequences of binary digits, with component-wise addition modulo 2, and scaling by 0 and by 1.
   
   Since it is a vector space, using the axiom of choice, we know that it must have a basis.
   
   I am not able to visualize such a basis. It must be some collection of sets, from which any set can be uniquely expressed as the symmetric difference of a finite number of sets in the collection.
   
   The answer would be trivial if we took, instead of 2^S, the collection of _finite_ subsets of S: then the basis would be the collection of all singleton subsets of S.
   
   Can anyone provide a constructive description of a basis for 2^S? Or is this another example of a queer implication of the axiom of choice, where it must exist but we don't know how to describe it?
2. • CommentRowNumber2.
   • CommentAuthorRodMcGuire
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: RodMcGuire
   Format: MarkdownItexYou appear, maybe, to be assuming that your basis will be finite. $2^S$ is atomistic (aka. atomic) and its atoms (singleton sets) form a basis of a complete atomic Boolean lattice. It is possible to have infinite Boolean lattices that don't have atoms but that is not the case here. Or, maybe I am really missing something to do with size issues.

   You appear, maybe, to be assuming that your basis will be finite.

   $2^S$ is atomistic (aka. atomic) and its atoms (singleton sets) form a basis of a complete atomic Boolean lattice.

   It is possible to have infinite Boolean lattices that don’t have atoms but that is not the case here.

   Or, maybe I am really missing something to do with size issues.

3. • CommentRowNumber3.
   • CommentAuthorTodd_Trimble
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexRod: he's not assuming the basis will be finite. Also, the atoms do not form a vector space basis when $S$ is countably infinite, which is what he specified. David: I think it's just one of those things, where there is no explicit constructive description that can be given.

   Rod: he’s not assuming the basis will be finite. Also, the atoms do not form a vector space basis when $S$ is countably infinite, which is what he specified.

   David: I think it’s just one of those things, where there is no explicit constructive description that can be given.

4. • CommentRowNumber4.
   • CommentAuthorTobyBartels
   • CommentTimeFeb 14th 2013
   • PermaLink
   Author: TobyBartels
   Format: MarkdownItexAccording to Howard & Rubin (Consequences of the Axiom of Choice), AC is equivalent (over ZF) to the statement that every generating set in every vector space over $2$ contains a basis. But I can't find in there the mere statement that every vector space over $2$ has a basis.

   According to Howard & Rubin (Consequences of the Axiom of Choice), AC is equivalent (over ZF) to the statement that every generating set in every vector space over $2$ contains a basis. But I can’t find in there the mere statement that every vector space over $2$ has a basis.

5. • CommentRowNumber5.
   • CommentAuthorjcmckeown
   • CommentTimeFeb 15th 2013
   • PermaLink
   Author: jcmckeown
   Format: MarkdownItexOf course, the underlying set of a vector space is also a generating set for that vector space.

   Of course, the underlying set of a vector space is also a generating set for that vector space.

6. • CommentRowNumber6.
   • CommentAuthorTobyBartels
   • CommentTimeFeb 15th 2013
   • PermaLink
   Author: TobyBartels
   Format: MarkdownItexRight, so AC implies the existence of the basis; but there are many other generating sets, so we don't have that the existence of a basis (for every vector space over $\mathbb{F}_2$) implies AC.

   Right, so AC implies the existence of the basis; but there are many other generating sets, so we don’t have that the existence of a basis (for every vector space over $\mathbb{F}_2$) implies AC.