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

4
votes
0answers
44 views

Uncountable series without axiom of choice

Consider a sequence of positive real numbers $(\alpha_i)_{i\in I}$ for some (suppose maybe wellordered for now) set $I$. Using axiom of choice, it is easy to see that $\sum_i \alpha_i$ is infinite if ...
2
votes
0answers
28 views

Differentiability and Monotonic Functions

I just read proof from Royden of theorem: 'Every Monotonic functions are differentiable almost everywhere.' But proof use Vitali Covering Lemma. But Vitali Covering Lemma is based on fact if we assume ...
0
votes
2answers
45 views

Countable collection of countable sets and Axiom of choice

Do we need Axiom of choice(or weaker version axiom of countable choice) to say countable Cartesian product of countable sets is nonempty? I think yes. I read somewhere answer no giving argument: each ...
12
votes
1answer
222 views

Infinite prisoners with hats — is choice really needed?

The problem is this (recently asked about here): A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces ...
2
votes
1answer
47 views

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$ and show where it was used the axiom of choice. ...
7
votes
1answer
80 views

Functions that satisfy $f(x+y)=f(x)f(y)$ and $f(1)=e$

My real analysis professor mentioned in passing that there exist functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy all of the following conditions for all $a,b \in \mathbb{R}$: $$f(1)=e$$ ...
1
vote
0answers
20 views

Existence of minimal sub-systems

A topological dynamical system is a topological space $X$ together with a continuous function $f : \ X \to X$. In the following, I will assume that $X$ is compact and Hausdorff (in other words, I work ...
1
vote
1answer
47 views

Fixed Point Equivalences of Axiom of Choice

Axiom of Choice has many known equivalences. Also there are many known fixed point theorems (unproved statements) which provide useful information about existence of fixed points for particular ...
0
votes
1answer
61 views

How much conservative ZF+AC and ZF+DC are over ZF?

A logical theory $T_2$ is a (proof theoretic) conservative extension of a theory $T_1$ if the language of $T_2$ extends the language of $T_1$; every theorem of $T_1$ is a theorem of $T_2$; and any ...
-5
votes
2answers
178 views

What is the most important (outside of mathematics) results known to require the axiom of choice? [duplicate]

I'm skeptical of the utility of the axiom of choice. Of course I realize that it CAN be used, but I'm not convinced that there are many (any?) practical results that require it.
1
vote
1answer
59 views

On conglomerates' axiom of choice(Category theory)

There is a requirement of conglomerate(collection of classes) which demands the following property. Axiom of choice for conglomerates: For each surjection between congomerates $f:X\to Y$, there is an ...
0
votes
2answers
46 views

$x$ is an adherent point of $X$ iff $\exists (a_n)_{n=0}^\infty$ such that $a_n \in X$, which converges to $x$.

Lemma Let $X$ be a subset of $\Bbb R$, and let $x\in\Bbb R$. Then $x$ is an adherent point of $X$ if and only if there exists a sequence $(a_n)_{n=0}^\infty$ consisting entirely of elements in $X$, ...
14
votes
1answer
912 views

What is the “opposite” of the Axiom of Choice?

One might think that, trivially, the "opposite" of AC is $\neg$AC. However, thinking about it differently, I'm not sure this is intuitively the case. AC says that every set has a choice function. ...
1
vote
1answer
29 views

Using Zorn's lemma to show a set is measurable.

If $S_j\subset \mathbb{R}^n$ and for all $j\in \mathbb{N}$ the set $S_j$ is measurable, show that $\bigcup S_j$ and $\bigcap S_j$ are measurable. I think I can use Zorn's lemma to show that this is ...
7
votes
1answer
96 views

Consistency strength of the “club ultrafilter”

What are the consistency strengths of $$ZF+``\text{The club filter on $\omega_1$ is an ultrafilter}"$$ and $$ZF + DC + ``\text{The club filter on $\omega_1$ is an ultrafilter}"?$$ I know that the ...
2
votes
1answer
52 views

Axiom of Choice Equivalent

I'm trying to prove the following statement is equivalent to the Axiom of Choice: "For any set $A$, there exists a function $F$ with dom $F = ⋃A$ and for each $x ∈ ⋃A$, $x ∈ F(x) ∈ A$." (1) The ...
2
votes
2answers
67 views

Does the statement ''PID of dimension $0$ $\Longrightarrow$ field'' actually use Zorn's Lemma?

Everywhere I look seems to blow by the statement that PIDs which are not fields have Krull dimension $1$. This relies on the fact: A PID with Krull dimension $0$ is a field. (*) It seems that the ...
0
votes
0answers
37 views

Does this version of Schröder-Bernstein-Cantor imply choice? [duplicate]

Consider the following statement: $(*)$ For all sets $A$,$B$ and surjections $f\colon A \rightarrow B$, $g\colon B \rightarrow A$ there is a bijection $h\colon A \rightarrow B$ Given choice, this ...
1
vote
1answer
28 views

Generic in Boolean-Valued-Models

Let $M$ be a transitive $\in$-interpretation of a extension $T$ of $ZF$ in $ZF$,and let $B$ such that $$T\vdash B\in M\wedge B\text{ is a complete Boolean algebra}$$ Then, using the fact that any set ...
2
votes
1answer
43 views

Bases of complex vector spaces and the axiom of choice

In Zermelo-Fraenkel set theory $ZF$ consider the following statement defined for every field $K$: $B_K$ : Every vector space over $K$ has a basis. It is well-known that $AC \Rightarrow \forall K ...
0
votes
1answer
21 views

Proof Explanation: Existence of “fg-chains” Axiom of Choice implies Zorn's Lemma

I would be very glad if someone could explain the validity of a passage of this paper to me. In the proof of Lemma 3.3, "Fundamental Lemma", the notion of "fg-chains" is introduced and later on, we ...
1
vote
1answer
47 views

What kind of Choice am I making in this argument?

I have an argument that's supposed to imply Choice, but I'm afraid it may be using some choice. If it does, how much choice? This is the part of the argument that might use some Choice. I marked the ...
0
votes
1answer
67 views

Infinite Cardinal Addition Without the Axiom of Choice

In the book 'Introduction to Set Theory' by Hrbacek and Jech, cardinal addition is defined as $$\sum_{i \in I}{\kappa_i}=\left|\bigcup_{i \in I}{A_i} \right|$$ where $|A_i|=k_i$ for all $i \in I$ ...
0
votes
2answers
61 views

Cardinality of the union of two infinite set

Suppose that $A$ and $B$ are two infinite sets and $|A|<|B|$. The question is that how to prove that $|A∪B|=|B|$. The proof is related to the Axiom of Choice.
3
votes
1answer
42 views

Existence of non-trivial linear functional on any vector space

For every vector space $V$ does there exist a linear functional $f$ ( a linear map from $V$ to $F$ the underlying field ) such that for some $ \vec v \in V$ , $f(\vec v) \ne 0$ ? If it does exist , ...
2
votes
3answers
99 views

$\mathbf{Q}$ basis of $\mathbf{R}$.

Could someone give me an explicit basis of $\mathbf{R}$ as a vector space over $\mathbf{Q}$? I no some linearly independent subset, namely $1,e,e^2,\ldots$ but this seems to be a deep result already ...
1
vote
1answer
53 views

Does the existence of a recursive sequence that involves an arbitrary choice at every step require the axiom of choice?

Say I want to define a sequence $(x_n)$ recursively, and at each step I make an arbitrary selection for $x_{n+1}$ out of some nonempty pool of acceptable candidates dependent on $x_n$. Does the ...
2
votes
1answer
66 views

How big can the continuum be without choice?

I've heard an argument before (although I can't remember where) that the continuum hypothesis is false, since the powerset operation is a something much more 'powerful' than the mere cardinal ...
34
votes
1answer
396 views

Over ZF, does “every Hilbert space have a basis” imply AC?

I know there is a similar result due to Blass [1] that over ZF, "every vector space has a (Hamel) basis" implies AC. Looking around, however, I can't find any results on the question for Hilbert ...
0
votes
0answers
43 views

Existence of a basis in constructive vector spaces

As I was trying to review forgotten knowledge on Vector Spaces in wikipedia, I read that the existence of a basis follows from Zorn lemma, hence equivalently from the axiom of choice. Actually, the ...
0
votes
1answer
44 views

Dedekind finite set and a special well ordered set

In ZFC, Dedekind finite set and finite set are same things. So I have a set say A(which is equal to N in ZFC) all Dedekind finite set are equivalent to proper subsets of A and A is well ordered set. ...
0
votes
1answer
49 views

Basis in topology and AC

Let S ⊂ ℘(X). Let T be the coarsest topology on X which contains S. Then we call T the topology generated by S. Let S ⊂ ℘(X). Then we can easily prove using (generalised distributive law) the ...
0
votes
1answer
25 views

Countable union of countable sets is countable and AC(or axiom of countable choice)

It is written in tag page of Axiom of choice in MSE that Countable union of countable sets is countable is a theorem which follows from AC. Do we really need AC to prove this. Please see following ...
5
votes
1answer
78 views

What is needed to make Euclidean spaces isomorphic as groups?

Consider the abelian groups $G_n=(\mathbb R^n,+)$ for $n\geq1$. Claim: For any $n$ and $m$ the groups $G_n$ and $G_m$ are isomorphic. This claim is true if one assumes the axiom of choice, and I ...
0
votes
1answer
52 views

Existence of non measurable set and ZF theory?

Does statement: 'Existence of non measurable set' consistent with ZF theory. or if I throw Axiom of choice from ZFC theory. Can I prove or disprove existence of a countably additive measure function ...
3
votes
1answer
53 views

Does there exist a connected 2-regular uncountable graph, or an uncountable path?

Does there exist a connected 2-regular uncountable graph? Can I use the axiom of choice to construct an uncountable path of elements from the reals? The question arose when reading this: Also, ...
2
votes
2answers
106 views

How does one prove $ZF\vDash MC\Rightarrow AC$?

This is somewhat adressed to Andreas Blass, whose papers I have read, in particular I make reference to an old paper of his »Existence of Basis implies the Axiom of Choice« (84). Anyone who happens to ...
1
vote
0answers
66 views

First Order Model Existence without Weak Konigs Lemma or Choice

In studying Godel's Completeness Theorem and its various related formulations like the Model Existence Theorem and the Lowenheim-Skolem Theorem there is one rather subtle point that I have not yet ...
2
votes
1answer
82 views

Infinite Set has greater or equal cardinality that of N

For any infinite set, we can find a 1-1 function (not necessary onto) from N (set of natural no.) to that set. The proof of this theorem I know using axiom of choice. Can we prove it without using ...
0
votes
1answer
44 views

Choice function to obtain all elements of an infinite set

I'm following a proof of "Axiom of Choice implies Well Ordering Theorem" (from a not-well-known book we use for class), and the author uses this procedure: First, he takes any non-empty set $X$ and ...
2
votes
1answer
67 views

Does this argument rely on countable choice?

Consider the following Theorem: Any algebraic field extension $K|F$ of infinite degree contains finite subextensions of arbitrarily high degree. Proof: We'll prove that, for any n, there's a ...
1
vote
1answer
74 views

Proof of one instance of the Axiom of Choice from another

I'm trying to show (i) $\implies$ (ii): (i) For any relation $R$, there exists a function $H\subseteq R$, with $\newcommand{\dom}{\mathrm{dom} \ } \dom H = \dom R$. (ii) For any set $I$ and any ...
1
vote
1answer
67 views

Proving equivalence of Axiom of Choice

I am working on the following question concerning the axiom of choice and one of its many equivalences. Advice as to whether I am on the right track would be appreciated. As a preface, I have looked ...
1
vote
0answers
38 views

divisible subgroup without axiom of choice

the theorem asserting that the divisible subgroup of an Abelian group is a direct summand depends on Zorn's lemma. in ZF without AC is there a construction which yields a model of an Abelian group ...
3
votes
1answer
47 views

Absolute coequalizers in $\mathbf {Set} $

Let $ A $ be a set and let $ R\subseteq A\times A $ be an equivalence relation on $ A $. Denote by $ p, q $ the projections $ R\longrightarrow A $ on the first and second factor, respectively. The ...
1
vote
1answer
117 views

Miller's Construction, Partition Principle and Failure of Axiom of Choice

Partition Principle ($PP$) is the following statement: For all sets $a$, $b$ there is an injection $f:a\rightarrow b$ iff there is a surjection $g:b\rightarrow a$ It is known that $ZF\vdash ...
2
votes
0answers
37 views

Is this an equivalent form of Axiom of Choice? [duplicate]

It is known that Axiom of Choice implies the following statement: For each two sets $A$ and $B$, there is a one to one function from $A$ to $B$ iff there is a function from $B$ onto $A$ Is above ...
3
votes
1answer
109 views

Why is the powerset axiom more acceptable than the axiom of choice?

The key step in Zermelo's proof of the well ordering theorem is to use $\text{AC}$ to simultaneously choose the next elelment for all possible partial chains in prospective well orderings, but that ...
2
votes
1answer
42 views

Existence of a Set Function Axiom of Choice

I have the following problem. Let $A$ be a set and $B\neq\emptyset$ be a proper subset. Prove the existence of a function $f:A\to A$ such that $f\circ f=f$ and $\text{im}~f=B$. In the case where $A$ ...
0
votes
2answers
75 views

Does the Cartesian product of an infinite family have all the elements we expect?

Given the axiom of choice, we know that the Cartesian product of an infinite family of non-empty sets is non-empty. However, this doesn't tell us whether the Cartesian product contains every element ...