Hot answers tagged

48

The well-ordering principle does not say, "Every linear order is a well-ordering." It says, "Every set can be well-ordered." For instance, the set of integers is usually ordered as: $. . . -3<-2<-1<0<1<2<3<. . .$. This is clearly not a well-ordering. However, we can define a new ordering, $\prec$, as follows: $$0\prec -1\prec 1\prec ...


22

Noah wrote an excellent answer. But let me make one of his points even clearer. Sets do not carry any structure. Some sets, however, arise in a very natural way from structure, that when we write them we implicitly think about them as structured sets. $\Bbb R$ is just a set, but we think about it as an ordered field. $\ell^2$ is just a set, but we think ...


14

This is a very natural question, even if a little subjective (due to the inherent subjectivity of what does it mean "weird"). But the answer is that the axiom of choice is not the cause of weirdness. The axiom of choice is just a tool with which we can prove there is some uniform "mess" throughout the universe of sets. But it really helps us to rein down ...


14

Brian's answer addresses the "strong" version of your question: asking for an explicit counterexample. If, on the other hand, all you want is an example of a pair of sets which might form a counterexample to Trichotomy, it turns out we can do this! The easiest is probably the following: it is undecidable in ZF whether there is an injection in either ...


14

If we could give an explicit example of sets for which we could prove the non-existence of such injections, the axiom of choice would be false. However, there are models of $\mathsf{ZF}$ without the axiom of choice in which there are Dedekind finite sets that are not finite. If $X$ is such a set, there is no injection from $X$ to $\Bbb N$ or from $\Bbb N$ to ...


8

There is no example in any good and reasonable sense of the word. Given any two sets $A$ and $B$, there is an extension of the universe, to a larger universe of $\sf ZF$, in which both $A$ and $B$ are countable, and therefore can be compared. You might want to talk about "definitions" rather than concrete sets. But even that can be difficult. Any ...


4

No, your solution does not work because you appealed to the axiom of choice in choosing $z$ in order to define the injection. Instead, use the fact that $f$ is a bijection to conclude that $f(\{(x,y)\mid y\in b\})\cap b$ creates a partition of $b$ indexed by $a$, and therefore defines a surjection from $b$ onto $a$.


4

There is no explicit example of a non-principal ultrafilter over the natural numbers without appealing to choice. We know this because there are models of $\sf ZF$ where every ultrafilter over the natural numbers is principal. In fact there are models where every ultrafilter over any set is principal. The proofs are quite technical and require ...


3

Yes, the point is that $W=X$. The key to that is the last part of the conclusion of the lemma: $F(W)\in W$, which is the same as $\sigma(X\setminus W)\in W$. If $X\setminus W$ is nonempty, then this contradicts $\sigma$ being a choice function, so the only way we can have $\sigma(X\setminus W)\in W$ is if $X\setminus W=\varnothing$, in which case ...


3

This is the Szpilrajn extension theorem; it’s a result that follows from the axiom of choice. In fact, it follows from but does not imply the weaker compactness theorem for first-order logic or the equivalent Boolean prime ideal theorem. Its proof from the result for finite partial orders and either the compactness theorem or the equivalent ultrafilter ...


2

The question is what do you mean by large cardinals and what do you mean by useful? For example, it is consistent that there exists a set $A$ such that the cofinite filter on $A$ is an ultrafilter. We can even show that such ultrafilter is closed under intersection of ordinal-indexed sequences (mainly because under this assumption every such sequence is ...


2

Choice is indeed necessary - for one thing, even the statement "Every set can be linearly ordered" is not provable in ZF alone! See http://mathoverflow.net/questions/37272/are-all-sets-totally-ordered.


2

No, of course not. Consider the case with Russell's socks. It is consistent that there is a countable family of pairwise disjoint sets of size $2$, whose union does not have any countably infinite subset. Namely, the coproduct $\coprod_{n\in\Bbb N}P_n$ is not isomorphic, or even comparable, with $\Bbb N$. But on the other hand, $\Bbb N$ can certainly be ...


2

You can do much better. Assuming the axiom of choice, you can partition $\mathbb R$ into $2^{\aleph_0}$ disjoint parts, so that every uncountable Borel set intersects all of the parts. The construction is a straightforward diagonalization, using the fact that there are only $2^{\aleph_0}$ uncountable closed sets, and each of those sets contains ...


2

The question can be answered browsing: Gregory H. Moore, Zermelo's Axiom of Choice: Its Origins, Development, and Influence (1982, also Dover reprint. [page 167] the concept of maximality, though not the name, emerged as a distinct notion only with Hausdorff's researches of 1907 on ordered sets of real functions. In particular, he applied the ...


1

It means that if you assume the truth of the Axiom of Choice then you can prove the well-ordering theorem, and if you assume the well-ordering theorem then you can prove Zorn's Lemma and if you assume Zorn's Lemma you can prove the Axiom of Choice. Take your pick. Each is equivalent to the other, but the only thing proved is their equivilence.


1

In ZF: You can define the $\sigma$-rank of a member of $X$ as the first $\alpha$ at which it shows up in $\gamma_\alpha$ if it ever does, and $0$ otherwise. Replacement then gives you a set of all $\sigma$-ranks of members of $X$. Every set of ordinals has an upper bound (due to Burali-Forti), so you can safely stop the iteration when you reach that upper ...


1

The other direction is trickier because it requires more assumptions. Specifically, the implication from "The power set of an ordinal can be well-ordered" to "The axiom of choice" requires the use of the axiom of foundation. Which is usually less natural when it comes to thinking about mathematics... naively. We also know this is necessary. In $\sf ZFA$, ...


1

Too long for a comment: Certainly no choice can be required here. The comments sketch a solution, but even without knowing the solution, this follows from a general fact: Shoenfield absoluteness. Shoenfield absoluteness (among other things) isolates a class of statements which, if provable from ZFC, are also provable from ZF. Certainly not every statement ...



Only top voted, non community-wiki answers of a minimum length are eligible