Binary relations and sets

54
0
1. The problem statement, all variables and given/known data
Let A = {a, b, c} be a set with 3 elements.
(a) How many binary relations are there on A?
(b) How many binary relations on A are reflexive?
(c) How many relations on A are symmetric?
(d) How many binary relations on A are both symmetric and reflexive?

2. Relevant equations


3. The attempt at a solution
a) There are 2^9 = 512 binary relations on A.

b) Therere are 2^(9-3)=8 relations that are reflexive.

c) Here's where I got a bit stuck, not sure if this one's right.
(i) Sets with elements of the form (x,x) 2^3 = 8
(ii) Pairs with elements of the form (x,y) (y,x) (where x /= y): (9-3)/2 = 3. Sets with these elements: 2^3 = 8.
Is that right? And how do I get the number of relations which are symmetric from that? Is it just 8x8?

d) Completely confused, I don't get any of this part.

Any help would be appreciated!
1. The problem statement, all variables and given/known data



2. Relevant equations



3. The attempt at a solution
 

Dick

Science Advisor
Homework Helper
26,249
611
Draw a three by three grid hence having 9 pairs. You are good for the first one. There are nine possible choices of {true,false} to fill in for those 9 pairs. So 2^9=512 looks ok. But I start losing you at b). If it's reflexive then the three pairs along the diagonal must all be true. That leaves you only 9-3=6 pairs to fill in with your choice of {true,false}. But 2^6 is not equal to 8.
 
54
0
Sorry, typo. I meant 2^6=64 reflexive relations, but I'm still not sure about (c). Is the way I did it right? Because it doesn't feel right...
 

Dick

Science Advisor
Homework Helper
26,249
611
Yes, I think. If it's symmetric you get to make an arbitrary choice of {true,false} along the diagonal (x,x) and (x,y) for y<x. That's 6 choices. 2^6=64. Right. If it's reflexive and symmetric you lose the choice along the diagonal. Now you only have three free choices to make, right?
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top