I had to prove that if $A$ and $B$ are both finite sets, then so is $A \cap B$ finite. I solved it in a different way (using induction) and the grader said "that is not correct at all", I am really confused, I actually got help from this site with this question and it seemed correct!
This is how it went:
Let $A$ and $B$ both finite sets. If one of them is empty, $A \cap B$ is empty and thus finite.
Let $f$ be a one-to-one function and onto $A$ to: $\{1,2, \dots ,n\}$ and $g$ one-to-one and onto $B$ to $\{1,2, \dots, m\}$
I will prove that $A \cap B$ is finite using induction.
if $n=1$ then $A = \{f^{-1}(1)\}$ and thus $A \cap B = \emptyset$ OR $A \cap B = A$ and thus finite.
Assuming that $A \cap B$ is finite for $n=k$
We will try and prove this is correct for $n = k+1$
so:
$A \cap B = (\{f^{-1}(1), \dots , f^{-1}(k)\} \cap B) \cup (\{f^{-1}(k+1)\} \cap B)$
Because $\{f^{-1}(1) , \dots , f^{-1}(k)\} \cap B$ is finite (The assumption of the induction) and we have $\{f^{-1}(k+1)\} \cap B$ which is finite (At most $1$ element)
So: $A \cap B$ is finite.
Where is the error in this solution? Is it not correct and thus the grader is right about saying "not correct"?
If it is correct, what should I tell him? how can I explain this more so that he will understand..
I am very confused. Thank you very much!
Thank you!