Home » Blogs » Mgccl's blog

Commutative, Transitive but not Reflexive

Wed, 10/28/2009 - 14:25 | by Mgccl

I remember this problem from Apostol's calculus textbook.

Let \Box be a commutative and transitive relation over a non-empty set. Show this proof is flawed:

a\Box b \implies b\Box a
a\Box b \wedge b\Box c \implies a\Box c
a\Box b \wedge b\Box a \implies a\Box a
\Box is also reflexive over the set.

I asked this online like few months ago. One of the people said something about it is related to logic and I should figure it out by looking over the definition of the relations.

I thought of this again, and put it up on Facebook. Thx to Sackel sending me part of this Wikipedia article on equivalence relation.

The empty relation R on a non-empty set X (i.e. aRb is never true) is vacuously symmetric and transitive, but not reflexive.

awesome, now I see how this is not true.
First, here are the definition of the 3 kind of relations.
\forall_{a \in X} a \Box a (reflexive)
\forall_{a,b \in X} a \Box b \implies b \Box a (commutative)
\forall_{a,b,c \in X} a\Box b \wedge b\Box c \implies a\Box c (transitive)

(a\Box b \wedge b\Box a \implies a\Box a) \Leftrightarrow True
but that doesn't mean a \Box a \Leftrightarrow True. So the last step of the proof was wrong.

Logic. I see.


Tags:

Comments

Post new comment

  • Allowed HTML tags: <img> <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <span> <fn>
  • Lines and paragraphs break automatically.
  • Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>. The supported tag styles are: <foo>, [foo].
  • Mathematical equations and graphs can be added between [tex] and [/tex], [graph] and [/graph] tags.
  • Textual smileys will be replaced with graphical ones.

More information about formatting options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
- eight = minus five
Solve this math question and enter the solution with digits. E.g. for "two plus four = ?" enter "6".
Honey Pot that kill bots