0

I just wanted to check if this proof works, as I couldn't find anything online. Thanks!

  • A relation is complete: $(_xR_y) \cup (_yR_x)\; \forall x,y \in X $

  • A relation is reflexive: $(_xR_x) \; \forall x \in X $

Proof by contradiction that completeness implies reflexivity

  1. Let's assume R is complete, and not reflexive, i.e. $\exists \, x' \in X, s.t. \; x'\not\mathrel{R} x' $

  2. Then using completeness we must have $(x'Ry) \cup (yRx')$.

  3. Setting $x' = y$ we have our desired contradiction. As we must have $x'Rx'$

My only concern with this is that given the definition of completeness, $(_xR_y) \cup (_yR_x)\; \forall x,y \in X $, are we aloud to assume $x = y$? Thanks!

CormJack
  • 422
  • 1
    Your proof is ok. And yes, $\forall x,y$ includes the case $y=x.$ Direct proof is simpler than by contradiction. – Anne Bauval Dec 18 '22 at 13:25
  • Thank you. @Anne Bauval - I actually tried this initially, but struggled, perhaps because I wasn't sure I could equate x = y. Can you give me a clue. Thanks! – CormJack Dec 18 '22 at 13:29
  • I gave a "clue" ($\forall$ is like that, nothing more) and a link (saying the same). – Anne Bauval Dec 18 '22 at 13:30
  • 1
    Yep, I've just realised. Now I know I can set x = y. It follows immediately, thanks! I'll post it as an answer. The link opens oddly for me, can you confirm the page you are referring too. Cheers! – CormJack Dec 18 '22 at 13:32
  • Can we always set x = y in all definitions that state $\forall x,y \in X$ – CormJack Dec 18 '22 at 13:40
  • 1
    Yes, see my 1st comment. As for the link, it is Statistical Machine Learning: A Unified Framework (by Richard Golden) page 71 (if it does not work, insert this title + Google Books in a Google search) – Anne Bauval Dec 18 '22 at 13:47
  • Apologies @AnneBauval can you tell me which page number you are referring to, because the link sends me to sample pages that won't open. Thanks! – CormJack Dec 18 '22 at 13:51
  • 1
    Ah the rest of that comment didn't load. Appreciate it, have a great day! – CormJack Dec 18 '22 at 13:53

1 Answers1

0

Now I know that I can set $x = y$ in the definition of completeness. The answers follows Immediately.

Using Completness $(_xR_y) \cup (_yR_x)\; \forall x,y \in X $

Setting $x = y$ we must have $(_xR_x) \cup (_yR_y)\; \forall x,y \in X $

Hence Reflexive. Thanks @Anne Bauval!

CormJack
  • 422