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

1
vote
2answers
166 views

The Axiom of choice

I'm a little lost with this proof: If every set is equipotent to an ordinal, then we have the axiom of choice And I want to know if someone can help or maybe give me a hint of how to proceed.
1
vote
1answer
66 views

If AC is false , is this statement about the halting problem true?

Assume AC is false. (AC = axiom of choice ) Let $n,m$ be positive integers. Let $f: \Bbb N \rightarrow \Bbb N$ and $f(m)=m$. Let $g(n,m)=1$ if the iterations $f(n),f(f(n)),...$ converges to $m$. ...
1
vote
0answers
46 views

Is there a connection between contravariant functors and the axiom of choice?

Given that both can be seen as talking about reversing arrows between two objects: Is there a connection between contravariant functors and the axiom of choice? I'm initially motivated geometrical ...
4
votes
2answers
160 views

Existence of surjection implies existence of injection? [duplicate]

Let $A$ and $B$ be sets. If there exists a surjection $f : A \to B$ then there exists an injection $g : B \to A$. Proof: given $b \in B$ select an element $a \in f^{-1}(b)$. Denote this element by ...
6
votes
1answer
95 views

If a filter has a unique ultrafilter extending it, then it is that ultrafilter (prove without $\sf{AC}$)

I am not certain if $\sf AC$ (or more conservatively, $\sf UF=$ there is an ultrafilter extending any given filter) is necessary to prove the following statement: For filters $F,G$ with $\bigcup ...
1
vote
1answer
74 views

$\aleph(X) < \aleph(\mathcal{P}(\mathcal{P}(\mathcal{P}(X))))$

Prove: $\aleph(X) < \aleph(\mathcal{P}(\mathcal{P}(\mathcal{P}(X))))$ With $W(X)=\{\langle A,R\rangle: A \in \mathcal{P} (X),R \in \mathcal{P}(X \times X)$ and $ R $ wellorders $ A \}$ And ...
4
votes
2answers
107 views

Zorn's Lemma and Injective Modules

In my study of injective modules over commutative rings, i noticed that Zorn's Lemma is often employed in the proofs. Here are three examples: 1) Baer's Criterion 2) the characterization of injective ...
0
votes
0answers
44 views

A theorem of Tarski [duplicate]

A theorem of Tarski says that if it is so that, for all infinite sets $X$, $\;\operatorname{card}(X^2)=\operatorname{card}(X),\,$ then the axiom of choice applies. I would like to see a proof of ...
1
vote
1answer
49 views

What does the Axiom of Choice have to do with right inversibility?

I have encountered an exercise that asks to prove that, these two statements are equivalent: every surjective function has a right inverse. Axiom of choice. Definition: Given a function $f$, we ...
3
votes
2answers
135 views

Canonical Vitali set

The axiom of choice implies that there is a subset $E$ of $\mathbb R$ that are Vitali sets : this means that $E$ is a transversal with respect to the additive subgroup $\mathbb Q$ of $\mathbb R$, ...
5
votes
1answer
174 views

Compact metric spaces is second countable and axiom of countable choice

Why we need axiom of countable choice to prove following theorem: every compact metric spaces is second countable? In which step it's "hidden"? Thank you for any help.
1
vote
1answer
100 views

Axiom of choice and vector space bases

Is this: for every vector space $V$, if $B$ and $C$ are bases of $V$, then there is a bijection: $B\to C$ iff the axiom of choice holds true? Or, perhaps, if axiom of choice is replaced by ...
3
votes
1answer
104 views

Is there anything wrong with this use of the axiom of choice?

I have a proof of the following theorem: Let A be a finite set and X be a perfectly normal topological space, and let $\{(A,\succsim_x): x\in X\}$ be a family of binary relations on $A$ satisfying ...
2
votes
1answer
48 views

well ordering principle implies Zorn's Lemma

In here: Proving that well ordering principle implies Zorn's Lemma. I asked how to finish a proof of this statement. After a few helpful remarks, I think I have managed to finish it. What do you ...
4
votes
1answer
107 views

Proving that well ordering principle implies Zorn's Lemma.

I am trying to prove that well ordering principle implies Zorn's Lemma. I think that I'm close but don't quite know to make the last step of my proof. Here is what I wrote so far: Given that on every ...
7
votes
1answer
119 views

Can Tarski's circle squaring problem be solved with measurable sets and/or without the Axiom of Choice?

Tarski asked whether a disk can be decomposed into finitely many pieces which can be rearranged into a square (necessarily of the same area by the failure of the Banach-Tarski paradox in two ...
4
votes
2answers
73 views

Does the dualizing process on vector spaces necessarily terminate?

It's well-known (assuming the axiom of choice) that the inclusion $\ell^1 \subset (\ell^1)^{**}$ is proper as a simple corollary of the Hahn-Banach theorem. But is this the end of the dualizing ...
9
votes
3answers
137 views

Can $\mathbb{R}$ be written as an ascending union of proper additive subgroups?

Can the group $\mathbb{R}$ be written as countable ascending union of proper subgroups? (i.e. does there exists a series of proper subgroups $H_1\leq H_2\leq \cdots $ such that $\cup ...
6
votes
1answer
174 views

Can we prove that every ordered space is normal without choice?

In ZFC, every linear ordered space respect to the order topology is completely normal. I saw the this proof and proof of this statement in the book "Counterexamples of topology" (Example 39). But as I ...
3
votes
1answer
65 views

The union of a countable set of countable sets is countable

Here is the proof provided in my lecture notes: Let $A = \{B_n | n < \omega =\mathbb{N}\}.$ Assume each $B_n$ is countable. For each $n < \omega,$ let $E_n$ be set of all bijections between ...
1
vote
1answer
72 views

Relative Consistency proof for the Axiom of Choice

I've been reading about relative consistency proofs in Kunen's latest Set Theory text and going over which Axioms hold in certain classes. To get my hands dirty, I've been working on an exercise that ...
1
vote
1answer
62 views

Extending a Filter in a Well-Ordered Boolean Algebra to an Ultrafilter WITHOUT the Axiom of Choice

Hypothesis: Let $B$ be a well-ordered boolean algebra and let $F \subseteq B$ be a filter on $B$. Goal: Show that $F$ can be extended to an ultrafilter without the axiom of choice (or any equivalent ...
4
votes
1answer
59 views

Inductive definition with choice for sequence

In topology there is a very common way to define a sequence. This usually go something like: "Define $\{z_{n}\}$ to be a sequence such that $z_{0}$ is <blah blah blah>, and $z_{n}$ is such that ...
0
votes
2answers
72 views

Do we need the axiom of choice in here?

Axiom of choice: Given $\mathbb{F}$ is a set of non-empty sets. Then, there is a function $f$ with $\text{Dom}(f)=\mathbb{F}$ such that, for every $A \in \mathbb{F}$, $f(A) \in A$. The ...
2
votes
5answers
150 views

Axiom of countable choice

I apologize in advance for my neophytic question. Let $(A_n)$ be a countable family of disjoint sets. Why is it not possible define a sequence $(x_n)$ with $x_n\in A_n$ using recursion? It seems clear ...
4
votes
2answers
284 views

Well-ordering theorem and second-order logic

I am confused by this sentence in the Wikipedia article for "Well-ordering theorem": ...the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with ...
2
votes
4answers
134 views

Boolean prime ideal theorem and the axiom of choice

The Boolean prime ideal theorem is strictly stronger than ZF, and strictly weaker than ZFC. I'm looking for nice examples (like the existence of non-measurable set) that request at least that theorem ...
4
votes
4answers
125 views

Proving that without the axiom of choice there is a set with an accumulation point that isn'tthe limit of a convergeant sequence

I've been reading the simple parts of Thomas Jech's book on the Axiom of Choice and came across the following proof on page 141. The proof assumes a mathematical model without the axiom of choice. ...
3
votes
2answers
190 views

Why is the measure of the reals not zero?

I have followed the argument that rationals, being countable and ordered, can be covered by a convergent sequence of decreasing intervals. I am trying to understand why the same argument can’t be ...
3
votes
2answers
108 views

Proving Zermelo's Theorem implies the Axiom of Choice

I thought it would be fun to try and prove this. It turned out to be pretty simply and maybe too simple so I was wondering if anybody could verify if this proof is correct. Suppose we have a family ...
0
votes
0answers
29 views

Is it possible to prove product of basis is a basis for the box topology without AC?

Let $\{(X_i,\tau_i)\}$ be a collection of topological spaces and $\mathscr{B}_i$ be a basis for $\tau_i$. Let $\mathbb{B}=\{\prod p_i : p\in \prod \mathscr{B}_i\}$. Then is $\mathbb{B}$ a basis for ...
0
votes
2answers
180 views

Why is the l.u.b. property equivalent to Cauchy-sequence convergence for $\mathbb{R}$?

Math people: I browsed some questions with similar titles and could not find a duplicate. I apologize if it is. If you read my question it will be obvious that I am not a logician, so please be ...
4
votes
1answer
116 views

Question regarding disjoint unions, sequential compactness, and Dedekind-finiteness

I have proved the following two results: $[\mathsf{ZF}]$ The disjoint union of a Dedekind-finite family of sequentially compact topological spaces is again sequentially compact. ...
6
votes
2answers
147 views

In ZF, how would the structure of the cardinal numbers change by adopting this definition of cardinality?

In ZFC, a good way of ordering sets by cardinality is by leveraging the notion of an injection. We define: $$X \lesssim Y \leftrightarrow \mbox{ there exists an injection } X \rightarrow Y.$$ ...
7
votes
0answers
262 views

Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5: Each of the following statements imply those beneath it. The countable union of ...
1
vote
2answers
62 views

How do i formally write down a countable choice function?

Let $A$ be an infinite set. Then, we can construct an injective function $f:\omega \rightarrow A$. But how do i construct this via orginal statement of $AC_\omega$? (i.e. $\forall countable X, ...
1
vote
1answer
80 views

Showing that if every open subspace is Lindelöf, then the space is hereditarily Lindelöf.

Background: A topological space $X$ is said to be Lindelöf if for every cover $\mathcal O$ of $X$ by open subsets of $X$, there is some $\mathcal C\subseteq\mathcal O$ such that $\mathcal C$ is a ...
1
vote
2answers
160 views

Algebraic closure exists: What's wrong with this proof?

Given a field $K$, let $U = K[X] \times \mathbb{N}$. Identify each $k\in K$ as $(X-k,1) \in U$, so $K \subseteq U$. Consider fields $(S,+,\cdot)$ where $K \subseteq S \subseteq U$, and the inclusion ...
8
votes
3answers
243 views

Is Zorn's lemma necessary to show discontinuous $f\colon {\mathbb R} \to {\mathbb R}$ satisfying $f(x+y) = f(x) + f(y)$?

A UC Berkeley prelim exam problem asked whether an additive function $f\colon {\mathbb R} \to {\mathbb R}$, i.e. satisfying $f(x + y) = f(x) + f(y)$ must be continuous. The counterexample involved ...
2
votes
0answers
230 views

Normal closure of field extension, axiom of choice

Update My previous proof was incorrect. This updated proof is inspired by the comment by 'MartianInvader'. Problem I can prove the statement 'Every algebraic extension $L:K$ has a normal closure ...
6
votes
1answer
74 views

Is the following equivalent to the axiom of choice?

For sets $A,B$, let $|A|\leq^*|B|$ say that there exists an onto map $f:B\rightarrow A$ or $A=\emptyset$. My question is, is $$\forall A,B(|A|\leq^*|B|\longrightarrow |A|\leq|B|)$$ equivalent to the ...
2
votes
1answer
280 views

Algebraic complements in vector space of functions without the axiom of choice

The axiom of choice is equivalent to the statement that every subspace $U$ of every vector space $V$ has an algebraic complement, i.e. another subspace $W$ that has a trivial intersection with the ...
0
votes
2answers
195 views

Can the axiom of choice be used to define the real numbers?

I realize this is possibly a copy of another question (The Axiom of Choice and definability) but I would appreciate an explanation with less set theoretical explanations if that is at all possible. I ...
1
vote
1answer
134 views

Using Zorn's Lemma-Topology

Question: A subset $W$ of the set $Z$ of integers is said to be closed under addition if given any elements $w$ and $w'$ of $W$, $w+w'\in W$. Prove that there is a maximal subset of $Z$ which is ...
3
votes
1answer
369 views

Can a vector subspace have a unique complement in absence of choice?

Let $V$ be a vector space (not necessarily finite dimensional and over some arbitrary field), and $W$ a proper non-zero subspace. If we assume existence of bases, it is easy to show that $W$ can be ...
0
votes
1answer
58 views

Tychonoff's theorem and axiom of choice in Hausdorff spaces

Does anyone know if axiom of choice is nessesary in proving Tychonoff's theorem in a Hausdorff space? Thanks!
2
votes
1answer
133 views

Logic: Teichmüller-Tukey Lemma and the Axiom of Choice

How can you proof that the Teichmüller-Tukey Lemma (which says that if $S$ is nonempty and of finite character, $S$ contains a maximal element with respect to the subset ordering), implies the Axiom ...
1
vote
1answer
85 views

Axiom of choice needed? finite sets

I have to show that the following 2 quotes are equivalent: a) The set A is finite b) Every injective function from A to A is also surjective The direction a) ==> b): I've worked with induction on the ...
1
vote
2answers
89 views

Logic: on the Axiom of Choice

Let $X,Y,Z$ be infinite sets and $f:X \rightarrow Y$ be a surjective function. How can I prove that if $|Y| \le |Z|$ and for every $y \in Y$ is $|f^{-1}(y)| \le |Z|$, the following inequality holds: ...
3
votes
2answers
593 views

The Continuum Hypothesis & The Axiom of Choice

Does anyone here know of a reference to an analysis on a proposed relationship between The Continuum Hypothesis and The Axiom of Choice?