0
$\begingroup$

Suppose that $\mathscr{P}$ is a partition of A and suppose $xQy$ if there exists $C \in \mathscr{P}$ such that $x \in C$ and $y \in C$. Prove that Q is symmetric and Q is reflexive on A.

Proof.

Let $x \in A$ and $y \in A$.

Assume that $xQy$. By definition, for all $x \in A$ and $y \in A$, if $xQy$, then $yQx$. Therefore, $\exists C \in \mathscr{P}$ such that $x \in C$ and $y \in C$. Therefore $yQx$. Hence Q is symmetric.

Let $x \in A$.

By definition, the partition of A is represented as $$A =\bigcup_{c\in \mathscr{P}}C.$$ Since $x \in A$, it follows that $x \in \bigcup_{c \in \mathscr{P}}C$. So $\exists C \in \mathscr{P}$ such that $x \in C$. Hence $xQx$. Q is reflexive.

These are my proofs. If needed, can someone correct them?

$\endgroup$
  • $\begingroup$ The rest of the problem is to show that Q is transitive, ie an equivalence relation, and that the set of equivalence classes of Q is the partition P. $\endgroup$ – William Elliot Oct 20 '17 at 2:05
0
$\begingroup$

Let $x \in A$ and $y \in A$.

Assume that $xQy$. By definition, for all $x \in A$ and $y \in A$, if $xQy$, then $yQx$.

There's an issue here; this is not "by definition," and is in fact precisely what you're trying to conclude, so it's not OK to claim that $y Q x$ yet.

Therefore, $\exists C \in \mathscr{P}$ such that $x \in C$ and $y \in C$. Therefore $yQx$.

It might be slightly better to explicitly restate that we can conclude for this $C$ that "$y \in C$ and $x \in C$", in that order. This is obviously true, but it's the crux of why you can claim that $y Q x$. Whether or not this is imperative depends on how picky your teacher is, most likely.

Hence Q is symmetric.

Let $x \in A$.

By definition, the partition of A is represented as $$A =\bigcup_{c\in \mathscr{P}}C.$$ Since $x \in A$, it follows that $x \in \bigcup_{c \in \mathscr{P}}C$. So $\exists C \in \mathscr{P}$ such that $x \in C$.

Again, it may be worth explicitly saying that "for this $C$, we can say '$x \in C$ and $x \in C$.'" But this feels even more nitpicky than the last thing and may be unnecessary.

Hence $xQx$. Q is reflexive.

(This whole thing mostly looks good, by the way! The only serious problem is the one about prematurely claiming that $y Q x$.)

$\endgroup$

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.