Forcing without choice: when countable sets yield reals

One natural way to show that a forcing adds no new reals is to show that it is countable closed (EDIT: this is somewhat misleading, see Joel’s comment below). However, it turns out that this is overkill: there are forcings not adding any reals which are not countably closed, in particular, which do add a … Read more

Equivalence of Rathjen’s continuum hypothesis and another form of the CH without choice

(This question is already posted on Math SE but it isn’t answered, so I ask same question on this site.) The following form of a continuum hypothesis occurs in Rathjen’s paper “Indefiniteness in semi-intuitionistic set theories: On a conjecture of Feferman”: Every non-empty subset A of R is a surjective image of ω or R … Read more

Graphs without maximal vertex-transivite subgraphs

The axiom of choice is of no use when trying to prove that every vertex-transitive subgraph is contained in a maximal vertex-transitive subgraph, because a union of an ascending chain of vertex-transitive subgraphs need not be vertex-transitive. Question. What is an example of a simple, undirected graph G=(V,E) that contains no maximal vertex-transitive subgraph? Precise … Read more

Cofinality without choice: can this coarse definition suffer badly?

This is a rephrased version of a question previously asked at MSE without success. Working in ZF, it is no longer possible in general to give every linear order an ordinal cofinality. For example, an infinite Dedekind-finite set of reals without a greatest element (viewed as a linear order) has no cofinal well-orderable suborder, and … Read more

How close to being well-orderable does this make my powerset?

Let’s work in a set theory without assuming AC (for instance, but not necessarily, ZF). Fix a set k satisfying k×k≃k, and consider its powerset X=2k. I have a technical condition that is satisfied whenever X is well-orderable, but I can’t tell what other examples there might be. Excuse the peculiar phrasing: I’m aiming for … Read more

Distributive lattices and axiom of choice

What form of the axiom of choice is equivalent (in ZF) to the statement that every distributive lattice is isomorphic to a lattice of sets? Answer According to Wikipedia the prime ideal theorem for distributive lattices is equivalent to the Boolean prime ideal theorem. (Look in the “Further prime ideal theorems” section.) AttributionSource : Link … Read more

Surreal numbers and the Axiom of Choice

In ZFC and its conservative extension NBG, it can be shown that every ordered field embeds into the surreal numbers. How much choice is needed to prove this? Without choice, what is a simple example of an ordered field that doesn’t fit into the surreals? Without choice, does there exist a strictly larger ordered field … Read more

How much choice do we need for regularity of product of regular spaces ?

It is usually stated that the (possibly uncountable) product of regular topological spaces is regular. However the only proof that I know of this fact seems to use the full axiom of choice : See here (proof based on Mukres’ Topology p.197). Do we really need AC (does this imply AC) ? Would it hold … Read more

Does ZF prove that proximity spaces are completely regular?

(This is based on my earlier question, but I think this one would be easier to answer.) Let ⟨X,δ⟩ be a separated proximity space, and let T be the induced topology on X. Then, ZF proves that ⟨X,T⟩ is regular Hausdorff, and ZF + (Dependent Choice) proves that ⟨X,T⟩ is completely regular. Does ZF prove … Read more

Stronger negation of AC given by rejecting “infinite hat” puzzles

Some of the strangest implications of AC are the “infinite hat” puzzles, which are on Wikipedia, and have been talked about on MO several times, including some variants. There are different ways to formalize these puzzles, but most of them follow the same basic principle: There is a countably-indexed sequence of things (reals, naturals, bits, … Read more