Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

I have been recently studying relations and mappings and I have come across the following problem. Consider two non empty finite sets $I,J$ and their cartesian product $I\times J$. Let $f\colon I\times J\to I\times J$ be some bijection. Suposse now, that $|I|=n\in\mathbb{N}$ and let $i_1,i_2,\dots,i_n$ be the elements of $I$. For each $1\leq j\leq n$ define $$ A_j=\{a\in I; (\exists j_1,j_2\in J)\ [f((i_j,j_1))=(a,j_2)]\} $$ My question is, does now necessarily exists a bijection $g\colon I\to I$ such that $g(i_j)\in A_j$ for every $j=1,2,\dots,n$? I would appreciate any help with this, as I am really stuck. Thanks.

share|cite|improve this question
up vote 0 down vote accepted

For a particular j, Aj is just the projection of f(ij x J) back on I.

Every element of I must appear in some Aj because f is a bijection: if ik is not in any Aj then ik x J cannot appear in the mapping by f from I x J to I x J.

So you can choose (without AofC because the sets are finite) a sequence of elements from I such that each belongs to the correspondinlgy sequenced Aj.

Therefore you can map the the original sequence of elements to this new sequence by a bijection (permutation) g and then have g(ij) an element of Aj

(must learn how to do the mark-up sometime).

share|cite|improve this answer
Actually the third step needs a little more justification. We need to establish that elements of any subset of k elements of I occur in at least k different sets Aj. Let |J| = m and let Bj be the sets f(ij x J): each set Bj contains exactly m elements and the k elements of I must map to k.m different elements (because f is a bijection) so that there cannot be less than k sets Bj containing them. Then project Bj to Aj and there must be k different Aj. – Tom Collinge Feb 25 '14 at 14:17

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.