Different ways of proving that two sets are equal - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T20:22:14Z http://mathoverflow.net/feeds/question/16534 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal Different ways of proving that two sets are equal Suresh Venkat 2010-02-26T18:09:42Z 2011-08-08T21:08:35Z <p><em>I'm not sure if this is a soft question, or should be community wiki.</em> </p> <p>I was explaining to a student how to prove that two sets were equal using what I called the 'oldest trick in the book': to show that $A = B$, prove $A \subseteq B$ and $B \subseteq A$. This got me thinking: what <strong>are</strong> the other ways of showing that two sets are equal. There's of course the bijection method (establish a 1-1 onto correspondence), but I couldn't think of others off the top of my head. </p> <p>Are there many more general-ish techniques for proving two sets equal ? </p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16536#16536 Answer by Pete L. Clark for Different ways of proving that two sets are equal Pete L. Clark 2010-02-26T18:33:17Z 2010-04-22T12:31:53Z <p>If $A$ and $B$ are both finite, it suffices to show:</p> <p>(i) $A \subseteq B$ and (ii) <code>$\# A \geq \#B$</code>.</p> <p>There are variations on this when the sets have more structure e.g.:</p> <p>If $A$ and $B$ are finite-dimensional vector spaces over a field $K$, it suffices to show that one is contained in the other and that they have the same dimension. </p> <p>For "naked" infinite sets, I am tempted to say that I know of no way to show equality other than directly from the definition: every element of $A$ is an element of $B$ and conversely. So I'm interested to hear what others have to say. [Edit: I feel that Qiaochu's answer successfully meets this challenge: it is another way to show equality, and it is both obvious and useful.]</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16538#16538 Answer by Gerald Edgar for Different ways of proving that two sets are equal Gerald Edgar 2010-02-26T18:38:40Z 2010-02-26T18:38:40Z <p>To show that a set $A$ is equal to $\mathbb{N}$ use the amazing method of <em>mathematical induction</em>.</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16542#16542 Answer by Ilya Grigoriev for Different ways of proving that two sets are equal Ilya Grigoriev 2010-02-26T18:54:47Z 2010-02-26T18:54:47Z <p>This won't work for bare sets, but for most things with additional structure (groups, modules, etc.), the first isomorphism theorem is often used to show that some set (with structure) is equal to a quotient of other sets.</p> <p>For sets with <em>G</em>-action, the orbit-stabilizer theorem is used for the same purpose.</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16545#16545 Answer by Tony Huynh for Different ways of proving that two sets are equal Tony Huynh 2010-02-26T19:08:50Z 2010-02-26T21:09:35Z <p>To expand on Pete's comment where we have additional structure, in any context where <em>duality</em> makes sense, to show that $A=B$, it suffices to show that they both have the same duals. Of course this does not answer the question, since we still need a way of showing that their duals are equal, but sometimes this may be easier. Examples of duals are when $A$ and $B$ are both subsets of a common universe $U$ and the dual is just the complement. Or, if $A$ and $B$ are both subspaces of $R^n$ and the dual is the orthogonal complement. </p> <p><strong>Edit:</strong> Although I'm not an expert, I'm guessing there are examples coming from topological structure as well. For example, to show that a subset $A$ of a topological space $X$ is equal to $X$, it suffices to show that $A$ is closed and contains a dense subset of $X$. </p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16549#16549 Answer by Qiaochu Yuan for Different ways of proving that two sets are equal Qiaochu Yuan 2010-02-26T19:41:40Z 2010-02-26T19:41:40Z <p>This is an extremely general answer, but often it's easiest to show that there exists some other set (or structured set) $C$ such that $A = C$ and $B = C$. For example, one way to show that two vector spaces are the same is to exhibit a common basis of both.</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16555#16555 Answer by Akhil Mathew for Different ways of proving that two sets are equal Akhil Mathew 2010-02-26T21:07:00Z 2010-02-26T21:12:37Z <p>One may show that $A$ is dense in $B$ and $A$ closed. For instance, if $A \subset \mathbb{C}^n$ is an algebraic variety that contains $\mathbb{Z}^n$, it is all of $\mathbb{C}^n$ (of course, I am using the Zariski topology here). </p> <p>One way of showing this density is to use the Hahn-Banach theorem (an example is the Muntz-Szasz theorem, cf. <a href="http://deltaepsilons.wordpress.com/2009/11/28/the-hahn-banach-theorem-and-two-applications/" rel="nofollow">here</a>, and there are other such applications such as the Stone-Weierstrass theorem that can be proved similarly). If every continuous linear functional vanishing on $B$ vanishes on $A$ and $A,B$ are linear subspaces of a Banach space, then $A$ is dense in $B$.</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16558#16558 Answer by gowers for Different ways of proving that two sets are equal gowers 2010-02-26T21:52:50Z 2010-02-26T22:20:36Z <p>In a similar spirit to the dense+closed answer, there are some proofs where to show that a subset of a connected space is the whole space, one shows that it is non-empty, open and closed. An example of this is the proof that a connected open subset of $\mathbb{R}^n$ is path-connected (the set of points you can meet from x is open and non-empty and its complement is open). Another is the proof of the identity theorem in complex analysis (the set where your two analytic functions have the same Taylor expansion locally and therefore agree locally is obviously open, and it is also closed because the set of points where the nth derivatives agree is obviously closed, and the set where they have the same Taylor expansion is therefore an intersection of closed sets).</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16564#16564 Answer by unknown (google) for Different ways of proving that two sets are equal unknown (google) 2010-02-26T23:26:12Z 2010-02-26T23:26:12Z <p>To show that two sets are equal, show that both satisfy a condition $P$ for which it is known that there exists a unique set $X$ with $P(X)$. What I really have in mind here is to use the uniqueness part of universality. For example, if two arrows to a limit (in some category) have the same compositions with the limiting cones, then they are the same. We can think of these arrows as sets (e.g., in ZFC without urelements), and so we proved that two sets are the same. (In any case, we can restrict attention to $\mathbf{Set}$ where arrows (function) are sets.) </p> <p>As another example, if a functor $V:A\to X$ is known to creates $J$-limits, and two cones $\nu$ and $\tau$ in $A$ happen to satisfy $V\nu=V\tau=$ a limiting cone in $X$, then $\nu=\tau$. </p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/16569#16569 Answer by Igor Pak for Different ways of proving that two sets are equal Igor Pak 2010-02-27T00:56:30Z 2010-02-27T00:56:30Z <p>In bijective combinatorics, there is another method. Say, both $A$ and $B$ are subsets of a large set $X$ which is split into a "positive" and a "negative" part: $X = X_+ \sqcup X_-$, such that $A,B \subset X_+$. Suppose $\alpha, \beta$ are two sign-reversing involutions on $X$, i.e. such that $\alpha(X_-) \subset X_+$ and $\beta(X_-) \subset X_+$. Suppose further that $A$ is the set of fixed points of $\alpha$ and $B$ is the set of fixed points of $\beta$. Then, obviously, $|A| = |X_+|-|X_-| = |B|$. Moreover, the action of the infinite dihedral group $\ D_\infty = \langle \alpha,\beta\rangle \$ on $X$ gives a bijection between $A$ and $B$ (take $a \to b$ if they lie in the same orbit). </p> <p>This idea is known as the "Garsia-Milne involution principle" and can be used to construct bijections proving various partition identities (see <a href="http://www.math.ucla.edu/~pak/papers/psurvey.pdf" rel="nofollow">here</a>). Other places where a version of this principle comes up is <a href="http://tinyurl.com/yzcepv8" rel="nofollow">this</a> Zagier's famous proof of Fermat's theorem on sums of two squares, and Doyle &amp; Conway's famous "Division by three" <a href="http://www.math.dartmouth.edu/~doyle/docs/three/three.pdf" rel="nofollow">paper</a> (read the "division by 2" section first to understand the connection). </p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/22197#22197 Answer by Nate Eldredge for Different ways of proving that two sets are equal Nate Eldredge 2010-04-22T15:02:56Z 2010-04-22T15:02:56Z <p>In measure theory, one often wants to show some property $P$ is true of all the sets in some $\sigma$-algebra $\mathcal{B}$. So one sets $\mathcal{A}$ to be all those sets in $\mathcal{B}$ for which $P$ holds, and tries to show $\mathcal{A} = \mathcal{B}$. $\mathcal{A} \subset \mathcal{B}$ is obvious. The reverse is hard to show directly because the sets in $\mathcal{B}$ are usually hard to characterize explicitly. So one often uses something like the Dynkin $\pi$-$\lambda$ theorem. One finds a subset $\mathcal{C} \subset \mathcal{A}$ which is closed under intersection (a $\pi$-system) and with $\sigma(\mathcal{C}) = \mathcal{B}$. Then one shows that $\mathcal{A}$ is a $\lambda$-system (closed under set subtraction and increasing countable union), usually by showing that these operations preserve the property $P$. Using the theorem, one concludes that $\mathcal{B} \subset \mathcal{A}$.</p> <p>This is really in the spirit of the "closed and dense" technique from topology / analysis.</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal/22198#22198 Answer by Mark Meckes for Different ways of proving that two sets are equal Mark Meckes 2010-04-22T15:20:14Z 2010-04-22T16:39:29Z <p>Here's a generalization of Pete's answer. If $A$ and $B$ are subsets of some measure space with $A \subseteq B$ and $\mu(A) \ge \mu(B)$, then $A$ and $B$ are equal up to a set of measure 0, which is good enough for some purposes.</p>