Abstract Algebra: Relations

  • Thread starter Raze
  • Start date
  • #1
29
0
Abstract Algebra: Relations; Find a relation that is symmetric, etc

Homework Statement


Find a relation that is symmetric and transitive but not reflexive.


Homework Equations



None, other than my chosen condition on the relation, namely: xy > |x + y|.

The Attempt at a Solution



I'm sure this is on here every semester, but if possible I'd like some feedback on my attempt. This is a product relation in Z x Z.


Call the set O.

O = {(x,y)∈ Z2: xy > |x + y|}


Symmetric:

Since in the integers xy = yx and |x + y| = |y + x|, (y,x)∈ O (it is symmetric).


Transitive:

This means, if (a,b)∈ O and (b,c)∈ O then (a,c)∈ O, that is, if ab > |a + b| and bc > |b + c|, then ac > |a + c|.

First of all, none of a, b or c can be zero, otherwise somewhere along here you'd have 0 > a positive number, because the absolute values are taken.

Second, either a AND b are positive or a AND b are negative, or you'd get a negative number > a positive number.

In the first case, if a and b are positive, then by the assumption that bc > |b + c|, c has to be positive. In that case, it is true that ac > |a + c| (if a were 1 and c were 2 this would be false, but we're already assuming that ab > |a + b| and bc > |b+ c|).

HOWEVER, I'm not exactly clear on how I would give a good reason for the above.

The similar reasoning is done if a and b are negative. The relation seems to be transitive. I need a little help in demonstrating this, assuming I'm right.



Reflexive:

It is NOT reflexive for the following reason: (1,1)∉ O. (1)(1) = 1, but |1 + 1| = 2, and 1 > 2 is nonsense.



What do you think? Thanks for any help.
 
Last edited:

Answers and Replies

  • #2
575
76

Homework Statement


Find a relation that is symmetric and transitive but not reflexive.


Homework Equations



None, other than my chosen condition on the relation, namely: xy > |x + y|.

The Attempt at a Solution



I'm sure this is on here every semester, but if possible I'd like some feedback on my attempt. This is a product relation in Z x Z.


Call the set O.

O = {(x,y)∈ Z2: xy > |x + y|}


Symmetric:

Since in the integers xy = yx and |x + y| = |y + x|, (y,x)∈ O (it is symmetric).


Transitive:

This means, if (a,b)∈ O and (b,c)∈ O then (a,c)∈ O, that is, if ab > |a + b| and bc > |b + c|, then ac > |a + c|.

First of all, none of a, b or c can be zero, otherwise somewhere along here you'd have 0 > a positive number, because the absolute values are taken.

Second, either a AND b are positive or a AND b are negative, or you'd get a negative number > a positive number.

In the first case, if a and b are positive, then by the assumption that bc > |b + c|, c has to be positive. In that case, it is true that ac > |a + c| (if a were 1 and c were 2 this would be false, but we're already assuming that ab > |a + b| and bc > |b+ c|).

HOWEVER, I'm not exactly clear on how I would give a good reason for the above.

The similar reasoning is done if a and b are negative. The relation seems to be transitive. I need a little help in demonstrating this, assuming I'm right.



Reflexive:

It is NOT reflexive for the following reason: (1,1)∉ O. (1)(1) = 1, but |1 + 1| = 2, and 1 > 2 is nonsense.



What do you think? Thanks for any help.
Edit: Oops. Irreflexive is not the same as not reflexive.

(2,3) and (3,2) are in O, but (2,2) is not. So O is not transitive.
 
Last edited:
  • #3
34,692
6,396
Does the relation have to be one like > or < or =? The problem statement, which I quote below, doesn't place any conditions such as that it must be a relation between numbers.
Raze said:
Find a relation that is symmetric and transitive but not reflexive.
Do you have any brothers or sisters? Think about brotherhood or sisterhood as relations.
 
  • #4
29
0
Edit: Oops. Irreflexive is not the same as not reflexive.

(2,3) and (3,2) are in O, but (2,2) is not. So O is not transitive.
Okay, but wouldn't that mean that every relation that is symmetric and transitive is also reflexive? Because I know that is actually false.

EDIT:
I'm thinking here that a, b, and c have to be distinct. Is that not the case?

Does the relation have to be one like > or < or =? The problem statement, which I quote below, doesn't place any conditions such as that it must be a relation between numbers.
It has to be in Z x Z. Other than that, no.
Do you have any brothers or sisters? Think about brotherhood or sisterhood as relations.
I understand that one pretty well. I can't be a brother to myself.

So we all agree that my example fails, correct?


How about this one (I was trying to be fancy earlier. I'll try something easier).

O = {(x,y)∈ Z2: x≠y}

Well, if x≠y, then y≠x => symmetric

If a≠b and b≠c, then a≠c => transitive

And, a≠a is nonsense => reflexive.




How is that?


The reason I didn't use that first is that I have to come up with TWO of these in the integers, and I thought x >y and then x<y for the next one would be kind of lame.
 
Last edited:
  • #5
29
0
Okay, but wouldn't that mean that every relation that is symmetric and transitive is also reflexive? Because I know that is actually false.

EDIT:
I'm thinking here that a, b, and c have to be distinct. Is that not the case?



It has to be in Z x Z. Other than that, no.

I understand that one pretty well. I can't be a brother to myself.

So we all agree that my example fails, correct?


How about this one (I was trying to be fancy earlier. I'll try something easier).

O = {(x,y)∈ Z2: x≠y}

Well, if x≠y, then y≠x => symmetric

If a≠b and b≠c, then a≠c => transitive

And, a≠a is nonsense => reflexive.




How is that?


The reason I didn't use that first is that I have to come up with TWO of these in the integers, and I thought x >y and then x<y for the next one would be kind of lame.
Does the relation have to be one like > or < or =? The problem statement, which I quote below, doesn't place any conditions such as that it must be a relation between numbers.

Do you have any brothers or sisters? Think about brotherhood or sisterhood as relations.
Wait. No no no no no. Disregard my answer/question to you at the end of that.

First, if the relation is x ≠ y, then I won't necessarily have a transitive relation, because just because a ≠ b and b ≠ c, it does not follow that a ≠ c (choose a = 1, b = 2, and c = 3, for example).

Second, x > y stops me from having symmetry, because if x > y it is not true that y > x.

Likewise with x < y.


Third:


Edit: Oops. Irreflexive is not the same as not reflexive.

(2,3) and (3,2) are in O, but (2,2) is not. So O is not transitive.
If I add one more stipulation to my condition, I think I'll take care of it. If I forbid x from equaling y, I think that solves that problem.


How about this:

O = {(x,y)∈ Z2: xy > |x + y| and x ≠ y}.


Would that not take care of all cases where (a,b), (b,a)∈ O but (a,a) not in O? I can think of no other thing that could prevent that relation from being transitive. Can anyone else?
 
  • #6
34,692
6,396
Okay, but wouldn't that mean that every relation that is symmetric and transitive is also reflexive? Because I know that is actually false.

EDIT:
I'm thinking here that a, b, and c have to be distinct. Is that not the case?



It has to be in Z x Z. Other than that, no.

I understand that one pretty well. I can't be a brother to myself.

So we all agree that my example fails, correct?


How about this one (I was trying to be fancy earlier. I'll try something easier).

O = {(x,y)∈ Z2: x≠y}

Well, if x≠y, then y≠x => symmetric

If a≠b and b≠c, then a≠c => transitive
No, that doesn't work. 2 ≠ 3 and 3 ≠ 2, but 2 = 2. Even though (2, 3) and (3, 2) are in your set, (2, 2) is not.


And, a≠a is nonsense => reflexive.
No, that makes the relation ≠ irreflexive.
How is that?


The reason I didn't use that first is that I have to come up with TWO of these in the integers, and I thought x >y and then x<y for the next one would be kind of lame.
 
  • #7
29
0
No, that doesn't work. 2 ≠ 3 and 3 ≠ 2, but 2 = 2. Even though (2, 3) and (3, 2) are in your set, (2, 2) is not.


No, that makes the relation ≠ irreflexive.
*I meant to put NOT reflexive there, but I realized that that relation would make it not necessarily be transitive. Just because a≠b and b≠c, it does not follow that a≠c.

But what about my new condition, if you don't mind?

O = {(x,y)∈ Z2: xy > |x + y| and x ≠ y}

(I'm trying to make a relation that is symmetric and transitive, but not reflexive)
 
  • #8
34,692
6,396
What's the relation itself? Typical relations are =, ≠, <, ≤, >, ≥, divides, and so on. All you have is a set of ordered pairs, but no operation that is defined on each member of the pair.
 
  • #9
29
0
What's the relation itself? Typical relations are =, ≠, <, ≤, >, ≥, divides, and so on. All you have is a set of ordered pairs, but no operation that is defined on each member of the pair.
Sorry that's the notation the instructor wants used. The relation is:

xy > |x + y| AND x≠y
 
  • #10
575
76
What's the relation itself? Typical relations are =, ≠, <, ≤, >, ≥, divides, and so on. All you have is a set of ordered pairs, but no operation that is defined on each member of the pair.
A binary relation on a set X is, by definition, just a subset of X[itex]\times[/itex]X. There's no need to use any well-known "operations" to define the relation.
 
  • #11
575
76
*I meant to put NOT reflexive there, but I realized that that relation would make it not necessarily be transitive. Just because a≠b and b≠c, it does not follow that a≠c.

But what about my new condition, if you don't mind?

O = {(x,y)∈ Z2: xy > |x + y| and x ≠ y}

(I'm trying to make a relation that is symmetric and transitive, but not reflexive)
Part of your difficulty with this problem stems from the fact that if you have any two distinct elements x and y with xRy, then symmetry forces yRx, and then transitivity forces xRx (and also yRy). So in a symmetric transitive relation, any element that is related to another must also be related to itself. Trying to keep all elements of the form (x,x) out of your relation is a bad idea.

The easiest example of a relation on a set that is symmetric and transitive and not reflexive that is remotely interesting is to take a three-element set {x,y,z} and let the relation R be given by R={(x,x),(y,y),(x,y),(y,x)}. Note that it's not reflexive since (z,z) is not in R. It's also not irreflexive, since (x,x) and (y,y) are in R.
 
  • #12
29
0
Part of your difficulty with this problem stems from the fact that if you have any two distinct elements x and y with xRy, then symmetry forces yRx, and then transitivity forces xRx (and also yRy). So in a symmetric transitive relation, any element that is related to another must also be related to itself. Trying to keep elements of the form (x,x) out of your relation is a bad idea.
But my text specifically says that the above argument is insufficient to show reflexivity (namely, Symmetry implies xRy and yRx, then transitivity implies xRx, hence reflexivity). Or is that not reflexivity? What more is required to show it?

No wait. I think I might be getting it. Any symmetric and transitive relation will have each element in the SUBSET where the relation applies relate to itself, but NOT necessarily every element in the original set itself?

The easiest example of a relation on a set that is symmetric and transitive and not reflexive that is remotely interesting is to take a three-element set {x,y,z} and let the relation R be given by R={(x,x),(y,y),(x,y),(y,x)}. Note that it's not reflexive since (z,z) is not in R. It's also not irreflexive, since (x,x) and (y,y) are in R.
I see here that the relation doesn't use every element in the set (it is missing z). However, every element in the subset R is related to itself.


Now the question is, how do I find one in Z x Z. I will be working on that pending any more responses.
 

Related Threads on Abstract Algebra: Relations

Replies
6
Views
4K
Replies
2
Views
2K
Replies
5
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
Top