A property of an ultrafilter

The name of the pictureThe name of the pictureThe name of the pictureClash 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$.










share|cite|improve this question

























    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$.










    share|cite|improve this question























      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$.










      share|cite|improve this question













      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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 2 hours ago









      Taras Banakh

      14.1k12882




      14.1k12882




















          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$.






          share|cite|improve this answer




















          • So nice argument! Thank you for the help.
            – Taras Banakh
            10 mins ago

















          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.






          share|cite|improve this answer


















          • 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










          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "504"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













           

          draft saved


          draft discarded


















          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






























          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$.






          share|cite|improve this answer




















          • So nice argument! Thank you for the help.
            – Taras Banakh
            10 mins ago














          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$.






          share|cite|improve this answer




















          • So nice argument! Thank you for the help.
            – Taras Banakh
            10 mins ago












          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$.






          share|cite|improve this answer












          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$.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 19 mins ago









          Nik Weaver

          18.9k145117




          18.9k145117











          • 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




          So nice argument! Thank you for the help.
          – Taras Banakh
          10 mins ago










          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.






          share|cite|improve this answer


















          • 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














          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.






          share|cite|improve this answer


















          • 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












          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.






          share|cite|improve this answer














          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.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          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












          • 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

















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          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













































































          Popular posts from this blog

          How to check contact read email or not when send email to Individual?

          Displaying single band from multi-band raster using QGIS

          How many registers does an x86_64 CPU actually have?