Tag Info

Hot answers tagged

52

Importance is a relative thing. For a computer scientist, or an applied mathematician, or a combinatorialist working with finite sets the axiom of choice might be the least important axiom in mathematics. As instances involving only finite sets will never require the axiom of choice. We can see the axiom of choice budding importance when you reach to ...


14

You're tacitly assuming that $\mathscr{E}$ contains more than a single element. But suppose that $\varphi$ and $\psi$ are theorems of $\mathsf{ZFC}$. Then in particular, in every single model $M$ of $\mathsf{ZFC}$, $\varphi$ and $\psi$ are true. As such, we find that $M\vDash (\varphi\leftrightarrow \psi)$ for every model $M$, so by Completeness we see ...


8

Being logically equivalent is far far stronger than $\sf ZFC\vdash\phi\leftrightarrow\psi$. Since the proof of equivalence can be non-trivial at all. For example, just to give an example, $\sf ZFC$ proves that the compactness theorem for FOL and Łoś's theorem are equivalent (like any two theorems of $\sf ZFC$); but $\sf ZF$ does not prove that at all. So ...


7

The answers already given are absolutely right, but another more basic issue shows up in your last paragraph: just knowing that $\varphi$ and $\psi$ are not "equivalent" (whether this means that they are not logically equivalent, or equivalent modulo some theory, does not matter), does not mean that $\varphi$ and $\neg\psi$ are equivalent. That is: if we ...


5

This is not that incredible if you understand what's going on. Given a second-countable space $X$, fix a countable basis $\{U_n\mid n\in\Bbb N\}$. Now you can observe that every open set is uniquely determined by the basis elements it contains, namely the function $U\mapsto\{n\in\Bbb N\mid U_n\subseteq U\}$ is an injective function. And since the real ...


5

Assuming the axiom of choice, first prove that $\Bbb R$ can be well-ordered. Since Cantor's theorem says that $\aleph_0<2^{\aleph_0}$ this means that $\aleph_1\leq 2^{\aleph_0}$, and so $\sf CH$ implies $2^{\aleph_0}=\aleph_1$. Without assuming the axiom of choice, Solovay's model as well the various Truss models (which don't use an inaccessible cardinal ...


4

When you give a recursive definition of a sequence, then you define a sequence uniquely. You're not making arbitrary choices, since $a_{n+1}$ is picked uniquely once you know the values of $a_0,\ldots,a_n$. So giving a recursive formula and a starting condition makes no appeals to the axiom of choice. This is different from the fake proof you presented, ...


3

The discrete topology on a countable set is second countable; it has a countable base consisting of the singleton sets. Thus, the assertion that all second countable spaces are Lindelöf implies that every cover of a countable set $N$ by subsets of $N$ has a countable subcover. I will show that the latter (ostensibly weaker) assertion implies ...


3

You do not need to appeal to the axiom of choice. Since there is only one choice from each singleton, you can essentially write down the function explicitly: $$\Big\{\big\langle A,x\big\rangle\mathrel{}\Bigm|\mathrel{} x\in A\in\mathscr C\Big\}.$$ Since each $A$ is a singleton, it appears in exactly one ordered pair, so it is indeed a function whose ...


3

We can prove, without the axiom of choice, the following theorem: If $\langle A_i\mid i\in\Bbb N\rangle$ is a sequence of sets, and $\langle f_i\mid i\in\Bbb N\rangle$ is a sequence of injections $f_i\colon A_i\to\Bbb N$, then $\bigcup_{i\in\Bbb N}A_i$ is countable. Namely, if the enumerations of each $A_i$ were given, then we can enumerate the union. ...


3

Such a choice mechanism would translate to a canonical choice for a function $\Bbb N \to \Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me). Given $f: \Bbb N \to \Bbb N_{>0}$, define: $$b_f (n) = \begin{cases}2^{-k} &: n = \sum\limits_{i=0}^k f(i) ...


2

Yes. You have used the axiom of countable choice to choose $x_n$ from each $B_{\frac1n}(x)\cap A$. To wit, in Cohen's first model there exists a dense subset $D$ of $\Bbb R$ which is Dedekind-finite. Namely $D$ has no countably infinite subset. It is not hard to see, if so, that any $x\in\Bbb R\setminus D$ is in the closure of $D$, but no sequence in $D$ ...


2

The proof given uses choice to select a $\delta_x$ for each $x\in[0,1]$. However, this can be avoided, for the combination of two reasons: For every $x$ it is possible to select a rational $\delta_x$ with the desired property. Even without the axiom of choice there exists a choice function for (nonemepty) subsets of $\mathbb Q$: Since $\mathbb Q$ is known ...


2

Simple. $2\cdot\operatorname{Card}(X)$ is the cardinality of $X\times\{0,1\}$. Now consider the following injection: $$\langle x,i\rangle\mapsto\begin{cases}\{x\} & i=0\\ X\setminus\{x\} & i=1\end{cases}$$ This gives us $\leq$; whereas in the other direction, if $\operatorname{Card}(2^X)=2\cdot\operatorname{Card}(X)$, we have that ...


2

There's really nothing much to it. We can easily use symmetric forcing the axiom of choice to fail only above rank $\omega+\omega$. Then if $\sf CH$ was true in the ground model, it will be true while $\sf AC$ is false; and if $\sf CH$ was false in the ground model, it will be false in the symmetric extension. Do note, however, that $\sf CH$ has several ...


2

You're right. The axiom of choice is needed, albeit in a limited form. It is consistent that there is a countable collection of pairs, $P_n$ such that there is no choice function from the $P_n$'s themselves. In particular, $\bigcup P_n$ is not a countable set, and in fact cannot even be linearly ordered. But since it is consistent with $\sf ZF$ that the ...


2

The comment of rschwieb made me think it's time put everything together. The statement A) The set of zero divisors of a commutative ring is the union of prime ideals. requires the existence of prime ideals in any commutative ring. According to this MO answer, prime existence is equivalent to the boolean prime ideal theorem (BPI for short). Since there ...


2

I would like to explain why the proof above do not need to use the axiom of choice. When you said ''so let's take the minimum m out of it'' you have done a defined choice. If someone else do you proof he will ''choose'' the same ''m'' as you because the way the choice is done is specified. This choice is done infinitely many times. However, assume that ...


2

As it turns out, the answer is negative. But the solution, as far as I understand requires [very] large cardinals. To see this, first note that the first statement necessarily means that $X$ can be well-ordered (since it can be mapped into a well-ordered set injectively). So it suffices to show that for well-ordered sets this happens, while the axiom of ...


1

Here is some context for thinking about this question. Suppose, more generally, that $$0 \to A \to B \to C \to 0$$ is a short exact sequence of modules over some ring $R$, and you want to know whether this short exact sequence splits in the sense that it is isomorphic to the short exact sequence $$0 \to A \to A \oplus C \to C \to 0$$ where the first map ...


1

Yes, and not only that, it is in fact equivalent to Zorn's lemma. Just to give an example of something that might happen, it could be that there is a vector space over, say $\Bbb Q$, that every proper subspace is finitely dimensional, but the space itself is not finitely generated. In particular no nontrivial subspace has a complement!


1

There's no issue with the axiom of choice here. We construct increasingly longer initial segments of our subsequences. This is like looking at some tree of finite sequences of natural numbers. The tree itself is already provably well-orderable. So the existence of a branch, the infinite sequence, is not using the axiom of choice.


1

The assumption is not that $Y$ is finite. But in order to verify that $\bigcup Y$, as the increasing union of linearly independent sets, is linearly independent, we only need to verify that finite combinations with non-zero coefficients do not produce $0$. So given finitely many vectors (or in this case, real numbers) in $\bigcup Y$, there is some ...


1

Looking at the original Halbeisen-Shelah paper, they point out this in Corollary 3. This is a corollary of the fact every ordinal has a Cantor normal form. We use that fact to produce an injection from $\operatorname{Seq}(\alpha)$ into $\alpha$, then use the Cantor-Bernstein theorem (which, given two injections gives a well-defined and relatively canonical ...


1

No. Suppose that $A$ is a Dedekind-finite set such that $\aleph_0\nleq^*|A|$. For example if $A$ is an amorphous set. Then $B=A\cup\{A\}$ is such that $|A|<|B|$ and $\aleph_0\nleq^*|B|$. (This example can be easily generalized. Given a $\kappa$-amorphous set $A$ such that $\aleph(A)=\kappa$, take $B=A\times\{0,1\}$. Then $|A|<|B|$, since $B$ can be ...


1

Yes, this is fine. In fact you don't even need the full strength of the axiom of choice: the axiom of dependent choice is all that you're really using.


1

Yes, it's fine. Note that the use of the axiom of choice is only in proving that a choice function $g$ exists, and we fix this choice function before starting the recursion. Afterwards it's just recursion. Also note that you don't choose from $f(n)$, but rather from $\{y\mid f(n)<y\}$, which is nonempty since $f(n)$ is not maximal.


1

For $\omega^\omega$ this is easy. You can note that this is just the order type of $\Bbb N[x]$, the polynomials with natural numbers coefficients, ordered lexicographically by length. In general, if $\langle A_n\mid n\in\Bbb N\rangle$ is a sequence of countable sets such that there is a uniformly definable bijection between $A_n$ to $\Bbb N$, then without ...


1

This is much weaker. Consider the natural numbers, with an added maximal point which we shall call $\infty$. This partial order satisfies Zorn's lemma, every chain has an upper bound, indeed $\infty$ itself is an upper bound (it's a maximum element!) of any chain. But the chain $\Bbb N$ is strictly increasing and does not stabilize. So this linear order ...


1

Yes, it is very much possible to have $S(2)$ without the axiom of choice. Suppose that $X$ is a set such that: $X$ is infinite Dedekind-finite, so every countable subset is finite. If $\mathcal S$ is a partition of $X$, so that every part is finite, then all but finitely many parts are singletons. Then I claim that every permutation of $X$ has ...



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