Let A be A set of n Distinct Elements.

In summary: They are just asking you to compute the number of subsets of A X A in 3 different ways. The first specifiies no condition, the 2nd and 3rd give you some restrictions.
  • #1
nowimpsbball
15
0
Let A be a set of n distinct elements. There is a one to one correspondence between binary relations on the set A and subsets R<= A x A
a. Computer the number of binary realtions on A
b. A binary relation R is said to be symmetric if for every (a,b) in R, (b,a) is also in R. Compute the number of symmetric binary relations on A.
c. A binary relation R is said to be antisymmetric if for every (a,b) in R (a doesn't equal b), (b,a) is not in R. Compute the number of antisymmetric binary relations on A




Really no equations to my knowledge, a Discrete Math course.



I am really having a hard time getting off the ground on this one, and I don't know why...I am thinking/hoping this problem is easier than I am making it out to be...I tend to over think a lot

Thanks, any hints/suggestions/solutions would be greatly appreciated.
 
Physics news on Phys.org
  • #2
They are just asking you to compute the number of subsets of A X A in 3 different ways. The first specifiies no condition, the 2nd and 3rd give you some restrictions.
 
  • #3
nowimpsbball said:
Let A be a set of n distinct elements. There is a one to one correspondence between binary relations on the set A and subsets R<= A x A
a. Computer the number of binary realtions on A

You are told that "there is a one to one correspondence between the collection of binary relations and the collection of subsets of A- there are the same number. Okay, do you know a (simple) formula for the number of subsets? If not think about it this way: The empty set has 1 subset: itself. set with exactly one element, {a}, has two subsets: {a} and {}. A set with 2 elements, {a,b}, has {}, {a}, {b}, {b}: four subsets. A set with 3 elements {a, b, c} has... Instead of listing them all, think of it this way: if we remove c, we have two elements, a, b, left and we know that has 4 subsets. Okay, those subsets are also subsets of {a,b,c}. Any other subset must contain c: and, in fact, is exactly a subset without to which we have added c: there are, again, 4 of those: the set {a,b,c} has 4 subsets that contain c and 4 that do not: it has 4+ 4= 8 subsets. What about {a,b,c,d}? Again, every subset either contains d or does not. Removing d, we have 3 elements left- there are 8 such subsets. Every subset that does contain d, is just one of those that do not contain d, with d added! There are, again, 8 of those: {a,b,c,d} has 8+ 8= 16 elements. Do you see how we are doubling each time?

b. A binary relation R is said to be symmetric if for every (a,b) in R, (b,a) is also in R. Compute the number of symmetric binary relations on A.
c. A binary relation R is said to be antisymmetric if for every (a,b) in R (a doesn't equal b), (b,a) is not in R. Compute the number of antisymmetric binary relations on A
Really no equations to my knowledge, a Discrete Math course.



I am really having a hard time getting off the ground on this one, and I don't know why...I am thinking/hoping this problem is easier than I am making it out to be...I tend to over think a lot

Thanks, any hints/suggestions/solutions would be greatly appreciated.
 

1. What is a set?

A set is a collection of distinct and well-defined objects, called elements. Each element in a set is unique and there is no specific order to the elements.

2. What are distinct elements in a set?

Distinct elements in a set refer to objects or values that are different from each other. In other words, there are no duplicate elements in a set.

3. What is the cardinality of a set?

The cardinality of a set is the number of elements in the set. In the case of set A with n distinct elements, the cardinality is n.

4. How is a set represented?

A set can be represented in a variety of ways, such as using curly braces { } or using set-builder notation. For example, set A can be represented as {a, b, c} or {x | x is an integer and x < 5}.

5. What is the significance of "Let A be a set of n distinct elements" in mathematics?

This statement is often used in mathematics to define a set and its elements. It is a way of establishing the properties and characteristics of a set before performing operations or making statements about it.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
452
  • Calculus and Beyond Homework Help
Replies
1
Views
533
  • Calculus and Beyond Homework Help
Replies
3
Views
763
  • Calculus and Beyond Homework Help
Replies
3
Views
467
  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
462
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
351
Back
Top