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

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)$ .

Re: problem about reflexive relation

ola fernando

thanks for verifying.

adios

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!. :)

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.

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".