16
$\begingroup$

I'm not sure if this is a soft question, or should be community wiki.

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

Are there many more general-ish techniques for proving two sets equal ?

$\endgroup$
4
  • 6
    $\begingroup$ Showing two sets are equal is a different thing than showing there is a bijection. Do you really mean the former or the latter? $\endgroup$ Feb 26, 2010 at 18:11
  • $\begingroup$ ah fair enough. I really mean the former. although you can use a bijection to prove equality $\endgroup$ Feb 26, 2010 at 18:26
  • $\begingroup$ I was debating this. I looked over the meta.MO link on CW, and thought that Andrew Stacey's comment on direct vs indirect experience was relevant here, in that people are sharing direct experiences of their techniques, rather than just citing references. But I'm fine either way. $\endgroup$ Feb 26, 2010 at 20:19
  • $\begingroup$ The only way to use a bijection to show 2 sets are equal is to use the identity map between them.So I don't really see how this is different from using containment. $\endgroup$ Apr 22, 2010 at 17:44

11 Answers 11

23
$\begingroup$

To show that a set $A$ is equal to $\mathbb{N}$ use the amazing method of mathematical induction.

$\endgroup$
1
  • 6
    $\begingroup$ And similarly, you can use transfinite induction to test equality of a subset of any well-ordered set. $\endgroup$ Feb 26, 2010 at 18:51
20
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ In PDE, this is known as the continuity method. $\endgroup$
    – Terry Tao
    Feb 26, 2010 at 21:56
  • 5
    $\begingroup$ Another example of this is when $U$ is an open subset containing the identity element of a connected topological group, then $U$ generates the group. $\endgroup$ Feb 26, 2010 at 22:08
19
$\begingroup$

If $A$ and $B$ are both finite, it suffices to show:

(i) $A \subseteq B$ and (ii) $\# A \geq \#B$.

There are variations on this when the sets have more structure e.g.:

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.

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

$\endgroup$
2
  • 1
    $\begingroup$ I like the vector space example. that's the kind of answer I was looking for ! $\endgroup$ Feb 26, 2010 at 18:36
  • 7
    $\begingroup$ In fact, you only need #A >= #B above. $\endgroup$ Feb 26, 2010 at 23:15
15
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ +1: OK, you win. I guess you could even show $A = C_1 = C_2 = \ldots = C_N = B$. Or the same with a well-ordered index set of $C_i$'s (with a maximal element) and a transfinite induction argument... $\endgroup$ Feb 26, 2010 at 21:17
  • 5
    $\begingroup$ I should mention a somewhat sophisticated example of this technique so it doesn't sound like too much of a tautology: one proves identities between modular forms by showing that they span the same subspace of the space of modular forms of some weight and level, and one way to do that is to verify that the two spans are both equal to the subspace of modular forms satisfying such-and-such properties at certain points. The same kind of technique is behind computer algebra methods to prove identities between holonomic generating functions. $\endgroup$ Feb 26, 2010 at 21:25
  • 9
    $\begingroup$ One runs this principle in reverse for combinatorics: Given a single $C$, describe it first as $A$, then as $B$, and count $A$ and $B$ separately to deduce (hopefully) a combinatorial identity. $\endgroup$
    – LSpice
    Feb 26, 2010 at 22:19
13
$\begingroup$

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

One way of showing this density is to use the Hahn-Banach theorem (an example is the Muntz-Szasz theorem, cf. here, 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$.

$\endgroup$
8
$\begingroup$

To expand on Pete's comment where we have additional structure, in any context where duality 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.

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

$\endgroup$
4
  • 1
    $\begingroup$ This isn't true if A and B are Banach spaces. You need a context where duality is an involution. $\endgroup$ Feb 26, 2010 at 19:27
  • $\begingroup$ Agreed. I should have made this explicit in my non-technical definition of duality. In my defense, both my cited examples are involutions. $\endgroup$
    – Tony Huynh
    Feb 26, 2010 at 20:44
  • $\begingroup$ I guess Akhil and I answered at the same time, so see his answer and ignore my edit. $\endgroup$
    – Tony Huynh
    Feb 26, 2010 at 21:12
  • $\begingroup$ And sometimes you show that vector subspaces $A,B$ of $V$ are the same by proving $A \subseteq B$ and $A^* \subseteq B^*$. $\endgroup$ Aug 9, 2011 at 0:23
7
$\begingroup$

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.

For sets with G-action, the orbit-stabilizer theorem is used for the same purpose.

$\endgroup$
1
  • 1
    $\begingroup$ A more impressive example in my opinion: kth roots are unique in the class of finite L-structures. By a homorphism counting argument, Lovasz shows that if A^k and B^k are isomorphic as L-structures (on a finite set) then A is isomorphic to B as L-structures. Gerhard "Ask Me About System Design" Paseman, 2010.02.26 $\endgroup$ Feb 27, 2010 at 0:17
6
$\begingroup$

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

This idea is known as the "Garsia-Milne involution principle" and can be used to construct bijections proving various partition identities (see here). Other places where a version of this principle comes up is this Zagier's famous proof of Fermat's theorem on sums of two squares, and Doyle & Conway's famous "Division by three" paper (read the "division by 2" section first to understand the connection).

$\endgroup$
3
$\begingroup$

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

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

$\endgroup$
1
$\begingroup$

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

This is really in the spirit of the "closed and dense" technique from topology / analysis.

$\endgroup$
1
  • $\begingroup$ Uh,isn't this just a convoluted way of doing the standard containment proof? $\endgroup$ Apr 22, 2010 at 22:26
0
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ Wow! I didn't know $(-1,1)$ and $(-1,0)\cup(0,1)$ were equal! Thanks! $\endgroup$ Apr 22, 2010 at 15:48
  • 4
    $\begingroup$ You're welcome; it's a surprisingly useful fact. I'm not sure what I was thinking there, but I'll edit my answer into something that's actually true. $\endgroup$ Apr 22, 2010 at 16:37
  • $\begingroup$ I remember now what I was thinking in my original answer: I meant for A to be closed, not open. $\endgroup$ Apr 22, 2010 at 16:44
  • 3
    $\begingroup$ But I already used your result to prove the Riemann Hypothesis. Now I have to send in a correction for that paper... $\endgroup$ Apr 22, 2010 at 17:08
  • 1
    $\begingroup$ Are you sure you should do that? mathoverflow.net/questions/22071/… $\endgroup$ Apr 22, 2010 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.