JB: So, let’s think about how we can prove this generalization of Gödel’s completeness theorem. First, remember that a hyperdoctrine B is consistent iff B(0) has at least two elements, or in other words, ⊤ ≠ ⊥ in this boolean algebra. Second, let’s say a hyperdoctrine C is set-based if every C(n) is the power set of Vn for some fixed set V. We call V the universe. Third, let’s say a morphism of hyperdoctrines, say F: B → C, is a natural transformation whose components F(n): B(n) → C(n) are Boolean algebra homomorphisms obeying the Beck–Chevalley condition and maybe the Frobenius condition. (We’re a bit fuzzy about this and we’ll probably have to sharpen it up.) Continue reading
Category Archives: Math
Set Theory Jottings 11. Zermelo to the Rescue! (Part 2)
In 1908 Zermelo published his paper “Investigations in the foundations of set theory”. This contained the axiom system that eventually led to ZFC. Zermelo opens the paper with this rationale: Continue reading
Filed under History, Set Theory
First-Order Categorical Logic 13
MW: It’s been a minute! Well, almost 60,000 minutes.
We left off with a question: does a natural transformation from a syntactic hyperdoctrine to a semantic hyperdoctrine automatically “respect quantifiers”? We saw that this amounts to a Beck–Chevalley condition. We wondered if we had to add that condition to our definition of a model, or if it came for free. Continue reading
Filed under Categories, Conversations, Logic
Set Theory Jottings 10. Axiomatic Set Theory
“An Axiom, you know, is a thing that you accept without contradiction. For instance, if I were to say ‘Here we are!’ that would be accepted without any contradiction, and it’s a nice sort of remark to begin a conversation with. So it would be an Axiom. Or again, supposing I were to say, ‘Here we are not!’, that would be—”
“—a fib!” cried Bruno.
“that would be accepted, if people were civil”, continued the Professor; “so it would be another Axiom.”
“It might be an Axledum”, Bruno said: “but it wouldn’t be true!”
—Lewis Carroll, Sylvie and Bruno Concluded
Filed under History, Set Theory
Set Theory Jottings 9. Cantor Normal Form
Suppose β>1, and let ζ>0 be arbitrary. Then ζ has a unique representation in so-called Cantor normal form: Continue reading
Filed under Set Theory
Set Theory Jottings 8. Ordinal Arithmetic
Usually one defines the ordinal operations via transfinite induction:
Filed under Set Theory
Set Theory Jottings 7. The (Cantor-Dedekind-Schröder)-Bernstein Theorem
The trichotomy of cardinals says that for any 𝔪 and 𝔫, exactly one of these holds: 𝔪<𝔫, 𝔪=𝔫, or 𝔪>𝔫. It’s equivalent to the conjunction of these two propositions, for any two cardinals 𝔪 and 𝔫:
Filed under History, Set Theory
Set Theory Jottings 6. Zorn’s Lemma
Zermelo’s 1904 proof of the well-ordering theorem got a lot of blowback, as we’ve seen. On the other hand, the very next year Hamel used it to prove the existence of a so-called Hamel basis. In 1910, Steinitz made numerous applications in the theory of fields. He wrote:
Filed under History, Set Theory
Nonstandard Models of Arithmetic 32
Prev TOC Next
Previous Paris-Harrington post
[Ed. note: This post was essentially ready two years ago, but I got distracted with other matters. If you’re seeing this for the first time, or want to refresh your memory, posts 8 and 9 introduced the Paris-Harrington theorem. Posts 21 through 24 continued the discussion, in a dialog with Bruce Smith. MW]
Filed under Conversations, Peano Arithmetic
First-Order Categorical Logic 12
MW: Last time we looked at the categorical rendition of “C is a model of B”:
- Functors B:FinSet→BoolAlg and C:FinSet→BoolAlg
- A natural transformation F:B→C
where B and C are hyperdoctrines, and
- B is syntactic: the elements of each B(n) are equivalence classes of formulas (which we agreed to call predicates);
- C is semantic: the elements of each C(n) are relations on a domain V.
(We’ve been saying that C(n) is the set of all n-ary relations on V, but I see no need to assume that.)
Filed under Categories, Conversations, Logic
