Questions tagged [axiom-of-choice]

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. Use this tag in tandem with (set-theory).

Filter by
Sorted by
Tagged with
2
votes
1answer
36 views

Can a partially ordered set $D$ have a function that maps every chain to a strict upper bound?

My Claim: Let (D,$\le$) be a poset and f a function from the set of linearly ordered subsets of D to D. Assume that for every linearly ordered subset U of D we have $\forall$x $\in$ U, x $\lt$ f(U). ...
2
votes
2answers
71 views

Help with the proof of Zorn's Lemma: if $A$ and $B$ are conforming subsets, why must it be that $A\subseteq B$ or $B\subseteq A$?

Here we can find a simple proof of Zorn's Lemma, but I find something that I can't really understand. There is an statement that say: If A and B are conforming subsets of $X$ and $A\neq B$, then one ...
1
vote
1answer
26 views

An example of a class of structures whose axiomatizability depends on the axiom of choice

Is there an example of a specific class $K$ of structures (in the sense of first-order logic), such that $K$ is first-order axiomatizable if the axiom of choice is assumed, but that its ...
0
votes
2answers
37 views

Axiom of Choice and Completeness of the Reals

I have a question regarding the Completeness axiom of R. Does It have a relation with the axiom of choice? I mean, does the axiom of choice implies the Completeness axiom? Or are they independent?
2
votes
1answer
40 views

Strengthening of the axiom of Dependent Choice

I have in mind the following statement: For every non empty set $X$ and for every entire binary relation $R$ over $X$, there exists a function $f:X\rightarrow X$ such that, for all $x \in X, \ \ x \ ...
4
votes
0answers
51 views

Weird cofinality behavior without choice?

I vaguely recall the following result, but can't find it or prove it on my own; I'd like to check if it, or something similar to it, is actually true. My memory is that the proof is rather hard, FWIW. ...
1
vote
1answer
53 views

Does this simple proof use the axiom of choice?

The axiom of choice lets us choose and single elements from an arbitrary amount of sets. I'm wondering if we can choose a single element from a single set and build another set from it without using ...
3
votes
0answers
129 views

Axiom of choice equivalence

A family of sets F is called interesting if $$\exists n \in \omega \forall X (X \in F \iff \forall Y (Y \subseteq X \land |Y| \leq n \implies Y \in F)$$ I have the following lemma: If F is an ...
1
vote
2answers
60 views

Given an arbitrary infinite set $S$, how to construct an injection $\mathbb{N} \to S$ with the Axiom of Choice?

Let $S$ be an arbitrary infinite set. As a part of our homework, I have the following question: Question: How can I construct an injection $\mathbb{N} \to S$? Intuitively, I understand that such an ...
0
votes
0answers
38 views

uses and proofs of the cardinality of the continuum

after reading this https://en.wikipedia.org/wiki/Cardinality_of_the_continuum I wonder what good is it as a tool in mathematics if there is no proof. is it merely useful to prove that it is ...
1
vote
1answer
51 views

In $\mathsf{ZF}$, for each set $A$ exists an ordinal $\alpha$ such that no surjection $A\to \alpha$ exists

Some observations. The statement can easily be proven in $\mathsf{ZFC}$, but we do not assume that $\mathsf{AC}$ holds. If one proves that $S=\{\beta \mid \text{there is a surjection $A\to \beta$}...
2
votes
1answer
44 views

Disjointness in proof of Tarski's Theorem that $|X\times X|=|X|$ for all infinite sets implies Choice

In the Wikipedia proof of Tarski's Theorem about Choice, one assumes that the infinite set $B$ and the ordinal $\beta$ are disjoint. While it is clear that this assumption can be made, is it actually ...
6
votes
1answer
81 views

How many nonprincipal ultrafilters exists on $X$ such that $|X|^2=|X|$?

Let $X$ be an infinite set, idemmultiple ($|X|^2 = |X|$) if that helps. I am looking for a proof that $X$ has more than $|X|$-many ultrafilters. It has $|X|$-many principal ultrafilters. Without at ...
0
votes
0answers
37 views

A fact about algebraic systems and axiom of choice

Algebraic system $\mathfrak A$ contains a proper subsystem $\mathfrak B$ isomorphic to $\mathfrak A$. Prove that $\mathfrak A$ is contained in a proper supersystem $\mathfrak C$ isomorphic to $\...
2
votes
0answers
41 views

Injection from $\mathbb{R}$ to $\mathbb{R}/\mathbb{Q}$ [duplicate]

Define an equivalence relation $\sim$ on $\mathbb{R}$ by $x\sim y\leftrightarrow x-y\in\mathbb Q$. Write $\mathbb R/\mathbb Q$ for the set of equivalence classes under $\sim$. If we assume the axiom ...
8
votes
1answer
172 views

Dual of axiom of choice

The (internal version of) axiom of choice, stated in the language of category theory says that every epimorphism splits - i.e., every epimorphism has a section. Now, just like any other category ...
2
votes
1answer
54 views

If $A$ is an infinite set and $b \notin A$, is the equivalence $A \sim A \bigcup \{b\}$ provable without the axiom of choice (i.e. in ZF)?

A set $A$ is said to be infinite if there is a surjection from $A$ to $\mathbb N_0$. Let $A$ be infinite, and denote by $b$ some set that is not included in $A$. (Such a $b$ exists by the ...
19
votes
1answer
338 views

Does ZF prove that there are more cardinals than elements of any set?

In ZFC, it is easy to prove there are more cardinals than elements of any set. Specifically, given a set $X$, pick a well-ordering of $X$, and then you can inject $X$ into the cardinals by mapping ...
2
votes
1answer
27 views

Coding $\omega$-sequences of 0,1 with $\mathbb{Z}$-sequences of 0,1

This is a question from the talk here on page 115. Define an equivalence relation $\sim$ on ${}^\mathbb{Z}2$ by $f\sim g$ iff $f$ is a constant shift of $g$ (i.e. we are forgetting the origin). What ...
7
votes
1answer
114 views

Strength of “Cofinite Choice”

Let $A$ be a set of sets such that $(\bigcup A) \setminus x$ is finite for every $x \in A$. How strong is the variant of AC asserting that such an $A$ has a choice function? I'd assume it to be weaker ...
2
votes
1answer
48 views

Does “All additive functions are linear” imply every set of reals has the Baire property?

This is a follow-up to my previous question. In that question, I asked whether "All additive functions are linear" imply every set of reals is measurable. The answer is no. So, a natural ...
3
votes
1answer
55 views

Product forcing of symmetric systems

Given a family of forcing notions $(P_i)_{i\in I}$ we can take the product $P:=\prod_{i\in I}P_i$ as a forcing notion to create a generic filter of the form $G=(G_i)_{i\in I}$ such that for each $i\in ...
3
votes
1answer
63 views

Characterizing Vector Spaces without (provable) Basis in ZF

Without the axiom of choice certain vector spaces cannot be proven to have a (hamel) basis in ZF alone and I am wondering whether there exists some criteria characterizing such spaces. Here is what I ...
1
vote
1answer
52 views

Consequences of Axiom of Choice

In a proof of Zorn's lemma by Jonathan Lewin published in AMM in 1991, a following reasoning appears: Suppose every chain of a set $\mathcal{P}$ has a strict upper bound in $\mathcal{P}$(an element ...
1
vote
1answer
26 views

Is AC required to demonstrate that every collection of disjoint open intervals in R is countable? [duplicate]

I understand that to prove this, one considers that each open interval contains a rational number and since the open intervals are disjoint, there exists an injection from the collection of intervals ...
1
vote
1answer
58 views

(Non)necessity of the axiom of choice in proving associativity of the tensor product

I am trying to prove the associativity of the tensor product $\otimes$ of vector spaces, along the line with the sketch discussed on a previously-asked question, but I got stuck on the last point. ...
10
votes
2answers
144 views

In ZF, does the ring of continuous functions $C([0,1], \mathbb{R})$ have prime ideals which is not maximal?

In ZFC, it is known that the ring of continuous functions $C([0,1], \mathbb{R})$ have prime ideals which is not maximal. But all proofs of this which I saw uses the axiom of choice. Then, in ZF, does ...
22
votes
1answer
368 views

Does “All additive functions are linear” imply every set of reals is measurable?

Suppose we are working in ZF set theory without choice. An additive function is a function defined over the real line such that $f(x+y)=f(x)+f(y)$. It is known that if every set of reals is measurable,...
0
votes
0answers
57 views

The Axiom of Choice implies that every topological vector space has a balanced base and every locally convex space has a balanced convex local base.

What is shown below is a reference from the text Functional Analysis by Walter Rudin. If $X$ s a vector space over the field $\Bbb F$ then the following notation well be used $$ x+A=\{x+a:a\in A\}\\ ...
4
votes
1answer
137 views

Proof that non-well-orderable sets are not equinumerous to their own cardinals (using Scott's trick)

Azriel Levy's Basic Set Theory (the 2002 Dover edition) contains the following problem (Chapter 3, Exercise 2.24): Prove that $|x|$ is an ordinal iff $|x| \approx x$, (i.e., iff $|\,|x|\,| = |x|$). ...
3
votes
2answers
227 views

Can you “construct” a category from another category?

It's perfectly possible that I have no idea what I'm talking about here, as I know little about category theory, but my understanding is that a category is a space of some objects equipped with some &...
1
vote
0answers
56 views

Are these two definitions of finiteness equivalent? [duplicate]

Def1. Say $X$ is finite, if there isn't a $Y\subsetneq X$ such that $|X|=|Y|$. Def2. Say $X$ is finite, if for every $f:X\to X$, $f$ is an injection iff $f$ is a surjection. It can be easily verified ...
2
votes
0answers
23 views

Is this proposition regarding equipotence true, without the needing axiom of choice? [duplicate]

Proposition: let $A$ and $B$ be arbitrary sets. Then, there exists a set $C$ such that $A\cap C=\varnothing$ and $C\sim B$. This proposition seems really easy at first, but when I tried to prove it, ...
1
vote
1answer
45 views

Do I understand this proof for AoC $\implies$ well-ordering theorem correctly?

Am a real beginner in set-theory. I read that the Axiom of Choice (AoC) implies the Well-Ordering Theorem... From what I understand, the gist of the proof is that given any set $X$, we can use AoC to ...
0
votes
0answers
24 views

equivalent versions of axiom of choice [duplicate]

Let $\Omega\neq \emptyset$ and let $\{X_\lambda\}_{\lambda \in \Omega}$ be a collection of sets. Define the Cartesian product of the sets $X_\lambda$ to be $\prod_{\lambda \in \Omega}X_\lambda := \{f :...
2
votes
2answers
98 views

Does the law of excluded middle imply the axiom of choice?

I know that the Axiom of Choice implies Excluded Middle, but I haven't been able to find any discussion of the other direction. Does the law of excluded middle imply the axiom of choice? Here's a stab ...
6
votes
1answer
94 views

Is it true ZF can't prove there is a choice function on the Turing degrees?

It is possible to show there is no Borel choice function on the Turing degrees. In fact we can even prove there is no Turing invariant Borel injection from $2^\omega$ to $2^\omega$, which sort of says ...
1
vote
0answers
32 views

Is this partition axiom equivalent to axiom of choice over ZF? [duplicate]

Suppose we add the axiom to ZF that for any set $S$, and any partition $P$ of $S$, the cardinality of $P$ is less than or equal to the cardinality of $S$. It is known that the axiom of choice implies ...
0
votes
0answers
46 views

Equivalent statement of AC or not? [duplicate]

Here's a corollary of AC stating that: if there exists an onto mapping $f:A\to B$, then there exists a 1-1 mapping $g:B\to A$. What I'm confused about is that whether or not AC can be derived from ...
5
votes
2answers
68 views

How is axiom of choice utilized within the given proof?

I (only a beginner in set theory...) want to see a prove that an infinite set must have an infinite countable subset U: The following answer sounds quite logically for me: John Wayland Bales, Prove ...
7
votes
1answer
142 views

Constructively embedding $\mathbb{Q}^\mathbb{N}$ into $\mathbb{R}$

Using the axiom of choice it is provable that $\mathbb{R}$ is isomorphic to $\mathbb{Q}^\mathbb{N}$ as a vector space over $\mathbb{Q}$. (Assuming AC, both spaces have a Hamel basis over $\mathbb{Q}$ ...
0
votes
1answer
51 views

Basis of $\mathbb R$ seen as a $\mathbb Q$-vector space

$\mathbb R$ is clearly a $\mathbb Q$-vector space since all axioms needed to be a vector space are verified. Its basis is infinite because it would need to have all roots, $\pi$, $e$... Is there any ...
1
vote
1answer
50 views

Consequences of a class bijection $V\times V\to V$

A famous theorem of Tarski (proved in ZF) says that, if $\mathfrak{m}^2=\mathfrak{m}$ for every infinite cardinal $\mathfrak{m}$, then the Axiom of Choice holds. Consider the language $\{\in,F\}$, ...
1
vote
1answer
53 views

How much choice is needed to show that $|A\times \omega|=|A|$?

A recent question here (which I believe was deleted, unfortunately) came down to showing the title question, that $|A\times\omega|=|A|$ for all infinite sets $A$. In that situation, the questioner ...
6
votes
1answer
105 views

Basis for $\mathbb{R}^\mathbb{N}$ implies axiom of choice?

Let $\mathbb{R}^\mathbb{N}$ denote the vector space over $\mathbb{R}$ of sequences of real numbers, with multiplication and addition defined by component. It's well-known that though the subspace $\...
7
votes
0answers
87 views

“Self-counting” infinite Dedekind-finite sets

Finite sets have a nice "strong self-counting" property: if $X$ is finite, there is a linear order on $X$ such that every $n<\vert X\vert$ is the cardinality of some initial segment of ...
4
votes
1answer
63 views

Axiom of choice in proof of theorem 2.41 in Rudin's principles of real analysis?

I have looked through the many questions about this theorem on this website, but none that I could see adressed exactly what I am wondering about. For completeness, I will state the theorem below and ...
0
votes
1answer
33 views

Prove that if every family $\mathcal{C}$ of ideals in $R$ has a maximal element then every ideal is finitely generated.

This is what I want to prove: Every family $\mathcal{C}$ of ideals in $R$ has a maximal element in $\mathcal{C}$ implies that every ideal in $R$ is finitely generated. I found this answer here Every ...
0
votes
1answer
61 views

Proof that an infinite set can be written as the countably infinite union of pairwise disjoint infinite subsets without using the axiom of choice. [duplicate]

I have the following theorem Any infinite set can be written as the countably infinite union of pairwise disjoint infinite subsets I have found a couple of proofs for this but I was wondering if there ...
0
votes
1answer
32 views

If $R$ is noetherian then every family $\mathcal{C}$ of ideals in $R$ has a maximal element in $\mathcal{C}.$

Here is the question I want to answer: If $R$ is noetherian then every family $\mathcal{C}$ of ideals in $R$ has a maximal element in $\mathcal{C}$ relative to the partial order of set inclusion. Here ...

1
2 3 4 5
34