# problem about reflexive relation

• Aug 17th 2011, 12:23 AM
issacnewton
problem about reflexive relation
Hi

I have this problem in the topic of relations.

Suppose $\displaystyle R$ is a relation on $\displaystyle A$, and define a relation
$\displaystyle S$ on $\displaystyle \mathscr{P} (A)$ as follows.

$\displaystyle S=\{(X,Y) \in \mathscr{P} (A) \times \mathscr{P} (A) \vert \forall x \in X \exists y\in Y(xRy)\}$

for each part ,give either a proof or a counterexample to justify your answer.

a)If $\displaystyle R$ is reflexive , must $\displaystyle S$ be reflexive ?

I was able to prove this part. I was just playing with the examples which
satisfy the above theorem.

Let $\displaystyle A=\{1,2\}$

and lets define

$\displaystyle R=\{(1,2),(1,1),(2,2)\}$

clearly $\displaystyle R$ is reflexive. So S would be

$\displaystyle S=\{ (\{1\},\{2\}),(\{1\},\{1,2\}),(\{1\},\{1\}),(\{2\} ,\{2\}),\\ (\{2\}, \{1,2\}),(\{1,2\},\{1,2\}),(\{1,2\},\{2\}),\\ (\varnothing,\varnothing), (\varnothing, \{1\}),(\varnothing,\{2\}),(\varnothing,\{1,2\})\}$

is $\displaystyle S$ correct ? I included $\displaystyle \varnothing$ since , in the condition for
$\displaystyle S$ , we have ,

$\displaystyle \forall x \in X \exists y\in Y(xRy)$

which can be written as an implication,

$\displaystyle \forall x \left[ x \in X \Rightarrow \exists y \in Y(xRy) \right]$

so if

$\displaystyle X=\varnothing$

then the antecedent is true always , as can be seen from the truth table of the
implication. But I couldn't include the ordered pairs like

$\displaystyle (\{1\},\varnothing)$

in $\displaystyle S$ because if we let

$\displaystyle X=\{1\}$

and

$\displaystyle Y=\varnothing$

then $\displaystyle x \in X$ is true but $\displaystyle \exists y\in Y(xRy)$ is false

Which means that, in the implication , antecedent is true and the consequent is false,
which according to the truth table is false. So

$\displaystyle (\{1\},\varnothing)$

doesn't satisfy the condition for the inclusion in $\displaystyle S$.

is my reasoning correct ? If so, then we can see that $\displaystyle S$ is also reflexive,
which is what the above theorem asserts

I see one problem the way symbol for the power set P is displayed. I have used
\mathscr{P} to display slanted P, but it just displays ordinary $\displaystyle \mathscr{P}$. Is maths package mathrsfs installed on this forum ?

thanks
• Aug 17th 2011, 01:42 AM
FernandoRevilla
Re: problem about reflexive relation
Quote:

Originally Posted by issacnewton
is my reasoning correct ?

Yes,it is

Quote:

If so, then we can see that $\displaystyle S$ is also reflexive, which is what the above theorem asserts
Right.

Quote:

I see one problem the way symbol for the power set P is displayed. I have used \mathscr{P} to display slanted P, but it just displays ordinary $\displaystyle \mathscr{P}$. Is maths package mathrsfs installed on this forum ?
With \mathcal{P}(A) we get $\displaystyle \mathcal{P}(A)$ .
• Aug 17th 2011, 01:47 AM
issacnewton
Re: problem about reflexive relation
ola fernando

thanks for verifying.

• Aug 17th 2011, 02:08 AM
FernandoRevilla
Re: problem about reflexive relation
Quote:

Originally Posted by issacnewton
ola fernando

Ola in Spanish means wave and hola means hello. :)

Quote:

thanks for verifying.
You are welcome!. :)
• Aug 17th 2011, 02:09 AM
emakarov
Re: problem about reflexive relation
Quote:

Originally Posted by issacnewton
is my reasoning correct ?

Of course, it's not a proof of the statement, it's just one example.
• Aug 17th 2011, 02:19 AM
FernandoRevilla
Re: problem about reflexive relation
Quote:

Originally Posted by emakarov
Of course, it's not a proof of the statement, it's just one example.

Of course, but isaacnewton said "if so we can see that S is reflexive" i.e. he didn't say "my example proves S is reflexive".