Was asked to Work out transitive closure of: R = {(1, 1),(1, 3),(2, 2),(2, 1),(3, 3),(4, 4),(4, 3),(4, 2)}

I did using Warshall's, getting: R*={(1,1)(1,3)(2,1)(2,2)(2,3)(3,3)(4,1)(4,2)(4,3)(4,4)}

Is R* antisymmetric?

I understand antisymmetric means if (a,b) exists and (b,a) exists then a=b.

But I am confused here, since there are symmetric elements here too: (1,2)(2,1)

Does the exclusion of (1,2)(3,1)(3,2)(1,4) etc make R* antisymmetric or symmetric or neither?

  • $\begingroup$ Critics concerning title: being antisymmetric applies on relations (wich are specific sets). Not on sets in general. $\endgroup$ – drhab Oct 26 '15 at 12:41
  • $\begingroup$ Quite right, apologies. Will amend $\endgroup$ – ak1652 Oct 26 '15 at 12:44
  • $\begingroup$ @drhab relations are subsets of the cartesian product of a set with itself. So the poster is right telling "antisymmetric set". $\endgroup$ – user279325 Oct 26 '15 at 13:50
  • $\begingroup$ @user279325 I know that relations are specific sets (as mentioned in my former comment) but that is not a justification to speak of "antisymmetric sets". Likewise we do not speak about positive complex numbers. Using such terminology gives rise to senseless questions as: is set $\{\varnothing\}$ antisymmetric? $\endgroup$ – drhab Oct 26 '15 at 14:13
  • $\begingroup$ @drhab you're right. Mistake from me. Although the empty relation (corresponding to $\emptyset$ is antisymmetric. $\endgroup$ – user279325 Oct 26 '15 at 14:29

Checking element by element you see it's antisymmetric. If (2,1) and (1,2) exist, there would be a problem, but it's not the case.

  • $\begingroup$ Many thanks. If for example (1,2) existed, would it be neither symmetric nor anti symmetric? $\endgroup$ – ak1652 Oct 26 '15 at 12:21
  • $\begingroup$ If (1,2) exists, it's no antisymmetric because $1\neq2$, and it's no symmetric since $(1,3)$ exists, but $(3,1)$ doesn't exist. $\endgroup$ – user279325 Oct 26 '15 at 13:47

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.