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

I am reading the paper here and have a small doubt in Lemma 1. The proof (on page 1) begins with:

Lemma 1. Let $M$ and $N$ be cardinal numbers. Let $S$ be $N$-regular in $X$, a set of cardinality $M$, and let $T$ be $N^M$-regular in $Y$. Then if $S\otimes T$ is N-regular in $X\times Y$.

Proof: Let $P$ be a set of cardinality $N$. Then a partition of $X \times Y$ into $N$ parts can be represented by a function from $X \times Y$ into $P$. For each $y \in Y$, $f$ defines a function $f_y$ from $X$ into $P$ given by $f_y(x) = f(x,y)$. Since there are $N^M$ such functions the mapping $y \rightarrow f_y$ induces a partition of $Y$ into $N^M$ parts.

My doubt is that the proof should not the proof say "Since there are at least $N^M$ such functions the mapping $y \rightarrow f_y$ induces a partition of $Y$ into at least $N^M$ parts." since each of the $N^M$ functions from $X$ to $P$ may correspond to more then 1 $f_y$.

If my doubt is correct (and I expect that the proof will still go through) then should small omissions like this not be entirely unexpected in research papers. I am asking this because I have little experience in reading research papers.

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

The point is that the entire set of functions from $X$ to $P$ has cardinality $N^M$, since $|X|=M$ and $|P|=N$. Let $\mathscr{G}$ be the set of these functions. For each $g\in\mathscr{G}$ let $Y_g=\{y\in Y:f_y=g\}$. Then $\mathscr{P}=\{Y_g:g\in\mathscr{G}\}$ is a partition of $Y$ into $|\mathscr{G}|=N^M$ parts. (Actually, some of these parts may be empty, so if your definition of partition doesn’t allow you to count empty parts, you should say that $\mathscr{P}$ is a partition of $Y$ into at most $N^M$ parts.)

It’s perfectly true that there may be distinct $y_0,y_1\in Y$ such that $f_{y_0}=f_{y_1}$, but that just says that $f_{y_0}$ and $f_{y_1}$ belong to the same part of $\mathscr{P}$. There is no possibility that $\mathscr{P}$ has more than $N^M$ parts, since $\mathscr{G}$ has only $N^M$ members.

As for what you can expect from research papers: just about anything. Sometimes quite substantial details are silently left to the reader. Sometimes there are small errors. Very occasionally there are major errors. Expect to have to fill in a fair number of details. Don’t jump to the conclusion that something is wrong if it doesn’t at first seem straightforward, but bear in mind the possibility of small oversights, typos, etc.

share|cite|improve this answer

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.