A is a set. Let $B\subsetneq A$.

$R=A\times B \cup B\times A$

Determine if the relation is (a)reflexive, (b)symmetric, (c)transitive, (d)anti-reflexive, (e)anti-symmetric, (f)asymmetric, (g)equivalence relation.

This is what I did:

It isn't reflexive because there can't be a set that is a proper subset of itself. So it is anti-reflexive.

It is symmetric because a union is symmetric: $A\times B \cup B\times A=B\times A\cup A\times B$

It isn't transitive because not every ordered pair of (A and B) and (B and C) is in A and C, example:

$A=\{1\} \ B=\{1,2\} \ C=\{1,2,3\} \\ A\times B \cup B\times A = (1,1),(1,2),(2,1) \\ C\times B \cup B\times C = (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2) \\ A\times C \cup C\times A = ( 1,1 ),( 1,2 ),(1 ,3 ),( 2,1 ),( 3,1 ) $

There is no equivalence relation.

Is it correct ? Thanks.

  • $\begingroup$ You should make clear whether you are interested in the relation being a proper subset. (I.e., two subsets of given set are in the relation if $A\subsetneq B$. In this case your argument why it is antireflexive would be ok.) Or whether you are interested in $R=(A\times B)\cup(B\times A)$, which is entirely different thing. $\endgroup$ – Martin Sleziak Dec 27 '13 at 14:56

You need your counterexample to transitivity to be such that $B\subsetneq A$ and $C \subsetneq B$: $$C\subsetneq B \subsetneq A$$

So, for example, in your case, you'd need $$A = \{1, 2, 3\}, B = \{1, 2\}, C = \{1\}$$ Your approach, however, should still hold.

But you should note that because of the failure of reflexivity, the relation is not an equivalence relation, anyway.

  • $\begingroup$ Isn't this the the same as what I wrote only sort of reversed ? $\endgroup$ – GinKin Dec 14 '13 at 14:41
  • 1
    $\begingroup$ Yes, pretty much, that's why I said your approach is fine, you just mixed up which is a subset of which. $\endgroup$ – Namaste Dec 14 '13 at 14:42

You are asking about properties of $R=(A\times B)\cup(B\times A)$.

You know that $B\subsetneq A$, i.e., there is at least one element in $A\setminus B$. So let us choose one such element and denote it by $a_0\in A\setminus B$.

The relation $R$ is not reflexive, since $(a_0,a_0)\notin R$. (Can you explain why? Does the ordered pair $(a_0,a_0)$ belong to $A\times B$? Does it belong to $B\times A$?)

The relation $R$ is symmetric. (If $(x,y)\in R$ then the pair $(x,y)$ belongs to $A\times B$ or it belongs to $B\times A$. Suppose that $(x,y)\in A\times B$. What can you say about $(y,x)$?)

If the set $B$ has at least one element, then $R$ is not transitive. (Let $b_0\in B$. Then both $(a_0,b_0)$ and $(b_0,a_0)$ belong to $R$. Can you get from this a contradiction with transitivity?)

If the set $B$ has at least one element, then $R$ is not anti-reflexive. (Does $(b_0,b_0)$ belong to $R$?)

If the set $B$ has at least one element, then $R$ is not asymmetric. (Use that $(a_0,b_0)\in R$.)

If the set $B$ has at least one element, then $R$ is not antisymmetric. (Notice that $(a_0,b_0),(b_0,a_0)\in R$.)

Since $R$ is not reflexive, it is not an equivalence relation.


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.