2

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.

user1766555
  • 553
  • Do you know the definitions of the concepts involved? – Ittay Weiss Apr 22 '13 at 06:16
  • 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. – user1766555 Apr 22 '13 at 06:31
  • 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$. – Lior B-S Apr 22 '13 at 06:59
  • I don't understand how you got those pairs. Also how do you know it satisfies the relation? – user1766555 Apr 22 '13 at 07:07

1 Answers1

1

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.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • Would the answer be A? – user1766555 Apr 22 '13 at 06:55
  • what makes you think the relation is not transitive? why do you think it is anti-symmetric? – Ittay Weiss Apr 22 '13 at 06:59
  • 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.

     – user1766555 Apr 22 '13 at 07:06
  • 1
    it is not anti-symmetric: find two functions that satisfy $f(0)=g(0)=f(1)=g(1)$, yet $f(3)\ne g(3)$. – Ittay Weiss Apr 22 '13 at 07:25
  • 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) $ – user1766555 Apr 22 '13 at 07:28
  • yes, it should be 'or' instead of 'and'. You can still construct functions to show the relation is not anti-symmetric, following my instructions. – Ittay Weiss Apr 22 '13 at 07:38