I'm determining whether the relation is: reflexive, symmetric, transitive or anti-symmetric. Let $X$ be a non-empty set and let $\mathcal{P}(X)$ be the power set of $X$. Let $R_3$ be the relation defined on $\mathcal{P}(X)$ as follows: $\forall A, B\in \mathcal{P}(X)$, $(A, B) \in R_3$ if and only if $A \neq B$.

I've got that it is reflexive because $A R_3A $ since $A\neq B$ and $A=A$ therefore reflexive. It's not anti-symmetric because $A$ and $B$ have to be distinct values, but I'm not sure how to prove for symmetric and transitive.

I was thinking since $A\neq B$ then $A>B$ or $A<B$.

Any help would be appreciated.

  • $\begingroup$ What does $A!$ mean for an arbitrary set $A$? $\endgroup$ – DanielWainfleet Oct 8 '15 at 7:53
  • 1
    $\begingroup$ @user254665 I believe the author uses a pseudo-code convention and means $A \neq B$. $\endgroup$ – GenericNickname Oct 8 '15 at 7:55
  • $\begingroup$ @user254665 $A != B$ is how you often write $A \neq B$ in programming languages. $\endgroup$ – mrp Oct 8 '15 at 7:55
  • $\begingroup$ Yes that is correct. $\endgroup$ – user3491814 Oct 8 '15 at 7:58

The relation is:

  • not reflexive, since $(A,A) \in R_3 \Rightarrow A \neq A$, which obviously is not true.
  • symmetric, since $(A,B) \in R_3 \Rightarrow A \neq B \Rightarrow B \neq A \Rightarrow (B,A) \in R_3$
  • not anti-symmetric: Since $X \neq \emptyset$, we know that $X,\emptyset \in P(X)$ and $(X,\emptyset), (\emptyset, X) \in R_3$ but (as stated before) $X \neq \emptyset$.
  • not transitive: $(A,B), (B,C) \in R_3 \Rightarrow A\neq B$ and $B \neq C$ but this does not imply $A \neq C$. For example take $A = C = \emptyset$ and $B = X$. Then $(A,B),(B,C) \in R_3$ but $(A,C) \notin R_3$.

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.