8
votes
1answer
92 views

Can all theorems of $\sf ZFC$ about the natural numbers be proven in $\sf ZF$?

I know a proof of Hindman's theorem that uses ultrafilters on the natural numbers, and ultimately, the axiom of choice. But the theorem itself is essentially a combinatorial property of the natural ...
1
vote
2answers
59 views

An equivalence of AC

I have to prove the following: In $ZF^-$ the axiom of choice implies: For every set X there exist $Y \subseteq \bigcup X$ such that: Y has at most one element in common with each of X Y is maximal ...
5
votes
1answer
68 views

Existence of a real uncountable $\aleph_{\alpha}$ without $\mathsf{AC}$

Set theory (Jech) $\text{p.}\;27:$ It is an open problem whether one can prove without the axiom of choice that there exists a regular uncountable $\aleph_{\alpha}\;($the informed guess is that ...
3
votes
1answer
57 views

Book/Books leading up to the the axiom of choice?

I am familiar with the axioms of ZF set theory and some basic uses of them to completely formally construct more complex objects such as natural numbers etc. However I have pretty much no background ...
6
votes
1answer
114 views

Unions and the axiom of choice.

Is the following equivalent to the axiom of choice? Let $A = \{a_i: i \in I\}$ be a collection of pairwise-disjoint non-empty sets indexed by $I$. Similarly, let $B = \{b_i : i \in I \}$. Further ...
2
votes
2answers
45 views

Proving there is a sequence convergent to a limit point of a set without axiom of countable choice?

Often, we use a construction like this: Given a subset $ A $ of a metric space and its limit point $ a $, we know that for every $ \epsilon > 0 $ there is another point $ x $ different from $ a $ ...
1
vote
2answers
96 views

surjective map and cardinality

I work in $\mathsf{ZF}$(without the axiom of choice). Let $A, B$ be sets such that $\left| A \right |$ and $\left|B \right |$ are both defined and let $f \colon A \to B$ a surjective function. Can I ...
2
votes
2answers
47 views

Is the well-ordering in the well-ordering axiom required to be definable?

It is well-known that Axiom of Choice is equivalent to the statement that every set can be well-ordered. Now, to show that $M\models AC$, is it sufficient to show that there exists some well-order of ...
4
votes
1answer
68 views

Does restricting the range of a collection of nonempty sets to one dominated by the index set require the Axiom of Choice?

The title was difficult to write, because it is hard to say the property I am looking for in words. Here it is in symbols: $$\forall i\in I\ A_i\ne\emptyset\implies\exists X\preceq I\ \forall i\in I\ ...
2
votes
2answers
53 views

The axiom of countable choice.

There seem to be many questions along the same line but none of them seem to be quite what I am asking, so here goes: If a set is countable, then we know that a bijection exists between it and the ...
5
votes
2answers
143 views

Is (countable) AC necessary for a useful theory of Lebesgue measure?

I am working through some notes on the Lebesgue measure, and I noticed that the proof that $\lambda^*$ (the outer measure) is countably sub-additive requires countable choice. (Short version of the ...
1
vote
0answers
35 views

How is it possible that the well-ordering theorem is strictly stronger than the axiom of choice in second-order logic? [duplicate]

If I am not wrong, the well-ordering theorem is strictly stronger than the axiom of choice in second-order logic. I am not sure to understand how this is possible. The reason is that second order ...
8
votes
6answers
347 views

Countable axiom of choice: why you can't prove it from just ZF

This is a follow-up question to the discussion about the finite axiom of choice here. Suppose we have a countable collection of non-empty sets $\{A_1, A_2, A_3,\cdots\}$ Reasoning as indicated in ...
2
votes
1answer
75 views

Axiom of Choice and Zorn's Lemma Equivalence: some intuition

$$ \text{Axiom of Choice $\Rightarrow$ Zorn's Lemma } $$ $$\text{Axiom of Choice $\Leftarrow$ Zorn's Lemma } $$ I feel mathmatically immature to go through these proofs now. My quesiton therefore is: ...
6
votes
2answers
172 views

How can I explain to my professor his argument invokes the AC?

This is not the standard definition, but my topology professor restricted contexts in metric spaces. Definition An open set $U$ in a metric space $X$ is a subset of $X$ such that the interior ...
5
votes
1answer
130 views

Intuition for “the existence of a basis for every vector space is equivalent to the Axiom of Choice”?

Is there a intuitive way to understand "the existence of a basis for every vector space is equivalent to the Axiom of Choice"?
4
votes
2answers
110 views

The regularity of successor cardinal

I was looking at two different proofs of the fact that successor cardinals are regular. It struck me as odd that both proofs used AC. Looking at the concepts involved in defining cofinality I feel as ...
5
votes
3answers
214 views

Uncountable Cardinals without AC

I am doing an exercise, proving that without AC or Replacement that there are uncountable cardinals. As a point of reference I looked at the proof in Kunen's "The Foundations of Mathematics" that ...
6
votes
2answers
159 views

Understanding Zorn's lemma.

A lot of authors assume Zorn's lemma. I am told it is not an obvious mathematical fact, but I am having problems understanding why that is. Zorn's lemma states that if every chain in a partially ...
0
votes
1answer
76 views

Axiom of choice and an example of a Well-ordered $\Bbb R$

From the axiom of choice we get that every set can be ordered in a way that will make it a well ordered set, including $\Bbb R$. However, since the ordinal of such a well-ordered set of $\Bbb R$ will ...
2
votes
1answer
60 views

A well ordering on $\mathbb{R}$ and bigger sets

Consider the set of sequences $S = \{f:\mathbb{N}\to\mathbb{N}\}$, define an order on $S$ by the following: Based on the well-ordering of $\mathbb{N}$ and induction, either $f_1 = f_2$ or there is a ...
0
votes
1answer
48 views

On Counted Languages

In my recent question on Godel Completeness I mentioned that there was a related question I wanted to ask, but would keep separate. I have been recently studying "non-well ordered sets" and Chapter 7 ...
3
votes
1answer
50 views

When do surjections split in ZF? Two surjections imply bijection?

We have that the Axiom of Choice is equivalent to the principle that every surjection has a right inverse. However, without the Axiom of Choice we can determine for some $X$ that $X\succeq Y\implies ...
5
votes
2answers
141 views

Which sets are well-orderable without Axiom of Choice?

I know that, assuming Axiom of Choice, every set is well-orderable. I know also that the assertion that $\mathbb{R}$ is NOT well-orderable is consistent with ZF. How can I find other sets such that, ...
2
votes
3answers
191 views

Axiom of Choice and Cartesian Products

According to Wikipedia one formulation of AC is The Cartesian product of any family of nonempty sets is nonempty. If I consider an cartesian product $\prod_{i} X_i$ of nonempty sets $X_i$, then ...
1
vote
1answer
49 views

Kuratowski-Zorn Lemma with pre-order (quasi-order, proset) instead poset?

What would happen if we would use pre-order (there is no weak-antisymmetry, only reflexivity and transitivity) in Kuratowski-Zorn Lemma instead of partial order? Suppose that we have set P which ...
1
vote
1answer
58 views

Multiple context available for the AC?

I am surprised at the language used in connection with the axiom of choice. From the answer to a question a made (which turned out to be duplicate) about involvement of AC in Wiles’ proof of Fermat’s ...
1
vote
2answers
97 views

Set Theory and Zorn Lemma

Prove that there is a set $B\subseteq P(\mathbb N)$ such that for all $n\in \mathbb N:\mathbb N- n\in B$, every finite intersection of elements in B is not empty and for all $C\subseteq\mathbb N$ such ...
5
votes
1answer
82 views

Does the existence of products in the category of sets imply the Axiom of Choice?

If for every family $(X_i)_{i\in I}$ of sets, there exists a categorical product in the category $\mathbf{Set}$ of sets, does this imply that the set-theoretic construction $\left\{(x_i)_{i\in ...
4
votes
2answers
104 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
80 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 ...
4
votes
2answers
97 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 ...
3
votes
2answers
127 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
107 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.
7
votes
1answer
112 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 ...
6
votes
1answer
142 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 ...
1
vote
1answer
67 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 ...
4
votes
1answer
47 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 ...
2
votes
5answers
136 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
170 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 ...
4
votes
4answers
106 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. ...
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
248 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 ...
7
votes
3answers
218 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 ...
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 ...
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 ...
4
votes
2answers
416 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?
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 ...