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
10 views

Extending 2-adic valuation to real numbers

When proving Monsky's theorem, one of the steps, which, from what I have so far seen, no proof can avoid, is extending the 2-adic valuation to all real numbers, so that it still satisfies ...
2
votes
3answers
39 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 ...
8
votes
2answers
315 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 ...
5
votes
1answer
89 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
49 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
128 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
47 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
22 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
50 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
51 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
67 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
42 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
57 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
65 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
89 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
44 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
120 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
638 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
29 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
56 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
81 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
42 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
35 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
50 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
56 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
33 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
104 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
47 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
45 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
39 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
47 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
45 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
86 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
72 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
24 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 ...
2
votes
2answers
37 views

Does a direct sum decomposition of an infinite-dimensional vector space require Zorn's lemma?

Let $V$ be an infinite-dimensional vector space and $V'\subset V$ a subspace. Does it require Zorn's lemma to write $V=V'\oplus V''$ for some other subspace $V''\subset V$?
2
votes
2answers
45 views

Axiom of choice : continuous function and uniformly continuous

How I proof that every continuous function f in [0,1] is uniformly continuous, without axiom o choice? I took this from the book Axiom of Choice from Horst Herrilich He had a observation that ...
4
votes
3answers
134 views

Does the proof of Bolzano-Weierstrass theorem require axiom of choice?

When selecting the terms of subsequence from each bisections, I thought axiom of choice might be required. But I'm not so sure whether or not, so please tell me. [edited] I'm sorry for the lack of ...
2
votes
1answer
66 views

Can we prove AC from the statement “There is no $\aleph$ cardinal strictly between $\operatorname{CARD}(X)$ and $\operatorname{CARD}(2^X)$”?

If $X$ is a set, let $\operatorname{CARD}(X)$ denote the Cardinal number of $X$. Let GCH(1) be the statement "If $K$ is an infinite initial ordinal number, then there exists no initial ordinal number ...
2
votes
1answer
41 views

Is it consistent without the axiom of choice that every permutation of some infinite set have fixed points?

A "permutation" of a non-empty set means an injective mapping of the set onto itself. Let $S(1)$ be the statement "There exists a permutation of every set containing at least two elements, which has ...
1
vote
1answer
45 views

A question about infinite sets and Cantor's Power Set theorem

Let $\operatorname{Card}(X)$ denote the cardinal number of the set $X$. The standard proof of Cantor's Power Set theorem stating that "$\operatorname{Card}(X) < \operatorname{Card}(2^X)$" is ...
4
votes
2answers
58 views

Choosing a Cauchy sequence for a real

It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, ...
1
vote
1answer
41 views

Axiom of choice for singletons

Let $\mathscr C \subseteq \mathscr P (\mathbb R )$ be a family of singletons, i.e.: each element of $\mathscr C$ contains exactly one real number. Let $f: \mathscr C \to \mathbb R $ be the function ...
1
vote
1answer
52 views

Zorn's Lemma's chain condition

Zorn's Lemma requires that every chain in a partially ordered set $X$ has an upper bound. In this article Gowers uses Zorn's Lemma to find a maximal linearly independent (over $\mathbb{Q}$) subset of ...