How can Binary Relations on a Set with 3 Elements be Symmetric and Reflexive?

In summary, there are 512 binary relations on A, 64 binary relations on A that are reflexive, 64 binary relations on A that are symmetric, and 8 binary relations on A that are both symmetric and reflexive.
  • #1
muso07
54
0

Homework Statement


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?

Homework Equations




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!
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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...
 
  • #4
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?
 

Related to How can Binary Relations on a Set with 3 Elements be Symmetric and Reflexive?

1. What is a binary relation?

A binary relation is a mathematical concept that describes the relationship between two sets of elements. It is a subset of the Cartesian product of the two sets, where each element in the first set is paired with an element in the second set.

2. What are the different types of binary relations?

There are several types of binary relations, including reflexive, symmetric, antisymmetric, transitive, and equivalence relations. A reflexive relation is one where every element is related to itself. A symmetric relation means that if x is related to y, then y is also related to x. An antisymmetric relation is one where if x is related to y and y is related to x, then x and y must be the same element. A transitive relation means that if x is related to y and y is related to z, then x is also related to z. An equivalence relation is one that is reflexive, symmetric, and transitive.

3. What is a set?

A set is a collection of distinct objects, called elements, that have certain characteristics in common. These objects can be numbers, letters, or any other mathematical or physical entities. The elements in a set are enclosed in braces and are separated by commas.

4. What is the difference between a subset and a proper subset?

A subset is a set that contains some or all of the elements of another set. A proper subset is a subset that does not contain all the elements of the original set. In other words, a proper subset is a subset that is smaller than the original set.

5. How are binary relations and sets related?

Binary relations and sets are related in that binary relations can be represented using sets. The elements in a binary relation are pairs of elements from the two sets, where the first element comes from the first set and the second element comes from the second set. Additionally, sets can be used to define and classify different types of binary relations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
  • Set Theory, Logic, Probability, Statistics
2
Replies
35
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
849
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
17
Views
10K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
693
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top