(Mishnah): If two women were captured and each says 'I was captured but I am Tehorah', they are not believed;

If each testifies that the other is Tehorah, they are believed.

Similarly, if each of two men says 'I am a Kohen', they are not believed. If they also testify about each other, they are believed;

(Gemara could have citing R. Yochanan): Our Mishnah discusses Kodshei ha'Gevul (Terumah), but for lineage (for marriage) and Kodshei Mizbe'ach, two witnesses are needed.

Question (Beraisa): We establish Kehunah, Leviyah and Yisrael based on one witness;

Granted, Kehunah and Leviyah (need not refer to lineage or Kodshei Mizbe'ach. They could refer to Terumah and Ma'aser). However, is not Yisrael for lineage?!

Answer: [No, Yisrael] is to give to him Ma'aser Oni.

There are two matters [that establish] Kehunah in Eretz Yisrael - giving Birkas Kohanim, and receiving [Terumah] at the granaries.

In Surya, Birkas Kohanim [establishes Kehunah], but not receiving at the granaries (it is only mid'Rabanan, so people do not check so well that the recipient is a Kohen). This is up to the place that messengers about [which day was declared] Rosh Chodesh reach, i.e. until Namarin. (There is a Beis Din to accept the messengers, and they check lineage to allow Birkas Kohanim.) And Bavel is like Surya;

R. Shimon ben Elazar says, even in Alexandria, when Beis Din sits there [is like Surya].