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