287 New groups

October 22, 2014

Starting Monday, you guys should be organized in new groups. No group can have three members that are together in the current groups. When I arrive on Monday, the groups should already be formed. You guys should start working on the laboratory on Polyhedra, Chapter 7. Make sure to bring whatever materials may be needed for this.

There have been complaints about not everybody contributing their share to their respective groups. This is not acceptable, but it is sadly the main reason for the reorganization. So: If I receive two complaints about a member not contributing as required, and there are no reasonable extenuating circumstances, that person will be dropped out of their group (receiving a zero in their current project as a result). If the issue is not expected to be resolved for the next report, a new reorganization of groups will be triggered as a result.

Also, I am unhappy with the level of some of the reports. It seems the peer reviewing of other groups’ drafts is not being taken as seriously as needed. So: Now, on the dates drafts are due, each group should bring three copies of their current draft. When you review another group’s draft, write the members of your group on the copy you are reviewing. I’ll collect the copies, with your comments, copy them for my records and return. If I identify something that a group should have noticed and mentioned, but did not, that group will be penalized (since this means the group did not take their refereeing role seriously). Conversely, if a group mentions something that should be addressed, but I do not see the issue resolved in the final report, the group that failed to address the given comments will be penalized.

Finally, this being a mathematics course, I expect your projects to include proofs. If a project lacks proofs it will receive a failing grade.

Feel free to contact me be email if any of the above needs clarifying.

Two model theory meetings

October 19, 2014

At the 2015 Joint mathematics meetings (JMM), January 10-13, in San Antonio, TX, there will be two special sessions on model theory.

The first is Beyond First Order Model Theory, a special session of the ASL and the AMS. See here for the schedule, list of speakers, and abstracts.

The second is Model Theory and Applications. See here for schedule, speakers, and abstracts.

The first session will be preceded by a conference (with the same title) at the University of Texas, San Antonio. Additional details can be found here, the speakers are Will Boney (University of Illinois at Chicago), H. Jerome Keisler (University of Wisconsin – Madison), Michael Makkai (McGill),  Maryanthe Malliaris (University of Chicago), Paul Larson (Miami University), Chris Laskowski (University of Maryland), and Sebastien Vasey (Carnegie Mellon).

414/514 References on continuous nowhere differentiable functions

October 19, 2014

Just as the last two times I have taught 414/514, I am assigning a final project on the topic of continuous nowhere differentiable functions (see here and here for the previous times).

The project requires that you choose an example of a continuous nowhere differentiable function, and to write a report describing the function, indicating who first introduced it, and presenting complete proofs of its continuity and nowhere differentiability. Additional information relevant for context is highly encouraged.

I am including links to two encyclopedic references on the subject. Feel free to follow the arguments there closely if needed, or to consult other sources, but make sure that what you turn in is your own version of the details of the argument, and that full details (rather than a sketch) are provided.

1. Johan Thim’s Master thesis (Continuous nowhere differentiable functions), written under the supervision of Lech Maligranda.
2. A.N. Singh’s short book on The theory and construction of non-differentiable functions. (See here for a short review.)

As I mentioned before,

Please take this project very seriously (in particular, do not copy details from books or papers, I want to see your own version of the details as you work through the arguments). Feel free to ask for feedback as you work on it; in fact, asking for feedback is a good idea. Do not wait until the last minute.

The project should be typeset and is due Wednesday, December 17 (though I strongly encourage you to turn it in earlier).

Please contact me by email as soon as you have chosen the topic you are going to cover, and I’ll list it here, to avoid repetitions.

414/514 Homework 2 – Monotone and Baire one functions

October 10, 2014

This set is due in three weeks, on Monday, November 3, at the beginning of lecture.

1. Let $f:[a,b]\to\mathbb R$ be increasing. We know that $f(x-)$ and $f(x+)$ exist for all $x\in[a,b]$, and that $f$ has at most countably many points of discontinuity, say $t_1,t_2,\dots$ For each $i$ let $I_i,J_i$ be the intervals $(f(t_i-),f(t_i))$ and $(f(t_i),f(t_i+))$. Some of these intervals may be empty, but for each $i$ at least one of them is not. (Here we follow the convention that $f(a-)=f(a)$ and $f(b+)=f(b)$.) Let $\mathrm{lh}(I)$ denote the length of the interval $I$, and say that an interval $(\alpha,\beta)$ precedes a point $t$ iff $\beta\le t$.

Verify that $\sum_i(\mathrm{lh}(I_i)+\mathrm{lh}(J_i))<+\infty$ and, more generally, for any $x$,

$s(x):=\sum\{\mathrm{lh}(I_i)\mid I_i$ precedes $f(x)\}$ $+\sum\{\mathrm{lh}(J_i)\mid J_i$ precedes $f(x)\}<+\infty$.

Define a function $f_0:[a,b]\to\mathbb R$ by setting $f_0(x)=f(x)-s(x)$. Show that $f_0$ is increasing and continuous.

Now, for each $n>0$, define $f_n:[a,b]\to\mathbb R$ so that $f_n\upharpoonright[a,t_n)=f_{n-1}\upharpoonright[a,t_n)$, $f_n(t_n)=f_{n-1}(t_n)+\mathrm{lh}(I_n)$, and $f_n(x)=f_{n-1}(x)+\mathrm{lh}(I_n)+\mathrm{lh}(J_n)$ for all $x\in(t_n,b]$. Show that each $f_n$ is increasing, and its only discontinuity points are $t_1,\dots,t_n$.

Prove that $f_n\to f$ uniformly.

Use this to provide a (new) proof that increasing functions are in Baire class one.

2. Solve exercise 3.Q in the van Rooij-Schikhof book: If $f:[a,b]\to\mathbb R$ is such that for all $x$, we have that $f(x-)$ and $f(x+)$ exist, then $f$ is the uniform limit of a sequence of step functions. The approach suggested in the book is the following:

Show that it suffices to argue that for every $\epsilon>0$ there is a step function $s$ such that $|f(x)-s(x)|<\epsilon$ for all $x$.

To do this, consider the set $A=\{x\in[a,b]\mid$ there is a step function $s$ on $[a,x]$ such that $|f(t)-s(t)|<\epsilon$ for all $t\in[a,x]\}$.

Show that $A$ is non-empty. Show that if $a\le y\le x$ and $x\in A$, then also $y\in A$. This shows that $A$ is an interval ${}[a,\alpha)$ or ${}[a,\alpha]$, with $\alpha\le b$. Show that in fact the second possibility occurs, that is, $\alpha\in A$. For this, the assumption that $f(\alpha-)$ exists is useful. Finally, show that $\alpha=b$. For this, use now the assumption that $f(\alpha+)$ exists.

3. (This problem is optional.) Find a counterexample to the following statement: If $f:[a,b]\to\mathbb R$ is the pointwise limit of a sequence of functions $f_1,f_2,\dots$, then there is a dense subset $X\subseteq [a,b]$ where the convergence is in fact uniform. What if $f$ and the functions $f_n$ are continuous?  Can you find a (reasonable) weakening of the statement that is true?

4. (This is example 1.1 in Andrew Bruckner’s Differentiation of real functions, CRM monograph series, AMS, 1994. MR1274044 (94m:26001).) We want to define a function $f:[0,1]\to\mathbb R$. Let $C$ be the Cantor set in ${}[0,1]$. Whenever $(a,b)$ is one of the components of the complement of $C$, we define $f(x)=(2(x-a)/(b-a))-1$ for $x\in[a,b]$. For $x$ not covered by this case, we define $f(x)=0$. Verify that $f$ is a Darboux continuous function, and that it is discontinuous at every point of $C$.

Verify that $f$ is not of Baire class one, but that there is a Baire class one function that coincides with $f$ except at (some of) the endpoints of intervals $[a,b]$ as above.

Verify that $f$ is in Baire class two.

414/514 Simple examples of Baire class one functions

October 6, 2014

Recall that a real-valued function $f$ defined on an interval $I$ is (in) Baire class one ($\mathcal B_1$) iff it is the pointwise limit of continuous functions.

Examples are continuous functions, of course, but functions in $\mathcal B_1$ do not need to be continuous. An easy example is the function $f:[0,1]\to\mathbb R$ given by $f(x)=0$ if $x\ne 1$ and $f(x)=1$ if $x=1$. This is the pointwise limit of the functions $f_n(x)=x^n$. By the way, an easy modification of this example shows that any function that is zero except at finitely many points is in $\mathcal B_1$.

Step functions are another source of examples. Suppose that $a=x_0 and that $s:[a,b]\to\mathbb R$ is constant on each $(x_i,x_{i+1})$. Then $s$ is the pointwise limit of the functions $s_k$, defined as follows: Fix a decreasing sequence $\epsilon_k$ converging to $0$, with $\epsilon_k\le 1/k$ and $2\epsilon_k for all $i$. Now define $\hat s_k$ as the restriction of $f$ to

$\displaystyle \{x_0,x_1,\dots,x_n\}\cup\bigcup_{i=0}^{n-1}[x_i+\epsilon_k,x_{i+1}-\epsilon_k]$,

and let $s_k:[a,b]\to\mathbb R$ extend $\hat s_k$ by joining consecutive endpoints of the components of its domain with straight segments.

An important source of additional examples is the class of derivatives. Suppose $f:\mathbb R\to\mathbb R$ and $f(x)=g'(x)$ for all $x$. This is the pointwise limit of the functions $f_n(x)$ given by

$f_n(x)=\displaystyle\frac{g\left(x+\frac1n\right)-g(x)}{\frac1n}.$

This simple construction does not quite work if $f$ is defined on a bounded interval (as $x+1/n$ may fall outside the interval for some values of $x$). We can modify this easily by using straight segments as in the case of step functions: Say $f:[a,b]\to\mathbb R$. For $n$ large enough so $1/n, define $f_n(x)$ as above for $x\in[a,b-1/n]$, and now set $f_n(b)=f(b)$ and extend $f_n$ linearly in the interval ${}[b-1/n,b]$.

Additional examples can be obtained by observing, first, that $\mathcal B_1$ is a real vector space, and second, that it is closed under uniform limits (the latter is not quite obvious). This gives us, for instance, that all monotone functions are in $\mathcal B_1$, since monotone functions are the uniform limit of step functions on bounded intervals: Given an increasing $f:[a,b]\to\mathbb R$, let $f_n(x)=\lfloor nf(x)\rfloor/n$. It follows that all functions of bounded variation are in $\mathcal B_1$, since any such function is the difference of two increasing functions.

Another interesting source of examples is characteristic functions. Given $X\subseteq\mathbb R$, the function $\chi_X$ is in $\mathcal B_1$ iff $X$ is both an $\mathbf F_\sigma$ and a $\mathbf G_\delta$ set.

On the other hand, $\chi_{\mathbb Q}$ is not in $\mathcal B_1$, since it is discontinuous everywhere while Baire class one functions are continuous on a comeager set.

Comparability of cardinals from Zorn’s lemma

September 26, 2014

One of the basic consequences of the axiom of choice is that any two sets are comparable, that is, there is an injection from one into the other. The standard argument for this uses that choice is equivalent to the well-ordering theorem: One can prove (without choice) that any two well-ordered sets are comparable, and the well-ordering theorem states that any set is well-orderable.

If for some (foolhardy) reason (say, one is teaching an analysis or algebra course) one is interested in the result, but wants to avoid discussing the theory or well-orders, it seems desirable to have a proof based directly on Zorn’s lemma.

A few weeks ago, Sam Coskey and I found ourselves discussing such a proof. It turns out the argument, though not as well-known as may be expected, dates back at least to Chaim Samuel Hönig, and his short note Proof of the well-ordering of cardinal numbers, Proc. Amer. Math. Soc., 5, (1954), 312. MR0060558 (15,690a). It goes as follows: Let the sets $A$ and $B$ be given. Consider the collection of all partial injections $f$ from $A$ into $B$. That $f$ is partial means that there is a $C\subseteq A$ such that $f:C\to B$. Order this collection by extension: $f\le f'$ iff $f\subseteq f'$. This poset satisfies the conditions of Zorn’s lemma, so it admits maximal elements. One easily verifies that, if $f$ is maximal, then $A$ is the domain of $f$, or $B$ is its range. In either case, this gives us an injection from one of the sets into the other.

A natural extension of the idea allows us to recover that the class of cardinals is not just linearly ordered, but in fact well-ordered, but an additional use of the axiom of choice is needed now (namely, in the form: The product of non-empty sets is non-empty). Suppose first that $\mathcal C$ is a set. We argue that one of the members of $\mathcal C$ injects into all others. The proof is essentially the same as before: Let $A\in \mathcal C$, and consider the family of all sequences $(f_B\mid B\in\mathcal C)$ such that for some $A'\subset A$ and all $B$, we have that $f_B:A'\to B$ is injective. This is a partial order under coordinatewise inclusion. Again, Zorn’s lemma applies, so there is a maximal element $\vec f=(f_B\mid B\in \mathcal C)$; call $A'$ the common domain of all the $f_B$. If $A'=A$, we are done. Else (and this is where the additional use of choice comes in), for some $B$, the range of $f_B$ is $B$: Otherwise, we can pick $a'\in A\setminus A'$ and a sequence $(b_B\mid B\in\mathcal C)$ such that, for all $B$, $b_B\in B\setminus f_B[A']$. But then, setting $f'_B=f_B\cup\{(a',b_B)\}$, we see that $(f'_B\mid B\in\mathcal C)$ contradicts the maximality of $\vec f$. The result follows: Letting $B$ be such that $f_B$ is onto, we see that $B$ injects into $A'$, and $A'$ injects into all sets in $\mathcal C$.

Finally, consider a (proper) class $\mathcal C$. Again, fix $A\in\mathcal C$. Let $\mathcal C'$ be the collection of subsets of $A$ equipotent to sets in $\mathcal C$. Since $\mathcal C'$ is a set, the previous analysis applies, and we can find a $C\in \mathcal C$ that injects into all members of $\mathcal C$ that inject into $A$. It follows that $C$ actually injects into all members of $\mathcal C$. Otherwise, there is a $B\in\mathcal C$ that $C$ does not inject into. But then $B$ itself injects into $C$, and therefore into $A$. But this means that $C$ injects into $B$ after all.

Coming attractions

September 26, 2014