2
$\begingroup$

Let $A,B$ be finite sets, we'll say the sets are equivalent if $|A\setminus B|=|B\setminus A|$.

Prove with the above definition that if $|A|=|B|$ then $A,B$ are equivalent.

Suppose $|A|=|B|=n$.

If $A\cap B =\emptyset$ then $A\setminus B= A, B\setminus A= B$ and we know they're equivalent.

Move to induction:

Suppose $A\cap B \neq\emptyset$ then there's a least one shared element.

So $|A\setminus B|=n-1=|B\setminus A|$

Suppose that the statement hold for all $k\in \mathbb N: k<n$ shared elements and we'll prove that it holds for $n$ shared elements.

If there are $n$ shared elements then $|A\setminus B|=0=|B\setminus A|$ and we're done.

Notice I didn't use the induction hypothesis, so is there actually no need for induction here? If so how this could be proved any differently?

Is it wrong to use induction without using the induction hypothesis?

$\endgroup$
5
  • 2
    $\begingroup$ You have to note that $A \backslash B = A \backslash (A \cap B)$ and $B \backslash A = B \backslash (B \cap A)$ ; but $\cap$ is "symmetric", thus when we remove from two finite sets $A,B$ having the same number of elements the same set, what we get has necessarily the same number of elements. $\endgroup$ Jan 30, 2015 at 14:01
  • $\begingroup$ @MauroALLEGRANZA is my approach wrong? is not using the induction hypothesis in a proof with induction considered an error? $\endgroup$
    – shinzou
    Jan 30, 2015 at 15:22
  • 1
    $\begingroup$ The flaw in your proof is that you are using $n$ in two ways simultaneously : as the "index" of the induction and as the number of elements of $A$ and $B$. What happens if you choose in the purported induction step and $m \ne n$ ? $\endgroup$ Jan 30, 2015 at 15:32
  • $\begingroup$ @MauroALLEGRANZA but I have to show that the statement holds for every shared amount of elements including the amount of all the elements in the sets. $\endgroup$
    – shinzou
    Jan 30, 2015 at 15:37
  • $\begingroup$ @kuhaku That is exactly the problem: you need to show it for every quantity of shared elements, but you only consider the case where the number of shared elements $k$ is exactly equal to $n$, and blindly assume all the smaller values of $k$ without justification. $\endgroup$
    – Erick Wong
    Nov 15, 2015 at 23:39

1 Answer 1

0
$\begingroup$

We have, $|A|=|A\backslash B|+|A \cap B|$,

and $|B|=|B \backslash A|+|A \cap B|$
if $|A|=|B|$, then $|A\backslash B|+|A \cap B|=|B \backslash A|+|A \cap B|$.

We deduce that $|A\backslash B|=|B \backslash A|$

So, $A$ and $B$ are equivalent.

Ps. The inductive hypothesis is necessary to initialize the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .