# Bijection on a component of a cartesian product

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.

-

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).

-
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