502 – Cantor-Bendixson derivatives

November 8, 2009

Given a topological space X and a set B\subseteq X, let B' be the set of accumulation points of B, i.e., those points p of X such that any open neighborhood of p meets B in an infinite set.

Suppose that B is closed. Then B'\subseteq B. Define B^\alpha for B closed compact by recursion: B^0=B, B^{\alpha+1}=(B^\alpha)', and B^\lambda=\bigcap_{\alpha<\lambda}B^\alpha for \lambda limit. Note that this is a decreasing sequence, so that if we set B^\infty=\bigcap_{\alpha\in{\sf ORD}}B^\alpha, there must be an \alpha such that B^\infty=B^\beta for all \beta\ge\alpha. 

[The sets B^\alpha are the Cantor-Bendixson derivatives of B. In general, a derivative operation is a way of associating to sets B some kind of ``boundary.'']

Read the rest of this entry »


502 – The Löwenheim-Skølem theorem

November 8, 2009

In this note I sketch the proof of the Löwenheim-Skølem (or Löwenheim-Skølem-Tarski) theorem for first order theories. This basic result of model theory is really a consequence of a set theoretic combinatorial lemma, as the proof will demonstrate.

Let {{\mathcal L}} be a first order language, understood as a set of constant, function, and relation symbols. Let

\displaystyle  \kappa_{\mathcal L}=|{\mathcal L}|+\aleph_0,

so {\kappa_{\mathcal L}} is {|{\mathcal L}|,} unless {{\mathcal L}} is finite, in which case we take {\kappa_{\mathcal L}=\omega.} Talking about {\kappa_{\mathcal L}} rather than {|{\mathcal L}|} simplifies the presentation slightly.

The Löwenheim-Skølem theorem is concerned with the possible infinite sizes of models of first order theories. Of course, a theory {T} could only have finite models; the result does not say anything about {T} if that is the case.

Theorem 1 If {T} is a first order theory in a language {{\mathcal L},} and there is at least one infinite model of {T,} then there are models of {T} of size {\lambda,} for all {\lambda\ge\kappa_{\mathcal L}.}

We will prove a more precise statement. Before stating it, note that it is possible to have a theory {T} in some uncountable language {{\mathcal L}} such that {T} has models of certain infinite sizes, but not all. Theorem 1 does not say anything about infinite models of {T} of size {<\kappa_{\mathcal L}.} What cardinals in this range are the possible sizes of models of {T} is actually a rather difficult problem, and we will not address it.

Read the rest of this entry »


175 – Quiz 5

November 6, 2009

598 – Upcoming talk: Leming Qu

November 3, 2009

Leming Qu, Wed. November 11, 2:40-3:30 pm, MG 120.

Wavelet Image Restoration and Regularization Parameters Selection

For the restoration of an image based on its noisy distorted observations, we propose wavelet domain restoration by a scale-dependent L^1 penalized regularization method (WaveRSL1). The data-adaptive choice of the regularization parameters is based on the Akaike Information Criterion (AIC) and the degrees of freedom (df) are estimated by the number of nonzero elements in the solution. Experiments on some commonly used testing images illustrate that the proposed method possesses good empirical properties.


175 – Midterm 2

November 1, 2009

Here is the second midterm.

Read the rest of this entry »


598 – Upcoming talk: Jodi Mead

October 28, 2009

Jodi Mead, Wed. November 4, 2:40-3:30 pm, MG 120.

Non-smooth Solutions to Least Squares Problems

In an attempt to overcome the ill-posedness or ill-conditioning of inverse problems, regularization methods are implemented by introducing assumptions on the solution.  Common regularization methods include total variation, L-curve, Generalized Cross Validation (GCV), and the discrepancy principle. It is generally accepted that all of these approaches except total variation unnecessarily smooth solutions, mainly because the regularization operator is in L^2. Alternatively, statistical approaches to ill-posed problems typically involve specifying a priori information about the parameters in the form of Bayesian inference. These approaches can be more accurate than typical regularization methods because the regularization term is weighted with a matrix rather than a constant. The drawback is that the matrix weight requires information that is typically not available or is expensive to calculate.

The \chi^2 method developed by the author and colleagues can be viewed as a regularization method that uses statistical information to find matrices to weight the regularization term.  We will demonstrate that unique and simple L^2 solutions found by this method do not unnecessarily smooth solutions when the regularization term is accurately weighted with a diagonal matrix.


502 – Cancellation laws

October 28, 2009

Two homework problems. The first one is easier, so you can consider the second one to be extra credit. A proof of these results can be found in different places, for example, the paper Division by three, by Conway and Doyle. (Please don’t look at the paper while working on the homework, of course.) Unfortunately, the paper could use a serious trimming and editing, so I cannot really recommend it, but the proof is carefully written there.

  1. Without using the axiom of choice, show that if A and B are sets, and |A\times 2|=|B\times 2|, then |A|=|B|.
  2. Same as 1., but now with 3 instead of 2. 

598 – Upcoming talk: Jens Harlander

October 21, 2009

Jens Harlander, Wed. October 28, 2:40-3:30 pm, MG 120.

Introduction to Computational Complexity

Complexity theory provides ways of measuring the difficulty of computational mathematics problems. Some problems are indeed impossibly difficult (your Math 108 and 143 students are right after all!). For example, there does not exist an algorithm that decides whether a polynomial (in an arbitrary number of variables) with integer coefficients has integer roots. However for many difficult problems, simple strategies work well in practice as long as one is willing to ignore a hopefully sparse set of inputs. I will discuss basic features of the theory, give you more examples of impossibly hard problems and tell you about the relevance of all of this to Internet security.


598 – Schedule of talks

October 20, 2009

Here is the list of speakers for the rest of the term. 


175 – Quiz 4

October 18, 2009