Invariant for Gale–Shapley algorithm (Mating Ritual Algorithm)?

Question

I found the following invariant for Mating Ritual algorithm (Lehman, Leighton and Meyer, Mathematics for Computer Science, §6.4) while going through MIT reading material:

Definition. Let $P$ be the predicate: For every woman, $w$, and every man, $m$, if $w$ is crossed off $m$’s list, then $w$ has a suitor whom she prefers over $m$.

Lemma: $P$ is an invariant for The Mating Ritual.

Proof. By induction on the number of days.
Base Case: In the beginning (that is, at the end of day 0), every woman is on every list-no one has been crossed off and so $P$ is vacuously true.
Inductive Step: Assume $P$ is true at the end of day $d$ and let $w$ be a woman that has been crossed off a man $m$’s list by the end of day $d + 1$.
Case 1: $w$ was crossed off $m$’s list on day $d + 1$. Then,$w$ must have a suitor she prefers on day $d + 1$.
Case 2: $w$ was crossed off $m$’s list prior to day $d + 1$. Since $P$ is true at the end of day $d$, this means that $w$ has a suitor she prefers to $m$ on day $d$. She therefore has the same suitor or someone she prefers better at the end of day $d + 1$.

In both cases, P is true at the end of day $d + 1$ and so $P$ must be an invariant

I am unable to understand why the author is considering the Case 2.
In the inductive step first we are assuming the following:

"let $w$ be a woman that has been crossed off a man $m$’s list by the end of day $d + 1$"

And then later in Case 2, We are considering the possibility of $w$ being crossed of the day prior to $d+1$. I find it contradictory. Could you please me understand ?

Answer 1

We want to show that at any point in the algorithm, if it's true that $m$ has crossed off $w$'s name from his list at some point in the past, then $w$ has a suitor she likes better than $m$.

So the assumption at the beginning of the inductive step is simply describing the situation at the end of day $d+1$: we assume that, at this point in the algorithm, $w$'s name appears on $m$'s list with a line through it.

Then the two cases are considering different possibilities for when the crossing out occurred:

1. The current day, day $d+1$, is in fact the day that $w$'s name got crossed out. Then, we should look at how this happened: $w$'s name gets crossed out because she rejects $m$, and $w$ rejects $m$ because she has met a better suitor $m'$.
2. Actually, $w$'s name got crossed out on a previous day (and stays crossed out on day $d+1$, because once a name is crossed out, it stays crossed out forever). In this case, the inductive hypothesis applies, and you have the rest of the proof there.