Different ways of proving that two sets are equal - MathOverflow

Different ways of proving that two sets are equal

2010-02-26T18:09:42Z

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 ?

Answer by Pete L. Clark for Different ways of proving that two sets are equal

2010-02-26T18:33:17Z

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

Answer by Gerald Edgar for Different ways of proving that two sets are equal

2010-02-26T18:38:40Z

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

Answer by Ilya Grigoriev for Different ways of proving that two sets are equal

2010-02-26T18:54:47Z

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.

Answer by Tony Huynh for Different ways of proving that two sets are equal

2010-02-26T19:08:50Z

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

Answer by Qiaochu Yuan for Different ways of proving that two sets are equal

2010-02-26T19:41:40Z

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.

Answer by Akhil Mathew for Different ways of proving that two sets are equal

2010-02-26T21:07:00Z

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

Answer by gowers for Different ways of proving that two sets are equal

2010-02-26T21:52:50Z

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

Answer by unknown (google) for Different ways of proving that two sets are equal

2010-02-26T23:26:12Z

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

Answer by Igor Pak for Different ways of proving that two sets are equal

2010-02-27T00:56:30Z

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

Answer by Nate Eldredge for Different ways of proving that two sets are equal

2010-04-22T15:02:56Z

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.

Answer by Mark Meckes for Different ways of proving that two sets are equal

2010-04-22T15:20:14Z

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.