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
1answer
64 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
65 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
154 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
307 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
144 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
127 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
193 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
113 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
30 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
213 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
117 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
154 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
267 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
63 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
108 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 ...
2
votes
2answers
171 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
264 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
263 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
76 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
342 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
211 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
141 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
474 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
59 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
154 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
89 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
638 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?
2
votes
3answers
131 views

Definition of limit and axiom of choice

In the definition of limit of a function ($\epsilon-\delta$ definition) we say certain statements such as for every $\epsilon>0$ there exist $\delta>0$ .... Now my question is, is a choice ...
3
votes
1answer
113 views

Dependent choice does not imply “the reals are well-ordered”; citation?

As silly as this sounds, I can't find a proof that the axiom of dependent choice (DC) does not imply that the reals are well-orderable. My memory is that this is a fairly early result in the history ...
5
votes
1answer
137 views

Relationships between a few strong separation axioms without Choice

Disambiguation: Let $\langle X,\tau\rangle$ be a topological space. I will say that two subsets $A,B$ of $X$ are separated if they are disjoint from each other's closures (their closures needn't be ...
2
votes
3answers
1k views

Prove that Every Vector Space Has a Basis

My textbook extended the following proof to show that every vector space, including the infinite-dimensional case, has a basis. Condition: $S$ is a linearly independent subset of a vector space ...
4
votes
2answers
73 views

An uncountable well-ordered subordering of asymptotic growth rates?

Define the following relation $\le$ between arithmetic functions $f$ and $g$ (mappings from $\mathbb{N} \rightarrow \mathbb{N}$): $f \le g := \exists n_0, k: \forall n: n \gt n_0 \implies f(n) \lt k ...
2
votes
3answers
613 views

Axiom of Choice and Right Inverse

I read an Theorem that states: Let $A$ and $B$ be non-empty sets, and let $f:A \to B$ be a function, then the function $f$ has a right inverse if and only if $f$ is surjective. The Theorem ...
7
votes
2answers
167 views

Vector space bases without axiom of choice

I want to find an example of a vector space with no base if we assume that axiom of choice is incorrect. This question might be duplicate so please alert me. Thanks.
2
votes
1answer
31 views

How can one tell if a sequence is well-defined; is the axiom of choice needed?

This question is in the context of the following exercise: Let $X$ be a first countable topological space, let $A \subseteq X$, and let $x \in X$ with $x \in \overline{A}$. Then there exists a ...
1
vote
1answer
120 views

Why do sequences exist? What does “constructing a sequence” mean formally?

Everybody knows arguments like: "We can construct such a sequence inductively. Let $a_0$ be chosen as [..]. Then we can choose $a_{k+1}$ out of the set $A_{k+1}$ (which was shown to be non-empty)." ...
6
votes
1answer
84 views

Under what choice assumptions is there a monoid structure on every set?

The question arose when discussing possible cardinalities of hom-sets of whether it's any weaker than the axiom of choice that there exists a monoid of every cardinality. It's well known, or at least ...
6
votes
0answers
112 views

AC iff $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$ [duplicate]

I'm trying to do the following exercise: Exercise. Assume ZF. Then AC is equivalent to the statement that $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$. I'm struggling with the ...
3
votes
2answers
220 views

Axiom of Choice, Continuity and Intermediate Value Theorem

I am trying to understand a proof I read in Herrlich's book Axiom of Choice. For those who know the book, it is theorem 4.54 on page 74. The part I am interested in reads: (9) A function $f:X ...
6
votes
2answers
123 views

Axiom of dependent choice and $\aleph_1$

Assume we have to make a construction on countable sets, which requires choice. If we need to repeat the same construction up to cardinal $\aleph_1$ (for example to construct a chain of elementary ...
4
votes
3answers
213 views

We cannot write this function

I'm a new user so if my question is inappropriate, please comment (or edit maybe). If we accept axiom of choice, we can find a choice function for $\mathbb{R} / \mathbb{Q} $ , this is obvious. But we ...
2
votes
1answer
76 views

Back and forth and the axiom of choice

Is the axiom of choice a necessary condition for the application of "back and forth construction" in model theory?
2
votes
1answer
108 views

(Revisited$_2$) Injectivity Relies on The Existence of an Onto Function Mapping Back to Its Preimage

QUEST: For any sets $X$ and $Y$, there exists an injective function $f:X\rightarrow Y$ if and only if there exists a surjective function $g:Y\rightarrow X$. QUESTION$_1$: How do you people ...
1
vote
1answer
115 views

equivalence between axiom of choice and Zorn's lemma in a particular case.

Define $A(x)$ and $Z(x)$ as follows. $A(x)\Leftrightarrow $for every indexed family $(S_i)_{i\in I}$ of nonempty sets s.t. $\# I =x$, there exists an indexed family $(s_i)_{i\in I}$ s.t. $s_i \in ...
1
vote
2answers
103 views

Is there a deductive system for second-order logic that is complete with respect to Henkin semantics?

I have heard that second-order logic with Henkin semantics is a lot like first-order logic. Does this mean it has a complete deductive system? If so, what's an example of such a deductive system, and ...
1
vote
1answer
117 views

Extending our language with a new function symbol

Given an arbitray first-order theory (not necessarily a set theory) and definable predicates $P(*)$ and $Q(*,*)$ in the language of that theory, if we adjoin a new function symbol $f$ together with ...
-1
votes
2answers
229 views

The intersection of an infinite descending chain of non-empty sets [closed]

I am trying to prove something by contradiction and I am stuck as described below: From the (false) assumption, I have shown that for any $i \in \mathbf{N}$, $A_i \neq \emptyset$ and that $A_1 ...
0
votes
1answer
131 views

proof of equivalence of continuity and continuity in terms of limits of sequences

I am currently working on the axiom of choice and was looking for easy applications. A common example is the proof of the equivalence of continuity with continuity in terms of limits of sequences. ...