Let $A$ be the set of all functions from the set of integers to the set of integers, and let $R$ be the relation on $A$ given by $$ R = \{(f,g) \mid f(0) = g(0) \;\;\text{or}\;\;f(1) = g(1)\} $$ The relation is:

(a) reflexive, symmetric, anti-symmetric, not transitive.

(b) reflexive, symmetric, not anti-symmetric, and not transitive.

(c) not reflexive, not symmetric, anti-symmetric, and not transitive.

(d) reflexive, symmetric, not anti-symmetric, and transitive.

I'm not really sure how to go about this problem. I know how I can use the elements in the logical defintions of symmetric relations, but I'm not sure what elements I'm putting in.

  • $\begingroup$ Do you know the definitions of the concepts involved? $\endgroup$ – Ittay Weiss Apr 22 '13 at 6:16
  • $\begingroup$ I understand the logical defintions of symmetry relations. However I don't quiet understand what elements are involved in the relation. I just see two same y values that are produced by f and g. Then I'm unsure how the pairing would come into play for the relation. $\endgroup$ – user1766555 Apr 22 '13 at 6:31
  • $\begingroup$ I consider several examples of pairs $(f,g)$ that satisfy the relation to get a feeling what it is, and to check, at least in these examples, the properties. For example look at the pairs: $f_1(n)=n$ and $g_1(n) = -n$; $f_2(n) = n$ and $g_2(n) = 2n-1$; $f_3(n)=n+10$ and $g_3(n) = 11n$. $\endgroup$ – Lior B-S Apr 22 '13 at 6:59
  • $\begingroup$ I don't understand how you got those pairs. Also how do you know it satisfies the relation? $\endgroup$ – user1766555 Apr 22 '13 at 7:07

To be reflexive means that for all functions $f\in A$, holds that $fRf$. Now, is it the case that $fRf$? Let's see, it would hold if $f(0)=f(0)$ or $f(1)=f(1)$. Well, certainly then $fRf$. Now you can work through the other properties and check them for this relation.

  • $\begingroup$ Would the answer be A? $\endgroup$ – user1766555 Apr 22 '13 at 6:55
  • $\begingroup$ what makes you think the relation is not transitive? why do you think it is anti-symmetric? $\endgroup$ – Ittay Weiss Apr 22 '13 at 6:59
  • $\begingroup$ I believe it's anti-symmetric since IFF f(0) = 0, then g(0) = 0 And the definition of Anti-symmetry is: $ \forall a, b \in X, R(a,b) \land R(b,a) \implies a=b $ And $ (R(0, 0) \land R(0, 0)) \implies 0=0 $ is true. Also I do not see an answer that is a yes to all of the properties. $\endgroup$ – user1766555 Apr 22 '13 at 7:06
  • 1
    $\begingroup$ it is not anti-symmetric: find two functions that satisfy $f(0)=g(0)=f(1)=g(1)$, yet $f(3)\ne g(3)$. $\endgroup$ – Ittay Weiss Apr 22 '13 at 7:25
  • $\begingroup$ What does this part mean? "from the set of integers to the set of integers" Also shouldn't it be $ f(0) = g(0) \lor f(1) = g(1) $ $\endgroup$ – user1766555 Apr 22 '13 at 7:28

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.