« first day (2748 days earlier)      last day (363 days later) » 

05:14
@user21820 Do you know how much of the constructible universe PA2 can build? I know that, for any wellordering of the naturals, PA2 can perform a transfinite recursion which builds (a copy of) an initial segment of L to that length. I also know that, if two wellorders are isomorphic, then the resulting L structures are also provably isomorphic, and thus between any two such L structures, one of them is embeddable into the other in a natural way. Do you know if PA2 can unify all such structures?
The primary roadblock seems to come from the fact that the various L structures need to use completely different indexing/encoding schemes, since they are constructed relative to a certain encoding of a wellorder. Since we don't have sets of subsets of naturals, we cannot simply merge all these structures modulo the appropriate equivalence relation.... but maybe there's some other way to do it.
05:48
For example, if there were some method to choose a canonical representative of each wellordering (a way to choose a canonical subset of ℕ^2 for each wellordering), then we could unify all the L segments. We could define the order relation on these ordinals in terms of order embeddings, leading to a unification of all countable wellorderings. It should be possible to prove that the unified ordering is also a wellorder (as a theorem schema), and that we can perform transfinite recursions over the entire length of the ordering (again, as a schema).
 
3 hours later…
08:49
Ah, I figured it out
Also, hello 21820!
@JadeVanadium: I also figured it out before I saw your last message!
You can fix a recursive relation R between layers of L.
So you can then just use the tower technique.
Wait...
It doesn't work.
I know if you have a choice operator it is trivial, but I don't see how we can do without now.
Yeah, it seems we can't necessarily choose representatives for every layer, due to issues with Choice. There's also the possibility that the ℵ1 of L is smaller than the ℵ1 implicitly granted by PA2, which causes other issues. However, we can choose a representation for every wellordering which is countable in L, and this does permit us to build a unified L structure. This lets us interpret a theory of hereditarily countable sets in which every set is constructible.
09:11
Basically, given any set in L (defined in terms of any wellorder), we can find a subset of ℕ^2 which encodes the membership graph. We can then define a nonstandard membership relation between our encodings, by appealing to membership isomorphisms. This basically gives us a unified L, except there's no apparent way to quotient all the representatives down, because we have no way to choose between subsets of ℕ, i.e. there's no apparent way to choose a canonical encoding.

We can use the canonical wellordering of L, however, to choose the encodings. We do get some trouble here, though, because
09:22
The fine details are all handled using Replacement over the ordinals. We can "sum together" countably many wellorders of ℕ to get much larger wellorders, and this results in Replacement and Specification over L (where quantifiers/parameters are restricted to the encodings of constructible sets). It's then a standard property of L that you have Specification and Replacement below any cardinal, so L[ℵ1] behaves as expected and we get a theory for hereditarily countable sets.
09:55
@JadeVanadium Hi Jade. I want to ask you a question.
Howdy! shoot
What is cofinality in set theory?
Like it seems like an artificial concept to me.
Very good question. There are a bunch of different uses, but basically it's used as a tool to measure how susceptible an ordinal is to Replacement. So, the basic idea is, consider an ordinal number β (or it can be a wellordered set, or whatever). Given a subset S⊆β, we say that S is cofinal in β when: for all x<β, there exists y∈S such that x≤y. Since β is wellordered, then S is also wellordered, hence S can be assigned an ordinal number order type...
The cofinality of β is the smallest order type of any cofinal subset.
So, suppose the cofinality of β is some other ordinal number α. This means that there exists a cofinal set S⊆β such that the order type of S is exactly α. Of course, since the entire notion of order type is based on bijections, there is also an equivalent notion of cofinality defined in terms of functions. Given ordinals α,β, and a function f:α→β, we say that f is cofinal in β when it holds that, for all y<β, there exists x<α such that y≤f(x)
Using this functional definition, we could equivalently define "the cofinality of β" as the smallest ordinal α such that there exists a cofinal function f:α→β. This definition in terms of functions is equivalent to the previous definition in terms of sets. A function is cofinal if and only if its image is cofinal.
The reason set theorists care about cofinality is basically for the same reason we care about cardinality. For example, if I tell you that a set S is (infinite and) countable, then you know that there is a bijection between S and the natural numbers. Because you have this bijection, you know a lot of other things about S. For example, the powerset of S is bijectible with the powerset of the naturals. Also, S can be partitioned into countably many finite sets (or finitely many countable sets).
If S is some abstract structure, then you also know there's a very good chance that S could probably be constructed using first-order Peano Arithmetic, and this knowledge might tell you something else interesting.
Cofinality is used for the same kind of purposes. Take for example the cardinal number ℵ[ω]. It's not hard to prove that the cofinality of this cardinal is exactly ω. This happens because the set {ℵ[n] : n<ω} is a cofinal subset of ℵ[ω], and it has order type ω. Because it has cofinality ω, then ℵ[ω] is accessible via countable Replacement. That is to say, there is a definable function with domain ω such that the limit of the function is ℵ[ω], and this function is simply the map n↦ℵ[n].
If you were in a context where you have access to countable Replacement, and also you have access to all the ℵ[n] cardinals, then you immediately know you also have access to ℵ[ω], simply because ℵ[ω] is the limit of a countable sequence.
The relationship between cofinality and cardinality is actually much tighter than this. In general, the cofinality of an ordinal is always a cardinal number, and more specifically it's always a regular ordinal. Regular ordinals are ordinals which are equal to their own cofinality, and thus they are immune to Replacement. It's also possible to prove that an infinite ordinal is a cardinal if and only if it's the limit of regular ordinals, so they are very closely related.
Cofinality also comes up a lot when dealing with large cardinal axioms, and it is precisely because of its relationship with Replacement. For example, we know that all successor cardinals are regular, and thus they are immune to Replacement from below. However, successor cardinals are mune to Powerset, since the cardinality of the powerset is always at least as large as the cardinality of the successor cardinal.
The only case in which a cardinal is simultaneously immune to Replacement and Powerset is when it's a strongly inaccessible cardinal. Equivalently, the inaccessible cardinals are precisely the regular limit cardinals....
Due to the ambiguity about the Generalized Continuum Hypothesis, there is a notion of weakly inaccessible (a regular cardinal which is a limit of Aleph numbers) and strongly inaccessible (a regular cardinal which is a limit of Beth numbers), but it's basically the same idea. The two objects are equiconsistent; weakly inaccessible cardinals become strongly inaccessible in the constructible universe, so it's just a matter of taste.
10:26
@JadeVanadium Your explanation already exceeded all my expectations, but feel free to add more if you want =D
Nah, that's all I can think of, off the top of my head. TL;DR cofinality is just used to analyze the internal structure of an ordinal, to measure how susceptible it is to Replacement. In the context of large cardinals, cofinality is used to define inaccessible cardinals, which are the most fundamental type of large cardinals.
I wish someone told me sooner about the relationship of cofinality and replacement...
I don't know how to thank you enough. Thanks for enlightening me (^_^)
No problem, I love to nerd out about cardinals :)

« first day (2748 days earlier)      last day (363 days later) »