Let A be a finite set of size k and R a relation on the power set P(A) defined by R={(A,B):|A|=|B|}l. Show that A is an equivalence relation. Let a in A. What is the size of the equivalence class of {a}? Let a,b be two different elements of A. What is the size of the equivalence class of {a,b}?

Jayvion Caldwell

Jayvion Caldwell

Answered question

2022-07-17

Let A be a finite set of size k and R a relation on the power set P(A) defined by R = { ( A , B ) : | A | = | B | }
1. Show that A is an equivalence relation.
2. Let a A. What is the size of the equivalence class of {a}?
3. Let a,b be two different elements of A. What is the size of the equivalence class of {a,b}?

Answer & Explanation

grocbyntza

grocbyntza

Beginner2022-07-18Added 25 answers

Step 1
There are three criteria that must be followed in order to prove R is an equivalence relation,
1. Reflexive
2. Symmetric
3. Transitive
Step 2
To get you started, with generic sets B , C , D P ( A ), see that we always have | B | = | B |
so R is reflexive. This would mean ( B , B ) R for some B A
To show it's symmetric, it requires you to show that if | B | = | C | , then | C | = | B | .
To show it's transitive, it requires you to show if | B | = | C | , and | C | = | D | , then | B | = | D |
Nash Frank

Nash Frank

Beginner2022-07-19Added 10 answers

Step 1
Informally, under this equivalence relation two subsets are equivalent when they have the same size.
Thus, the equivalence class of {a} consists of all subsets of A with cardinality/size equal to one.
Thus the size of this equivalence class is k = | A | .
Step 2
The equivalence class of {a,b} consists of all two element subsets of A. Thus the size of this equivalence class is ( k 2 ) = k ( k 1 ) 2

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?