0
$\begingroup$

The definition of a reflexive relation over $A$ is:

$R$ is reflexive over $A$ iff $\forall a \in A :(a,a) \in R$

Why the '$\forall a \in A$'? Def. of transitive and symmetric relations don't have that:

$R$ is transitive iff $(a,b)\in R \wedge (b,c) \in R \implies (a,c) \in R$

$R$ is symmetric iff $(a,b) \in R \implies (b,a) \in R$

If the universal quantification is needed to define the reflexive relation, why isn't it needed for the other two?

$\endgroup$
3
$\begingroup$

Strictly speaking, the universal quantification should be there in all three cases. It's often just left out as a shorthand.


Edit: strictly speaking, all statements are implicitly universally quantified. This is true even if the statement is written as an implication e.g.

$$\text{ if } a \in A \text{ then } (a,a) \in R$$

is really just

$$\forall a \in A, (a,a) \in R$$

or if you like, it is equivalent to the redundant statement:

$$\forall a \in A, \text{ if } a \in A \text{ then } (a,a) \in R$$

Otherwise, what is the $a$ that we are talking about? It needs to be drawn from some universe. So much of maths is implicitly universally quantified that we forget it's going on in the background. But from a strict, logical standpoint, it's always there.

$\endgroup$
  • 1
    $\begingroup$ Would the downvoter like to comment on what is wrong with this post? $\endgroup$ – Colm Bhandal Jul 24 '15 at 18:11
  • $\begingroup$ So you're arguing that a theorem such as $$n \in \mathbb N \Rightarrow n+1 \in\mathbb N$$ is incomplete and we actually have to write $$\text{ for all } n \in\mathbb N, n \in\mathbb N \Rightarrow n+1 \in\mathbb N$$ This strikes me as a bit much and outside the bounds of usual mathematical writing, but I take your point. $\endgroup$ – Simon S Jul 24 '15 at 18:41
  • 4
    $\begingroup$ @SimonS: If you want to formalize your theorem, then you need to make the quantifier explicit. You're right that ordinary informal mathematical writing often omits the quantifier when there's a condition attached to it (and writes only the condition). This works well for a readership that knows enough to intuit what the role of each variable should be -- but students certainly ought to be made aware that the role of the variables in the three definitions is exactly the same, and it's just a quirk of mathematical prose that this is expressed with an explicit quantifier in only the first one $\endgroup$ – Henning Makholm Jul 24 '15 at 19:51
  • 1
    $\begingroup$ Cheers mate, that really cleared things up; as you said, without the quantification the variables would be free variables, which struck me as very counter-intuitive as I always thought free variables equal problems. $\endgroup$ – Daniel Mak Jul 25 '15 at 4:18
  • 1
    $\begingroup$ @Simon S I completely agree that the use of universal quantifiers is over the top in most cases. It's just a strict, technical thing under the hood that we usually don't have to worry about. $\endgroup$ – Colm Bhandal Jul 25 '15 at 10:57
1
$\begingroup$

Reflexive means EACH $a\in A$ is in relation with itself.

Symmetric means AS LONG AS $aRb$, then $bRa$.

Transitive means IF $aRb$, $bRc$, then $aRc$.

A relation that is reflexive, symmetric and transitive is called an equivalence relation. I would like to think "friendship" as an example of equivalent relation (in a perfect world in which 1) you are friend with yourself; 2) if you are friend to Tom, then Tom is a friend to you; 3) if you are friend to Tom, Tom is friend to Amy, then you are friend to Amy.)

$\endgroup$
  • $\begingroup$ Correction: a reflexive, symmetric, transitive relation is called an equivalence relation; it is not called equivalent or an equivalent relation. And your final statement is simply wrong: the definition of symmetry does require universal quantification, either over all $a,b\in A$ or over all $\langle a,b\rangle\in R$. $\endgroup$ – Brian M. Scott Jul 24 '15 at 23:17
  • $\begingroup$ @BrianM.Scott Thanks! Edited. $\endgroup$ – henryforever14 Jul 25 '15 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.