Let B be the set of all strings of 0’s and 1’s. A binary relation G is defined on B as follows: for all s, $t \in B$, s G t$\iff $ the number of 0’s in s is greater than the number of 0’s in t. Determine whether G is reflexive, symmetric, antisymmetric, transitive, or none of them. Justify your answer

I have no idea how to do this. Please someone help

  • $\begingroup$ Do you know the definitions of these properties ? Do you know if the $<$ relations on the integers is reflexive ? $\endgroup$ – Mirko Nov 28 '15 at 2:17

I'll start you off with reflexive to give you an idea. To prove $G$ is reflexive we need to show $\forall s \in B$ we have $s G s$. But since we defined our relation to be strictly greater than clearly the number of 0's in $s$ is not greater than the number of 0's in $s$.

If we think about the count of 0's in a string as a map from the alphabet 0,1 to $N$ then really this is equivalent to the $>$ operator properties.

| cite | improve this answer | |
  • $\begingroup$ why can't I get \N to give me natural numbers? $\endgroup$ – user2879934 Nov 28 '15 at 2:20
  • $\begingroup$ Use \Bbb N or \mathbb N. $\endgroup$ – Brian M. Scott Nov 30 '15 at 14:09

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.