McKay graph

December 16, 2011 Leave a comment

I decided to create a wikipedia page on McKay graphs. These lead to the McKay correspondence, one really beautiful result in Mathematics, that state that there exists a one-to-one correspondence between the finite groups of SU(2, \mathbb{C}) and the extended Dynkin diagrams, that appear in completely different area of mathematics. For example, they appear in the resolution of singularities and the classification of simple Lie algebras. You can find the article here.

In my previous post, I did a little introduction to Lie algebras, and I hope to have the time to explain in more details how can one classify simple Lie algebras with the Dynkin diagrams.

Filed under Lie Algebras, McKay correspondence

Lie Algebras

October 27, 2011 Leave a comment

Lie Algebras

I am currently learning Lie algebras as they will be really important for my master project. Here are some notes that I have taken about basic notions. I will probably post more stuff about what I am doing later. I am using a program that convert LaTex to WordPress, so I hope it will be readable. Most of the following notions about Lie Algebras were taken in Humphreys’ book. The book has a good basic knowledge in classification of Lie Algebras.

Definition (Lie Algebra)
A vector space {L} over a field {F}, with an operation {L\times L\rightarrow L}, denoted {(x,y)\rightarrow [xy]} and called the bracket or commutator of {x} and {y}, is called a Lie Algebra over {F} if the following axioms are satisfied:

Bilinearity: The bracket operation is bilinear, i.-e. {\forall a,b\in F},
{[(ax+by)z] = a[xz] + b[yz]}
{[z(ax+by)] = a[zx]+b[zy]. }
Antisymmetriy: {[xy] = -[yx]} for all {x,y\in L}.
Jacobi identity: { [x[yz]] + [y[zx]] + [z[xy]] = 0\,\,\, (x,y,z\in L)}.

Notice that we can deduced from these properties that {[xx]=0}.

Definition (Lie Isomorphisms)
We say that two Lie algebras {L,L'} over {F} are isomorphic if there exists a vector space isomorphism {\phi: L\rightarrow L'} satisfying {\phi([xy]) = [\phi(x)\phi(y)]} for all {x,y\in L}.

Definition (Lie Subalgebras)
A Lie Subalgebras is a subspace {K} of {L} such that {[xy]\in K} whenever {x,y\in K}.

Lie algebras first arose with the study of Lie groups, which are groups that are also smooth manifolds. Lee gives a good introduction in his book to Lie algebras from that point of view.
Let {V} and {W} be smooth vector fields on a smooth manifold {M}. Then the operator {[V,W] : C^{\infty}(M)\rightarrow C^{\infty}(M)} given by:

\displaystyle [V,W]f = VWf - WVf

is a Lie bracket. It is a smooth vector fields.

Definition (Left-Invariant Vector Fields)
Suppose {G} is a Lie group. Any {g\in G} defines maps {L_g, R_g: G\rightarrow G}, called Left translation and Right translation, respectively, by

\displaystyle L_g(h) = gh, \quad R_g(h) = hg.

A vector field {X} on {G} is said to be left-invariant if
\displaystyle (Lg)_*X_{g'} = X_{gg'}, \quad\forall g,g'\in G.

The space {\tau(M)} of all smooth vector fields on a smooth manifold {M} is a Lie algebra under the Lie bracket of vector fields. Given {G} is a Lie group, the set of all smooth left-invariant vector fields on {G} is a Lie subalgebra of {\tau(G)} and is therefore a Lie algebra. It is called the Lie algebra of G and is denoted by {Lie(G)}. The reason why this algebra is of particular importance is given by the following theorem:

Theorem
Let {G} be a Lie group. The evaluation map {\epsilon: Lie(G)\rightarrow T_eG}, given by {\epsilon(X) = X_e}, is a vector space isomorphism. Thus, dim{\, Lie(G)} = dim{\, G}.

Let {V} be a finite dimensional vector space over {F}, denote by End {\, V} the set of linear transformations {V\rightarrow V}. Define the bracket as {[x,y] = xy-yx}. With this operation End {\, V} is called the general linear algebra, denoted by {\mathfrak{gl}}. One interesting theorem links {\mathfrak{gl}} to {Lie(GL(V))}.

Theorem
{Lie(GL(V))} is isomorphic to {\mathfrak{gl}}.

Any subalgebra of a Lie algebra {\mathfrak{gl}(V)} is called a linear Lie algebra.
Some Lie algebras of linear transformations arise most naturally as derivations of algebras. By an F-algebra, we simply mean a vector space {\mathfrak{U}} over {F} endowed with a bilinear operation {\mathfrak{U}\times\mathfrak{U}\rightarrow\mathfrak{U}}. By a derivation of {\mathfrak{U}}, we mean a linear map {\delta:\mathfrak{U}\rightarrow\mathfrak{U}} satisfying the Liebnitz’s rule: {\delta(ab) = a\delta(b) + \delta(a)b}. Let Der {\,\mathfrak{U}} denote the set of all derivations of {\mathfrak{U}}. Then, Der {\,\mathfrak{U}} is a subspace of End {\,\mathfrak{U}}. Since the commutator {[\delta, \delta']} of two derivations is again a derivation, Der {\,\mathfrak{U}} is a subalgebra of {\mathfrak{gl}(\mathfrak{U})}. Certain derivations arise quite naturally. If {x\in L, y\rightarrow [xy]} is an endomorphism of {L}, which is denoted ad {x}. In fact, ad {x\in} Der{\, L}. Derivations of this form are called inner and all other are called outer. The map {L\rightarrow\mbox{Der}\, L} sending {x} to ad {x} is called the adjoint representation of {L}.
It is know (cf. Jacobson Chapter VI) that every finite dimensional Lie algebra is isomorphic to some linear Lie algebra.

Definition (Abelian Lie algebras)
A Lie algebra is called abelian if {[xy] = 0} for all {x,y\in L}.

1.1. Ideals and homomorphism

A subspace {I} of a Lie algebra {L} is called an ideal of {L} if {x\in L}, {y\in I} together imply {[xy]\in I}.

Example 1 The centre {Z(L) = \{z\in L | [xz] = 0\,\,\forall\,\, x\in L\}} is an ideal. Another important example of ideal is the derived algebra of {L}, denoted {[LL]}, which is analogous to the commutator subgroup of a group. It consists of all linear combinations of commutators {[xy]}. It is clear that if {I,J} are two ideals, then {I+J} is an ideal. Similarly, {[IJ]} is an ideal.
If {L} has no ideals except itself and {0}, and if moreover {[LL]\not = 0}, then {L} is called a simple Lie algebra.

In the case where {L} is not simple, and {I} is a proper ideal of {L}, then the construction of a quotient algebra is formally the same as the construction of a quotient ring: A quotient space with Lie multiplication defined by {[x+I, y+I] = [xy] +I}.

The normalizer of a subalgebra (or just subspace) {K} of {L} is defined by {N_L(K) = \{x\in L | [xK] \subset K\}}. By the Jacobi identity, {N_L(K)} is a subalgebra of {L}. It is the largest subalgebra of {L} which includes {K} as an ideal. If {K = N_L(K)}, we call {K} self-normalizing. The centralizer of a subset {X} of {L} is {C_L(X) = \{x\in L | [xX] = 0\}}. It is a subalgebra of {L}.

A linear transformation {\phi: L\rightarrow L'} is called an homomorphism if {\phi([xy]) = [\phi(x), \phi(y)]}.

Note that {Ker(\phi)} is an ideal of {L}. Also, the standard isomorphism theorems hold.

Let {V} be a vector space over {F}. A Representation of a Lie algebra {L} is a homomorphism {\phi: L\rightarrow\mathfrak{gl}(V)}.

An important example to bear in mind is the adjoint representation {ad: L\rightarrow\mathfrak{gl}(L)}. The kernel of ad is {Z(L)}. If {L} is simple, then {Z(L) = 0}, so {ad: L\rightarrow\mathfrak{gl}(L)} is a monomorphism. Then, any simple Lie algebra is isomorphic to a linear Lie algebra.

1.2. Solvable and nilpotent Lie algebras

The derived series of {L} is defined by {L^{(0)} = L, L^{(1)} = [LL], L^{(2)} = [L^{(1)},L^{(1)}], \ldots} {L} is called solvable if {L^{(n)} = 0} for some {n}.

Theorem
Let {L} be a Lie algebra.

If L is solvable, then so are all subalgebras and homomorphic images of L.
If I is a solvable ideal of {L} such that {L/I} is solvable, then {L} itself is solvable.
If {I, J} are solvable ideals of {L}, then so is {I+J}.
We are now about to define really important Lie algebras. Let {S} be a maximal solvable ideal of {L}. Such an ideal exists. Call this ideal the radical of {L} and denoted Rad {L}. If {L\not = 0} and Rad {L=0}, then {L} is called semisimple. If {L} is not solvale, i.e., {L\not =} Rad {L}, then {L/\mbox{Rad}\,\,L} is semisimple.

Define a sequence of ideals of {L} (the lower central series) by {L^0 = L, L^1 = [LL], L^2 = [LL^1]\ldots} {L} is called nilpotent if {L^n = 0} for some {n}.

Theorem
Let L be a Lie algebra.

If {L} is nilpotent, then so are all subalgebras and homomorphic images of {L}.
If {L/Z(L)} is nilpotent, then so is {L}.
If {L} is nilpotent, then {Z(L)\not = 0}.
Now if {L} is any Lie algebra, and {x\in L}, we call x ad-nilpotent if ad {x} is a nilpotent endomorphism.

Theorem
All elements of {L} are ad-nilpotent if and only if {L} is nilpotent.

James E. Humphreys, Introduction to Lie Algebras and Representation theory, Second Edition, Springer-Verlag, New-York, 1972.
John M. Lee, Introduction to Smooth Manifolds, Springer-Verlag, New-York, 2003.

Filed under Lie Algebras

First-Order Logic: The Downward Löwenheim – Skolem Theorem and the Lindström’s Theorem

July 28, 2011 Leave a comment

In this post, we will see the downward Löwenheim- Skolem theorem and how it is link, with the Compactness theorem, to the Lindström’s theorem, which states an important property of first order logic. I want to thank Nigel Sequeira for giving me the suggestion of this post. Every needed definition is in the previous post on the Compactness Theorem and the references are the same.

The Vaught Test

The Vaught Test is an important lemma for the Downward Lowenheim- Skolem Theorem. We first need to give the definition of substructure and elementary substructure.

Definition

Let \bf{M} and \bf{N} be two L-structures, with M\subset N. Then, \bf{M} is a substructure of \bf{N}, and we write \bf{M}\subset\bf{N}, if

  • f^{\bf{M}} = f^{\bf{N}}|_{M^k} for every n-ary fonction f\in\bf{L};
  • R^{\bf{M}}\subset R^{\bf{N}}\cap M^k for every n-ary relation R\in\bf{L}.

Definition

Let \bf{M} and \bf{N} be two L-structures. Then,  \bf{M} is an elementary substructure of \bf{N}, and we write \bf{M}\prec\bf{N}, if \bf{M}\subset\bf{N} and for every \bar{m}\in M^k and formula \phi, we have \bf{M}\models\phi(\bar{m}) iff \bf{N}\models\phi(\bar{m}).

We are now ready to state and prove the Vaught Test.

Lemma (Vaught Test)

Let \bf{M} and \bf{N} be two L-structures such that \bf{M}\subset\bf{N}. Then, \bf{M} is an elementary substructure of \bf{N} iff for all formulas \phi(x,\bar{y}), if \bf{N}\models\exists_x\phi(x,\bar{m}), where \bar{m}\in M^k, then there is m\in M such that \bf{N}\models\phi(m,\bar{m}).

Proof

We first suppose that \bf{M}\prec\bf{N}. Then, \bf{N}\models\exists_x\phi(x,\bar{m}) implies that \bf{M}\models\exists_x\phi(x,\bar{m}), by the definition of elementary substructures. Then, there exists m\in M such that \bf{M}\models\phi(m,\bar{m}). Then, using again the definition, we have that \bf{N}\models(m,\bar{m}).

For the converse, the proof goes by induction on the complexity of \phi. This is true for quantifiers-free formulas \psi, since in this case, we have that \bf{M}\subset\bf{N} implies \bf{M}\models\psi(\bar{m}) iff \bf{N}\models\psi(\bar{m}). This can be proved using induction on the complexity of the formula.

Now suppose the result holds for \phi_1 and \phi_2. Then, it is easy to verify that the theorem holds for \neg\phi_1 and \phi_1\wedge\phi_2.

Let \psi = \exists_x\phi_1(x). If \bf{M}\models\exists_x\phi_1(x,\bar{a}), then there exists a m\in M such that \bf{M}\models\phi_1(m,\bar{a}). By the induction hypothesis, this implies that there exists a m\in M\subset N such that \bf{N}\models\phi_1(m,\bar{a}). Thus, \bf{N}\models\exists_x\phi_1(m,\bar{a}).

Conversely, if \bf{N}\models\exists_x \phi_1(x, \bar{a}), then, using the assumption, there exists m\in M such that \bf{N}\models\phi(m,\bar{a}). Then, there exists m\in M such that \bf{M}\models\phi(m,\bar{a}). Thus, \bf{M}\models\exists_x\phi_1(x,\bar{a}). This completes the proof.

The Downward Löwenheim-Skolem Theorem

The Downward Lowenheim- Skolem Theorem is one of the most important theorem for First Order Logic. It is a very beautiful result, that we can state as follow:

Theorem (Downward Löwenheim-Skolem Theorem)

Let \bf{N} be a L-structure and A be any subset of N. There exists a \bf{M} with A\subset M and \bf{M}\prec\bf{N} such that \|\bf{M}\|\leq\|\bf{L}\|+\|A\|, where \|X\| denotes the cardinality of X.

Proof

Choose a point k\in N. For each L-formula \phi (x,y), we define the Skolem function g_{\phi}: N^m\to N of \phi as follow: for each n\in N^k, we associate some n'\in N such that \bf{N}\models\phi(n,n'), if such an n' exists, otherwise we associate k. The set of Skolem functions has cardinality \|\bf{L}\|. Set A_0 = A, A_{i+1} = \{g_{\phi}(n)| n\in A_i\}. Let M= \cup_i A_i. Then, M is closed under the skolem functions. Also, \| M\|\leq\omega\cdot\|\bf{L}\| + \| A\| = \|\bf{L}\| +\| A\|.  It is possible to provide appropriate interpretation of the relation, function and constant symbols using \bf{N} so that we can induce a L-structure \bf{M}, having M as a domain. Then, we have a model \bf{M} that is close under the Skolem functions. We now have to prove that \bf{M}\prec\bf{N}, and this will conclude the proof. If we have formula \exists_y\phi(x,y) and m\in M^l, then we can find a witness for \exists_y\phi(m,y). In fact, we have that if \bf{N}\models\exists_x\phi(m,x), then \bf{N}\models\phi(m, g_{\phi}(m)). Since, \bf{M} is closed under skolem functions, we have that g_{\phi}(m)\in M. Thus, by the Vaugh Test, we have that \bf{M}\prec\bf{N}.

The Lindstrom’s Theorem

The Lindstrom’s theorem gives an important property of First Oder Logic. It roughly states that First Order Logic is the biggest abstract logic which satisfies the countable compactness theorem and the Downward Lowenheim- Skolem theorem. I will not prove this theorem, but it is possible to prove it using Ehrenfeucht-Fraisse games, which is a very important concept in the project I am working on at the Fields Institute. I will now state some definitions in order to understand the main theorem.

Definition

An elementary class K_{\phi} is a class of structures of the same type, that is, K_{\phi} = \{\bf{M}: \bf{M}\models\phi\}.

Definition

Let L = (S,T) be a logic, where S is a set and T = T(\bf{M}, \phi) is a relation between arbitrary structures and element of the set S. For example, the first order logic is L_{\omega\omega} = (S_0,T_0), where S_0 is the set of all first order sentences and T_0 (\bf{M},\phi) is the truth predicate, that is, T_0 (\bf{M},\phi) iff \bf{M}\models\phi. If \tau is a language, then we define Str(\tau) to be the class of structures of the language. For \phi\in S, we define Mod_{L,\tau}(\phi) = \{\bf{M}\in Str(\tau) : T(\bf{M},\phi)\}. This can be intuitively view as the class of models of \phi.

Definition

I will list some properties that a Logic can have. 

  • A logic L is said to be closed under negation, if for all languages \tau and all \phi\in S there exists \psi\in S such that Mod_{L,\tau}(\psi) = Str(\tau)\setminus Mod_{L,\tau}(\phi). We denote \psi by \neg\phi.
  • We say that L is closed under conjunction is for all languages \tau and all \phi,\psi\in S there exists \alpha\in S such that Mod_{L,\tau}(\alpha) = Mod_{L,\tau}(\phi)\cap Mod_{L,\tau}(\psi). We denote \alpha by \phi\wedge\psi.
  • We say that L is closed under existential quantification if for all languages \tau, for all constant symbols c\in\tau and for all \phi\in S, there exists \psi\in S such that Mod_{L,\tau\setminus c}(\psi) = \{\bf{M} : (\bf{M}, c^{\bf{M}})\in Mod_{L,\tau}(\phi)\,\,\mbox{for some}\,\,c^{\bf{M}}\in\bf{M}\}.
  • We say that L is closed under renaming if whenever \pi:\tau\to\tau' is a permutation which respects to arity and \pi':Str(\tau)\to Str(\tau') is a canonical extension of \pi, we have that for all \phi\in S, there exists \psi\in S such that \{\pi'(\bf{M}):\bf{M}\in Mod_{L,\tau}(\phi)\}= Mod_{L,\tau'}(\psi).
  • We say that L is closed under free expensions if whenever \tau\subset\tau' and \phi\in S, there exists \psi\in S such that Mod_{L,\tau}(\phi) = Mod_{L,\tau'}(\psi).
  • We say that L is closed under isomorphisms if whenever \phi\in S, \bf{M}\in Mod_{L,\tau}(\phi) and f:\bf{M}\to\bf{N} is an isomorphism, than \bf{N}\in Mod_{L,\tau}(\phi).

Definition

An Abstract logic is a logic having the properties described above.

Definition

Let L = (S,T) and L' = (S',T') be two abstract logics. We say that L is a sublogic of L', and we write L\leq L', if for all \phi S, there exists \phi'\in S' such that for all \tau, Mod_{L,\tau}(\phi) = Mod_{L', \tau}(\phi'). We say that L and L' are equivalent, and we write L\equiv L', if L\leq L' and L'\leq L.

Definition

An abstract logic L = (S,T) satisfies the (comptable) compactness property if for any (comptable) \Sigma\subset S, \cap\{Mod_{L,\tau}(\phi): \phi\in\Sigma\} = \emptyset implies \cap\{Mod_{L,\tau}(\phi) : \phi\in\Sigma_0\} = \emptyset for some finite \Sigma_0\subset\Sigma. L satisfies the downward Löwenheim-Skolem property if for every countable language \tau, every non-empty Mod_{L,\tau}(\phi) contains a countable model.

In this post and in the preceding post, we have proven that first order logic possesses the compactness property and the downward Löwenheim-Skolem property. It is also possible to see that the first order logic is an abstract logic. Lindström’s theorem states that first order logic is in fact the largest abstract logic having all of these properties, which is a very beautiful result! We will denote the first order logic by L_{\omega\omega}.

Theorem (Lindström)

Suppose that L is an abstract logic such that L_{\omega\omega}\leq L. Then L has the countable compactness property and the downward Löwenheim-Skolem property iff L\equiv L_{\omega\omega}.

Filed under Fields-Mitacs USRP, First Order Logic, Logic

First Order Logic: The Compactness Theorem

July 12, 2011 2 Comments

The Fields-Mitacs Undergraduate Summer Research Program has now begun! My project will be on Model theory of Operator Algebras. I will work in collaboration with Nigel Sequeira and Ferenc Bencs under the supervision of Prof. Bradd Hart from McMaster University and Prof. Ilijas Farah from York University. We will study the asymptotic behavior of sentences in continuous logic in matrix algebra. I will probably post on continuous logic later, but for now I want to introduce First Order Logic and prove one of the most important theorem in this field: The Compactness Theorem. It is a direct consequence of Gödel’s Completness Theorem, but I will do a proof without using it. I will instead use ultraproducts. The proof is using, at some point, the Axiom of Choice.

Preliminary definitions

In mathematical logic, we use a language to describe mathematical structures.

Language

A language \bf{L} can be described by these three following elements:

  • a set of function symbols \bf{F} and positive integers n_f for each f\in \bf{F};
  • a set of relation symbols \bf{R} and positive integers n_R for each R\in \bf{R};
  • a set of constant symbols \bf{C}.

The numbers n_f and n_R tell us that f is a function of n_f variables and R is an n_R-ary relation.

L-Structure

An L-structure \bf{M} is described by the following elements:

  • A non-empty set M called the underlying set of \bf{M};
  • A function f^{\bf{M}}:M^{n_f}\to M for each f\in\bf{F};
  • a set R^{\bf{M}}\subset M^{n_R} for each R\in\bf{R};
  • an element c^{\bf{M}} for each c\in\bf{C}.

f^{\bf{M}}, R^{\bf{M}} and c^{\bf{M}} are called the interpretations of the symbols f, R and c.

L-Terms

The set of L-terms is the smallest set T such that

  • c\in\bf{T} for each constant symbol c\in\bf{C};
  • each variable symbol v_i\in\bf{T} for i=1,2,\ldots;
  • if t_1,t_2, \ldots, t_{n_f}\in\bf{T} and f\in\bf{F}, then f(t_1,\ldots,t_{n_f})\in\bf{T}.

If t is a term built using m variables, we interpret t as a function t^{\bf{M}}:M^m\to M. The interpretation can be define rigorously by induction, but we can see it as “the meaning” of the term.

L-formulas

If \phi is either

  • t_1 = t_2,, with t_1, t_2\in\bf{T};
  •  R(t_1,\ldots, t_{n_R}) with R\in\bf{R} and t_1,\ldots,t_{n_R}\in\bf{T},

then we say that \phi is an atomic L-formula.

The set of L-formulas is the smallest set W containing the atomic L-formulas such that

  • if \phi\in\bf{W}, then \neg\phi\in\bf{W};
  • if \phi,\psi\in\bf{W}, then (\phi\wedge\psi), (\phi\vee\psi)\in\bf{W};
  • if \phi\in\bf{W}, then \exists v_i\,\,\phi,\forall v_i \,\,\phi\in\bf{W}.

A variable is free in a formula if it is not inside a quantifier. A sentence is a formula with no free variable. From this definition, we can see that sentences are either true or false in a specific L-structure, whereas formula with free variables express a property of an element.

Satisfiability

Let \phi be a formula with free variables, \bf{M} be a L-structure and \bar{a}= (a_{i_1},\ldots, a_{i_m})\in M^m. Intuitively, we say that \bf{M} satisfies \phi(\bar{a}) if \phi(\bar{a}) is true in \bf{M}, and we write \bf{M}\models\phi(\bar{a}).

There is a rigorous definition using induction, and anyone who is interested can look it in Marker’s book. I put the reference above.

Theories

Let \bf{L} be a language. An L-theory T is a set of L-sentences. Let \bf{M} be a L-structure. We say that \bf{M} is a model of T if \bf{M}\models\phi for all \phi\in T.

We say that a theory is satisfiable if it has a model. We write T\models\phi if every model of T is a model of \phi.

These definitions are a little bit difficult to understand the first time. We should look at an example.

Example : Ring Theory

In the Ring Theory T, a language could be the set \{+,-,\cdot,0,1\}, which has three function symbols, zero relation symbol and two constant symbols. The interpretation of these symbols is basically how we define them. A model could be the ring \mathbb Z. An example of sentence could be

\forall x\forall y\forall z (x\cdot(y\cdot z) = (x\cdot y ) \cdot z),

which is true in every model of T.

We are now ready to state the Compactness theorem.

The Compactness theorem

Let T be a theory. Then,

  1. T is satisfiable iff every finite subset of T is satisfiable.
  2. T\models\phi iff there is a finite T_0\subset T such that T_0\models\phi.

Ultraproducts

In order to prove the compactness theorem, we have to introduce the concept of Ultraproduct. We first define what an ultrafilter is.

Definition

Let X be a set. An Ultrafilter U on X is a subset of P(X) having these properties:

  1. The empty set is not in U;
  2. If A and B are subsets of X, A is a subset of B and A is in U, then B is in U;
  3. U is close under finite intersection;
  4. If A is a subset of X, then either A is in U or X\setminus A is in U.

We can think of U as a very large set. The definition of Ultraproduct may be hard to understand the first time, but it will be really useful. A filter is a set satisfying the three first properties. For every filter, there exists an ultrafilter containing it.

Definition

Let \{\bf{M}_i\}_{i\in I} be a collection of models and U be an ultrafilter on I. We define an equivalence relation \sim on \prod_{i\in I}\bf{M}_i as follow:

m\sim n if \{i\in I | m_i = n_i\}\in U.

Then \bf{M}= \prod_{i\in I}\bf{M}_i/\sim is called an ultraproduct. We often write the ultraproduct as \prod_{i\in I}\bf{M}_i/U.

We can think of the equivalence relation as m\sim n if m_i = n_i “almost everywhere”.

We now have to define the interpretation in the ultraproduct of relation, function and constant symbols in L.

First of all, for each constant symbol c,  c^{\bf{M}} = [c^{\bf{M}_i}].

Now suppose that R is a n-ary relation symbol. Let ([f_1],\ldots,[f_n]) be a n-tuples of elements in \bf{M}. Then ([f_1],\ldots,[f_n])\in R^{\bf{M}} iif \{i\in I | (f_1(i),\ldots,f_n(i))\in R^{\bf{M_i}}\}\in U. It is important to verify that this function is well-defined.

Finally, suppose that h is a n-ary function symbol. Let ([f_1],\ldots,[f_n]) be a n-tuples of elements in \bf{M}. We define \tilde{h}^{\bf{M}}([f_1],\ldots,[f_n]): i\to h^{\bf{M_i}}(f_1(i),\ldots,f_n(i)). Then, h^{\bf{M}} is the equivalence class of the previous function. We would also need to verify that the function is well-defined.

Los’s Theorem

We will now prove an important lemma, called the Los’s Theorem.

Theorem

Let \{M_i\}_{i\in I} be a collection of models and U be an ultrafilter on I. Also, let \phi(x_1,\ldots, x_n) be a formula and f_1, \ldots, f_n\in\prod_{i\in I}M_i. Then

M= \prod_{i\in I}M_i/U\models \phi([f_1],\ldots,[f_n]) iff \{i\in I | M_i\models\phi(f_1(i),\ldots,f_n(i))\}\in U.

Proof

We prove it by induction on the complexity of the formulas.

If the formula is atomic, this is true, because of how we defined the interpretation of the symbols.

Now, suppose that the theorem is true for some formulas \psi_0 and \phi_0. Then, we will need to show that this is true for \neg\psi_0, \psi_0\wedge\phi_0 and \exists x \phi_0(x). Then, we will have conclude the proof, because every non-atomic formula is obtained from another formula by these three negation, connective and quantifier.

If \phi = \neg\psi_0. By the induction hypothesis, we have that M\models\psi_0 iff \{i\in I | M_i\models\psi_0\}\in U. By negating both sides, we then have that M\models\phi iff \{i\in I | M_i\models\psi_0\}\not\in U. Using the fourth property of the ultrafilter, this means that M\models\phi iff I\setminus\{i\in I | M_i\models\psi_0\}\in U. This is equivalent to say that the theorem holds for \phi.

If \phi = \psi_0\wedge\phi_0. We have that M\models\phi iff M\models\psi_0 and M\models\phi_0. By using the induction hypothesis and the fact that U is closed under finite intersection, we have that the theorem holds for \phi.

If \phi = \exists x\psi_0(x). We may assume that x is free in \psi_0. By the induction hypothesis, we have that for all m = [m_i]\in M, M\models\psi_0(m) iff \{i\in I | M_i\models\psi_0(m_i)\}\in U. This is equivalent to say that M\models\phi iff there exists an m\in M such that \{i\in I | M_i\models\psi_0(m_i)\}\in U. To show that a model N\models\exists x\omega(x), where \omega is a formula, we need to find a witness a\in N for which the statement \omega(a) is true in N. Thus, we have shown that if M\models\phi, then \{i\in I | M_i\models\exists x\psi_0(x)\}\in U, since the m_i are the witnesses that we are looking for. Now, we need to prove the converse of the previous statement, and this will complete the proof. Suppose \{i\in I | M_i\models\exists x\psi_0(x)\}\in U. By applying the axiom of choice, we select for each i\in\{i\in I | M_i\models\exists x\psi_0(x)\} a witness m_i\in M_i such that M_i\models\psi_0(m_i). We select for each i not in this set an arbitrary element m_i\in M_i. Taking m = [m_i]\in M, we have that there exists an m\in M such that \{i\in I | M_i\models\psi_0(m_i)\}\in U. Then M\models\phi.

Proof of the Compactness theorem

We are now ready to prove the first statement of our main result.

Proof

If T is satisfiable, then every finite subset of T is, of course, satisfiable. Conversely, suppose that every finite subset of T is satisfiable. Let P_{fin}(T) be the set of all finite subsets of T. For each sentence \phi\in T, let \uparrow(\phi) denote the collection of finite subsets of T containing \phi. It is easy to prove that \{\uparrow(\phi) | \phi\in T\} is a filter. Then, there exists an ultrafilter U on P_{fin} containing it. We associate for each T_0\in P_{fin} a model M_{T_0}. We define M to be the ultraproduct \prod_{T_0\in P_{fin}} M_{T_0}/U. Then M is a model of T and T is satisfiable. In fact, let \phi be in T. We have that if \phi\in T_0, then M_{T_0}\models\phi. Then, \uparrow(\phi)\subset\{T_0\in P_{fin}| M_{T_0}\models\phi\}. It follows by the choice of the ultrafilter, and by the second property of the definition of ultrafilters, that \{T_0\in P_{fin}| M_{T_0}\models\phi\}\in U. Then, by the Los’s theorem, M\models\phi.

References

  • David Marker, Model Theory: An Introduction, Graduate texts in Mathematics, Springer.
  • Ebbinghaus, Flum and Thomas, Mathematical Logic, Undergraduate texts in Mathematics, Springer.

Filed under Fields-Mitacs USRP, First Order Logic, Logic

Universality of the Riemann Zeta function

June 27, 2011 2 Comments

At the CUMC 2011, I did a talk in French about a universal property of the Riemann Zeta function. This property is very important for the resolution of the Riemann Hypothesis. I think it is not a well-known property, but there is some beautiful results that has been shown.

You can see the slides of my talk in French here.

The Riemann Zeta Function

The Riemann Zeta function can be defined by the following equation:

\zeta(z) = \sum_{n=1}^{\infty}\frac{1}{n^z},\quad\quad\quad\mbox{Re}(z)>1.

It extends meromorphically to the entire complex plane where it satisfies the following conditions:

  • \zeta has a simple pole at z = 1
  • \zeta(z) = \overline{\zeta(\overline{z})}
  • \zeta satisfies the functional equation:

\zeta(z)\pi^{-z/2}\Gamma\left(\frac{z}{2}\right) = \zeta(1-z)\pi^{-(1-z)/2}\Gamma\left(\frac{1-z}{2}\right),

where
\Gamma(z) = \int_{0}^{\infty}t^{z-1}e^{-t}dt, \quad\quad Re(z)>0.

The trivial zeroes of the Riemann Zeta function are:

\zeta(-2n) = 0, \quad\quad\quad n= 1,2,\ldots

The Riemann Hypothesis says that every non-trivial zeroes are on the line Re(z) = 1/2.

Universality and the Riemann Hypothesis

In 1929, G.D. Birkhoff invented the concept of universality. He proved a very surprising theorem:

Theorem (Birkhoff 1929)

There exists an entire function f such that for all entire functions g, there exists a sequence \{a_n\} such that

\lim_{n\to\infty} f(z+a_n) = g(z)\quad\quad\forall z\in\mathbb C,

and the convergence is uniform on compact subsets.

In 1952, Gerald Maclane proved another interesting universal property of some entire functions on the complex plane.

Theorem (Maclane 1952)

There exists an entire function f such that for all entire functions g, there exists a sequence \{n_k\} such that

\lim_{k\to\infty} f^{(n_k)}(z) = g(z)\quad\quad\forall z\in\mathbb C,

and the convergence is uniform on compact subsets.

One may find amusing that these mathematicians are not Garrett Birkhoff and Saunders Maclane who are well known for their work in algebra and category theory. George David and Gerald are respectively the father and brother of Garrett Birkhoff and Saunders Maclane.

The functions having the property in the two preceding theorems are called universal functions in the sense of Birkhoff and Maclane. The existence of such functions may be surprising as their translates approximate every other entire functions. Nevertheless, it is now proven that almost every entire functions is universal. However, no example of universal functions were known until Voronin proved a remarkable universal theorem. He showed that the Riemann Zeta function had a universal property.

Theorem (Voronin 1975)

For every 0<r<1/4 and for every zero-free function f holomorphic on the closed disk K of center 3/4 and radius r, there exists a sequence of real numbers \tau_n\to\infty such that

\max_{z\in K} |\zeta(z+i\tau_n)-\zeta(z)| \to 0 \quad\quad\mbox{as}\,\, n\to\infty.

As an immediate corollary, we find that the Riemann Zeta function can be approximated by its own translates.

Corollary

For every 0<r<1/4, there exists a sequence of real numbers \tau_n\to\infty such that

\max_{z\in K} |\zeta(z+i\tau_n)-\zeta(z)| \to 0 \quad\quad\mbox{as}\,\, n\to\infty.

The Riemann Zeta functions was the first function to be known to have universal properties. After, only other Zeta functions were known to have this property.

Bagchi and Reich extended the Voronin Universality Theorem.

Theorem (Voronin 1975, Reich 1977, Bagchi 1981)

Let S= \{z: 1/2 < Re\, z < 1\}. For every non-zero function f holomorphic in S, there exists a sequence \{\tau_n\} of real numbers such that

\zeta(z + i\tau_n)\to f(z)\quad\quad\forall z\in S,

and the convergence is uniform on compact subsets of S.

The hypothesis in the preceding theorem that the function f has to be non-zero in S seems to be consistent with the Riemann Hypothesis. In fact, roughly speaking, if the Riemann Zeta function could approximate entire function having zeroes in S, then the Riemann Zeta function itself should have zeroes in S, which contradicts the Riemann Hypothesis. It is not known if the preceding theorem remains true without the zero-free hypothesis, but it has been proven that this would contradicts the Riemann Hypothesis.

Theorem

If there exists a function f holomorphic in S, having zeroes but not f\equiv 0 in S, for which there exists a sequence of real numbers \{\tau_n\}\to\infty  such that

\zeta(z + i\tau_n)\to f(z)\quad\quad\forall z\in S,

then the Riemann Hypothesis is false.

The Riemann Hypothesis can also be characterize in term of the universality of the Riemann Zeta function.

Theorem (Bagchi 1981)

The Riemann Hypothesis is true if and only if for each compact K in the critical strip S and for each \epsilon >0,  the set of \tau\in\mathbb R, such that

\max_{z\in K}|\zeta(z+i\tau)-\zeta(z)|<\epsilon

has a positive upper density.

Perturbation of the Riemann Zeta-function

In 2003, Pustyl’nikov showed the existence of a very surprising function!

Theorem (Pustyl’nikov 2003)

For every compact subset K\in\mathbb C not containing the point 1 and for every \epsilon>0, there exists a function \zeta_- sharing important properties with \zeta:

  • \zeta_- is a meromorphic function with a unique pole at z=1;
  • The real zeroes of \zeta_- are the negative even integers.
  • \zeta_- satisfies the same functional equation.

The function \zeta_- fails to satisfy the Riemann Hypothesis. Moreover,

|\zeta_-(z)-\zeta(z)|<\epsilon, \quad\quad\forall z\in K.

In 2009, Niess showed the existence of such a function having the property of universality. One may think that this means that the Riemann Hypothesis has a strong probability to be false. Indeed, the \zeta_- function approximates the \zeta function, shares fundamental properties with the Riemann Zeta Function and fails to satisfy the Riemann Hypothesis.

But, it is also possible to find a function \zeta_+, analogous to the function \zeta_-, which satisfies the Riemann Hypothesis! 

This means that it is possible to approximate the Riemann Zeta function by functions which satisfy the Riemann Hypothesis and by functions which do not satisfy the Riemann Hypothesis!

If you want to know more about this, you should read these articles:

  • Paul M. Gauthier. Approximation of and by the Riemann Zeta-function, Computational Methods and Function Theory.
  • Paul M. Gauthier. Approximating functions having zeros or poles by the Riemann Zeta-function, Computational Methods and Function Theory.
  • Paul M. Gauthier and Eduardo S. Zeron. Small Perturbations of the Riemann Zeta-function and their zeros, Computational Methods and Function Theory.

Filed under Complex Analysis, CUMC2011, Number theory, Riemann Hypothesis, Riemann Zeta function, Universal functions

Interesting talks at the CUMC 2011

June 22, 2011 1 Comment

In June, Université Laval held the CUMC 2011. The CUMC is one of North America’s largest undergraduate conferences. Undergraduate students across Canada come to exchange on mathematics and to learn on different interesting fields. There is usually 8 Keynote Speekers and a lot of different talks given by the students. This year, I have learned on subjects that I had no idea of their existence. I also learned on different activities and student organizations that exist in Canada.

Here are the talks that I really enjoyed for different reasons.

Before I begin, I just want to write about Bruno Joyal’s talk: Universality across mathematics. I did not see his talk, but he put a paper of his talk on his blog that I found interesting.

First, let’s begin with the Keynote speakers.

  • I really enjoyed Pamela Gorkin‘s talk: Not an ellipse? Not my problem. She talked about “Blaschke Products and several seemingly unrelated results in which ellipses make an unexpected appearance.” The talk was really clear and surprising!
  • Frederick Rickey was also a great speaker. His talk, The fundamental Theorem of Calculus: History, Intuition, Pedagogy, Proof, was dynamic. I really enjoyed to hear him talking about how it was to teach in a military school.
Second, here are my favorite student talks.
  • Ana Iorgulescu : Why Mathematicians Will Never be Out of a Job: Gödel’s First Incompletness Theorem. The talk was about a simplified proof of the FIrst Incompleteness Theorem, which was given by George Boolos. I did not know about this simplified proof and found the concepts involved interesting. It is based on the paradox that the least integer not nameable in fewer than 19 syllables is in fact nameable in 18 syllables.
  • John Yang : A Painless Introduction to Complex Dynamics. This talk was about Complex Dynamics. John Yang made an introduction to Julia Sets, Normal families, invariance lemma and iteration lemma. These concepts really kept my attention and I will certainly read on this in the future.
  • Jean- Sébastien Turcotte : Une généralisation de l’intégrale de Riemann. This talk was about the Henstock-Kurzweil integral. This is a really nice concept, which is more general then the Riemann and the Lebesgue’s integral. For instance, the set of Henstock-Kurzweil integral functions contain the set of Riemann integral functions and Lebesgue integral functions.
  • Eric Naslund : Pretentious Number Theory. This talk was about a new branch of analytic number theory. It tries to give elementary proofs to important theorems of analytic number theory, that is, without using the Riemann Zeta function and its zeros. This theory has been mainly developed by Granville and Soundararajan.
So these are topics that I found interesting and I will certainly read on these new concepts. Maybe some of you will also want to know what are these subjects.

Filed under CUMC2011

Interesting websites on Galois Theory

June 22, 2011 2 Comments

This summer, I plan to learn Galois Theory as I feel it is very important and interesting. I did not have the opportunity to take a course in Galois theory as an undergraduate student. I am currently reading the Dummit and Foote’s Abstract Algebra, but there are also other course notes that a professor at l’Université de Montréal suggested to me.

If you want to learn on this subject, you should visit the Ramdom Math blog. There are some solutions of problems in Galois Theory. The problems are taken from Patrick Morandi’s Fields and Galois Theory (Springer). I talked to the administrator of this blog, and he said that this book may be a little bit hard for someone who has never done Galois theory. On the other hand, he said that the Dummit and Foote’s Abstract Algebra was not the best one either.

So, here are two possible course notes if you want to learn Galois theory:

Filed under Galois Theory

← Older posts

Follow

Get every new post delivered to your Inbox.