Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

{(A,B) : A, B ⊆ X, there is a bijective f : A → B}, X is limited.

I have to show if this is (for proving that's an equivalence relation):
$R ⊆ X \times X$
I) reflexive (if $∀x ∈ X : (x, x) ∈ R$)
II) symmetrical (if $∀x,x' ∈ X : (x, x') ∈ R ⇒ (x,x') ∈ R$)
III) transitive (if $∀x, x', x'' ∈ R : (x, x') ∈ R (x',x'') ∈ R ⇒ (x, x'') ∈ R$)

Alright, I understand what and how I have to do it, but somehow not with this task.

Maybe someone could show me how to transform the very first line into something I can work on. I'm also a little confused about that $R⊆X \times X$ thing. It's A, B ⊆ X and I'm afraid that my 3 points I have to show can't be applied that easily on my task.

share|cite|improve this question
The relation is on the set of subsets of $X$, in fact it is a subset of $\mathcal{P}(X)\times\mathcal{P}(X)$. – egreg Apr 26 '13 at 13:05
@egreg So would it be R ⊆ A x B in this case? – nullmoon Apr 26 '13 at 13:07
No, $R\subseteq\mathcal P(X)\times\mathcal P(X)$, and if $A,B\subseteq X$ (that is, $A,B\in\mathcal P(X)$), then $(A,B)$ might be an element of $R$. – Berci Apr 26 '13 at 13:08
up vote 4 down vote accepted

For this particular relation $R$, we have two base sets, one is $X$, its subsets are the 'elements' among which $R$ is interpreted, so the base set of $R$ now is the power set $\mathcal P(X)$, that is, $R\subseteq \mathcal P(X)\times\mathcal P(X)$.

You need to show that, for all $A,B,C\in\mathcal P(X)$:

  1. $(A,A)\in R$, i.e. there is a bijection $A\to A$.
  2. If there is a bijection $A\to B$, then there is one $B\to A$.
  3. If there are bijections $A\to B$ and $B\to C$, then there is one $A\to C$.
share|cite|improve this answer
Thank you, I'll try it now as I am sure I understand everything I need to continue. – nullmoon Apr 26 '13 at 13:25
Sets as $A=\{1,2\}$ to show 'something like this'.. What do you mean? – Berci Apr 26 '13 at 14:08
Doesn't matter now, I thought I had to show it by an example of numbers, but it was my mistake thinking this. Thanks anyway. :) – nullmoon Apr 26 '13 at 14:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.