Relations – Full justification

This post was first published on WordPress at
https://explainingmaths.wordpress.com/2021/02/14/relations-full-justification/

Here is another question and answer from my first-year Pure Piazza forum this year.
Question: When a question asks whether a relation is either reflexive, symmetric or transitive and requires full justification for your answer, if for example it's not reflexive, is it enough just to give one counter example of it not being reflexive? Does a counter example count as enough for full justification?
My answer:
Hi,
Suppose that \(R\) is a relation on a set \(S\).
Then, in full, \(R\) is reflexive if and only if the following condition (E1) holds:
(E1)      \(\forall x \in S, x R x\).
To prove such a "for all" statement true, you need to prove it for all \(x \in S\). Such a proof begins with "Let \(x \in S\)" or (if you think \(S\) might be empty) "Suppose that \(x \in S\)."
However, if you want to show that \(R\) isn't reflexive, then you just need one counterexample (that's how you disprove a "for all" statement). So you just need to find one specific \(x \in S\) such that \(x{\mkern 3 mu\not\mkern -5 mu R\mkern 2 mu}x\). Of course, with "full justification" you have to show that your example really does have the properties you claim, though sometimes you can say (if it's true!) that the relevant property of your specific example is "clear".

• You may have similar questions about symmetry and transitivity? If so, let me know!
• That probably answers your question. (A more concise answer would be "Yes".) But read on, if interested, for further information.

Another way to think about this is to work with negations. Negation is an important skill!
[Note: for symmetry and transitivity the negations are harder. This is because "not if" is tricky! "Does not imply", \(\not \Rightarrow\), is not too bad, but needs careful interpretation. In all cases, you are looking for a specific counterexample to disprove the relevant implications. See Lecture Engagement and some of my other posts for more on this.]
Fortunately (E1) is fairly easy to negate mechanically, to get
\(\neg\)(E1)    \(\exists x \in S : x {\mkern 3 mu\not\mkern -5 mu R\mkern 2 mu} x\).
This is a "there exists" statement, so to prove \(\neg\)(E1) you only need to find one value of \(x\) which works. So this time we would be looking for one specific example of \(x \in S\) satisfying the condition \(x{\mkern 3 mu\not\mkern -5 mu R\mkern 2 mu}x\) in order to prove that \(\neg\)(E1) is true. Of course this example is nothing but a counterexample to (E1).
We often say "proof by example is not valid". But what we really mean is that you can't (usually) prove a for all statement true by checking a few examples.
[The exception is when your set only has finitely many elements, when you really can check all the cases separately. This is essentially case by case analysis, or proof by exhaustion (it has lots of different names)]
But "proof by example" is completely correct as a way to prove a there exists statement. You only need one valid example!

It gets more complicated if you have a statement with more than one quantifier, like the true statement
     \(\forall n \in \mathbb{Z}, \exists m \in \mathbb{Z}: m<n.\)
To prove this, you need to prove that the "for all" statement is true for all \(n\), so you start with
    Let \(n \in \mathbb{Z}\).
(We know that \(\mathbb{Z}\) isn't empty!)
Now you have to deduce (from the fact that \(n \in \mathbb{Z}\)) that the "there exists" statement is true. This only needs one example, and the example is allowed to depend on \(n\)! In fact, here the example really does depend on \(n\): the smaller \(n\) is, the smaller \(m\) has to be. This is like \(\varepsilon\) and \(\delta\) in the definition of continuity, and \(\varepsilon\) and \(N\) (or \(n_0\)) in the definition of convergence of sequences.
Fortunately, it is easy to find a suitable example of \(m\) in terms of \(n\). The example \(m=n-1\) is perhaps the most obvious example that proves the "there exists" statement true. (This \(m\) "clearly has the required properties", namely \(m \in \mathbb{Z}\) and \(m<n\).)
Now I always say that a specific example is the most convincing, and that there shouldn't be any variables left in your answer. But when your example depends on \(n\), \(n-1\) is really about as specific as you can get!

One way to think about this is that \(n\) is treated as a constant in the "inner statement" \((\exists m \in \mathbb{Z}: m<n)\) that we are investigating. So \(m=n-1\) really is just one example that proves this "there exists" statement true.

Why do I call it the "inner statement"? Because you can add in some optional brackets to the original statement if you want, to obtain:.

   \(\forall n \in \mathbb{Z}, (\exists m \in \mathbb{Z}: m<n).\)

So this is a bit like working with a double sum (see @59). Instead of an "inner sum" you have an "inner statement" in which the outer variable is treated as constant.

This also relates back to Question 4(a) on the FPM Assessed Coursework, where (with one approach) you needed to prove the true statement
           \(\forall x \in \mathbb{Q}^c, \exists y \in \mathbb{Q}^c: xy \in \mathbb{Q}.\)
Again you need a proof valid for all irrational numbers \(x\), so you have to start with "Let \(x \in \mathbb{Q}^c\)".
Then you have to investigate the "inner statement". This is a "there exists" statement, so you need to find an example \(y\) which has the desired properties and, as usual, \(y\) has to depend on \(x\). This isn't as easy as the example \(m=n-1\) above. But, once you realise that this is what you need to do (and you notice that \(x \neq 0\), because \(x\) is irrational) you may have the idea that you have to set \(y=q/x\) for some rational number \(q\), and, to make it as specific as possible, you should choose a specific rational number \(q\). At the very least, you must specify that \(q \neq 0\), because otherwise \(y\) won't be irrational! The most obvious thing to try is probably \(q=1\), in which case you try \(y=1/x\). Here \(xy=1 \in \mathbb{Q}\) is clear, but the fact that \(1/x\) is irrational is not standard, and needs a proof.

Best wishes,
Dr Feinstein