understanding proof by contradiction with example

Question

I'm rather new to the concept of proving and I am currently thinking about the proof by contradiction. I will give an example later on.

If we, lets say, have a set $M$ and we want to show that $\forall x\in M \lnot P(x)$ where $P(x)$ is some property. Would my following thought be sufficient?

"We prove the this statement by contradiction by assuming that $\forall x\in M,\;P(x)$ holds. Then we give an counter example, so now it clearly doesn't hold for all x."

Real example: Let's try to prove that the relation "<" is not reflexive.Let $x \in \mathbb{R}$ We assume that it is reflexive but we can clearly see that x < x is not the case so we're done?

Answer 1

"We prove the this statement $\big( \forall x \in M(\lnot P(x)\big)$ by contradiction by assuming that $\forall x\in M,\;P(x)$ holds. Then we give an counter example, so now it clearly doesn't hold for all x."

No. That's not correct.

---

$$\forall x \in M\;(\lnot P(x))\equiv \lnot \exists x \in M\;(P(x))$$ So the negation of the statement (for the sake of contradiction), is given by $$\exists x\in M\;(P(x))$$

---

You might want to think about using an example of a predicate P that involves only one argument: For example, let M represent the set of all even numbers. Let $P(x)$ denote "x is odd."

Then certainly, $$\forall x\in M(\lnot P(x)),$$ which is equivalent to $$\lnot \exists x\in M (P(x))$$ Which says: There are no even numbers that are odd." If you want to prove this by assuming its negation, then you would assume: "There exists an even number that is odd." $$\exists x \in M\;(P(x)).$$ It is easily seen that this statement arrives at a contradiction, by definition of an even/odd number.

---

Your example is not appropriate for a predicate with $x$ as its only argument. If we use $P(x, y)$ to mean "$\;x\lt y,$" then reflexivity would require that $\forall x \in M (P(x, x))$.

(Note that reflexivity is not a property of or assigned to $x \in M$. It is a property of the relation $P$ on $M$, which here is a total order relation given by <.)

The relation $P$, to be reflexive, demands that $\forall x \in M(P(x, x)).$ But clearly, given $P(x, x) = x \lt x$, we are correct to say that $\forall x \in M(\lnot P(x, x)),$ precisely because a number x can not be less than itself.

To force a contradiction, you'd need to assume that, $\exists x \in M(P(x,x)).$ "There is an element x in M such that $x \lt x$". Which is absurd, because there is no real, rational or irrational nor any integer

---

Answer 2

No you showed that $\forall x \in M: P(x)$ isn't true, which equivalent to $\neg\forall x \in M :P(x)$ is true. Mind that the negation works as the following example shows $$ \neg\forall x \in M :P(x) = \exists x\in M : \neg P(x) $$

Answer 3

This not correct.

The statement "$\forall x \in M$ $\lnot P(x)$" says, in plainer language, "for all $x \in M$ the statement $P(x)$ is false".

What you have proposed is to find one example of an $x \in M$ which makes the statement $P(x)$ false, which is much weaker than what you have to prove. Even though $P(x)$ might be true for the example of $x$ that you carefully picked, there might be a different example of $x \in M$ which makes the statement $P(x)$ true.

Instead, what you have to do to prove that statement is every example of an $x \in M$ makes the statement $P(x)$ false.

Now, on to your example. The statement "$<$ is not reflexive" does not match the original format "$\forall x \in M \lnot P(x)$". Instead, it matches the format "$\lnot\bigl( \forall x \in M, P(x)\bigr)$", because "$<$ is reflexive" means "$\forall x \in \mathbb{R}$, $x<x$". So "$<$ is not reflexive" means "$\lnot \bigl( <$ is reflexive$\bigr)$" which means $$\lnot \bigl( \forall x \in \mathbb{R}, x<x \bigr) $$ You have to be very careful about the placement and order of these logical symbols.