Generic Elements of a Set.

Mild Motivation: In writing a post about the Baire Category Theorem, I learned the neat fact that a "generic" $f\in C^{0}([a,b], {\mathbb R})$ was nowhere differentiable and not monotone on any subinterval. The term "generic" was defined as follows: if $A$ is the complement of a meagre set and all points in $A\subseteq X$ for $X$ some space share some property, then the property is said to be generic of the set.

Question: How standard is this definition of generic, and how useful is it to talk about something which is generic of a set?

To expand on this last part a bit: a generic real number is an irrational number (since the rationals are not comeagre) so what does this tell us about the real numbers? If we were to prove something for just a generic element, how would we describe this (as in, for a set of measure zero we say, "almost everywhere," --- would we say something is true "up to a meagre set")?

• dyinglovegrape.wordpress.com/2012/01/05/baire-category-theorem The relevant section is "a surprising result." – user2959 Jan 6 '12 at 14:39
• Wikipedia: Generic property – Martin Sleziak Jan 6 '12 at 16:03
• Haha, I'll just note (so as to not look so lazy) that I did search wikipedia first, but because the references were few and recent, I wasn't sure how standard the term was! – user2959 Jan 6 '12 at 16:26

The following is a fairly well-known result: If a function is monotone on an interval, then the function is a.e. (finitely) differentiable on the interval. From this it follows that every nowhere differentiable function also fails to be monotone on every interval. In fact, the much weaker result monotone on an interval implies differentiability on a nonempty subset of the interval would be enough. For a glimpse at several more nuanced notions, see the following paper (freely available on the internet):

Jack B. Brown, Udayan B. Darji, and Eric P. Larsen, Nowhere monotone functions and functions of nonmonotonic type, Proceedings of the American Mathematical Society 127 (1999), 173-182. http://www.auburn.edu/~brownj4/jbamsla.pdf

The terms first category and second category are due to Baire (around 1899), and the terms meager and residual are due to Bourbaki. The term co-meager is also used for residual, although I don't know its origin. Denjoy introduced the term residual around 1912 or 1913. I believe he was trying to distinguish between when a set is second category (i.e. the set is big) and when the set has a first category complement (i.e. the set is so big that what's left over is small). During this period some authors (most people, including Baire and Lebesgue) used "second category" for "not first category", while a few authors (Lusin, Schönflies, Hobson come to mind) used "second category" for "residual". Then, to further muddy the waters, when "second category" meant "not first category" for an author, quite often that author would use second category in the statement of a theorem, but then wind up proving the set was actually residual. (This last thing still happens, especially in areas of math that are not very close to topology or analysis.)

The term "generic" is also commonly used for "residual", but I don't know the origin of this term off-hand. Incidentally, I've come across some instances (I think the papers were in dynamical systems theory and/or differential geometry) where an author uses "generic" to mean "open dense set" (i.e. the complement is not just first category, it's actually nowhere dense), or perhaps more generally, "contains an open dense set".

Finally, in some literature (especially in real analysis), the term typical property refers to a property that holds for a residual set of elements. The term probably originated with Andrew M. Bruckner in a 1973 Amer. Math. Monthly paper. (Bruckner told me back in 1992 or 1993 that he made up this term for his 1973 Monthly paper, and since then I have not come across an earlier appearance of of "typical" for this property.)

An interesting feature of typical properties (residual properties, generic properties, etc.) is that any countable conjunction (intersection) of typical properties is a typical property. This follows easily from the fact that a countable union of first category sets is a first category set. Thus, you can collect together countably many typical properties of (say) a continuous function defined on $[0,1]$ (sup norm), and it will follow that the typical continuous function simultaneously has all of these properties. This is often useful in proofs that a certain property is typical. For example, if you can show that the typical continuous function has some property at any specified point, then it automatically follows that the typical continuous function has this property on any specified countable set, and hence the typical continuous function has this property on a set dense in the reals. For another example, if you can show that the typical continuous function has some property at any specified subinterval (thus, the function can wiggle a lot or be nice, as needed, elsewhere), then it automatically follows that the typical continuous function has this property on every subinterval.

Over the years I've posted (mostly in sci.math) a huge number of lesser known applications of the Baire category theorem. To find these, google in sci.math (or just do a web search) for "Renfro" along with appropriate terms such as "first category", "Baire category", "residual", "generic", etc.

(Later) What follows is largely taken from some sci.math posts I made on 16 June 2006.

The theorem below was known by 1933. All of the results in this theorem have been significantly strengthened in several directions since then.

Let $C\left({\mathbb R}\right)$ be the collection of continuous functions $f:{\mathbb R} \rightarrow {\mathbb R}$ with the sup metric.

$d_{L}$ and $d_{R}$ are the left and right lower Dini derivates

$D_{L}$ and $D_{R}$ are the left and right upper Dini derivates

The function and the point are suppressed in this notation because both will be clear from context.

Theorem: There exists a co-meager subset $P$ of $C\left({\mathbb R}\right)$ such that for each $f \in P$ we have the following:

(1) At each $x \in {\mathbb R}$ we have $(d_{L} = -\infty$ or $d_{R} = -\infty)$ and $(D_{L} = +\infty$ or $D_{R} = +\infty).$

(2) At each $x \in {\mathbb R}$ we have $(d_{L} = -\infty$ or $D_{L} = +\infty)$ and $(d_{R} = -\infty$ or $D_{R} = +\infty).$

(3) For all $x$ not belonging to some set of measure zero, we have $(d_{L} = d_{R} = -\infty)$ and $(D_{L} = D_{R} = +\infty).$

(4) Each of the following $4$ sets is such that its intersection with each open interval in $\mathbb R$ has cardinality $c$:

$$S_{1} = \{x: d_{L} = D_{L} = -\infty\}$$

$$S_{2} = \{x: d_{L} = D_{L} = +\infty\}$$

$$S_{3} = \{x: d_{R} = D_{R} = -\infty\}$$

$$S_{4} = \{x: d_{R} = D_{R} = +\infty\}$$

Property (1) says that for each point and for each sign (negative or positive), there exists a side (left or right) such that $f$ has an infinite Dini derivate at that point on that side with that sign. Thus, at each point there exists a sequence approaching that point giving rise to difference quotients based at that point that approach $-\infty,$ and at the same point there exists a sequence approaching that point giving rise to difference quotients based at that point that approach $+\infty.$ (For each choice of sign, however, we are not assured of being able to pick both sequences so that they lie on the same side of the point.) Alternatively, one says that at each point, the bilateral lower derivative is $-\infty$ and the bilateral upper derivative is $+\infty.$ In particular, at each point there does not exist a finite or an infinite bilateral derivative. Property (1) was proved by V. Jarnik in 1933.

Property (2) says that for each point and for each side (left or right), there exists a sign (negative or positive) such that f has an infinite Dini derivate at that point on that side with that sign. Thus, at each point there exists a sequence approaching that point from the left giving rise to difference quotients based at that point that are unbounded, and at the same point there exists a sequence approaching that point from the right giving rise to difference quotients based at that point that are unbounded. (For each choice of side, however, we are not assured of being able to pick both sequences so that the difference quotients are unbounded in the same way, both unbounded from above or both unbounded from below.) In particular, at each point there does not exist a finite unilateral derivative. Property (2) was proved by Banach and Mazurkiewicz (independently) in 1931.

Property (3) says that Properties (1) and (2) occur simultaneously almost everywhere in the sense of Lebesgue measure. In particular, at almost every point, $f$ has no finite or infinite unilateral derivative. Property (3) was proved by V. Jarnik in 1933.

Incidentally, the measure zero exceptional set in Property (3) was shown by K. M. Garg in 1970 to also be meager in $\mathbb R.$ Later, L. Zajicek showed the exceptional set was $\sigma$-porous in a very strong way; strong enough so that, given any Hausdorff measure function $h$, one can then choose the co-meager subset of $C\left({\mathbb R}\right)$ so that this exceptional set has zero Hausdorff $h$-measure. [Note what is claimed. The Hausdorff measure function $h$ has to be specified prior to obtaining the corresponding co-meager subset of $C\left({\mathbb R}\right)$.]

Property (4) says that $f$ has each of the $4$ possibilities for an infinite unilateral derivative realized on a set of points that is $c$-dense in $\mathbb R.$ [Note that the possibility of such points is not excluded by (1), (2), and (3).] Property (4) was proved by S. Saks in 1932.

One way that I've come up with conceptualizing these results is to view Properties (1) and (2) as sign and side types of pathology (respectively), with Property (3) saying that both types occur almost everywhere, and Property (4) being a sort of Heisenberg uncertainty principle at work that prevents us from co-meagerly having both sign and side pathology occurring on sets that are too large. [Actually, no continuous function can have Property (3) hold throughout an open interval, or even co-countably throughout an interval.]

In the case of almost all continuous functions in the sense of Wiener measure:

Dvoretzky/Erdos/Kakutani (1961) proved Property (1).

Paley/Wiener/Zygmund (1933) proved Property (2).

Foschini/Mueller (1970) proved Property (3).

Karoly Simon (1989) and (independently) S. A. Shkarin (1994) proved Property (4).

In 1984, Masatoshi Fukushima introduced a notion of "super-Wiener almost everywhere" (which he called "quasi everywhere") and proved Property (2) for this stronger largeness notion. Related results were proved by Masayoshi Takeda in 1984 and David Mathew Penrose in 1988 (University of Edinburgh Ph.D. Dissertation).

Gandini/Zucco (1989), Valeriu Anisiu (1993), and Renfro (1993 Ph.D. Dissertation) proved some or all versions of Properties (1) through (4) for almost all in the sense of $\sigma$-porosity. [I proved preponderant derivate versions of all of all 4 properties, along with certain positive lower density versions for the symmetric derivative and the Zygmund-smooth notion, for a very strong liminf version of $\sigma$-porosity.]

Brian Hunt (1994) proved that all but a Haar null set of continuous functions fail to have a finite bilateral derivative at each point. In fact, he proved that at each point, no bilateral pointwise Hölder condition holds at that point.

Jan Kolár (2001) proved some non-differentiability results for all but an HP-small set of continuous functions. This is a notion of smallness that he introduced (in his Ph.D. work under L. Zajicek) that is a proper strengthening of being simultaneously $\sigma$-porous (in a rather strong way) and Haar null.

• I wasn't aware of all of this madness! I'd been told that "first category" and "second category" can get a bit muddy (and I was told to avoid using them and to use meagre, etc.). Also, thank you for letting me know about your applications of Baire. I'm a huge fan of giving tons and tons of examples when I go over a theorem with students, so this will help tremendously. – user2959 Jan 6 '12 at 16:25

The definition in Kechris' Classical Descriptive Set Theory [1, p. 42] this is the given definition of generic as a property holding for a co-meager set. I would say that this is indeed the standard definition, as Kechris is where most people are likely to take their descriptive set theory from.

Do note that the term is closely related to forcing (in the set theoretical sense) as a generic filter meets every dense subset of the forcing poset.

Indeed as you say, to be an irrational number is indeed a generic property as being a transcendental number.

Bibliography:

1. A.S. Kechris, Classical descriptive set theory, Springer, 1995.
• Just to clarify: descriptive-set-theory tag was added by me. (Basically because of use of the term generic in the question and, to my knowledge, the meaning from descriptive theory is used quite frequetly.) It was not in the original post. – Martin Sleziak Jan 6 '12 at 16:03
• Thank you, this text seems quite helpful so far! – user2959 Jan 6 '12 at 16:12
• @Martin: Yes, I saw that. Regardless, your tagging was correct and this is the context I'd have read the question anyway. – Asaf Karagila Jan 6 '12 at 16:14

It has no strict definition. Depending on the context, this can mean "except for a meager set", "except for a zero measure set" etc. "A generic real number" can be stated also in terms of cardinality: rationals have countable cardinality which is strictly less than the cardinality of the set of the reals.

• Any countable set has measure $0$, so your last example is a special case of the one before it. – Alex Becker Jan 6 '12 at 14:42
• For the cardinality thing, I'm not sure how far that would extend --- it seems like one could come up with some set which had strictly greater cardinality than another, but wasn't comeagre or of measure zero. – user2959 Jan 6 '12 at 14:57