The axiom of choice is a common set-theoretic axiom with many equivalents and consequences. This tag is for questions on where we use it in certain proofs, and how things would work without the assumption of this axiom.

learn more… | top users | synonyms

0
votes
0answers
14 views

Indexed sum of cardinals [duplicate]

Let $\{ \kappa_i | i\in I \}$ be an indexed set of cardinals. We define the sum as: $\sum\limits_{i\in I}\kappa_i = \left\vert \bigcup\limits_{i\in I}X_i \right\vert$, where $\left\vert X_i ...
5
votes
1answer
52 views

Approximating nice functions with wild ones

Let $X$ and $Y$ be toplogical spaces, and call a function $f:X\to Y$ wild if the preimage $f^{-1}(\{y\})$ is dense in $X$ for every $y\in Y$ -- or, equivalently, if the image of every nonempty open ...
5
votes
2answers
105 views

Explicit construction of a nonmeasurable set, where only the proof of correctness uses choice?

By Solovay's theorem, assuming the existence of an inaccessible cardinal, the axiom of choice is necessary to prove the existence of nonmeasurable sets. In the past, I've thought that one consequence ...
4
votes
1answer
69 views

Does Lowenheim-Skolem theorem depend on axiom of choice?

The proofs of Lowenheim-Skolem I have seen all depended on the use of choice functions. Is there any proof not dependent on axiom of choice? Or is Lowenheim-Skolem a result of axiom of choice?
2
votes
1answer
46 views

Find a uniquely defined element in this $\aleph_1$-indexed Cartesian product

Denote by $A$ the set of all ordinals with cardinality exactly equal to ${\aleph}_0$, and for $\alpha\in A$ let $B_{\alpha}$ denote the set of all bijections between $\alpha$ and $\omega$ ; finally ...
12
votes
3answers
494 views

Does this proposition from complex analysis depend on AC?

I was reading III vol. of Princeton lectures on analysis. Proposition 1.4: "If $\Omega_{1}\supset\Omega_{2}\supset\ldots\supset\Omega_{n}\supset\ldots $ is a sequence of non-empty compact sets in ...
1
vote
2answers
116 views

Where is the axiom of choice used in Rudin's proof of “the countable union of countable sets is countable”?

Baby Rudin proves that the countable union of countable sets is countable. From reading other proofs online, the axiom of choice has to be invoked; however, I'm not seeing immediately where that is ...
24
votes
2answers
836 views

W. Mückenheim claims a severe inconsistency of transfinite set theory; true? [closed]

The abstract for a paper on arxiv.org (http://arxiv.org/pdf/math/0408089v3.pdf) reads (with my emphasis): "Transfinite set theory including the axiom of choice supplies the following basic theorems: ...
9
votes
1answer
58 views

If a set $S$ has a choice function, does $\bigcup S$ have one too?

I have an exercise in a book that asserts that if a set $S$ has a choice function on it, then so does the union of all its elements $\bigcup S$ (without assuming the axiom of choice). I, however, have ...
2
votes
2answers
43 views

If $n < \aleph^*(m)$, then $n < 2^m$.

Without $AC$ Let $\aleph^*(m)$ be the least aleph that $\not\leq^* m$. I need a help or hint that if $n < \aleph^*(m)$, then $n < 2^m$. $a \leq^* b$ means we can define a surjective map from ...
3
votes
3answers
65 views

Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice)

I am interested in proving the titular claim: Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice) My approach: Let $R$ be a well-founded relation. We ...
9
votes
2answers
352 views

Does the definition of the fundamental group implicitly assume the Axiom of Choice?

Okay, I'm a little foggy around the axiom of choice, so help me out here. The standard way the fundamental group of a connected space $X$ is defined is as follows. You consider the set of all loops ...
7
votes
1answer
105 views

Good resources for studying independence proofs

I've finished most of Enderton's set theory. And I intend to spend some time studying independence proofs. I'm more interested in independence of axiom of choice not CH. From I know so far, there ...
2
votes
1answer
50 views

A Banach space of (Hamel) dimension $\kappa$ exists if and only if $\kappa^{\aleph_0}=\kappa$

A Banach space of (Hamel) dimension $\kappa$ exists if and only if $\kappa^{\aleph_0}=\kappa$. How will we prove the converse implication. One sided implication for Hilbert Space is proved in ...
7
votes
1answer
159 views

What is the significance of having Prime Ideal Theorem in models for failure of Axiom of Choice?

Prime Ideal Theorem says: PIT: Every ideal on a Boolean algebra can be extended to a prime ideal. It follows from Axiom of Choice but is weaker than it. In many cases I saw that people check ...
2
votes
1answer
54 views

Basis for $\mathbb{R}^{\infty}$ [duplicate]

It follows from Zorn's Lemma that every vector space $V$ has a basis (this means, a subset $B$ of $V$ that generate any $v \in V$ by means a finite linear combination, and such that $B$ is LI) . But, ...
2
votes
1answer
23 views

The least $\aleph$ that has no surjective map from $m$ to it.

Without $AC$. Let $\aleph^*(m)$ be the least aleph that $\not\leq^* m$. How to show that $\aleph^*(m)$ exists and $\aleph^*(m)= \{\alpha\in ON\mid\ \alpha\leq^*m\}$. $ON$ is the class of all ...
0
votes
0answers
18 views

onto map implies existence of one one map and AC [duplicate]

Let us assume the fact: $f: A \to B$ onto function implies there exist $1-1$ function from $B$ to $A$. Would it imply AC? I know every surjective function has right inverse this fact is ...
1
vote
1answer
54 views

dual Dedekind-infinity may not imply Dedekind-infinite without AC

It is written in wikipedia: https://en.wikipedia.org/wiki/Dedekind-infinite_set It is not provable (in ZF without the AC) that dual Dedekind-infinity implies that A is Dedekind-infinite. (For ...
1
vote
2answers
54 views

Does the principle of schematic dependent choice follow from ZFCU?

Let ZFCU be ZFC modified in the usual way to allow for urelements but without an axiom stating that there is a set of all urelements. Let the principle of Schematic Dependent Choice (SDC) be: ...
3
votes
1answer
71 views

Are there weak versions of the axiom of choice equivalent to weak versions of Zorn's lemma and similar principles?

I recalled reading about other weaker forms of $AC$, for example countable choice, where we could make choices from a sequence $(S_{k})_{k \in \mathbb{N}}$ of non-empty sets. I also recalled mention ...
4
votes
1answer
55 views

Does there exist a model of $ZF¬C$ in which there is a function on $\mathbb R$ which is sequentially continuous at a point where it is not continuous? [duplicate]

Does there exist a model of $ZF¬C$ in which there is a function $f:\mathbb R \to \mathbb R$ such that $f$ is sequentially continuous at some $a \in \mathbb R$ but not $\epsilon-\delta$ continuous , ...
2
votes
1answer
51 views

“Sequential continuity is equivalent to $\epsilon$-$\delta $ continuity ” implies Axiom of countable choice for collection of subsets of $\mathbb R$?

"A function $f: \mathbb R \to \mathbb R$ is continuous at $x \in \mathbb R$ , if and only if it is sequentially continuous " , does this statement imply "the Axiom of Choice for countable collections ...
3
votes
1answer
63 views

Proof that every field $F$ has an algebraic closure $\bar F$

I am reading the book A First Course in Abstract Algebra written by Fraleigh and I do not really understand the proof of theorem 31.22, that every field $F$ has and algebraic closure $\bar F$. I ...
4
votes
1answer
72 views

First Uncountable Ordinal Cofinality: Needs AC?

Say $\omega_1$ is the first uncountable ordinal. The reason I care about $\omega_1$ is Any countable subset of $\omega_1$ is bounded (or if you prefer, there is no countable cofinal subset). This ...
6
votes
0answers
92 views

(Non-Hopfian) groups that only have quotients that are themselves or the trivial group.

A group is non-Hopfian provided it is isomorphic to a proper quotient. The classic, finitely presented, example of such a group is the Baumslag-Solitar group $$BS(2,3)= \langle x,t \mid t^{-1}x^2 t ...
2
votes
1answer
45 views

ZF and the Existence of Finitely additive measure on $\mathcal{P}(\mathbb{R})$

My understanding is that Solovay (1970)'s relative consistency shows that if ZFC+I has a model then ZF+DC has a model in which every subset of the reals is Lebesgue measurable (and hence ...
6
votes
2answers
125 views

The non-existence of non-principal ultrafilters in ZF

In Hrbacek and Jech (1999, p.205), they point out that "it is known that the theorem [the extension of any filter to an ultrafilter] cannot be proved in Zermelo-Fraenkel set theory alone." And in Jech ...
14
votes
2answers
652 views

Do we know that we can't define a well-ordering of the reals?

Folklore has it that it is impossible to define a well-ordering of the reals explicitly. There exist pointwise definable models of ZFC where every set is definable without parameters: it is the ...
1
vote
2answers
30 views

undecidable statement of the form “$F$ is a choice function on $M$”

Are there unary predicates $\varphi(x), \psi(x)$ such that The formula that states "There is a set $M$ with: $\forall x[x\in M \leftrightarrow \varphi(x)]$" is provable in $ZFC$. The formula that ...
2
votes
1answer
59 views

Lindenbaum-Theorem only concerning sentential logic provable in ZF?

Is the Lindenbaum-Theorem of sentential logic (= propositional logic) provable in ZF (i. e. without the axiom of choice)? Lindenbaum's theorem of sentential logic states that every set $\Sigma$ of ...
4
votes
1answer
82 views

If I assign a random number $r_x \in (0,1)$ to every $x \in (0,1)$ what are the odds that one of them will be a specific number?

I'll start by motivating by question with a simpler scenario to ensure I've at least understood that scenario properly. Scenario 1 : Imagine an infinite sequence of numbers where $i$ is the ...
6
votes
0answers
44 views

Undetermined game of length $\omega_1+\omega$, without choice

On the following page, Taranovsky is talking about his "Determinacy Maximum" axiom: http://web.mit.edu/dmytro/www/DeterminacyMaximum.htm He also justifies the choice of the name, by pointing out that ...
2
votes
1answer
38 views

Partition the set of positive real number into pairs without axiom of choice?

Backround. Yesterday I made a comment on Achuille hui's answer and then I discuss on the chat with Paul Plummer about the way to partition the set of positive real number into pairs ...
6
votes
1answer
62 views

Is there a constructive discontinuous exponential function? [duplicate]

It is well-known that the only continuous functions $f\colon\mathbb R\to\mathbb R^+$ satisfying $f(x+y)=f(x)f(y)$ for all $x,y\in\mathbb R$ are the familiar exponential functions. (Prove ...
1
vote
1answer
60 views

Box topology and axiom of choice

Below is the definition of box topology: Given an indexed family of topological spaces $X_\alpha $, the collection of all sets of the form $$\prod_{\alpha\in J} U_\alpha,$$ where $U_\alpha$ is open ...
0
votes
1answer
34 views

Could the Hamel basis of $\mathbb{R^Z}$ be the set $\mathbb{R^Z}-{\mathbf{\{0\}}}$?

This is the follow up question to this question (*) According to page 2 of this link 1 and this link 2, $\mathbb{R^Z}$ (which is referred as $\mathbb{R^\infty}$ in link 1) has elements of the ...
7
votes
1answer
106 views

For an infinite cardinal $\kappa$, $\aleph_0 \leq 2^{2^\kappa}$

I'm trying to do a past paper question which states: $$ \text{For all infinite cardinals $\kappa$, we have } \aleph_0 \leq 2^{2^\kappa}. $$ I'm supposed to be able to do this without the axiom of ...
1
vote
1answer
50 views

Zorn's lemma converse? (Context: Maximal proper subgroups)

So, in my qual prep class a pretty simple question popped up: "Prove that for any nontrivial finite group there exists a maximal proper subgroup." So of course, my natural inclination was to ...
2
votes
2answers
65 views

$|\alpha\times\alpha|=|\alpha|$ for infinite ordinal $\alpha$, definably

I am trying to prove Proposition 1.7 of http://math.bu.edu/people/aki/7.pdf: Proposition 1.7 (Halbeisen–Shelah). If $\aleph_0\le|X|$, then $|{\cal P}(X)|\not\le|{\rm Seq}(X)|$. In words, ...
5
votes
3answers
1k views

What's wrong with this proof of the inconsistency of the axiom of choice?

Let $\mathscr{T}$ be the (countable) collection of all theorems provable in ZFC. Define an equivalence relation on $\mathscr{T}$ by $\phi\sim\psi$ iff $(\phi \iff \psi)$. In other words, two theorems ...
2
votes
2answers
49 views

Choice function for collection of arbitrary finite sets. AC required?

I understand how we can show the existence of a choice function for any (finite or infinite) collection of (finite or infinite) subsets of, say, $\mathbb{N}$ or $\mathbb{Z}$ without using the axiom of ...
0
votes
1answer
40 views

Looking for explanation of Banach-Tarski Proof, preferably by visual methods “Video, Pictures, Diagrams…”

could someone please explain the four steps of Banach-Tarski? 1- Find a paradoxical decomposition of the free group in two generators. 2- Find a group of rotations in 3-d space isomorphic to the free ...
2
votes
1answer
23 views

Is AC necessary to show that in metric spaces $x\in\operatorname{closure}(A)$ implies $\exists\{a_n\}_{n=1}^\infty\subseteq A$ s.t. $\lim a_n=x$?

Let $(X,d)$ be a metric space. Let $x\in\operatorname{closure}(A)$, where $A\subseteq X$. Then for each $n\in\mathbb{N},\exists x_n\in B_{\frac{1}{n}}(x)\cap A$, where $B_\varepsilon(x)$ is the open ...
1
vote
1answer
48 views

If $|A|<|B|$ does $B$ surject onto $\aleph(A)$?

After reading Proving existence of a surjection $2^{\aleph_0} \to \aleph_1$ without AC I became curious if there is a generalization to arbitrary cardinals. That is, if $\frak m<n$, does it follow ...
1
vote
1answer
49 views

How to show countability of $\omega^\omega$ or $\epsilon_0$ in ZF?

I know that with choice, the countable union of countable sets is countable, making $\omega^\omega$ and $\epsilon_0$ both countable. Can we show this without choice? E.g. in the case that $\omega_1$ ...
4
votes
1answer
89 views

How to prove that $\sf CH$ implies $2^{\aleph_0}=\aleph_1$

Of course, most of you will, upon reading the title, exclaim "But isn't that the definition of the continuum hypothesis?" So I need to be a little more careful about the exact definitions. Let ...
3
votes
0answers
48 views

Does “$(\exists f:A\twoheadrightarrow B)\implies(\exists f:B\hookrightarrow A)$” implies the axiom of choice? [duplicate]

Let $P$ denotes the property that if there exists a surjection from set $A$ to set $B$, then there exists an injection from $B$ to $A$. It's apparent that $P$ can be proved in ZFC. My question is that ...
1
vote
1answer
73 views

Can we prove, without axiom of choice, that the set of all zero divisors (including $0$) of a commutative ring with unity contains a prime ideal?

Let $R$ be a commutative ring with unity , I know that assuming axiom of choice , if $A$ is the set of all zero divisors (including $0$ ) then it is a union of prime ideals so it contains a prime ...
1
vote
1answer
29 views

The existence of the sequence corresponding to some asymptotic sequence

The following proof of the axiom of choice by induction is obviously false: Let $(\Lambda)_{i=1, 2, \ldots}$ be an infinite sequence of nonempty sets. When $i=1$, self-evident. We will assume this ...