A property of an ultrafilter
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
Let $mathcal U$ be a free ultrafilter on a set $X$. For $ninmathbb N$ let $mathcal F$ be a family of $n$-element subsets of $X$ such that $bigcupmathcal Finmathcal U$.
Question. Is there a set $Uinmathcal U$ and a subfamily $mathcal Esubsetmathcal F$ such that $bigcupmathcal Einmathcal U$ and $|Ucap E|=1$ for every $Einmathcal E$?
I do not know the answer even for $n=2$ and countable set $X$.
set-theory ultrafilters
add a comment |Â
up vote
5
down vote
favorite
Let $mathcal U$ be a free ultrafilter on a set $X$. For $ninmathbb N$ let $mathcal F$ be a family of $n$-element subsets of $X$ such that $bigcupmathcal Finmathcal U$.
Question. Is there a set $Uinmathcal U$ and a subfamily $mathcal Esubsetmathcal F$ such that $bigcupmathcal Einmathcal U$ and $|Ucap E|=1$ for every $Einmathcal E$?
I do not know the answer even for $n=2$ and countable set $X$.
set-theory ultrafilters
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Let $mathcal U$ be a free ultrafilter on a set $X$. For $ninmathbb N$ let $mathcal F$ be a family of $n$-element subsets of $X$ such that $bigcupmathcal Finmathcal U$.
Question. Is there a set $Uinmathcal U$ and a subfamily $mathcal Esubsetmathcal F$ such that $bigcupmathcal Einmathcal U$ and $|Ucap E|=1$ for every $Einmathcal E$?
I do not know the answer even for $n=2$ and countable set $X$.
set-theory ultrafilters
Let $mathcal U$ be a free ultrafilter on a set $X$. For $ninmathbb N$ let $mathcal F$ be a family of $n$-element subsets of $X$ such that $bigcupmathcal Finmathcal U$.
Question. Is there a set $Uinmathcal U$ and a subfamily $mathcal Esubsetmathcal F$ such that $bigcupmathcal Einmathcal U$ and $|Ucap E|=1$ for every $Einmathcal E$?
I do not know the answer even for $n=2$ and countable set $X$.
set-theory ultrafilters
set-theory ultrafilters
asked 2 hours ago
Taras Banakh
14.1k12882
14.1k12882
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Here's a try for $n=3$ which I think generalizes to any $n$.
Well-order $mathcalF$ as $F_alpha$. By discarding any $F_alpha$ which is contained in $bigcup_beta <alpha F_beta$, we can ensure that each $F_alpha$ contains at least one point which is not in any previous $F_beta$, without affecting $U = bigcup F_alpha$.
We can now inductively construct a set $V subset U$ with the property that $|V cap F_alpha|= 1$ or $2$ for all alpha. At each $alpha$ at least one element of $F_alpha$ is new and we can include it or not to ensure the condition for $F_alpha$.
Now $U setminus V$ has the same property, so since $U in mathcalU$, wlog we can assume $V in mathcalU$.
Let $mathcalE_1 subseteq mathcalF$ consist of those $F_alpha$ which intersect $V$ in exactly one point, and let $mathcalE_2$ consist of the other $F_alpha$, which all intersect $V$ in two points. If the union of $mathcalE_1$ belongs to $mathcalU$ then we are done. Otherwise the union of $mathcalE_2$ belongs to $mathcalU$ and this reduces us to the $n=2$ case.
The general reduction turns the problem for an arbitrary $n$ into the same problem for some smaller $n$.
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
add a comment |Â
up vote
2
down vote
For $n=2$ and any $X$: for each $xin cup mathcal F$ fix any edge $(x,y)in mathcal F$ and draw an arrow from $x$ to $y$. Remove all other edges. Remaining edges still have the same union as $mathcalF$, but they form a directed graph with outdegrees at most 1. Such a graph has a proper 3-coloring (it suffices to prove this for finite subgraphs by compactness theorem, and for them the result is well known and easy: remove the vertex with minimal in-degree, it is at most 1, and proceed by induction). One of three colors works.
2
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
2
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
1
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Here's a try for $n=3$ which I think generalizes to any $n$.
Well-order $mathcalF$ as $F_alpha$. By discarding any $F_alpha$ which is contained in $bigcup_beta <alpha F_beta$, we can ensure that each $F_alpha$ contains at least one point which is not in any previous $F_beta$, without affecting $U = bigcup F_alpha$.
We can now inductively construct a set $V subset U$ with the property that $|V cap F_alpha|= 1$ or $2$ for all alpha. At each $alpha$ at least one element of $F_alpha$ is new and we can include it or not to ensure the condition for $F_alpha$.
Now $U setminus V$ has the same property, so since $U in mathcalU$, wlog we can assume $V in mathcalU$.
Let $mathcalE_1 subseteq mathcalF$ consist of those $F_alpha$ which intersect $V$ in exactly one point, and let $mathcalE_2$ consist of the other $F_alpha$, which all intersect $V$ in two points. If the union of $mathcalE_1$ belongs to $mathcalU$ then we are done. Otherwise the union of $mathcalE_2$ belongs to $mathcalU$ and this reduces us to the $n=2$ case.
The general reduction turns the problem for an arbitrary $n$ into the same problem for some smaller $n$.
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
add a comment |Â
up vote
3
down vote
accepted
Here's a try for $n=3$ which I think generalizes to any $n$.
Well-order $mathcalF$ as $F_alpha$. By discarding any $F_alpha$ which is contained in $bigcup_beta <alpha F_beta$, we can ensure that each $F_alpha$ contains at least one point which is not in any previous $F_beta$, without affecting $U = bigcup F_alpha$.
We can now inductively construct a set $V subset U$ with the property that $|V cap F_alpha|= 1$ or $2$ for all alpha. At each $alpha$ at least one element of $F_alpha$ is new and we can include it or not to ensure the condition for $F_alpha$.
Now $U setminus V$ has the same property, so since $U in mathcalU$, wlog we can assume $V in mathcalU$.
Let $mathcalE_1 subseteq mathcalF$ consist of those $F_alpha$ which intersect $V$ in exactly one point, and let $mathcalE_2$ consist of the other $F_alpha$, which all intersect $V$ in two points. If the union of $mathcalE_1$ belongs to $mathcalU$ then we are done. Otherwise the union of $mathcalE_2$ belongs to $mathcalU$ and this reduces us to the $n=2$ case.
The general reduction turns the problem for an arbitrary $n$ into the same problem for some smaller $n$.
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Here's a try for $n=3$ which I think generalizes to any $n$.
Well-order $mathcalF$ as $F_alpha$. By discarding any $F_alpha$ which is contained in $bigcup_beta <alpha F_beta$, we can ensure that each $F_alpha$ contains at least one point which is not in any previous $F_beta$, without affecting $U = bigcup F_alpha$.
We can now inductively construct a set $V subset U$ with the property that $|V cap F_alpha|= 1$ or $2$ for all alpha. At each $alpha$ at least one element of $F_alpha$ is new and we can include it or not to ensure the condition for $F_alpha$.
Now $U setminus V$ has the same property, so since $U in mathcalU$, wlog we can assume $V in mathcalU$.
Let $mathcalE_1 subseteq mathcalF$ consist of those $F_alpha$ which intersect $V$ in exactly one point, and let $mathcalE_2$ consist of the other $F_alpha$, which all intersect $V$ in two points. If the union of $mathcalE_1$ belongs to $mathcalU$ then we are done. Otherwise the union of $mathcalE_2$ belongs to $mathcalU$ and this reduces us to the $n=2$ case.
The general reduction turns the problem for an arbitrary $n$ into the same problem for some smaller $n$.
Here's a try for $n=3$ which I think generalizes to any $n$.
Well-order $mathcalF$ as $F_alpha$. By discarding any $F_alpha$ which is contained in $bigcup_beta <alpha F_beta$, we can ensure that each $F_alpha$ contains at least one point which is not in any previous $F_beta$, without affecting $U = bigcup F_alpha$.
We can now inductively construct a set $V subset U$ with the property that $|V cap F_alpha|= 1$ or $2$ for all alpha. At each $alpha$ at least one element of $F_alpha$ is new and we can include it or not to ensure the condition for $F_alpha$.
Now $U setminus V$ has the same property, so since $U in mathcalU$, wlog we can assume $V in mathcalU$.
Let $mathcalE_1 subseteq mathcalF$ consist of those $F_alpha$ which intersect $V$ in exactly one point, and let $mathcalE_2$ consist of the other $F_alpha$, which all intersect $V$ in two points. If the union of $mathcalE_1$ belongs to $mathcalU$ then we are done. Otherwise the union of $mathcalE_2$ belongs to $mathcalU$ and this reduces us to the $n=2$ case.
The general reduction turns the problem for an arbitrary $n$ into the same problem for some smaller $n$.
answered 19 mins ago
Nik Weaver
18.9k145117
18.9k145117
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
add a comment |Â
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
So nice argument! Thank you for the help.
â Taras Banakh
10 mins ago
add a comment |Â
up vote
2
down vote
For $n=2$ and any $X$: for each $xin cup mathcal F$ fix any edge $(x,y)in mathcal F$ and draw an arrow from $x$ to $y$. Remove all other edges. Remaining edges still have the same union as $mathcalF$, but they form a directed graph with outdegrees at most 1. Such a graph has a proper 3-coloring (it suffices to prove this for finite subgraphs by compactness theorem, and for them the result is well known and easy: remove the vertex with minimal in-degree, it is at most 1, and proceed by induction). One of three colors works.
2
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
2
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
1
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
add a comment |Â
up vote
2
down vote
For $n=2$ and any $X$: for each $xin cup mathcal F$ fix any edge $(x,y)in mathcal F$ and draw an arrow from $x$ to $y$. Remove all other edges. Remaining edges still have the same union as $mathcalF$, but they form a directed graph with outdegrees at most 1. Such a graph has a proper 3-coloring (it suffices to prove this for finite subgraphs by compactness theorem, and for them the result is well known and easy: remove the vertex with minimal in-degree, it is at most 1, and proceed by induction). One of three colors works.
2
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
2
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
1
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
For $n=2$ and any $X$: for each $xin cup mathcal F$ fix any edge $(x,y)in mathcal F$ and draw an arrow from $x$ to $y$. Remove all other edges. Remaining edges still have the same union as $mathcalF$, but they form a directed graph with outdegrees at most 1. Such a graph has a proper 3-coloring (it suffices to prove this for finite subgraphs by compactness theorem, and for them the result is well known and easy: remove the vertex with minimal in-degree, it is at most 1, and proceed by induction). One of three colors works.
For $n=2$ and any $X$: for each $xin cup mathcal F$ fix any edge $(x,y)in mathcal F$ and draw an arrow from $x$ to $y$. Remove all other edges. Remaining edges still have the same union as $mathcalF$, but they form a directed graph with outdegrees at most 1. Such a graph has a proper 3-coloring (it suffices to prove this for finite subgraphs by compactness theorem, and for them the result is well known and easy: remove the vertex with minimal in-degree, it is at most 1, and proceed by induction). One of three colors works.
edited 1 hour ago
answered 1 hour ago
Fedor Petrov
45.5k5109214
45.5k5109214
2
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
2
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
1
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
add a comment |Â
2
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
2
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
1
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
2
2
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
You can alternatively take a covering forest of the graph (which constructs $mathcalE$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color.
â YCor
1 hour ago
2
2
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
It's just a maximal subset of edges with containing no loop.
â YCor
1 hour ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
Thank you for the answers. What about the case $nge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans).
â Taras Banakh
26 mins ago
1
1
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $mathcalE$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $ge 2$. It follows that each of its component is a tree, with one vertex joined to all others.
â YCor
13 mins ago
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f312592%2fa-property-of-an-ultrafilter%23new-answer', 'question_page');
);
Post as a guest
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
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
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