Confused about negation within a proof

Question

I wanted to come up with a proof using contrapositive, so I needed the negation of the following: "one of x and y is congruent to 1 modulo 6 while the other is congruent to 5 modulo 6."

I interpreted this statement as being the same as "one of x and y is congruent to 1 modulo 6 and the other is congruent to 5 modulo 6", so the negation I got was "one of x and y is not congruent to 1 modulo 6 or the other is not congruent to 5 modulo 6".

Turns out the negation is "one of x and y is not congruent to 1 or 5 modulo 6."

I'm not seeing it. Please help me understand.

Answer 1

Without loss of generality, we may assume your statement is, in effect,

$$x \equiv 1 \pmod 6 \land y \equiv 5 \pmod 6$$

(This is equivalent since, in the end, the assignments of $x,y$ are arbitrary since they're not further defined outside of these properties.) Then why is the negation of this

$$x \not \equiv 1 \pmod 6 \lor y \not \equiv 5 \pmod 6$$

instead of your suggestion?

---

The issue lies, fundamentally, with the logical "and" ($\land$) operator. If $P \land Q$ is true, that means $P,Q$ individually are both true. What would be the negation of that, then? It would be whenever $P \land Q$ is false, i.e. one of the following holds:

• $P$ false, $Q$ true
• $P$ true, $Q$ false
• $P,Q$ both false

This can be summarized more succinctly as "at least one of $P,Q$ are false," or perhaps even more clearly as "$P$ is false or $Q$ is false."

Symbolically, this would be notated $\neg (P \land Q) = \neg P \lor \neg Q$ -- the negation of an "and" statement, in other words, is one of the comprising statements of it is false.

Answer 2

they are both wrong.

I see the statement as, the set of congruences of the set $x,y$ is the set $1,5$.

The negation of that is, the set of congruences of the set $x,y$ is not the set $1,5$.

So they could both be congruent to $1$, the could both be congruent to $5$, one could be congruent to $1$ and the other to anything else but $5$, one could be congruent to $5$ and the other to anything else but $1$, or they could both be congruent to something other than $1$ or $5$.