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
2answers
133 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
105 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
128 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
249 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
58 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
66 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
144 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 ...
7
votes
3answers
219 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
146 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
72 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
213 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
149 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
125 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 ...
2
votes
1answer
271 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
54 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
114 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
80 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
85 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: ...
4
votes
2answers
418 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
108 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
104 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
109 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
539 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
67 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
413 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
153 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
29 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
107 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
65 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
107 views

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

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
178 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
88 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
208 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
74 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
98 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 ...
-2
votes
1answer
85 views

Axiom of Choice: An Invocation Necessary for A Proof on Surjectivity [closed]

Prove that if $f\colon X\rightarrow Y$ is surjective, then there must exist a function $g\colon Y\rightarrow X$ such that $f\circ g=1_Y$, where $1_Y$ is the identity map on $Y$.
1
vote
1answer
99 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
89 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
115 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
168 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
90 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. ...
2
votes
1answer
97 views

Cluster point of a sequence $\{x_n\}$ is the limit of some subsequence - Axiom of Choice? [duplicate]

In a metric space, a cluster point of a sequence $\{x_n\}$ is the limit of some subsequence. The only proof that I know works like this: Construct a sequence $\delta _k \to 0$. For each $\delta _k$ ...
9
votes
1answer
156 views

Proof of Zorn's Lemma using the Axiom of Choice. Why is $\mathscr U$ a tower?

I am reading a proof of Zorn's Lemma using the Axiom of Choice in Halmos' classical text, and I fail to see how to prove$\mathscr U$ satisfies the third condition of the definition of a tower. I will ...
4
votes
3answers
454 views

Why is the well ordering principle counter-intuitive?

I read here that while 'The Axiom of Choice agrees with the intuition of most mathematicians; the Well Ordering Principle is contrary to the intuition of most mathematicians'. I don't understand why ...
8
votes
3answers
340 views

Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable. Question: can we show the stronger result that if $X$ is ...
0
votes
1answer
114 views

Need help in Proofwiki of Axiom of choice implies Zorn's Lemma

I don't understand some point in proofwiki. (Here is link to the current revision of the ProofWiki article.) Firstly, it introduces $\mathbb{X}$ be the set of all chains in $(X,\preceq)$ while ...
1
vote
1answer
74 views

Can Zorn's lemma be applied to a class that is not a set?

I know that Zorn's lemma or its equivalent axiom of choice and so on can be applied to a set - but I am not sure if it can be applied to a class. I think I've seen an usage of axiom of choice to a ...
1
vote
1answer
96 views

Infinite Cartesian Product minus AC example

I've been looking for an example of an empty Cartesian product whose factors are non-empty. From what I've gathered so far, this statement is equivalent to the negation of AC, ie. AC fails. So ...
6
votes
0answers
202 views

A few standard results (on metrizability and relative separation strength) without choice?

I've been going back over some results from Munkres's Topology, and I'm curious about some things.... I know that Choice principles have some connection to the separation axioms (in ZF, at ...
4
votes
2answers
198 views

Cardinality of an ultrafilter

If $\mathscr F$ is an ultrafilter on an infinite set $M$, then it can be shown that $|\mathscr F|=2^{|M|}$. We know that for each subset $A\subseteq M$ we have $A\in\mathscr F$ or $M\setminus A \in ...