Can someone walk me through how to do these types of problems in my Discreet Mathematics II Textbook? (ex.):

Determine whether the given relation is an equivalence relation on the set. Describe the partition arising form each of the equivalence relation.

(a) Let $A$ be the set of all lines in a plane. Let $R$ be the relation in $A$ defined as $R$ = {$(A_1, A_2)|A_1$ is parallel to $A_2$}.

(b). Let $Z$ be the set of integers. Let $R$ be the relation in $Z$ defined as $R$={$(x,y)|x$ and y are both even}.

Now, I know that a poset is a relation which is reflexive, antisymmetric, and transitive, and an equivalence relation is one which is reflexive, symmetric, and transitive.

Then for Partitions, a previous question had me finding which subsets of a set were partitions, found by seeing if the Union (U) of all the subsets resulted in the initial Set and that the Intersections were all pairwise-disjoint. Like for example: $S$ = {$-3,-2,-1,0,1,2,3$} with subsets {-3,3}, {-2,2}, {-1,1}, {0} together Unioned make the initial set and are uniquely pairwise disjoint, thus being a partition, but subset {-3,-2,-1,0},{0,1,2,3} is not pairwise disjoint with the 2 zeroes intersecting and subset {-3,-2,2,3},{-1,1} is not a partition of Set (S) due to not containing '0'.

But as far as the actual problem here goes, I'm not even sure how to conceptualize what is given let alone answer it? Can someone assist with this?

  • $\begingroup$ Is a line parallel to itself (is the first relation reflexive)? I suppose that depends on your definition of parallel, but usually that means in this context that they have the same slope or direction. If line $A_1$ has the same slope as the line $A_2$ does it follow that line $A_2$ has the same slope as the line $A_1$ (is the first relation symmetric)? What if $A_2$ has the same slope as $A_3$, does it follow that $A_1$ has the same slope as $A_3$ (is it transitive)? For the second relation, for any integer $x$ (even or odd) is it true that $(x,x)\in \mathcal{R}$? (is $(1,1)\in R$?) $\endgroup$ – JMoravitz Apr 20 '16 at 18:43
  • $\begingroup$ As far as partitions are concerned, for the first relation, is there a something common to all elements which are related to one another? There will be infinitely many parts in the partition, which is perfectly fine. What it is asking for is some part, $P_x$, to give a piece of information about all elements in $P_x$ which is true only for elements in $P_x$ and not in any other $P_y$ (perhaps something to do with slope might be convenient). $\endgroup$ – JMoravitz Apr 20 '16 at 18:48

If you want to find out whether a relation $R$ on a set $A$ is an equivalence relation then it is a handsome strategy to look for a function $f:A\to Y$ such that $aRb\iff f(a)=f(b)$.

If you can find one then you are indeed dealing with an equivalence relation. Note that e.g. reflexivity of $R$ follows directly from the evident fact that $f(a)=f(a)$ for each $a$. Also symmetry and transitivity become easy: if $f(a)=f(b)$ then of course $f(b)=f(a)$ and if $f(a)=f(b)\wedge f(b)=f(c)$ then $f(a)=f(c)$.

Equivalence classes are subsets of $A$ with the property that the elements of the subset are sent by $f$ to the same output. So if $Z:=\{f(a)\mid a\in A\}\subseteq Y$ then a set $P\subseteq A$ is an equivalence class if and only if $P=f^{-1}(\{z\}):=\{a\in A\mid f(a)=z\}$ for some $z\in Z$.

(a) think of the function prescribed by: $$\text{line}\mapsto\text{slope of line}$$

(b) check whether this relation is reflexive.


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.