Can the size of any E-class be either 9 or 99?

[bedi]

Homework Statement

Let A be the set of all subsets of {1,2,...,99} and E an equivalence
relation on A. Can the size of any E-class be either 9 or 99?

Homework Equations

The Attempt at a Solution

I think yes but can't see how...

 

[mfb]

How many subsets of A are there?

If you want to define an equivalence relation where each class has 9 members, how many equivalence classes do you get? Does that make sense?

 

[Ray Vickson]

How many subsets of A are there?

If you want to define an equivalence relation where each class has 9 members, how many equivalence classes do you get? Does that make sense?

Much depends on the meaning of "any" in the question "Can the size of any E-class be either 9 or 99?" You seem to be assuming that "any" = "every", but maybe the question wants to know if anyone (but not all) of the equivalence classes can have size 9 (or 99).

 

[mfb]

I thought about that, but that would make the question weird and (imho) pointless.

 

[I like Serena]

The only relevancy that I see, is as an exercise to understand the definitions of equivalence relations and of equivalence classes.

bedi, can you give an example of an equivalence relation on A?
And more to the point, can you give an example of an equivalence relation that has an equivalence class of size 9?

 

[bedi]

bedi, can you give an example of an equivalence relation on A?
And more to the point, can you give an example of an equivalence relation that has an equivalence class of size 9?

As an example of an equivalence relation on A:
Provided X,Y are elements of A, X≈Y iff either X is a subset of Y or Y is a subset of X. In view of this relation ≈ every element of A is related, right?
But I cannot find an equivalence relation that has an equivalence class of size 9... And cannot see why it is impossible.

 

[I like Serena]

Good. That is indeed an equivalence relation.
One that has only 1 equivalence class, which is A.

What about the relation given by the set of pairs:
{(a,a) : a in A} + {({2},{2}), ({2},{3}), ({3},{2}), ({3},{3})}.

Is it an equivalence relation on A?
If so which equivalence classes does it contain?

 

[bedi]

Yes I think this is an equivalence relation on A. And the equivalence classes are:
[1]={{1}}, [2]={{2},{3}}, [3]={{3}}. Actually I'm not sure if an equivalence relation on any given set must say something about all the elements of the set. For instance in this eq. relation we do not have [4], is this a problem?

 

[I like Serena]

Actually, you'd have [3]={{2},{3}}.
And so {{2},{3}} is the corresponding equivalence class of size 2.

From wiki:

A given binary relation ~ on a set A is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive.
Equivalently, for all a, b and c in A:

1. a ~ a. (Reflexivity)
2. if a ~ b then b ~ a. (Symmetry)
3. if a ~ b and b ~ c then a ~ c. (Transitivity)

​

So yes, each element a in A must at least have an equivalence relation with itself.Now, can you think of an equivalence relation on A that contains an equivalence class of size 9?

 

[bedi]

On the other hand, mfb asked that "if you want to define an equivalence relation where each class has 9 members, how many equivalence classes do you get?" and since equivalence classes are also a partition on A, we have to have 2^99/9 classes in this case, which is not possible. Correct?

 

[I like Serena]

On the other hand, mfb asked that "if you want to define an equivalence relation where each class has 9 members, how many equivalence classes do you get?" and since equivalence classes are also a partition on A, we have to have 2^99/9 classes in this case, which is not possible. Correct?

Correct. ;)

 

[bedi]

Thank you, you are so helpful!

 

[I like Serena]

Btw, I concur with Ray that this is not what the problem asks.

The problem asks for "any", and not for "every" or "each".
I interpret it that it suffices if there is just a single equivalence class of size 9.

 

[bedi]

Alright, that can happen right? Why not?

 

[I like Serena]

To properly answer the question, you have to give a specific example, and prove that it is indeed an equivalence relation.

But yeah, it can happen. ;)

 

[mfb]

Well, it is trivial.

Spoiler

Take any 9 elements of A, let them be in the same equivalence class, ignore the other elements (apart from the required M~M for every element of A).

It is not an interesting equivalence relation, but that was not requested.

As an example of an equivalence relation on A:
Provided X,Y are elements of A, X≈Y iff either X is a subset of Y or Y is a subset of X. In view of this relation ≈ every element of A is related, right?

I don't see how this is an equivalence relation.

{1,2}~{1}~{1,3}, but not {1,2}~{1,3}