1

For example, I have a set of A = {1,2,3}. To express relations on the set A, we need the Cartesian product A x A.

For example, I want to express a relation that is reflective and I will write R = {(1,1), (2,2), (3,3)} But I often heard that there is also a term or phrase that is called the smallest relation. What in this case will be the smallest relation and how it differs from the not smallest relation one by the example of the property of reflexivity (if possible).

Andrés E. Caicedo
  • 79,201
MaximPro
  • 133

1 Answers1

1

As you say, a relation is a set of ordered pairs taken from the Ccartesian product of a set with itself. We can partially order relations by inclusion. The smallest one will be the one that is a subset of all the others. Among reflexive relations, the one you give is the smallest because those three pairs must be in every reflexive relation. You can add any other pairs you wish without spoiling the fact that the relation is reflexive.

As another example, the empty relation is the smallest of all relations.

Ross Millikan
  • 374,822
  • If I understand correctly, the smallest relation you brought is not reflective. And such a question, why, for example, R = {(1,1), (2,2)} - is not reflective? But R = {(1,1), (2,2), {3,3} {3,1}} is reflective. You can explain the reasons. Why is one not reflective and the other is? – MaximPro Oct 01 '19 at 21:50
  • A reflexive relation has to have $aRa$ for all $a$ in your set. Your first example does not satisfy that because you do not have $3R3$. Your second example is reflexive. The addition of $(3,1)$ does not change that. – Ross Millikan Oct 01 '19 at 21:51
  • Well, that is, it turns out for any property, for example, transitive or trichotomative or coreflective, or even some in total or without - all pairs from the set A x A must correspond to this property/s. Right? Compliance with the property will mean that the relation is smallest. But when a relation has pairs that go beyond the set of correspondence to a property, then it becomes not smallest. – MaximPro Oct 01 '19 at 22:05
  • Sometimes adding a new pair in will spoil a property. If we start with ${(1,1),(2,2),(3,3)}$ that is symmetric. If we add in $(3,1)$ it is no longer symmetric. We would have to add in $(1,3)$ as well and we would again have a symmetric relation. The smallest symmetric relation is the empty relation. – Ross Millikan Oct 01 '19 at 22:09
  • At the expense of symmetry, not everything is so clear. Why is empty relation the smallest? Why an empty relation cannot be reflective for example then? And then from my Cartesian product, the smallest symmetric relation is the following R = {(1,1) (2,2) (3,3) (1,2) (2,1) (1,3) (3,1) ( 2,3) (3,2)} by analogy with the smallest reflective relation – MaximPro Oct 01 '19 at 22:20
  • I have answered every one of these already. The empty relation is smallest because it is a subset of every other relation. It is not reflexive because it does not have $3R3$. The empty relation is symmetric because there is no case where $aRb$ but not $bRa$. – Ross Millikan Oct 01 '19 at 22:23
  • @RossMilikan I understood you. To summarize, the smallest relation is the one that meets the requirements of the properties minimally and without any additional elements that do not spoil these properties. Right? – MaximPro Oct 02 '19 at 18:12