Basic properties and intuition behind an independent family of subsets of a set.
up vote
2
down vote
favorite
Ultimately I'm trying to understand the result that for a set X the number of ultrafilters on X is equal to $2^{2^{|X|}}$. The proofs I've found use the notion of an independent family of subsets of X. My question has some parts:
(1) What is the origin of this idea of independent family of subsets and what was it's motivation, i.e. what is it capturing?
(2) Is there a basic treatment somewhere? I've been trying to figure out more about it, but the definitions vary a bit. In general it looks something like:
Definition Let X be a set. Let $mathscr{A}$ be a collection of subsets of X. $mathscr{A}$ is an independent family of subsets of X if, whenever $mathscr{F}subsetmathscr{A}$ and $mathscr{G}subsetmathscr{A}$ are finite and disjoint,
$$(bigcaplimits_{Ainmathscr{F}}A)cap (bigcaplimits_{Ainmathscr{G}}A^{c})neqemptyset$$
Sometimes it's stated that the intersection is not only nonempty but has a particular cardinality, but I don't think that matters for the ultrafilter argument.
For a independent family of subsets it would seem as though it's a stronger property than the finite intersection property. We need at least that otherwise there would be ways of choosing $mathscr{F}$ such that $cap_{Ainmathscr{F}}A=emptyset$ and then the rest of the big ole intersection would fail.
Also it would seem that for any subsets A and B of X, if $Acup B=X$, then you cannot have both A and B in the set since their intersection of their complements would be empty. Likewise we can't have the empty set or X in the family $mathscr{A}$ because of complements.
I have been looking for treatments of this topic but I've missed something very obvious I'm willing to take some well meaning abuse :)
general-topology set-theory
asked Nov 18 at 14:45
kevin roberge
112
add a comment |
up vote
2
down vote
favorite
Ultimately I'm trying to understand the result that for a set X the number of ultrafilters on X is equal to $2^{2^{|X|}}$. The proofs I've found use the notion of an independent family of subsets of X. My question has some parts:
(1) What is the origin of this idea of independent family of subsets and what was it's motivation, i.e. what is it capturing?
(2) Is there a basic treatment somewhere? I've been trying to figure out more about it, but the definitions vary a bit. In general it looks something like:
Definition Let X be a set. Let $mathscr{A}$ be a collection of subsets of X. $mathscr{A}$ is an independent family of subsets of X if, whenever $mathscr{F}subsetmathscr{A}$ and $mathscr{G}subsetmathscr{A}$ are finite and disjoint,
$$(bigcaplimits_{Ainmathscr{F}}A)cap (bigcaplimits_{Ainmathscr{G}}A^{c})neqemptyset$$
Sometimes it's stated that the intersection is not only nonempty but has a particular cardinality, but I don't think that matters for the ultrafilter argument.
For a independent family of subsets it would seem as though it's a stronger property than the finite intersection property. We need at least that otherwise there would be ways of choosing $mathscr{F}$ such that $cap_{Ainmathscr{F}}A=emptyset$ and then the rest of the big ole intersection would fail.
Also it would seem that for any subsets A and B of X, if $Acup B=X$, then you cannot have both A and B in the set since their intersection of their complements would be empty. Likewise we can't have the empty set or X in the family $mathscr{A}$ because of complements.
I have been looking for treatments of this topic but I've missed something very obvious I'm willing to take some well meaning abuse :)
general-topology set-theory
asked Nov 18 at 14:45
kevin roberge
112
Considered hiw many untrafilters there is on a finite set.
– William Elliot
Nov 19 at 0:29
I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets?
– kevin roberge
Nov 19 at 14:01
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Ultimately I'm trying to understand the result that for a set X the number of ultrafilters on X is equal to $2^{2^{|X|}}$. The proofs I've found use the notion of an independent family of subsets of X. My question has some parts:
(1) What is the origin of this idea of independent family of subsets and what was it's motivation, i.e. what is it capturing?
(2) Is there a basic treatment somewhere? I've been trying to figure out more about it, but the definitions vary a bit. In general it looks something like:
Definition Let X be a set. Let $mathscr{A}$ be a collection of subsets of X. $mathscr{A}$ is an independent family of subsets of X if, whenever $mathscr{F}subsetmathscr{A}$ and $mathscr{G}subsetmathscr{A}$ are finite and disjoint,
$$(bigcaplimits_{Ainmathscr{F}}A)cap (bigcaplimits_{Ainmathscr{G}}A^{c})neqemptyset$$
Sometimes it's stated that the intersection is not only nonempty but has a particular cardinality, but I don't think that matters for the ultrafilter argument.
For a independent family of subsets it would seem as though it's a stronger property than the finite intersection property. We need at least that otherwise there would be ways of choosing $mathscr{F}$ such that $cap_{Ainmathscr{F}}A=emptyset$ and then the rest of the big ole intersection would fail.
Also it would seem that for any subsets A and B of X, if $Acup B=X$, then you cannot have both A and B in the set since their intersection of their complements would be empty. Likewise we can't have the empty set or X in the family $mathscr{A}$ because of complements.
I have been looking for treatments of this topic but I've missed something very obvious I'm willing to take some well meaning abuse :)
general-topology set-theory
asked Nov 18 at 14:45
kevin roberge
112
Ultimately I'm trying to understand the result that for a set X the number of ultrafilters on X is equal to $2^{2^{|X|}}$. The proofs I've found use the notion of an independent family of subsets of X. My question has some parts:
(1) What is the origin of this idea of independent family of subsets and what was it's motivation, i.e. what is it capturing?
(2) Is there a basic treatment somewhere? I've been trying to figure out more about it, but the definitions vary a bit. In general it looks something like:
Definition Let X be a set. Let $mathscr{A}$ be a collection of subsets of X. $mathscr{A}$ is an independent family of subsets of X if, whenever $mathscr{F}subsetmathscr{A}$ and $mathscr{G}subsetmathscr{A}$ are finite and disjoint,
$$(bigcaplimits_{Ainmathscr{F}}A)cap (bigcaplimits_{Ainmathscr{G}}A^{c})neqemptyset$$
Sometimes it's stated that the intersection is not only nonempty but has a particular cardinality, but I don't think that matters for the ultrafilter argument.
For a independent family of subsets it would seem as though it's a stronger property than the finite intersection property. We need at least that otherwise there would be ways of choosing $mathscr{F}$ such that $cap_{Ainmathscr{F}}A=emptyset$ and then the rest of the big ole intersection would fail.
Also it would seem that for any subsets A and B of X, if $Acup B=X$, then you cannot have both A and B in the set since their intersection of their complements would be empty. Likewise we can't have the empty set or X in the family $mathscr{A}$ because of complements.
I have been looking for treatments of this topic but I've missed something very obvious I'm willing to take some well meaning abuse :)
general-topology set-theory
general-topology set-theory
asked Nov 18 at 14:45
kevin roberge
112
asked Nov 18 at 14:45
kevin roberge
112
asked Nov 18 at 14:45
kevin roberge
112
asked Nov 18 at 14:45
kevin roberge
112
asked Nov 18 at 14:45
kevin roberge
112
112
Considered hiw many untrafilters there is on a finite set.
– William Elliot
Nov 19 at 0:29
I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets?
– kevin roberge
Nov 19 at 14:01
add a comment |
Considered hiw many untrafilters there is on a finite set.
– William Elliot
Nov 19 at 0:29
I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets?
– kevin roberge
Nov 19 at 14:01
Considered hiw many untrafilters there is on a finite set.
– William Elliot
Nov 19 at 0:29
Considered hiw many untrafilters there is on a finite set.
– William Elliot
Nov 19 at 0:29
I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets?
– kevin roberge
Nov 19 at 14:01
I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets?
– kevin roberge
Nov 19 at 14:01
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Let $mathcal F$ be a family of subsets of some set $X$, and suppose we play the following game. I pick some $Ainmathcal F$ and tell you which $A$ it is; I tell you that I'm thinking of some $xin X$ but I don't tell you which $x$ it is; you're supposed to guess whether $xin A$. Before you make your guess, you're allowed to ask me questions "Is $xin B$?" for any $Binmathcal F$ except that $B$ can't be $A$ (i.e., you can't ask me the question you're supposed to guess the answer to). You can ask lots of these questions, but at some point (after finitely many of your questions have been answered) you have to give your answer, either $xin A$ or $xnotin A$. At that point, if I can find an $xin X$ for which all my answers to your questions are correct but your decision about $xin A$ is incorrect, then I win; otherwise, you win.
To say that $mathcal F$ is an independent family is equivalent to saying that I can answer your questions completely arbitrarily (flipping a coin or just saying whatever comes to mind) as long as, if you ask the same question twice then I give the same answer both times, and then, whatever answer you decide about $xin A$, I can still find an $x$ to win the game.
In other words, no matter how much information you collect from me about $xin B$ for various (finitely many) $Binscr F$, it doesn't help you determine whether $xin A$; I can always find an $x$ consistent with my answers yet violating yours.
I think this makes the terminology "independent" quite reasonable: Information about some members of $mathcal F$ tells you nothing about other members.
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Let $mathcal F$ be a family of subsets of some set $X$, and suppose we play the following game. I pick some $Ainmathcal F$ and tell you which $A$ it is; I tell you that I'm thinking of some $xin X$ but I don't tell you which $x$ it is; you're supposed to guess whether $xin A$. Before you make your guess, you're allowed to ask me questions "Is $xin B$?" for any $Binmathcal F$ except that $B$ can't be $A$ (i.e., you can't ask me the question you're supposed to guess the answer to). You can ask lots of these questions, but at some point (after finitely many of your questions have been answered) you have to give your answer, either $xin A$ or $xnotin A$. At that point, if I can find an $xin X$ for which all my answers to your questions are correct but your decision about $xin A$ is incorrect, then I win; otherwise, you win.
To say that $mathcal F$ is an independent family is equivalent to saying that I can answer your questions completely arbitrarily (flipping a coin or just saying whatever comes to mind) as long as, if you ask the same question twice then I give the same answer both times, and then, whatever answer you decide about $xin A$, I can still find an $x$ to win the game.
In other words, no matter how much information you collect from me about $xin B$ for various (finitely many) $Binscr F$, it doesn't help you determine whether $xin A$; I can always find an $x$ consistent with my answers yet violating yours.
I think this makes the terminology "independent" quite reasonable: Information about some members of $mathcal F$ tells you nothing about other members.
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
add a comment |
up vote
0
down vote
Let $mathcal F$ be a family of subsets of some set $X$, and suppose we play the following game. I pick some $Ainmathcal F$ and tell you which $A$ it is; I tell you that I'm thinking of some $xin X$ but I don't tell you which $x$ it is; you're supposed to guess whether $xin A$. Before you make your guess, you're allowed to ask me questions "Is $xin B$?" for any $Binmathcal F$ except that $B$ can't be $A$ (i.e., you can't ask me the question you're supposed to guess the answer to). You can ask lots of these questions, but at some point (after finitely many of your questions have been answered) you have to give your answer, either $xin A$ or $xnotin A$. At that point, if I can find an $xin X$ for which all my answers to your questions are correct but your decision about $xin A$ is incorrect, then I win; otherwise, you win.
To say that $mathcal F$ is an independent family is equivalent to saying that I can answer your questions completely arbitrarily (flipping a coin or just saying whatever comes to mind) as long as, if you ask the same question twice then I give the same answer both times, and then, whatever answer you decide about $xin A$, I can still find an $x$ to win the game.
In other words, no matter how much information you collect from me about $xin B$ for various (finitely many) $Binscr F$, it doesn't help you determine whether $xin A$; I can always find an $x$ consistent with my answers yet violating yours.
I think this makes the terminology "independent" quite reasonable: Information about some members of $mathcal F$ tells you nothing about other members.
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
add a comment |
up vote
0
down vote
up vote
0
down vote
Let $mathcal F$ be a family of subsets of some set $X$, and suppose we play the following game. I pick some $Ainmathcal F$ and tell you which $A$ it is; I tell you that I'm thinking of some $xin X$ but I don't tell you which $x$ it is; you're supposed to guess whether $xin A$. Before you make your guess, you're allowed to ask me questions "Is $xin B$?" for any $Binmathcal F$ except that $B$ can't be $A$ (i.e., you can't ask me the question you're supposed to guess the answer to). You can ask lots of these questions, but at some point (after finitely many of your questions have been answered) you have to give your answer, either $xin A$ or $xnotin A$. At that point, if I can find an $xin X$ for which all my answers to your questions are correct but your decision about $xin A$ is incorrect, then I win; otherwise, you win.
To say that $mathcal F$ is an independent family is equivalent to saying that I can answer your questions completely arbitrarily (flipping a coin or just saying whatever comes to mind) as long as, if you ask the same question twice then I give the same answer both times, and then, whatever answer you decide about $xin A$, I can still find an $x$ to win the game.
In other words, no matter how much information you collect from me about $xin B$ for various (finitely many) $Binscr F$, it doesn't help you determine whether $xin A$; I can always find an $x$ consistent with my answers yet violating yours.
I think this makes the terminology "independent" quite reasonable: Information about some members of $mathcal F$ tells you nothing about other members.
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
Let $mathcal F$ be a family of subsets of some set $X$, and suppose we play the following game. I pick some $Ainmathcal F$ and tell you which $A$ it is; I tell you that I'm thinking of some $xin X$ but I don't tell you which $x$ it is; you're supposed to guess whether $xin A$. Before you make your guess, you're allowed to ask me questions "Is $xin B$?" for any $Binmathcal F$ except that $B$ can't be $A$ (i.e., you can't ask me the question you're supposed to guess the answer to). You can ask lots of these questions, but at some point (after finitely many of your questions have been answered) you have to give your answer, either $xin A$ or $xnotin A$. At that point, if I can find an $xin X$ for which all my answers to your questions are correct but your decision about $xin A$ is incorrect, then I win; otherwise, you win.
To say that $mathcal F$ is an independent family is equivalent to saying that I can answer your questions completely arbitrarily (flipping a coin or just saying whatever comes to mind) as long as, if you ask the same question twice then I give the same answer both times, and then, whatever answer you decide about $xin A$, I can still find an $x$ to win the game.
In other words, no matter how much information you collect from me about $xin B$ for various (finitely many) $Binscr F$, it doesn't help you determine whether $xin A$; I can always find an $x$ consistent with my answers yet violating yours.
I think this makes the terminology "independent" quite reasonable: Information about some members of $mathcal F$ tells you nothing about other members.
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
answered Nov 19 at 1:51
Andreas Blass
48.8k350106
48.8k350106
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
add a comment |
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Oh interesting. Let me see if I understand.
– kevin roberge
Nov 19 at 14:13
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $mathscr{F}$ and not in the subsets of $mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine?
– kevin roberge
Nov 19 at 14:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game.
– Andreas Blass
Nov 19 at 15:29
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003617%2fbasic-properties-and-intuition-behind-an-independent-family-of-subsets-of-a-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Considered hiw many untrafilters there is on a finite set.
– William Elliot
Nov 19 at 0:29
I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets?
– kevin roberge
Nov 19 at 14:01