Tag Info

Hot answers tagged

18

First let us clear up the definitions, since there may be some confusion about them. We say that a set $A$ is finite, if there is a natural number $n$ and a bijection between $A$ and $\{0,\ldots,n-1\}$. If $A$ is not finite, we say that it is infinite. We say that a set $A$ is Dedekind-finite, if whenever $f\colon A\to A$ is an injective function, then $f$ ...


17

This cannot be proved without the axiom of choice. A set with no countably infinite subset is called a Dedekind-finite set. An equivalent characterization is that the set is not in one-to-one correspondence with any proper subset of itself. This condition is equivalent to finiteness in ZFC but not in ZF. (See ...


8

Yes, some part of the axiom of choice is needed. In the absence of the axiom of choice it's consistent that there be an infinite, Dedekind finite set, and such a set admits no injection from $\Bbb N$.


6

It looks like it requires countable choice, but you can certainly modify it so that it no longer requires choice. Namely, define $a_1=r_1$ and $b_1=b$. Then, for each $n \in \mathbb{N}$, given $a_n,b_n$, there are two possibilities: $r_{n+1} \le a_n$ or $r_{n+1} \ge b_n$. In this case, let $a_{n+1} = \frac{2a_n+b_n}{3}$ and $b_{n+1} = \frac{a_n+2b_n}{3}$; ...


5

No, this is impossible. While $\operatorname{Con}\sf (ZFC)$ is an arithmetic statement which can therefore be used to construct a Turing machine which will not provably half in $\sf ZFC$, the axiom of choice is not even remotely a statement about the integers. So there is no chance that this is going to happen. Slightly more formally, though, recall that ...


5

What you call the "special continuum hypothesis" (NOTE: this term does not appear anywhere I can find; the abbreviation "SCH" refers to the "Singular Cardinal Hypothesis," a quite different statement) does not imply choice. First of all, note that even the full continuum hypothesis - "Every infinite set which is not countable, admits an injection from ...


5

There are no implications whatsoever. As a general rule, if $\varphi$ is a statement which only deals with a single definable set (e.g. the natural numbers, or the real numbers), then it will not imply the axiom of choice. More correctly, if $\varphi$ is a statement such that for some $\alpha$, $\varphi$ holds if and only if $(V_\alpha,\in)\models\varphi$, ...


4

If the definition for a set $A$ being infinite is $\exists f: \omega \to A$ injective, then in any model of ZF you can find a countably infinite subset of $A$ by taking the range of $f$ whose existence follows from replacement. However, if the definition is $A$ is not finite, namely, there exists no bijection from $A$ to any $n\in \omega$, then the ...


4

This statement is in fact equivalent to the axiom of choice. Suppose that the axiom of choice fails, and let $\{A_i\mid i\in I\}$ be a family of non-empty sets not admitting a choice function. Take $X=\bigcup A_i\cup I$. Now fix some $i_0\in I$ and consider the function $f(x)=\begin{cases}A_i& x=i\\ A_{i_0}& x\notin I\end{cases}$, if this admitted ...


3

Not quite a complete answer to your question, but too long for a comment: http://projecteuclid.org/download/pdf_1/euclid.pjm/1102983625 shows that e.g. the axiom of choice for all familes of sets with exactly two elements, does not prove the axiom of choice for all families of sets with exactly 3 elements. (see page 235). This strongly suggests that the ...


3

In very short terms (you are allready overwhelmed by good answers of experts): $$\omega\leq_{1}A\implies\neg A<_{1}\omega$$ Or in words:$$A\text{ is Dedekind-infinite}\implies A\text{ is infinite}$$ But for the converse you need a weakened form of AC. The axiom that every countable set has a choice-function (denoted as CC) will do. This axiom ...


3

First of all, yes. $\omega_1$ exists without assuming the axiom of choice. However it can be the countable union of countable sets, which can cause some troubles. Let me just point out that $\omega_1$ is, by definition, the set $[0,\omega_1)$. So I'll just use the shorter notation to make it easier. So if $\omega_1$ is the countable union of countable sets, ...


2

Recall that $x$ is a limit point of $A$ if and only if every neighborhood of $x$ meets $A$ on an infinite set. So in any case a discrete space will never be Weierstrass compact. Simply because $\{x\}$ is a neighborhood of $x$. So no infinite set has any limit point. So the only way a discrete space can be Weierstrass is that it is finite, and the ...


2

The proof is presented in a way that supposedly use dependent choice, which is in fact stronger than countable choice. However this can be avoided in one of several ways. As Clive suggested, using $(a,b)$ as a bootstrap, you can generate algorithmically smaller and smaller intervals. As Carl suggested, you can use the fact that the rational numbers are ...


2

You are correct that you can construct the ordinals and prove they can have unboundedly large cardinality without Choice. However, the problem with your argument is that you can't explicitly write down a correspondence between elements of your set and ordinals without a choice function on subsets of your set. To see this more clearly, let's make your ...


2

I suppose that you mean the proof of the well-ordering theorem. You construct an injective function from a set $X$ into an ordinal. At each step you choose an arbitrary element. And at limit steps you want to be sure that all your previous steps are coherent. And these two things you can't really pull transfinitely without the axiom of choice. The proof, ...


1

Short answer : no At first, you must understand that, for any machine $M$, the proposition "$M$ halts" is false or provable. It comes from the fact that this formula is like $$\exists n\in\mathbb N \;\varphi(n) $$ with $\varphi$ primitive, and so you can always exhibit the $n$ such that $\varphi(n)$ is true, if it exists. So each time "$M$ halts" is not ...


1

The axiom you propose is inconsistent: take $\beta=\omega2$, and consider the set $R(\langle y_\eta\rangle_{\eta<\alpha})\iff \alpha<\omega$. Then certainly $R(\langle x_0\rangle)$ (regardless of what $x_0$ is), and $R(\langle y_0, y_1, . . . \rangle)$ implies $R(\langle y_0, y_1, . . . , z\rangle)$ (since appending an additional term to a finite ...


1

Let me give a different reference from the one Noah gave (although the mathematics is more or less the same). Jech, "The Axiom of Choice", Chapter 7. The last part of the chapter deals with all sort of various implications and separations of choice from finite sequences, including a nontrivial condition which guarantees some sort of control on when one type ...


1

Certainly, the Continuum Hypothesis (simple or generalised) can be formulated in the language of pure second-order logic. This is done explicitly in Stewart Shapiro's wonderful book on second-order logic, Foundations without Foundationalism: see pp. 105-106. The full story is a bit too long to give here. But as a taster, you start off by essentially using ...



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