User dave doty - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T11:13:20Z http://mathoverflow.net/feeds/user/9961 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115104/weakest-hypothesis-needed-for-axiom-of-replacement Weakest Hypothesis Needed for Axiom of Replacement Dave Doty 2012-12-01T20:02:47Z 2012-12-01T21:01:38Z <p>A typical formal statement of the Axiom of Replacement is (leaving out some technical details about extra "parameter variables" that $\phi$ sometimes takes.)</p> <p>$[\forall x,y,z\ (\phi(x,y) \wedge \phi(x,z) \implies y=z)] \implies [\forall X \exists Y \forall y\ (y \in Y \iff (\exists x \in X)\ \phi(x,y))]$.</p> <p>The hypothesis "$\forall x,y,z\ (\phi(x,y) \wedge \phi(x,z) \implies y=z)$" states that the relation $\phi$ defines a function: to each $x$ that is related with some $y$, it is related with only one $y$. One tempting revision to express that hypothesis more succinctly is as $\forall x \exists ! y\ \phi(x,y)$. However, this implies something stronger about $\phi$, namely, that it relates <em>every</em> $x$ to some (unique) $y$, whereas the first formulation allows that for some $x$ and all $y$, $\phi(x,y)$ is false.</p> <p>Can one safely replace the original hypothesis by the revised one, using the following argument? Suppose $\phi$ is not defined for some values of $x$. Then pick some "dummy" $y'$ (such as $\emptyset$) and let $\phi(x,y')$ be true. Then apply the revised axiom to conclude the original version of the axiom, with some technicalities to handle the fact that $Y$ might now include an extra element $y'$. I don't really do set theory, so it's not clear to me exactly what technicalities would pop up and whether they can be handled, possibly using the other axioms.</p> <p>I've read a lot about different ways to define the Axiom of Replacement, and the related Axiom of Collection, but no one ever seems to state the hypothesis in exactly this way, so I'm wondering if something goes wrong if you try to use this formulation of the axiom.</p> <p><strong>(Update: question after here answered in comments)</strong> <strike>For that matter, is the uniqueness of $y$ even required, or could the axiom be revised to $[\forall x \exists y\ \phi(x,y)] \implies [\forall X \exists Y \forall y\ (y \in Y \iff (\exists x \in X)\ \phi(x,y))]$?</strike></p> http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper How many collections of subsets of {1,2,...,n} are closed under the superset operation? Dave Doty 2010-10-11T22:55:18Z 2011-07-17T17:08:19Z <p>Say that I have the set $[n] = \{1,2,...,n\}$ and a collection $\mathcal{C} = \{ S_1, S_2, ..., S_k \}$ of subsets of $[n]$. Say that $\mathcal{C}$ is <em>valid</em> if it is closed under the superset operation; i.e., if $(S \in \mathcal{C} \wedge S \subseteq S' \subseteq [n]) \implies S' \in \mathcal{C}$. How many valid collections $\mathcal{C}$ are there, as a function of $n$?</p> <p>Without the requirement to be closed under superset, the question is easier. There are $2^n$ subsets of $[n]$, and so there are $2^{2^n}$ ways to choose which of them belong to the collection. But not all collections are valid; for instance, if $n=2$, the valid collections are</p> <p>$\mathcal{C} = \{ \emptyset, \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 1 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 2 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 1,2 \} \}$, and</p> <p>$\mathcal{C} = \{ \}$.</p> <p>So rather than the answer being $2^{2^2} = 16$, there are only 6 valid collections.</p> <p>Thank you in advance.</p> http://mathoverflow.net/questions/115104/weakest-hypothesis-needed-for-axiom-of-replacement/115111#115111 Comment by Dave Doty Dave Doty 2012-12-01T21:29:34Z 2012-12-01T21:29:34Z Thank you! That is helpful. http://mathoverflow.net/questions/115104/weakest-hypothesis-needed-for-axiom-of-replacement Comment by Dave Doty Dave Doty 2012-12-01T20:29:22Z 2012-12-01T20:29:22Z Joel: thanks, I see. I'm revising the question because I'm still interested in the question if y is required to be unique. Andres: Thanks for that link! http://mathoverflow.net/questions/107929/curves-that-do-not-get-arbitrarily-close-to-the-x-axis Comment by Dave Doty Dave Doty 2012-09-24T20:51:33Z 2012-09-24T20:51:33Z Theo: I want to reduce the number of x-intercepts of one curve c1 without causing it to cross another c2. So if c1 has two adjacent x-intercepts x1 &lt; x2 and is positive along the curve between them, and c2 has no x-intercepts between x1 and x2, then I want to modify c1 to be a straight horizontal line at distance epsilon under the x-axis. So I needed that if c2 does not hit the x-axis between x1 and x2, then it is far enough away that it also doesn't hit the line x=epsilon in that region. The curves are polygonal so this is easy to prove, but I wanted to state the theorem more generally. http://mathoverflow.net/questions/107929/curves-that-do-not-get-arbitrarily-close-to-the-x-axis Comment by Dave Doty Dave Doty 2012-09-24T20:46:28Z 2012-09-24T20:46:28Z Thank you for the answers. Realizing that the curve defines a compact set is very useful, it seems. Sergei: can I ask why the question was closed as &quot;off-topic&quot;? It seems it is on-topic, but simply easy for experts in the area. This seems to me to be one of the main purposes of Mathoverflow, to help non-experts seek help from experts who often know the answer right away. Is there a reason the question was closed rather than simply being answered? http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper/41845#41845 Comment by Dave Doty Dave Doty 2010-11-16T07:56:58Z 2010-11-16T07:56:58Z Thanks again Aaron. Here is the paper that motivated this question: <a href="http://arxiv.org/abs/1011.3493" rel="nofollow">arxiv.org/abs/1011.3493</a>. The relevant part is Proposition 4.3. I added an acknowledgement to you for your help. http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper/41845#41845 Comment by Dave Doty Dave Doty 2010-10-11T23:44:49Z 2010-10-11T23:44:49Z Sorry, the last comment did not parse the link correctly: they are called Dedekind numbers, <a href="http://en.wikipedia.org/wiki/Dedekind_number" rel="nofollow">en.wikipedia.org/wiki/Dedekind_number</a> http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper/41845#41845 Comment by Dave Doty Dave Doty 2010-10-11T23:43:20Z 2010-10-11T23:43:20Z It seems these are called &lt;a href=&quot;<a href="http://en.wikipedia.org/wiki/Dedekind_number&quot;&gt;Dedekind" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> numbers&lt;/a&gt;. Thank you!