Hot answers tagged axiom-of-choice
12
Before entering, the mathematicians agree on a choice of representatives for real sequences when two sequence are equivalent if they are equal past some index ; and a re-labeling of $\Bbb N$ into $M \times \Bbb N$ where $M$ is the set of mathematicians.
Once a mathematician $m$ is in the room, he opens every box not labeled $(m,x)$ for $x \in \Bbb N$, and ...
7
Here is a nice way of proving the well-ordering principle from "Every tree has a branch":
Let $A$ be an infinite set, and let $\lambda$ be the least ordinal such that there is no injection from $\lambda$ into $A$. Consider the set $A^{<\lambda}$, that is all the functions from ordinals smaller than $\lambda$ into $A$, and order those by end-extension ...
7
It is a theorem of Wolk [1] that for every infinite $\kappa$ the axiom $\sf DC_\kappa$ is equivalent to the following statement:
If $(P,\leq)$ is a partially ordered set in which every well-ordered chain has order type $<\kappa$ and has an upper-bound, then $P$ contains a maximal element.
In the case of $\kappa=\omega$ this means that every partial ...
7
The answer is yes, under the axiom of choice, such a partition is possible. There are several ways of seeing this. For example, choice gives us that any set is in bijection with an infinite ordinal. But, for any infinite ordinal $\alpha$, there is a bijection between $\alpha$ and $\alpha\times \{1,\dots,n\}$. The bijection is in fact canonical, in the sense ...
6
Assume that we have a poset $(X,\leq)$ such that each linearly ordered subset of it has an upper bound. Define the following tree:
$s\in T$ if $s\subseteq X$ and $(s,\leq)$ is a linear order and let the order relation of the tree be $s<t$ if and only if $s$ is an initial segment of $t$. It's easy to see that this is a tree. Now take a branch of the ...
5
Let me rewrite the answer completely.
You wrote three definitions for a regular cardinal, and you made two false claims. First let me write the definitions, so we'll be clear on those.
Let $\kappa$ be an infinite initial ordinal (i.e. a cardinal in the context of $\sf ZFC$).
$\kappa$ is $1$-regular if every unbounded subset of $\kappa$ has order type ...
5
Suppose that $A$ is infinite and Dedekind finite. Then $\mathfrak m=|A\cup\mathbb N|$ satisfies that $|A|<\mathfrak m$, $\aleph_0<\mathfrak m$, and $\mathfrak m+\mathfrak m>\mathfrak m$.
To see the last inequality, note that if $\mathfrak m+\mathfrak m=\mathfrak m$ then $A\times 2$ embeds into $A\cup\mathbb N$, say via $f$, but only a finite ...
4
To add slightly on Andres' answer, it is not only that $\frak m+m=m$ does not imply $\sf AC_\omega$, but in the other direction we can have $\sf DC_\kappa$ (for an arbitrary $\kappa$) but $\frak m+m=m$ fails.
We say that $A$ is a $\kappa$-amorphous set if every subset of $A$ has cardinality $<\kappa$, or its complement has such cardinality - but not ...
4
There is a concept called amorphous sets, which becomes interesting when the axiom of choice fails. These sets are such that you cannot partition them into two distinct infinite sets.
One property of amorphous sets is that if we take an infinite partition of an amorphous set, then all but finitely many parts have the same size (and all these sizes are ...
3
In fact ZF also has non-definable sets. All you need is that classical logic holds and that it is a subtheory of ZFC.
Let $\phi(x)$ state that $x$ is a set that is a well ordering of the reals if a well ordering of the reals exists. By excluded middle there is such an $x$, because if there is a well ordering of the reals, we can use that, and if there is no ...
3
No. You can never map $\omega$ onto $\omega_1$. Not without the axiom of choice, and certainly not with it.
The reason is that if $f\colon\alpha\to A$ is a surjection, and $\alpha$ is an ordinal, then there is an injection from $A$ into $\alpha$. Simply take $g(a)=\min\{\beta<\alpha\mid f(\beta)=a\}$. You should convince yourself that this is a ...
3
Yes, assuming the axiom of choice. Without the axiom of choice one might have an amorphous set. Such a set is uncountable in the sense that it is not finite, and there is no bijection between it and $\Bbb N$. However, it is not the disjoint union of any two infinite subsets.
2
Every set of ordinals is well-ordered by $\in$, and therefore is isomorphic to a unique ordinal, and in fact the isomorphism is unique and does not require the axiom of choice. In fact this is the Mostowski collapse of $S_n$. The minimum goes to $0$, and by recursion we continue and collapse more and more ordinals until we finish collapsing $S_n$. Being ...
2
No.
Without choice, we can say that if $A,B$ are sets and $B$ is well-orderable, then $|A|\le|B|$ iff there is a surjection $B\to A$. The Axiom of Choice is equivalent to the statement that every set is well-orderable, which is why we needn't make the distinction in that setting.
If we could map $\aleph_0\to\aleph_1$ surjectively, then we could map ...
2
The answer is undecidable. We know it could be $2^{\aleph_0}$ and it could be $2^{2^{\aleph_0}}$. I am unaware of results that it could be an intermediate cardinality, though.
It is true that there are always the continuous ones (and there are $2^{\aleph_0}$ of those), but it is consistent that there are only the continuous ones. For example in Solovay's ...
2
The argument proposed by Zhen Lin works once one knows that $Y$ (as defined there) is well-ordered by the "obvious" relation $\prec$, namely that one equivalence class is smaller than another if some (equivalently every) element of the first class embeds as a proper initial segment in some (equivalently every) element of the second class. Zhen Lin leaves ...
2
Some Choice is used in justifying the assumptions on $B$ -- effectively, in proving Exercise 16.1. I will sketch this below.
It is clear that passing to an uncountable subset of our given family does not influence solving the problem (a $\Delta$-system on this subset is one for the entire family as well).
Now we invoke a bit of Choice to ensure that ...
1
A geometric answer, for cardinality $c$. For $x, y \in S^1$ (the unit circle), let $x \sim y$ iff $x$ and $y$ are vertices of the same regular $n$-gon centered at the origin. Now the title of this question speaks of infinite sets generally, which is a different question. The approach by Hagen von Eitzen is probably about the best you'll find in the general ...
1
This is mentioned (and proved) in the second page of the following paper,
Herbert Federer and Bjarni Jonsson, Some Properties of Free Groups. Transactions of the American Mathematical Society, Vol. 68, No. 1 (Jan., 1950), pp. 1-27.
Some three decades later this was also addressed in the following paper (Problems 4 & 5),
Paul E. Howard, ...
Only top voted, non community-wiki answers of a minimum length are eligible
