Hot answers tagged

12

The statement "every cardinality has an ordinal with this cardinality" is equivalent to axiom of choice (and hence is unprovable without it). It is so because, if you think about it a little, your statement is equivalent "every set has an ordinal of the same cardinality", and so "for every set there is a bijection between it and some ordinal" and thus "every ...


8

With your definition of "infinite set" (which is Dedekind's definition, not the usual one), no axioms beyond ZF are needed to prove that $\aleph_0$ is the smallest infinite cardinal. Let $A$ be an infinite set, and let $\phi:A\to A$ be an injection which is not a bijection. Choose an element $a\in A\setminus\phi(A).$ Then ...


7

This is an open problem. It was shown that for every $\kappa$, $\sf DC_\kappa$ cannot prove that the cardinals are well-founded. While not enough to conclude the principle is equivalent to the axiom of choice ($\sf BPI$ does not follow from $\sf DC_\kappa$ either), it is worth remarking that we really don't know much about this principle. A very recent ...


6

The answer is that you can't. Instead of omitting foundation, I'll add atoms. You can replace them by Quine atoms and have the same results without foundations to your liking. We construct the same permutation model as in this answer: start with a proper class of atoms and global choice, and make the class of atoms have only finite subsets while preserving ...


6

The "most natural axiom" to add is perhaps the axiom of countable choice which asserts the existence of a choice function for every countable family of non-empty sets. I'd even argue that the true "natural axiom" would be the principle of dependent choice, which is a slight (but significant) strengthening of countable choice which posits that recursive ...


5

You can indeed adopt the axiom "every infinite set has a countably infinite subset", i.e., "every set that is not equipotent to a natural number (=finite ordinal) has a subset equipotent to the set $\omega = \mathbb{N}$ of natural numbers". This can also be reformulated as "every D-finite set is finite", where a D[edekind]-finite set is one that does not ...


5

Based on the information you provide this is a mistake. You are correct in that it is consistent that there is a countable family of finite sets whose product is empty (namely, they do not have a choice function). For example in Cohen's second model for the failure of choice there is such family of sets of size $2$.


4

The answer is negative. An easy example is subsets of the Cantor set which have null measure, but can be "very non measurable". But this is sort of cheating since the Cantor set can be endowed with its own measure which is isomorphic to the actual Lebesgue measure on the unit interval, and there these subsets of the Cantor set need not be measurable ...


4

Yes. Suppose not, look at $X^c$ which is of positive measure. By Lebesgue Density Theorem, there exists $\sigma, \tau\in 2^{\omega}$ (WLOG might assume they have the same length) such that $X$ and $X^c$ has measure $>\frac{1}{2}$ above $\tau, \sigma$ respectively. By hypothesis, $X$ has measure $>\frac{1}{2}$ above $\sigma$ too. But then above ...


4

$\mathbb{R}/\mathbb{Q}$ is a $\mathbb{Q}$-vector space. Choose a $\mathbb{Q}$-basis for $\mathbb{R}/\mathbb{Q}$, and pick a preimage for each basis vector in $\mathbb{R}$. By mapping each basis vector to the chosen preimage, you have successfully constructed a $\mathbb{Q}$-linear map $\mathbb{R}/\mathbb{Q} \to \mathbb{R}$ that splits the quotient map. This ...


4

Note: I completely rewrote my previous attempt - posted in another (now deleted) answer, since the previous version was incorrect. Thanks to Asaf Karagila for pointing out the problem with my previous proof. And also to Eric Wofsey for simplifying some steps in the proof. Let us hope that this time I have avoided mistakes. The formulation of the version of ...


3

Yes, one can easily prove they are equivalent. The reason is that in order to prove the Axiom of Choice, for example, we resort to a partial order where each chain has a least upper bound. Similarly, to prove Hausdorff's maximality principle from Zorn's lemma we use only partial orders in which a chain has a least upper bound. And this can be used to prove ...


3

(1,2) As written, the proof certainly seems to appeal to the axiom of choice for choosing each of the $x_y$s. But this is not necessary and easily eliminated: since you know that $A$ is countable, you can choose a bijection $A\leftrightarrow \mathbb N$ once and for all, and then for every $y$ let $x_y$ be the element in $F_y$ that has the smallest index. ...


3

For the deepest results about partially ordered sets we need a new set-theoretic tool; ... We begin by observing that a set is either empty or it is not, and if it is not, then, by the definition of the empty set, there is an element in it. This remark can be generalized. If $X$ and $Y$ are sets, and if one of them is empty, then the Cartesian product ...


3

Your proof does not prove $\sf AC2$ as stated. It does show that if $f\colon A\to B$ is a surjection, and $g$ is a right inverse, then $g$ is a choice function from a family of pairwise disjoint non-empty sets. What you need to do is start with a family of pairwise disjoint non-empty sets, and then use that family of produce a surjection whose right inverse ...


3

This is probably going to be very unilluminating, but here goes: "If, in a partial order $P$, every chain $C$ has an upper bound, then $P$ has a maximal element." Let's start with the obvious bit: how do we talk about partial orders in set theory? Note that we could also ask, "How do we talk about groups in set theory?" or rings, or fields, or . . . ...


3

There is no simple explanation. The only thing you can give as an intuition is that Zorn's lemma fails. And its failure is witnessed already in these parts. The construction is written in a fairly outdated language, but here's what I can speculate from what's in the paper and the things I know about these constructions. We add a generic copy of the ...


3

Indeed, the cardinalities do not need to form a lattice without the axiom of choice. Suppose $A$ and $B$ are infinite Dedekind-finite sets of incomparable cardinality, and suppose $A, B$ both embed via $f, g$ into $C$, with $C=ran(f)\cup ran(g)$. Then it's easy to see that $C$ is also Dedekind-finite, so if we remove an element from $C$ we get a set of ...


2

Yes, this is consistent; for instance, if $A$ is an amorphous set. An amorphous set is an infinite set which cannot be partitioned into two infinite pieces: if $A=B\sqcup C$, then either $B$ or $C$ is finite. It's easy to show that any two subsets of an amorphous set are comparable, and the existence of amorphous sets is consistent with $ZF$. I'm not ...


2

As suggested by Wojowu and Henno, there are two prime reasons why you cannot show that every cardinality has an ordinal with this cardinality without the use of AC: The principle of linearity of cardinals is equivalent to AC, and if every cardinality has an ordinal with this cardinality, then, given two cardinalities, there are two ordinals with those ...


2

Try replacing $Y$ by the image of $f$; and extend the section you get by any means necessary (here the fact $X$ is nonempty plays a role). I'm not sure how to cast this in category theoretic terms. But the idea that you can factor $f$ via restricting the codomain, and then use the axiom of choice.


2

I'm no expert, but I think no. IIRC, ordinals are linearly ordered without using any choice. If we could show your result, it would imply cardinals are linearly ordered, and if memory serves me, this implies the Axiom of Choice.


2

Just use the same method as in the usual proof of Hahn-Banach to extend your functional to each point of a countable dense subset one at a time by induction. You then get that the functional is defined on a dense subspace of $X$, and so then you can extend it to all of $X$ by just taking limits (and can check that this is well-defined because the functional ...


1

The measure theoretic part was answered, so let me complement it by answering the choice related question. The axiom of countable choice is needed on a far more fundamental level when you talk about measure theory. It is consistent that the real numbers are a countable union of countable sets. In that case there is no $\sigma$-additive Borel measure ...


1

You have some boxes, at least one. There may be only one box, seven boxes, or infinitely many boxes. In each and every box, there are some items. at least one. There may be arbitrarily many items. Question: Can you pick, at least in principle, exactly one item from each box, without necessarily describing the details or rules of how you select them? The ...


1

No. Recall that $\Bbb C$ has a countable basis, which we can enumerate. Now given a set of isolated points, they can be separated by open sets, each containing a unique point in the set. So they can be separated by basic open sets. We can choose the least basic open set in our enumeration which works. So there is an injection from the set today isolated ...


1

If you're willing to think about semigroups rather than monoids, then some further comments are in order. First comment. Every set $X$ carries two canonical semigroup structures: The "left zero" semigroup: $xy=x$ for all $x,y \in X$. The "right zero" semigroup: $xy=y$ for all $x,y \in X$. This gives two non-equivalent functors $$\mathbf{SemiGrp} ...



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