How many binary relations in a set of 8

In summary, for a set A with 8 elements, there are 2^64 binary relations on A, 2^56 reflexive relations, and 2^36 symmetric relations. To find the number of binary relations that are both reflexive and symmetric, we use a similar counting argument as in part c and multiply the number of reflexive relations (2^56) by the number of symmetric relations (2^28), giving us a total of 2^28 binary relations that are both reflexive and symmetric.
  • #1
mr_coffee
1,629
1
Hello everyone. This problem has a few parts, and I'm on the last part and I'm having troubles and im' guessing my way is not the correct method. But here is the question.


Let A be a set with 8 elements.
a. how many binary relations are there on A?

answer: A binary relation is any subset of AxA and AxA has 8^2 = 64 elements. So there are 2^64 binary relations on A.

b. how many binary relations on A are reflexive?
There are exactly 8x, so you have 8 of the 64 results of AxA so you have 2^(64-8) = 2^56 reflexive relations.

c. HOw many binary relations on A are symmetic?
Form a symmetric relation by a 2 step process:
1. Pick a set of pairs of elements of the form (a,a) (there are 8 such elements , so 2^8 sets);
2. Pick a set of pairs of elements of the ofrm (a,b) and (b,a) where a != b (there are (64-8)/2 = 28 such pairs os 2^28 such sets. So the answer by the multiplicaiton rule is 2^8 * 2^28 = 2^36.

Now this is the one i can't get:
d. How many binary relations on A are both reflexive and symmetric?
I was thinking i could add parts c and b, and get
2^56 + 2^36...but that seems to easy, or am i allowed? I have no idea what process i would go about figuring this out if that's incorrect, nay help would be great.


Thanks.
 
Physics news on Phys.org
  • #2
Use a similar counting argument as in c

d.1 A reflexive relation includes ALL the elements (a,a)
d.2 Same as c.2
 
  • #3
For a relation to be called as reflexive, it must contain all the pairs (a,a) if a belongs to A. Such 8 pairs are possible over A. And all of those must be included.

A relation is symmetric if it contains
a. set of pairs of elements of the form (a,a)--> We have already included all such pairs while selecting reflexive relations. So, here, we don't have any choice.
b. set of pairs of elements of the ofrm (a,b) and (b,a) where a != b (there are (64-8)/2 = 28 such pairs and hence 2^28 such sets.

By product rule, it counts to be 1*2^28=2^28.
 

Related to How many binary relations in a set of 8

1. How many binary relations are there in a set of 8 elements?

There are 28*8 = 264 = 18,446,744,073,709,551,616 binary relations in a set of 8 elements. This is because for each pair of elements in the set, there are two possible outcomes (either the pair is related or not related), and since there are 8*8 = 64 possible pairs in a set of 8 elements, we have 264 binary relations.

2. What is the formula for calculating the number of binary relations in a set of n elements?

The formula for calculating the number of binary relations in a set of n elements is 2n*n or 2n2. This is because for each pair of elements in the set, there are two possible outcomes (related or not related), and since there are n*n = n2 possible pairs in a set of n elements, we have 2n2 binary relations.

3. Can a set of 8 elements have more than 18,446,744,073,709,551,616 binary relations?

No, a set of 8 elements cannot have more than 18,446,744,073,709,551,616 binary relations. This is because the maximum number of binary relations in a set of n elements is 2n2, and for n = 8, this is equal to 264 = 18,446,744,073,709,551,616.

4. Why is it important to understand binary relations in sets?

Understanding binary relations in sets is important because it allows us to analyze and compare different elements within a set. It also helps us to understand the properties and characteristics of the set, and to identify patterns and relationships between the elements. Additionally, binary relations are widely used in various fields of science, such as mathematics, computer science, and physics, to model and solve complex problems.

5. How do binary relations differ from other types of relations?

Binary relations differ from other types of relations in that they only have two possible outcomes for each pair of elements (related or not related), whereas other types of relations may have multiple outcomes or degrees of relatedness. Binary relations are also symmetric, meaning that the order of the elements in the pair does not change the outcome, whereas other types of relations may be asymmetric or anti-symmetric. Lastly, binary relations are transitive, meaning that if element A is related to element B and element B is related to element C, then element A is also related to element C, whereas other types of relations may not exhibit this property.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
679
  • Set Theory, Logic, Probability, Statistics
2
Replies
35
Views
992
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
3
Views
989
Replies
3
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Back
Top