Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a question from "Discrete Mathematics and Its Applications":

Determine whether the relation R on the set of all Web
pages is reflexive, symmetric, antisymmetric, and/or tran-sitive, 
where(a, b) ∈ R if and only if

a) everyone who has visited Web page a has also visited Web page b .

The answer is:

a) Reflexive, transitive

I don't understand well why it's "Reflexive". If there is a web page which has never been visited by anybody, (a,a) won't be belonged to R, that R should not be reflexive, right?

Do I misunderstand something wrong?


Thanks for @Brian M. Scott's answer, I understand it now. Let me add something important here:

The description of $R$ is:

$R$={$(x,y) | \forall p (F(p,x) \to F(p,y))$}, where $F(p,x)$ means "p has visited x", and $ p \in P $ where P is "all people".

When page $x$ has never been visited, that $F(p,x), p \in P$ is always false, that $\forall p (F(p,x) \to F(p,y))$ is always true, that F(x, any y) is always true.

That's why the relation is "Reflexive".

share|improve this question
    
It will be helpful for you to review the definition of a relation first. What does $aRb$ mean? What does $aba$ mean? –  Calvin Lin Jan 7 '13 at 4:11
    
"Everyone who has visited the Sun has (also) visited the Sun" is true. –  André Nicolas Jan 7 '13 at 4:16

1 Answer 1

up vote 5 down vote accepted

If $a$ is a web page, let $V(a)$ be the set of people who have visited $a$. Then $\langle a,b\rangle\in R$ if and only if $V(a)\subseteq V(b)$. Now it’s always true that $V(a)\subseteq V(a)$, even if $V(a)=\varnothing$, so it’s always true that $\langle a,a\rangle\in R$. Thus, $R$ really is reflexive.

Here’s a slightly different way to look at it. If $a$ and $b$ are particular web pages, how could you prove that $\langle a,b\rangle\notin R$? You would have to find someone who has visited $a$ but has not visited $b$. If no one has visited $a$, you can’t do this: you can’t find anyone who has visited $a$, let alone someone who has visited $a$ but not $b$! This shows that if $a$ has never been visited, then $\langle a,b\rangle\in R$ for all $b$ (and hence certainly for the particular case $b=a$).

share|improve this answer
    
$R$={$(x,y) | \forall p (F(p,x) \to F(p,y))$}, where $F(p,x)$ means "p has visited x". Is it right? –  Freewind Jan 7 '13 at 4:39
1  
@Freewind: Yes, that’s one correct way to describe it, though it would be better if you wrote $\forall p\in P$ and defined $P$ to be the set of all people. –  Brian M. Scott Jan 7 '13 at 4:41
    
If page $x$ has never been visited, that $F(p,x)$ will always be false, that $\forall p (F(p,x) \to F(p,y))$ will be true, so $(x, any y)$ belong to $R$. –  Freewind Jan 7 '13 at 4:41
    
@Freewind: Yes, that’s right. –  Brian M. Scott Jan 7 '13 at 4:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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