0
$\begingroup$

Only recently, my math teacher introduced me to the topic reflexivity, symmetry, and transitivity of binary relations, but there are some holes in my understanding that I am desperate to clarify. Each property is defined as "for all" this and this, this and this must be true. All the three definitions bear this general way of defining the properties.

The problem is I'm concerned about the "for all" phrase in the definitions. On what is it binding on? The relation or the set on which the relation is defined?

For example, if you had $A = \{a,b,c,d\}$, then why is $R_1 = \{(a,a),(b,b),(c,c),(d,d)\}$ considered to be symmetric? Shouldn't the relation also have the elements $(a,b),(b,a),(a,c)(c,a),\dots \ \ $also? I think this way because by definition, a relation is symmetric iff for all $a,b \in A, (aRb \implies bRa). $

$\endgroup$
1
$\begingroup$

As you said, a relation is symmetric if, for all $x,y\in A$, $xRy\implies yRx$. However, amore direct way of stating this definition is that, for all $x,y \in A$, $(x,y)\in R\implies (y,x)\in R$.

The key thing to notice in this definition is the protasis of the conditional: $(x,y)\in R$. Thus, this definition only really looks at tuples $(x,y)\in R$ and does not care about tuples outside of $R$. This is why $R_1$ is symmetric: If you take any $(x,y)\in R_1$, then $x=y$, so clearly $(y,x)\in R_1$ as well. $R_1$ is still symmetric because, even though it does not have $(a,b)$ and $(b,a)$, neither of those tuples are in $R_1$, so having $(a,b)$ and $(b,a)$ is not a requirement for being symmetric.

Now, if $(a,b)$ were in $R_1$, then to be symmetric, $(b,a)$ would also have to be in $R_1$ in order to satisfy the conditional $(x,y)\in R\implies (y,x)\in R$. However, since $(a,b)$ is not in $R_1$, the protasis of the conditional is not satisfied and thus the apodosis does not have to be satisfied either.

$\endgroup$
  • $\begingroup$ Ahhh... so the definition of symmetry is binding only on tuples in $R$, not on the set $A$. $\endgroup$ – Apekshik Panigrahi Apr 14 at 15:20
  • $\begingroup$ @ApekshikPanigrahi The antecedent makes it so that the consequent is 'binding' to all objects in $R$ ... but the quantifiers still have to quantify over all objects from $A$. See my answer for a more detailed explanation $\endgroup$ – Bram28 Apr 14 at 19:41
2
$\begingroup$

They apply to the set the relation is on. The symmetry axiom looks like $$\forall x \forall y( xRy) \implies yRx$$ The variables $x,y$ range over the base set, so your $R_1$ is symmetric. If we substitute $a$ for both $x,y$ we have $(aR_1a \implies aR_1a)$, which is true. If we substitute $a$ for $x$ and $b$ for $y$ we have $(aR_1b \implies bR_1a)$, which is true because the antecedent is false. All other substitutions look like one of these.

$\endgroup$
1
$\begingroup$

Usually (but one could take different approaches), in this context the language is extended by a relational symbol (i.e., we can write things like $xRy$) and the universe (i.e., the range of values variables, specifically those occurring after $\forall $ and $\exists$) is the set the relation is on.

$\endgroup$
1
$\begingroup$

Consider the truth table for the conditional $(a \implies b)$. If $a$ is a true statement, then for $a \implies b$ to be true it must be the case that $b$ is true. On another hand, if $a$ is false, then $b$ can be either true or false. In other words, we have

$$T \implies T,$$ $$F \implies T,$$ $$F \implies F.$$

So, we want to prove that $\forall x,y\in A: xRy \implies yRx$. (I'm using different symbols since your set $A$ is $\{a,b,c,d\}$, to avoid confusion.) If $xRy$ is false, then we do not need to check $yRx$ since the conditional statement is always true in this case. So, when is $xRy$ true? By your definition, it is true if and only if $(x,y) \in R_1$. But $R_1$ is the set of ordered pairs $(x,x)$ for some $x\in A$. Thus, $xRy$ is true iff $x=y$. Therefore, $yRx$ must be true since $(y,y)=(x,x)\in R_1$.

$\endgroup$
1
$\begingroup$

a relation is symmetric iff for all $a,b \in A, (aRb \implies bRa). $

The quantifiers in the formal definitions of reflexivity, symmetry, and transitivity are clearly all quantifying over set $A$. Take the definition you mention at the end of your post:

a relation is symmetric iff for all $a,b \in A, (aRb \implies bRa). $

The definition is quantifying both $a$ and $b$, where these are arbitrary objects from $A$. So, the quantifiers are quantifying over all of $A$

It is not quantifying over the relation $R$, because there are two problems with that:

  1. First of all, the objects in $R$ are $2$-tuples, rather than elements of $A$. As such, how would you even talk about something like symmetry? That is, if I tell you that $x \in R$, then what else should be in $R$ because of symmetry. Clearly, we need to know that $x$ is a $2$-tuple of the form $(a,b)$, and only then can we specify that in order for $R$ to be symmetric, we also need $(b,a) \in R$. So, we need to talk about the individual elements (from $A$!) in order to specify what we even mean by symmetry.

  2. Second, if we were to quantifying over objects from $R$ only, then how could you possibly specify reflexivity? That is, a universal quantifier that quantifies over all objects from $R$ effectively starts out by saying 'For all objects $x\in R$ ....'. Now, how would you finish that sentence and get a statement that expresses the reflexivity of $R$ out of that?! You can't: there is nothing you can say about the nature of the objects in $R$ that makes it clear that it is reflexive. For example, if I give you $R = \{ (a,a) , (b,b) , (c,c) \}$ ... can you tell me whether or not $R$ is reflexive? Of course not! You need to know what $A$ is before you can tell that. If, for example, $A$ contains some element $d$, then this $R$ is ont reflexive. So, you need to talk about all objects $a$ from $A$ in order to express reflexivity, and so once again you need to quantify over the objects from $A$, not over the objects from $R$.

Now, I think I know where your confusion is. Going back to your definition of symmetry:

for all $a,b \in A, (aRb \implies bRa)$

this certainly seems to be about objects from $R$, for it effectively says: if this object is in $R$, then this other object should be in $R$ as well.

However, this is something that you often get with universal quantifiers. For example, suppose I want to make the claim that all even numbers greater than $2$ are the sum of two prime numbers. Now, this certainly seems to be a claim about all even numbers greater than $2$, and so it seems like we are quantifying over all even numbers greater than $2$, rather than over all natural numbers. However, in order to talk about prime numbers, we clearly do need to talk about all natural numbers, i.e. we need to quantify over all natural numbers.

Formally, what you get, however, is something like:

$\forall x ((Even(x) \land x > 2) \to \exists y \exists z (Prime(y) \land Prime(z) \land x=y+z))$

So while the quantifiers range over all natural numbers, the antecedent of the conditional will immediately restrict the scope of the claim to even numbers greater than $2$, and thus effectively be a claim about all numbers greater than $2$ instead of being a claim about all natural numbers. Put differently: 'being the sum of two prime numbers' is what is being claimd of all even numbers greater than $2$, but what the claim is claiming to be true of all natural numbers, is that 'if you are an even number greater than $2$, then you are the sum of two prime numbers'

Finally, your final paragraph shows another point of confusion:

For example, if you had $A = \{a,b,c,d\}$, then why is $R_1 = \{(a,a),(b,b),(c,c),(d,d)\}$ considered to be symmetric? Shouldn't the relation also have the elements $(a,b),(b,a),(a,c)(c,a),\dots \ \ $also? I think this way because by definition, a relation is symmetric iff for all $a,b \in A, (aRb \implies bRa). $

No, to be symmetric you don't need $(a,b),(b,a),(a,c)(c,a),\dots \ \ $ as well. All symmetry says is that if $(a,b) \in R$, then we should have $(b,a) \in R$. But, it may well be that neither $(a,b)$ nor $(b,a)$ are in $R$, and $R$ still being symmetric. In fact, $R = \{ \}$ (i.e. the relationship $R$ holds between no pair of objects is symmetric!

Now, I know what you want to say at this point: 'Aha! So doesn't that show that we are only looking at elements from $R$, and not at all objects from $A$? That is, aren't we quantifying over $R$ after all?'

And the answer is: No, we're not quantifying over $R$. It's like the example of the even numbers being the sum of two primes again: Yes, it is true that because $a,b \in A, (aRb \implies bRa)$ contains a conditional, it effectively becomes a claim about all tuples in $R$, and the claim is that their 'swapped' tuple should also be in $R$. However, the claim as a whole is something about all possible tuples (although, as we saw before, we need to be able to say what elements the tuple is made of, and thus the claim is really about all objects from $A$ ..), and the claim is that 'If you are of the form $(a,b)$ and you are in $R$, then it better be true that $(b,a)$ is in $R$ as well.

$\endgroup$
1
$\begingroup$

My answer will not add anything substantial, it simply aims at providing some additional help.

Reading again your question and the argument you give at the end makes me think you possibly make a confusion regarding the " if ... then " operator ( --> ). Apparently, **you read aRb --> bRa " as " aRb therefore bRa".**

The expression " therefore" presupposes that the antecedent is true, and claims that, since the antecedent is true, the consequent is also true. So if the --> actually meant " therefore" , in that case , in order a relation to be symmetric , we should have for all a,b (1) aRb is true and ( 2) " therefore" bRa is also true. And that corresponds exactly to the argument you give at the end.

But be careful not to confuse " if ... then" with " therefore". Look at the truth table of the " --> " operator. You will see it absolutely does not presuppose the antecedent to be true. The expression " aRb --> bRa" simply means :

IT IS NOT THE CASE that , at the same time, aRb is true and that bRa is false.

Now if the difficulty is , in fact, related not to the meaning of " if ...then" but to the universal quantifier, you could rephrase it in the ( equivalent) negative form.

So instead of saying that a relation R is symmetric

iff for all pair a, b , if aRb then bRa

you could say that a relation R is symmetric

iff there is no pair of elements a, b such that aRb is true and bRa is false,

or, if you prefer,

iff there is no pair of elements a, b such that (a,b) belongs to R and (b,a) does not belong to R.

Now look at your relation R1 = { (a,a), (b,b), (c,c), (d,d) }. Does it pass the test?

Can you find a pair of elements , say, x and y, such that (x, y) belongs to R1 and (y,x) does not belong to R1?

You could ( and even would) find such a pair if you had , say, (a, c) but not (c,a). But here, for each pair belonging to R1 , the " converse" pair also belongs to R1. And that's not astonishing since all the pairs are of the form (x,x) , that is, each pair is itself its " converse" pair. Consequently, it is impossible here to have a pair and not its converse pair.

Remark. Same " rephrasing" for reflexivity and transitivity

R is reflexive iff there is no element x such that xRx is false ( or , if you prefer, such that there is no element x such that (x,x) does not belong to R)

R is transitive iff there are no elements x, y,z such that xRy and yRz but not xRz.

$\endgroup$

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.