# Generated by the singletons

1. Oct 7, 2013

### shoeburg

Hello,

I just started a prob theory class and i'm a total beginner. I can't find the definition of the following anywhere:
1) What does it mean for a set to be generated by the singletons? In other words, how do I show a certain set is generated by the singletons
2) Similarly, what does it mean to be generated by a collection of sets?

My guess: A set generated by the singletons (or a collection of sets) means that that set can be formed by taking all the singletons and unioning them and complementing them, which leads us to a borel field?

2. Oct 7, 2013

### jbunniii

It is meaningless to say that a SET is generated by singletons. But one can start with a set, say $X$, and a collection $B$ of subsets of $X$, and consider the algebra (aka field) generated by $B$. This is simply the smallest algebra that can be defined on $X$ which includes all of the subsets in $B$. Equivalently, it is the intersection of all algebras on $X$ which contain $B$.

In your case, you have some set $X$ and can define $B$ to be the set of all singletons in $X$. Then there is some smallest algebra which contains all the singletons, namely the intersection of all algebras that contain all the singletons.

3. Oct 8, 2013

### shoeburg

Okay. I'm slowly picking up on this. Specifically, I'm asked to prove: Let B be the collection of all subsets of A (a sigma-algebra?). A is countable if and only if B is generated by the singletons. See my only experience with generators is from a couple abstract algebra courses I've taken, so in my head I'm thinking of a bunch of singletons doing some operation amongst themselves like unioning until all possibilities are exhausted. I'm not sure what exactly I'm trying to prove to show its generated by said singletons. I appreciate your help.

4. Oct 8, 2013

### jbunniii

That's more or less correct, but it's not the only characterization, and sometimes other, equivalent statements are easier to work with:

(1) the sigma algebra $Y$ is generated by the singletons

if and only if

(2) $Y$ is the smallest sigma algebra on $A$ which contains all the singletons

if and only if

(3) $Y$ is the intersection of all sigma algebras on $A$ which contain the singletons

if and only if

(4) if $Z$ is any sigma algebra on $X$ which contains all the singletons, then $Y \subset Z$

Keeping this in mind, let's look at your problem. You have $B = \mathcal{P}(A) =$ the power set of $A$.

Suppose that $A$ is countable. Suppose that $Z$ is a sigma algebra containing all the singletons of $A$. Since $Z$ is closed under countable unions, and $A$ is countable, it follows that every subset of $A$ is in $Z$. Thus, $B = \mathcal{P}(A) \subset Z$. Therefore $B$ satisfies the role of $Y$ in (4) above. Since (4) is equivalent to (1), it follows that $B$ is generated by the singletons.

See if you can find a similar argument for the reverse implication.

5. Oct 10, 2013

### shoeburg

Okay. Let B be generated by the singletons. Since B is a sigma-algebra, it is closed under countable unions, and since it must contain every singleton, there must then only be a countable number of singletons, implying A is countable.

6. Oct 11, 2013

### jbunniii

I don't see where you used the fact that B is generated by the singletons.

The power set of $\mathbb{R}$ (i.e. the set of all subsets of the real numbers) is a sigma algebra, and it contains all the singletons, but there are an uncountable number of singletons.

7. Oct 11, 2013

### jbunniii

Suppose the sigma algebra $B = \mathcal{P}(A)$, the power set of $A$, is generated by the singletons of $A$.

Consider the set $C = \{S \subset A : \text{ either }S \text{ is countable or }S^c\text{ is countable}\}$.

Claim 1: $C$ is a sigma algebra
Claim 2: $B \subset C$

Can you prove these claims? Can you use them to prove that $A$ must be countable?

8. Oct 11, 2013

### shoeburg

Whoops. Does it make sense to say that since B is the smallest sigma-algebra on A containing the singletons, then it is at most countable, because if it was uncountable it couldn't be the smallest?

9. Oct 11, 2013

### shoeburg

Whoops again I didn't see your second post. I'll try that. I really appreciate your help.

10. Oct 11, 2013

### jbunniii

FYI, I made a correction to my last post - please refresh to make sure you get the corrected version.

11. Oct 11, 2013

### jbunniii

But your goal is to show that $A$ is countable, not $B$. Indeed, if $A$ is countably infinite and $B$ is the power set of $A$, then $B$ is always uncountable.