598 – Upcoming talk: Marion Scheepers

November 30, 2009

Marion Scheepers, Wed. December 2, 2:40-3:30 pm, MG 120.


Online shopping and banking, Wireless communication and remote control devices have become common place. Nontrivial computing power and scanning devices of high power have become readily available. This creates an environment in which information in transit can be easily accessed or changed by unknown parties.

Cryptography is the main tool used to keep information secure. In this talk we will give a brief, motivated, outline of some of the mathematical foundations of cryptography. We also give an example to illustrate that mere possession of a good crypto-system does not guarantee security – one must also use it right.

175 – Quiz 7

November 25, 2009

Happy Thanksgiving!

Here is quiz 7.

Read the rest of this entry »

175 – Quiz 6

November 13, 2009

Here is quiz 6.

Read the rest of this entry »

175 – Self test and Extra credit problems

November 12, 2009

Here are the two parts of the test (part 1, part 2), in case you want a blank copy. As I mentioned, they do not include all topics; they mostly cover material related to chapter 7 of the book, and even then, they are not comprehensive (for example, the second part does not include parts or word problems), but I hope you found them helpful in identifying topics that may require further study or review.

Here are two extra credit problems. Please let me know if you need me to clarify either one.

502 – Equivalents of the axiom of choice

November 11, 2009

The goal of this note is to show the following result:

Theorem 1 The following statements are equivalent in {{\sf ZF}:}

  1. The axiom of choice: Every set can be well-ordered.
  2. Every collection of nonempty set admits a choice function, i.e., if {x\ne\emptyset} for all {x\in I,} then there is {f:I\rightarrow\bigcup I} such that {f(x)\in x} for all {x\in I.}
  3. Zorn’s lemma: If {(P,\le)} is a partially ordered set with the property that every chain has an upper bound, then {P} has maximal elements.
  4. Any family of pairwise disjoint nonempty sets admits a selector, i.e., a set {S} such that {|S\cap x|=1} for all {x} in the family.
  5. Any set is a well-ordered union of finite sets of bounded size, i.e., for every set {x} there is a natural {m,} an ordinal {\alpha,} and a function {f:\alpha\rightarrow{\mathcal P}(x)} such that {|f(\beta)|\le m} for all {\beta<\alpha,} and {\bigcup_{\beta<\alpha}f(\beta)=x.}
  6. Tychonoff’s theorem: The topological product of compact spaces is compact.
  7. Every vector space (over any field) admits a basis.

Read the rest of this entry »

598 – Upcoming talk: Grady Wright

November 11, 2009

Grady Wright, Wed. November 18, 2:40-3:30 pm, MG 120.

Scattered Node Finite Difference-Type Formulas Generated from Radial Basis Functions with Applications

In the finite difference (FD) method for solving partial differential equations (PDEs), derivatives at a node are approximated by a weighted sum of function values at some surrounding nodes. In the one dimensional case, the weights of the FD formulas are conveniently computed using polynomial interpolation. These one dimensional formulas can be combined to create FD formulas for partial derivatives in two and higher dimensions. This strategy, however, requires that the nodes of the FD “stencils” are situated on some kind of structured grid (or collection of structured grids), which severely limits the application of the FD method to PDEs in irregular geometries.  In this talk, we present a novel approach that resolves this problem by allowing the nodes of the FD stencils to be placed freely and by using radial basis function (RBF) interpolation for computing the corresponding weights in the scattered node FD-type formulas. We show how this RBF approach can exactly reproduce all classical FD formulas and how compact FD formulas can be generalized to scattered nodes and RBFs. This latter result is important in that it allows the number of nodes in the stencils to remain relatively low without sacrificing accuracy.  For the Poisson equation, these new compact scattered node schemes can also be made diagonally dominant, which ensures both a high degree of robustness and applicability of iterative methods. We conclude the talk with some numerical examples and future applications of the method for geophysical problems.

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

Here is quiz 5.

Read the rest of this entry »

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.