Gracious Living

A Couple Nuances
December 6, 2010, 03:01
Filed under: Logic, Math | Tags: , , ,

Started reading through Peter Smith’s “Gödel Without (Too Many) Tears” lecture notes yesterday, and I realized I hadn’t been as clear as I should have been in my treatment of Peano arithmetic.  So I started typing some errata, and I ended up typing a super-long exposition about All the Logic I Know.  This isn’t very much, because really I find mathematical logic a fascinatingly dull subject: it’s the sort of thing that looked cool when I was a kid because I could actually understand it, but now everything I read about it seems like this confusing haze of definitions and pseudophilosophical “theorems” about things actual math has left behind years ago.  So yeah.  What this means is: if you’re a logician, correct me if I get something wrong and please please try to convince me that your subject is cool and point me to a place where I can see that again.  I feel bad casting scorn on an entire branch of math just because it feels too weird and abstract.

Anyway, read on if you’re curious.  If you’re not, don’t.  I’ll cite this post whenever I prove Gödel’s Theorems but probably at no other time, so you won’t really miss much.  I do define quantifiers, which are these useful math symbols I might reuse: \forall x means “for all x” and \exists x means “there exists an x such that.”  Okay?  Okay.

Continue reading

Peano Arithmetic
December 4, 2010, 14:45
Filed under: Logic, Math | Tags: , , ,

Let’s do something fun!

The Peano axioms for arithmetic are something like the Zermelo-Fraenkel axioms for sets.  They describe what we intuitively want to be true about the natural numbers.  Using ZFC, we were able to prove the existence of an inductive set \mathbb{N}, and it’s actually pretty easy to prove that the axioms below hold for that set.  But the idea of the Peano axioms is that any structure satisfying them is “just as good” a model for the natural numbers.  That is, it’s a necessary fact about \mathbb{N} that every number has a successor, but it’s not a necessary fact that the successor of x is the set x\cup\{x\}.  It’s not even necessary that x be a set at all.

And in fact, there are other models.  We could take a category-theory approach and look at \mathbb{N} as the initial object in a category of things satisfying the axioms.  We could treat numbers as just numbers and not suppose any internal structure.  It doesn’t really matter, and perhaps this is the reason why we axiomatize stuff, so that we know what matters and what doesn’t.

The following is meant to be a bit of an exploration, mirroring Peano’s own exposition, into the properties of the natural numbers.  Many of them you probably saw in school, but now you can actually prove them from a very small set of definitions and axioms.  If nothing else, it’s a nice exercise in thinking logically.

Continue reading

The Axiom of Choice
November 5, 2010, 06:33
Filed under: Math, Set Theory | Tags: , , , ,

This post is going to be a bit more technical than most, so feel free to skim it if you find it difficult.  You should know the statements of the theorems and the definition of well-ordering, though.

When I stated the ZFC set axioms, I put choice last for a reason.  As I said there, it’s a bit like the parallel postulate in Euclidean geometry (if you don’t know this story, you should read about it — it’s fascinating).  Unlike the other axioms, it’s non-constructive, and it looks complicated enough that you should be able to get it from the other axioms, though it’s in fact independent of them (meaning they can’t prove it or disprove it).  For these reasons, many mathematicians in the early half of the century used choice sparingly, and made it very clear what pieces of their work required it.  But as we’ve seen, we needed it to show that every infinite set contains a sequence, and likewise, many of its consequences are so useful that it’s common nowadays to use it without reservation.  (And yes, Munroe, the Banach-Tarski paradox is a good thing.)

Besides important consequences, there are about four important equivalent statements to the axiom of choice, and that’s what I’ll be talking about today.  Hopefully this will give you an idea of what a choice function is and how powerful it is.  We’ll be showing the following statements are equivalent:

  1. The axiom of choice: every set S has a choice function c:\mathcal{P}(S)\rightarrow S such that c(A)\in A for all A\subset S.
  2. Every Cartesian product of non-empty sets is non-empty.
  3. Zorn’s Lemma: Every partially ordered set, in which every totally ordered subset has an upper bound, has a maximal element.
  4. Hausdorff Maximum Principle: Every partially ordered set has a maximal totally ordered subset.
  5. Well-Ordering Theorem: Every set can be well-ordered.

Below the fold, definitions of these terms and proofs of equivalence.

Continue reading

The Zermelo-Fraenkel Axioms for Sets
October 29, 2010, 13:17
Filed under: Math, Set Theory | Tags: , ,

I’m going to change tacks a bit here, leave topology behind for a second, and talk about sets from a less naive, more higher math perspective.  An axiom, by the way, is an assumed truth or defining property.
Most people are at least a little bit familiar with Euclid’s axioms for geometry; without actually saying what points or lines or planes are, they define (more or less) the essential relationships between them, and the true statements of geometry are all logical consequences of the axioms.

Table, Chair, Beer Mug

A statement of geometry?

Points, lines, and planes are supposed to be atomic, not relying on any previous definitions, so that their meanings are entirely given by the axioms, and not our preconceived notions of what they “look like.”  In the immortal words of David Hilbert, we must always be able to replace the words “point,” “line,” “plane” by “table,” “chair,” “beer mug” and still have valid proofs.

Well, the Zermelo-Fraenkel axioms (or ZFC; the C stands for “choice,” the last axiom) do essentially the same thing for set theory, with the ideas “set” and “element” taken as atomic.  So we can think of “sets” as being a kind of thing and “is an element of” as being a kind of “relation” between two sets, but other than that we shouldn’t be using the standard “collection-of-things” visualization that sets were first introduced with.  Rather, the axioms will formally give us the idea that “piles-of-things” model so well.  We’re also going to go forward without “things” to pile: all sets will be sets of other sets, and we only know that a set exists if we can build it from the axioms.

Below the jump, I introduce the axioms.  They’re usually given as sentences of formal logic, using mathematical symbols, but I’d rather say them in plain English.

Continue reading