1
$\begingroup$

I'm new to discrete maths and struggling with Relations, need to test the following relations for equivalence on the set X also find an equivalence class if it is equivalence relation.

Ques 1. X = R, x ∼ y <=> 2y < x2 + 1

• For reflexivity

x ∼ x <=> 2x < x2 + 1

for x = 1, the statement is false.

=> It is not reflexive.

• For symmetry[updated]

x ∼ y <=> 2y < x2 + 1

y ∼ x <=> 2x < y2 + 1

for x = 1 and y = 5 in 2y < x2 + 1

10 < 2, which is false

=> It is not symmetric.

• For transitivity[updated]

x ∼ y <=> 2y < x2 + 1

y ∼ z <=> 2z < y2 + 1

x ∼ z <=> 2y < x2 + 1

similar to symmetry

=> It is not transitive.

Ques 2. X = 2N, A ∼ B <=> (A ∪ B)' = N

I'm not sure how to interpret X = 2N and check if it is an equivalence relation.

$\endgroup$
  • 1
    $\begingroup$ For the symmetry question, have you experimented with some simple (small positive and negative integer) values for $x$ and $y$? For question 2, $2^N$ probably means the power set of $N$, that is, the collection of subsets of $N$. $\endgroup$ – Steve Kass Nov 26 '16 at 21:20
  • $\begingroup$ On the first question for reflexivity, $x=1$ (and only $x=1$) fails. $\endgroup$ – Joffan Nov 26 '16 at 21:25
  • $\begingroup$ I edited the reflexivity. I still have to prove symmetry and transitivity. So if there's even one value for which the statement is false, the relation is not symmetric? eg. for x = 1 and y = 5 in 2y < x^2 + 1 gives 10 < 2 which is false. $\endgroup$ – Archetype2142 Nov 26 '16 at 21:26
  • $\begingroup$ That's correct; you only need one counterexample. $\endgroup$ – Joffan Nov 26 '16 at 21:29
0
$\begingroup$

For 2, $X$ is the set of subsets of $\{1,2,3,\ldots,N\}$. $A$ and $B$ are two of those subsets. They are related if the complement of their union is all of $\{1,2,3,\ldots,N\}$. First use DeMorgan's law on the complement of the union to get ??? Then check RST.

$\endgroup$
  • $\begingroup$ (A ∪ B)' becomes (A' ∩ B') after DeMorgan's if A = {1, 2, 3, 4} and B = {3, 4, 5, 6 }, for reflexive, A ∼ A = {6. 7. 8...N} ∩ {6. 7. 8...N} = {6, 7, 8, ... N} ≠ N. So it is not reflexive? $\endgroup$ – Archetype2142 Nov 26 '16 at 23:35
  • $\begingroup$ $A'$ includes $5$ in your example, but you are correct that it is not reflexive. You should not say $A \sim A=$ some set, you should say $A' \cap A'$=$ some set. The first is not a set, while the second is. $\endgroup$ – Ross Millikan Nov 27 '16 at 0:12

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.