mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, particularly in

set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...

, Fodor's lemma states the following: If

\kappa

is a regular,

uncountable In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal numb ...

cardinal Cardinal or The Cardinal may refer to: Animals * Cardinal (bird) or Cardinalidae, a family of North and South American birds **''Cardinalis'', genus of cardinal in the family Cardinalidae **''Cardinalis cardinalis'', or northern cardinal, the ...

S

is a stationary subset of

\kappa

, and

f:S\rightarrow\kappa

is regressive (that is,

f(\alpha)<\alpha

for any

\alpha\in S

\alpha\neq 0

) then there is some

\gamma

and some stationary

S_0\subseteq S

such that

f(\alpha)=\gamma

for any

\alpha\in S_0

. In modern parlance, the nonstationary ideal is ''normal''. The lemma was first proved by the Hungarian set theorist, Géza Fodor in 1956. It is sometimes also called "The Pressing Down Lemma".

Proof

We can assume that

0\notin S

(by removing 0, if necessary). If Fodor's lemma is false, for every

\alpha<\kappa

there is some

club set In mathematics, particularly in mathematical logic and set theory, a club set is a subset of a limit ordinal that is closed under the order topology, and is unbounded (see below) relative to the limit ordinal. The name ''club'' is a contraction o ...

C_\alpha

such that

C_\alpha\cap f^(\alpha)=\emptyset

. Let

C=\Delta_ C_\alpha

. The club sets are closed under

diagonal intersection Diagonal intersection is a term used in mathematics, especially in set theory. If \displaystyle\delta is an ordinal number and \displaystyle\langle X_\alpha \mid \alpha<\delta\rangle is a

, so

C

is also club and therefore there is some

\alpha\in S\cap C

. Then

\alpha\in C_\beta

for each

\beta<\alpha

, and so there can be no

\beta<\alpha

such that

\alpha\in f^(\beta)

, so

f(\alpha)\geq\alpha

, a

contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

. Fodor's lemma also holds for

Thomas Jech Thomas J. Jech ( cs, Tomáš Jech, ; born January 29, 1944 in Prague) is a mathematician specializing in set theory who was at Penn State for more than 25 years. Life He was educated at Charles University (his advisor was Petr Vopěnka) and from 2 ...

's notion of stationary sets as well as for the general notion of stationary set.

Fodor's lemma for trees

Another related statement, also known as Fodor's lemma (or Pressing-Down-lemma), is the following: For every non-special tree

T

and regressive mapping

f:T\rightarrow T

(that is,

f(t), with respect to the order on T, for every t\in T), there is a non-special subtree S\subset T on which f is constant.

References

* G. Fodor, Eine Bemerkung zur Theorie der regressiven Funktionen, ''Acta Sci. Math. Szeged'', 17(1956), 139-14

* Karel Hrbacek & Thomas Jech, ''Introduction to Set Theory'', 3rd edition, Chapter 11, Section 3. * Mark Howard, ''Applications of Fodor's Lemma to Vaught's Conjecture''. Ann. Pure and Appl. Logic 42(1): 1-19 (1989). * Simon Thomas, ''The Automorphism Tower Problem''.

PostScript PostScript (PS) is a page description language in the electronic publishing and desktop publishing realm. It is a dynamically typed, concatenative programming language. It was created at Adobe Systems by John Warnock, Charles Geschke, Doug Br ...

file a

* S. Todorcevic, ''Combinatorial dichotomies in set theory''.

pdf Portable Document Format (PDF), standardized as ISO 32000, is a file format developed by Adobe in 1992 to present documents, including text formatting and images, in a manner independent of application software, hardware, and operating systems. ...

a

{{Set theory Articles containing proofs Lemmas in set theory