Tag Info

Hot answers tagged

14

No. You may simply pick $x_i=42$ for all $i\in I$.


10

You need to go to the rational numbers, in order to ensure that every equation of the form $nx=m$ has a solution with $m,n$ natural numbers. Does that mean that there are no solutions, to any choice of $n,m$ in $\Bbb N$? No, it doesn't. $4x=8$ still has a solution in $\Bbb N$. Similarly with the axiom of choice. It is needed to ensure that every product of ...


10

No, ZF, without choice, suffices to prove that PA has nonstandard models. The reason is that PA is formalized in a countable first-order language. For such languages (indeed, for all first-order theories in well-orderable languages), the completeness theorem and therefore the compactness theorem are provable without choice. To prove the completeness ...


7

As Hagen points out in his answer, it is not always necessary. Sometimes, when the sets involved are specially nice, you can just write down an element in the product (as Hagen has done). However this is not always possible. The best way I've heard this put is the following (I think it is due to Hilbert, but I'm not sure), the idea of which is as follows. ...


7

You don't need the axiom of choice to show that $|\Bbb R|=2^{\aleph_0}$. If you observe carefully neither the injection from $\Bbb R$ into $\mathcal P(\omega)$ defined by enumerating the rationals and using Dedekind cuts, nor the injection from $\mathcal P(\omega)$ into $\Bbb R$ defined by creating the Cantor set use the axiom of choice. Since the proof of ...


5

No, it does not. Fix an enumeration of the rationals $\{r_k\}_{k = 0}^{\infty}$ and put an open interval $$\mathcal{O}_k = \left(r_k - \frac{1}{2^{k + 1}}, r_k + \frac{1}{2^{k + 1}}\right)$$ around this point. Define $$\mathcal{O} = \bigcup_k \mathcal{O}_k$$ in which case $\mathcal{O}$ is an open, dense subset of $\mathbb{R}$ with Lebesgue measure at most ...


3

You don't need the axiom of choice to prove this statement. You need the axiom of choice to prove that the product is non-empty, but here you allow for that possibility. Let $\{P_i\mid i\in I\}$ be an infinite family of sets with at least two elements each. If $\prod P_i$ is empty we're done, if not there is at least one $F$ in the product. Define a ...


3

1) Why does standard induction alone not suffice to show the axiom of choice for systems of countable sets? Doesn't induction show the truth of the statement for all natural numbers, and therefore for any system of sets that can be indexed by the natural numbers (countable sets)? I know this to be false, but I do not know why. As Jason DeVito points out ...


3

Picking an arbitrary $x_i$ is exactly where the axiom of choice gets into the picture. Otherwise, how can you justify the existence of such a function which picks this arbitrary $x_i$? Recall that the axiom of choice is needed when the product is infinite. When the product is finite, then indeed by induction we can choose an arbitrary $x_i$ and it's fine. ...


3

The trick is to embed the category of abstract simplicial complexes inside the category of symmetric simplicial sets (= functor $\mathbf{F}^\mathrm{op} \to \mathbf{Set}$, where $\mathbf{F}$ is the category of positive finite cardinals): this can be done by sending an abstract simplicial complex $X$ to the symmetric simplicial set ...


3

Yes, in the proof you link to, the well-ordering of $\mathbb R$ can be replaced by a choice function on the set of all infinite (or even continuum-sized) subsets of $\mathbb R$. It's essentially just a stylistic choice by the author which one to use. Certainly it doesn't have any deep significance, since the well-ordering theorem and the axiom of choice ...


3

The usual proof (which you mentioned) doesn't use the axiom of choice at all. You can prove this directly using induction. Pick some non-zero $w_1\in F$. Suppose that we chose $w_1,\ldots,w_n$ and $F_n$ is their span. If $F_n=F$ then $F$ is finite dimensional. Otherwise, $F_n$ is a proper subspace of $F$, then we choose some $w_{n+1}\in F\setminus F_n$. ...


3

No constructive example exists. Functions satisfying this inequality are called midpoint convex. Lebesgue measurable functions that are midpoint convex will be convex by a Sierpinski Theorem, therefore not just continuous but differentiable at all but countably many points. There is a model of set theory, called Solovay model, where all axioms are ...


2

If your sequence is given, then $\bigcup_{n\in\omega}X_n$ exists, yes. It is enough. If you have an inductive definition which goes from a given $X_n$ to $X_{n+1}$, then induction itself is not enough to give you the wanted sequence, and therefore its union. You need to show that you can get "through the induction" using very particular choices, which ...


2

It is not so much the area of certain 'figures' that depends on AC, it is the provability of existence/nonexistence of their area, once the manner of measuring areas is defined in some way, that may be affected by the presence/absence of AC. However, even when AC is present, there are certain 'figures' that may be given any area within certain bounds. Such ...


2

Short: First-order logic does not permit infinitely long statements. Infinitary logics do. To elaborate a little on Danul G's answer: If you can write a finite-length prescription for how to select each element from a collection, then you do not need choice. If, however, you would need an infinite-length prescription, then your prescription would be ...


2

Hint: Suppose $X$ is infinite and let $\mathcal{U}$ be the set of finite subsets of $X$. Now use the proposition.


1

What you would like to do is to say something like "Pick some element $x_0\in X$ then by induction pick $x_{n+1}\in X_n=X\setminus\{x_0,\ldots,x_n\}$" then $\mathcal U=\{X_n\mid n\in\Bbb N\}$ is a family of sets without a minimal element. But this is impossible, since moving from the induction to the infinite sequence requires some choice. But there is a ...


1

It seems that the answer was staring me in the face all along; since you can get a parity partition from either a nonprincipal ultrafilter or an $E_0$-selector, and the existence of just one of these objects does not imply the existence of the other (see this very interesting MO question), it follows that you can't get an ultrafilter or an $E_0$-selector ...


1

Figure whose area depends on the axiom of choice? Let $r=\begin{cases}1&\sf AC\\2&\sf \lnot AC\end{cases}$ then take $\{(x,y)\in\Bbb R^2\mid \max\{|x|,|y|\}\leq r\}$. Assuming the axiom of choice this is a square whose sides have length $2$, assuming the axiom of choice fails its sides have length $4$. This seems like a strange definition of a ...


1

Yes, the Feferman-Levy model is described in Jech The Axiom of Choice in Chapter 10 (Theorem 10.6), as well you can find nice detailed accounts in both Arnie Miller's papers about Dedekind-finite Borel sets and Long Borel Hierarchies (both of which you can find here), as well Ioanna Dimitriou M.Sc. and Ph.D. thesis (both of which appear here). The idea is ...


1

Linear independence does not depend on which vector space you're in since $F\subseteq E$. By definition a basis is a maximal, linearly-independent, spanning set. Let $x_1,\ldots, x_n$ be any $n$ vectors in $F$. Then because they are also vectors in $E$ the maximal size of a linearly independent subset is $\text{dim}(F)$, hence $E$ has finite dimension by ...


1

The well-ordering theorem just gives us a "reasonable" method of choosing the elements in the construction. If you have a choice function on the subsets of $\Bbb R$ then it suffices. However one can show the following theorem holds in $\sf ZF$. $X$ can be well-ordered if and only if there exists a choice function on $\mathcal ...


1

You can define a "simplex" as having an orientation, thus getting an easier answer. A $k$-simplex is the convex hull of a set of $k+1$ points. But what does it mean for a set to have $k+1$ points? That there is a bijection from $\{1,2,\dots,k+1\}$. So simply define "$k$-simplex" in terms of a map $\{1,2,\dots,k+1\}\to\mathbb R^n$ and you can pick an ...



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