Posets and Lattices

February 4, 2014

Definition 1.
A lattice is a nonempty poset with a maximum and a minimum, and such that any nonempty finite subset has a supremum (or join) and an infimum (or meet).

One could just as well simply say that a lattice is a poset \mathcal L where any finite subset has a supremum and an infimum, using the (natural) convention that the supremum of the empty set is the minimum of \mathcal L, and its infimum is the maximum of \mathcal L.

The requirement that a lattice \mathcal L has a minimum and a maximum is not universally followed, and lattices with this additional property are sometimes called bounded.

Examples 2.
Any linearly ordered set with a minimum and a maximum is a lattice. In this case, all infima and suprema of nonempty finite sets are just minima and maxima.

For a more interesting example, consider \mathbb N, partially ordered by divisibility. This is a lattice, with minimum 1 and maximum 0. The infimum of a nonempty set X\ne\{0\} is the greatest common divisor of the elements of X, and its supremum is their least common multiple.

Given a set X, its power set \mathcal P(X) is a lattice under containment, \subseteq. In fact, in this case any nonempty subcollection of \mathcal P(X) (whether finite or not) has an infinimum (its intersection) and a supremum (its union). This is an example of a complete lattice, as in Definition 3.

Given a set X, let \mathrm{Fin}(X) denote the collection of finite subsets of X, partially ordered under containment. If X is infinite, \mathrm{Fin}(X) is not a lattice (it lacks a maximum), but \{X\}\cup\mathrm{Fin}(X) is.

The partition lattice \Pi_n has as elements the partitions of \{1,\dots,n\} where, as usual, a partition of a set A is a collection \mathcal A of pairwise disjoint nonempty subsets of A whose union is A. The set \Pi_n is ordered by refinement: If x,y are partitions in \Pi_n, we say that x\le y iff every set in x is a subset of a set in y.

Definition 3.
A lattice \mathbb P=(P,\le) is complete iff any nonempty subset of P has a supremum and an infimum.

With the same convention as above, we could as well say that any subset of P admits a supremum and an infimum.

Examples 4.
By the completeness of the real line, any compact interval {}[a,b]\subseteq\mathbb R is a complete lattice under the usual order.

(\mathbb N,|) is actually a complete lattice. The supremum of any infinite set is 0.

The collection of convex subsets of \mathbb R^2 is a complete lattice under containment. The infimum  of a nonempty family \mathcal F of convex sets is just their intersection. Its supremum is their convex hull, that is, the intersection of all the convex subsets of \mathbb R^2 that contain all sets in \mathcal F.

Given a group G, the collection \mathrm{Sub}(G) of subgroups of G, partially ordered by containment, is a complete lattice.

If X is a linearly ordered set with a supremum and an infimum, then X is a complete lattice iff it is Dedekind complete, meaning that any cut admits a supremum. Cuts are defined as a natural generalization of the usual concept for \mathbb Q: A cut of X is a pair (A,B) of subsets of X such that B is the collection of upper bounds of A, and A is the collection of lower bounds of B. Note that this notion makes sense even if X is just a partially ordered set. Given a cut (A,B) in X, we say that it admits a supremum iff \sup(A) exists.

Given any partially ordered set P, there is always a complete lattice that contains P, for example, the collection of downward closed subsets of P, under containment, where p\in P is identified with \{x\in P\mid x\le p\}.

Exercise 5 (MacNeille).
In fact, any poset \mathbb P=(P,\le) admits a minimal completion \mathcal L, in the sense that \mathcal L is a complete lattice containing \mathbb P, and \mathcal L embeds (as a poset) into any complete lattice that contains \mathbb P (with the embedding fixing P pointwise).

As with the rationals and the reals, a natural way of defining this minimal completion \mathcal L of \mathbb P is simply to take as \mathcal L the collection of all cuts in \mathbb P, partially ordered by saying that (A,B)\le(C,D) iff A\subseteq C. This construction is called the Dedekind-MacNeille (or normal) completion, first introduced in MacNeille [Mac37]. Verify that it indeed results in the minimal completion of \mathbb P.

Suppose that (A,B) is a cut of \mathbb P. Show that either A and B are disjoint, or else they meet at exactly one point.

Suppose that a\in P, A\subseteq\mathbb P, and a=\max(A)=\sup(A\setminus\{a\}). Let \hat A be the downward closure of A, and let B be the set of upper bounds of A. Show that (\hat A,B) is a cut but (\hat A\setminus\{a\},B) is not. This is slightly different from the situation with \mathbb Q and its completion \mathbb R, where commonly we require the two sets in a cut to have no elements in common. Does the Dedekind-MacNeille completion of \mathbb Q actually coincide with \mathbb R?

Exercise 6 (Birkhoff).
Say that a lattice \mathcal L is distributive iff p \land (q \lor r) = (p \land q) \lor (p \land r) for any p,q,r\in\mathcal L, where a \land b denotes the meet of a and b, and a\lor b denotes their join.

For example, \mathcal P(X) is a distributive lattice. Give an example of a lattice that is not distributive.

Prove Birkhoff’s representation theorem, also called the fundamental theorem for finite distributive lattices, stating that any such lattice is isomorphic to a lattice of finite sets, where the lattice operations are just given by union and intersection.

References

[Mac37]
Holbrook M. MacNeille.
Partially ordered sets.
Trans. Amer. Math. Soc. 42 (3), (1937), 416–460.
MR1501929.

Advertisements

Interpretations

August 18, 2013

(This started as an answer on Math.Stackexchange. This version has been lightly edited and expanded. Also posted at fff.)

Throughout this post, theory means first-order theory. In fact, we are concerned with theories that are recursively presented, though the abstract framework applies more generally. Thanks to Fredrik Engström Ellborg for suggesting in Google+ the reference Kaye-Wong, and to Ali Enayat for additional references and many useful conversations on this topic.

1.

Informally, to say that a theory T interprets a theory S means that there is a procedure for associating structures \mathcal N in the language of S to structures \mathcal M in the language of T in such a way that if \mathcal M is a model of T, then \mathcal N is a model of S.

Let us be a bit more precise, and do this syntactically to reduce the requirements of the metatheory. The original notion is due to Tarski, see

Alfred Tarski. Undecidable theories. In collaboration with Andrzej Mostowski and Raphael M. Robinson. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, Amsterdam, 1953. MR0058532 (15,384h).

I follow here the modern reference on interpretations,

Albert Visser, Categories of theories and interpretations, in Logic in Tehran, Lecture Notes in Logic, vol. 26, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 284–341. MR2262326 (2007j:03083).

One can take “the theory T interprets the theory S to mean that there are

  1. A map i that assigns formulas in the language of T to the symbols of the language \mathcal L of S, and
  2. A formula \mathrm{Dom}(x) in the language of T,

with the following properties: We can extend i to all \mathcal L-formulas recursively: i(\phi\land\psi)=i(\phi)\land i(\psi), etc, and i(\forall x\phi)=\forall x(\mathrm{Dom}(x)\to i(\phi)). It then holds that T proves

  1. \exists x\,\mathrm{Dom}(x), and
  2. i(\phi) for each axiom \phi of S (including the axioms of first-order logic).

Here, T,S are taken to be recursive, and so is i.

If the above happens, then we can see i as a strong witness to the fact that the consistency of T implies the consistency of S.

Two theories are mutually interpretable iff each one interprets the other. By the above, this is a strong version of the statement that they are equiconsistent.

Two theories are bi-interpretable iff they are mutually interpretable, and in fact, the interpretations i from T is S and j from S in T can be taken to be “inverses” of each other, in the sense that T proves that \phi and j(i(\phi)) are equivalent for each \phi in the language of T, and similarly for S, \psi and i(j(\psi)). In a sense, two theories that are bi-interpretable are very much “the same”, only differing in their presentation.

Read the rest of this entry »


Dedekind infinite power sets

November 15, 2012

Write A\preceq B to indicate that there is an injection from A into B, and A\preceq^* B to mean that either A=\emptyset, or else there is a surjection from B onto A. It is a result of Kuratowski that (provably in \mathsf{ZF}) if \omega\preceq\mathcal P(X), then in fact \omega\preceq^* X, and therefore \mathcal P(\omega)\preceq \mathcal P(X). This appears as Théorème B in pages 94-95 of

Alfred Tarski. Sur les ensembles finis, Fund. Math. 6 (1924), 45–95.

To prove this result, note that it suffices to find a countably infinite family of disjoint subsets of X. Suppose (m_n\mid n<\omega) is an injection of  \omega into \mathcal P(X). These sets induce a partition of X: Consider the equivalence classes of the relation x\sim y iff

\forall n(x\in m_n\Longleftrightarrow y\in m_n).

It is natural to attempt to show that these equivalence classes can be enumerated. Of course, the class of x is completely specified by the list of values of n such that x\in m_n, but this list may be “wasteful” in the sense that it may contain redundant information. For example, if m_3\subsetneq m_{27}, and we know that x\in m_3, then we automatically know that x\in m_{27}, and there is no need to include 27 in our list if we already included 3. (On the other hand, if all we know is that x\in m_{27}, then including 3 in the list is certainly providing us with more information.) This suggests to assign to each x\in X the set F(x)=\{n_0,n_1,\dots\}\subseteq\omega defined recursively as follows: Let n_0 be least such that x\in m_{n_0}, if it exists. If n_0 is defined, let n_1>n_0 be least such that x\in m_{n_1} and m_{n_1}\not\supset m_{n_0}, if it exists, and note that this is the same as requiring that m_{n_1}\cap m_{n_0}\subsetneq m_{n_0}. Similarly, if n_1 is defined, let n_2>n_1 be least such that x\in m_{n_2}, and m_{n_2}\cap m_{n_1}\cap m_{n_0}\subsetneq m_{n_1}\cap m_{n_0}, if it exists, etc.

Clearly, for any x,y\in X, x\sim y iff F(x)\sim F(y). There are now two possibilities:

  • Case 1. For some x, the set F(x) is infinite.

In this case, we are done (and we do not even need to bother enumerating the classes), because the sequence

m_{n_0}\setminus m_{n_1}, (m_{n_0}\cap m_{n_1})\setminus m_{n_2},(m_{n_0}\cap m_{n_1}\cap m_{n_2})\setminus m_{n_3},\dots

is a countably infinite collection of non-empty disjoint subsets of X.

  • Case 2. All sets F(x) are finite.

In this case we are done as well, because there is a (canonical) bijection between \omega and \text{Fin}(\omega), which means that we have enumerated the equivalence classes (and, of course, there are infinitely many, since the sets m_n are all distinct, and each is a union of equivalence classes).

Read the rest of this entry »


580 – Topics in Set Theory. ANNOUNCEMENT

March 5, 2012

 This Fall I will be teaching Topics in set theory. The unofficial name of the course is Combinatorial Set Theory.

We will cover diverse topics in combinatorial set theory, depending on time and the interests of the audience, with emphasis on three topics: Choice-free combinatorics, cardinal arithmetic, and partition calculus (a generalization of Ramsey theory).

Time permitting, we can also cover large cardinals, determinacy and infinite games, or cardinal invariants (the study of sizes of sets of reals), among others. I’m open to suggestions for topics, so feel free to email me or to post a comment.

Pre-requisites: Permission by instructor. The recommended background is knowledge of cardinals and ordinals. A basic course on set theory (like 502: Logic and Set Theory) would be ideal but is not required.

Grading: Based on homework.

Textbook: Combinatorial set theory, by Neil H. Williams. Elsevier Science (1977). ISBN-10: 0720407222, ISBN-13: 978-0720407228. The book seems to be out of print.

We will also use:

  • Combinatorial Set Theory: Partition Relations for Cardinals, by Paul Erdös, András Hajnal, Attila Máté, and Richard Rado. Elsevier Science (1984). ISBN-10: 0444861572,  ISBN-13: 978-0444861573. Apparently, this is also out of print.

I will distribute notes on the material of these books, on additional topics, and some papers that we will follow, particularly:

  • András Hajnal and Jean A. Larson. “Partition relations”, in Handbook of set theory, 129–213, Springer, 2010.
  • Jean A. Larson. “Infinite combinatorics”, in Handbook of the history of science, vol. 6, 145-357, Elsevier, 2012.

580- Specker trees

February 11, 2011

In his proof that the axiom of infinity holds in Quine’s New Foundations, Specker associated to each set {X} a tree, now called the Specker tree of {X}. (The name is due to Randall Holmes.)

In order to make sense of the definition without needing to appeal to the axiom of choice, let us define an equivalence relation {\sim} on subsets of {X} by saying that {A\sim B} iff {|A|=|B|}. The nodes of the tree are equivalence classes of subsets of {X} under {\sim}. Specifically, at the root we have the class of {X}, and the immediate successors of a class {[Y]} are the classes {[Z]} such that {|{\mathcal P}(Z)|=|Y|}.

Of course, under choice we can simply use cardinals {|Y|} as nodes, rather than the classes {[Y]}.

If {X} is a set, let {\aleph(X)}, the Hartogs function of {X}, be the set of all ordinals {\alpha} that inject into {X}, so {\aleph(X)} is the first ordinal that cannot inject. Sierpiński proved that {\aleph(X)\preceq{\mathcal P}^3(X)} and therefore {\aleph(X)<\aleph({\mathcal P}^3(X))}. This observation gives us immediately that the Specker tree of any set {X} is well-founded.

Under choice, it follows that all trees have finite rank. This is because any branch through the tree is finite (its nodes being a strictly decreasing sequence of cardinals). Moreover, the smallest cardinal in a branch is larger than the smallest cardinal in any larger branch. But an infinite-rank tree must have arbitrarily large branches, so there is no smallest cardinal in the tree, which is absurd.

Remarkably, it is still open whether in the absence of choice it is consistent that there is a Specker tree of infinite rank.

Typeset using LaTeX2WP. Here is a printable version of this post.


Luminy – Coda

October 27, 2010

While at Luminy, David Asperó showed me a quick proof of a nice result on Reinhardt cardinals in {\sf ZF}. It complements Grigor Sargsyan’s result discussed here.

Theorem (Asperó). Work in {\sf ZF}. Suppose j:V\to V is a nontrivial elementary embedding. Then there are a \bar\kappa<{\rm cp}(j) and an ordinal \alpha such that for all \beta there is a \mu and an elementary

\pi:V_\mu\to V_\mu

such that {\rm cp}(\pi)=\bar\kappa and \pi(\alpha)>\beta.

Proof. For \alpha an ordinal, set

\kappa^\alpha=\min\{\kappa\mid\exists\mu\exists i:V_\mu\to V_\mu such that {\rm cp}(i)=\kappa and {\rm ot}(\{\beta<\mu\mid i(\beta)=\beta\})\ge\alpha\}.

Note that suitable fragments of j witness that \kappa^\alpha is defined for all \alpha. Moreover, \alpha<\beta implies that \kappa^\alpha\le\kappa^\beta\le{\rm cp}(j), and therefore there is a \bar\kappa\le{\rm cp}(j) such that \kappa^\beta=\bar\kappa for all \beta sufficiently large. Moreover, since it is definable, we actually have \bar\kappa<{\rm cp}(j).

Let \alpha be least with \kappa^\beta=\bar\kappa for \beta\ge\alpha. We claim that \bar\kappa and \alpha are as wanted. For this, consider some \beta>\alpha, and pick i:V_\mu\to V_\mu witnessing that \bar\kappa=\kappa^\beta. All we need to do is to check that i(\alpha)\ge\beta.

But note that if \gamma\in[\alpha,\beta), then V_\mu\models\kappa^\gamma=\bar\kappa Hence, if i(\alpha)<\beta, we have

V_\mu\models \kappa^{i(\alpha)}=\bar\kappa.

But \kappa^{i(\alpha)}=i(\kappa^\alpha)=i(\bar\kappa)>\bar\kappa. Contradiction. \Box


580 -Partition calculus (7)

May 6, 2009

Updates

Let me begin with a couple of updates.

In the last Corollary of the Appendix to lecture I.5, I indicate that in {{\sf ZF},} we have that

\displaystyle  \aleph(X)<\aleph({\mathcal P}^2(X))

whenever {\aleph(X)} is not {\aleph_\alpha} for some infinite limit ordinal {\alpha<\aleph_\alpha.} In fact,

\displaystyle  {\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)

holds.

This result is best possible in terms of positive results. In Theorem 11 of the paper by John Hickman listed at the end, it is shown that for any such {\alpha} it is consistent with {{\sf ZF}} that there is an {X} with {\aleph(X)=\aleph_\alpha} for which {\aleph(X)=\aleph({\mathcal P}^2(X)).}

I also want to give an update on the topics discussed in lecture III.3.

{\mbox{Erd\H os}} and Hajnal asked whether it is possible to have infinite cardinals {\tau,\lambda,\kappa} such that

\displaystyle  \tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa}.

Galvin and Prikry showed (see Corollaries 16 and 18 of lecture III.3) that any such {\tau} must be larger than {\lambda^\kappa} and that {\kappa<\lambda.}

Following a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot hold.

The key is the following:

Lemma 1 If there are infinite cardinals {\tau,\lambda,\kappa} such that {\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa},} then for every sufficiently large {\gamma} there is an elementary embedding {j:M\rightarrow V_\gamma} such that {|M|=\lambda^\kappa,} {{\rm cp}(j)<\lambda,} {j(\lambda)=\lambda,} and {{}^\kappa M\subseteq M.}

 
Here is a brief sketch:

Proof: By Corollary 20 from lecture III.3, the given relation is equivalent to {\tau\rightarrow[\lambda]^\kappa_\lambda.} Consider a {\kappa}-Skolem function {F:[V_\gamma]^\kappa\rightarrow V_\gamma} so that any {Y\subset V_\gamma} closed under {F} is both closed under {\kappa}-sequences and an elementary substructure of {V_\gamma.}

Use {F} to define a coloring {G:[\tau]^\kappa\rightarrow\lambda} by setting {G(x)=F(x)} whenever {F(x)\in\lambda,} and {G(x)=0} otherwise. By assumption, there is {H\in[\tau]^\lambda} with {G''[H]^\kappa\ne\lambda.} Note that if {Y} is the closure of {H} under {F,} then {Y\cap\lambda=G''[H]^\kappa\cap\lambda\ne\lambda.} But we can assure that {|H\cap\lambda|=\lambda,} and the result follows by taking as {M} the transitive collapse of {H.} \Box

One concludes the proof by noting that it is impossible to have such embeddings. For this, it suffices that {{}^\omega M\subseteq M} and that {M} admits a fixed point past its critical point. One then obtains a contradiction just as in Kunen’s proof that there are no embeddings {j:V\rightarrow V,} see Corollary 9 in lecture III.3.

Similarly, Matthew Foreman has shown that there are no embeddings {j:M\rightarrow V} with {M} closed under {\omega}-sequences. The reason is that any such embedding must admit a fixed point past its critical point, as can be argued from the existence of scales. See the paper by Vickers and Welch listed at the end for a proof of this result.

On the other hand, it is still open whether one can have embeddings {j:M\rightarrow V} such that {M} computes cofinality {\omega} correctly.

1. The Baumgartner-Hajnal theorem

In Theorem 2 of lecture III.5 we showed the {\mbox{Erd\H os}}-Rado result that

\displaystyle  \kappa\rightarrow_{top}(Stationary,\omega+1)^2

whenever {\kappa} is regular. It is natural to wonder whether stronger results are possible. We restrict ourselves here to the case {\kappa=\omega_1.} Due to time constraints, we state quite a few results without proof.

Read the rest of this entry »