1
vote
1answer
44 views

Miller's Construction, Partition Principle and Failure of Axiom of Choice

Partition Principle ($PP$) is the following statement: For all sets $a$, $b$ there is an injection $f:a\rightarrow b$ iff there is a surjection $g:b\rightarrow a$ It is known that $ZF\vdash ...
5
votes
1answer
70 views

Partial order on cardinalities without the axiom of choice

Cardinality can still be defined without choice, e.g. as equivalence class of equipotent sets, see Defining cardinality in the absence of choice. Injections define partial order on cardinalities by ...
6
votes
0answers
175 views

Is Kunen's claim about non-equivalent forms of Axiom of Choice, true?

Consider the following forms of the axiom of choice: $AC_1:\forall F\neq \emptyset~~~(\emptyset\notin F~\wedge~\forall x,y\in F~~~(x\neq y\rightarrow x\cap y= \emptyset))\rightarrow \exists C~\forall ...
1
vote
1answer
81 views

Hall's marriage Theorem and Tychonoff Theorem

I was reading this paper. In particular the second point. He proves the Hall's marriage Theorem for infinite family using the Tychonoff theorem on topological product of compact $T_2$ spaces and the ...
1
vote
0answers
37 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
407 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 ...
1
vote
1answer
40 views

What is necessary for having a free ultrafilter?

Without any choice axioms, are there free ultrafilters on the natural numbers? If not, can we prove the existence of ANY free ultrafilters, on any set?
0
votes
1answer
49 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 ...
6
votes
2answers
268 views

Constructiveness of Proof of Godel's Completeness Theorem

As a mathematician interested in novel applications I am trying to gain a deeper understanding of (the non-constructiveness of) Godel's Completeness Theorem and have recently studying two texts: ...
2
votes
1answer
58 views

Bourbaki and AC: How does he proves ZL?

In the book Set theory, Chapter 3 N.Bourbaki, I would like to understand how Bourbaki proves ZL. I wrote the proof. It uses Zermelo's principle (which is okay since they are equivalent), so I tried to ...
7
votes
2answers
173 views

Plausibility argument for Zorn's Lemma

In "Mathematical Physics" by Robert Geroch, the following 'plausibility argument' is given for Zorn's Lemma [If every totally ordered subset of a partially ordered set $S$ is bounded above, $S$ has a ...
8
votes
1answer
247 views

Axiom of Choice - Type Theory (Proof)

Background In Intuitionistic Type Theory (p. 27-28), Martin Löf provides a proof of the axiom of choice that is constructively valid. This version is considerably weaker than the ordinary set theory ...
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
2answers
262 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
131 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 ...
2
votes
1answer
128 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 ...
3
votes
1answer
107 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 ...
6
votes
2answers
105 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 ...
1
vote
2answers
99 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 ...
8
votes
1answer
158 views

If $B\not\prec A$, does $A\preceq {\cal P}(B)$ or $A\preceq {\cal P}{\cal P}(B)$, etc in ${\sf ZF}$?

I've heard it said that theorems based on choice are also available in ZF "a few powersets away", and I think this is one of them, but I'm not sure how to prove it. (I'm also interested to hear of ...
3
votes
1answer
126 views

Is it possible to prove $|V_\kappa|=\kappa$ for strongly inaccessible $\kappa$ without AC?

First, let me note that my definition of "strongly inaccessible" is that a nonzero ordinal $\kappa$ is strongly inaccessible if ${\rm cf}(\kappa)=\kappa$ and $\forall\alpha<\kappa, {\cal ...
4
votes
2answers
133 views

Axiom of Choice in Logic

The completeness and compactness theorems of first-order logic are well known to be equivalent to the ultrafilter lemma. Are there any theorems of logic that are similarly equivalent to the full axiom ...
7
votes
1answer
145 views

Nielsen-Schreier and the Axiom of Choice

The Nielse-Schreier (NS) Theorem says that every subgroup of a free group is free. The proof uses the Axiom of Choice, and Läuchli showed in 1962 that the negation of NS is consistent with ZFA (ZF ...
6
votes
2answers
130 views

Axiom of Choice-esque argument to show that a proof of a statement exists without actually giving a proof

What if the set of all well-formed statements in ZFC formed a kind of pseudo-category where a morphism f between objects A, B represented a formal proof that A implied B? What if that category could ...
6
votes
2answers
197 views

The Axiom of Choice and definability

I've seen a lot of relations between the notion of the existence of a definable set with a given property and the necessity of AC is proving that there is a set with the property. For example: Under ...
10
votes
1answer
238 views

Does a nonlinear additive function on R imply a Hamel basis of R?

A function is additive if $f(x+y) = f(x) + f(y)$. Intuitively, it might seem that an additive function from R to R must be linear, specifically of the form $f(x) = kx$. But assuming the axiom of ...
5
votes
2answers
222 views

Intuition behind the Axiom of Choice

Why is it different to make one choice or many choices than to make infinite choices from a theoretical point of view in which indeed you are not going to do any? How could that be different from ...
8
votes
1answer
143 views

Failure of Choice only for sets above a certain rank

Let $\alpha$ be an ordinal. How can we show that the following theory is consistent? $\mathrm{ZF}$ + "there exists a set with rank greater than $\alpha$ that is not well ordered" + "every set of rank ...
12
votes
1answer
260 views

Do you need the Axiom of Choice to assert that every real vector space has a norm?

Math people: This question is 95% answered (the first answer) at Does every $\mathbb{R},\mathbb{C}$ vector space have a norm? and Vector Spaces and AC . The questions, answers, and links found there ...
12
votes
0answers
143 views

Is Dover publishing Moore's book on the Axiom of Choice? [closed]

Dover is publishing a paperback edition of Gregory H. Moore's Zermelo's Axiom of Choice: Its Origins, Development, and Influence. It's supposed to come out March 20th and is available for pre-order at ...
9
votes
2answers
330 views

The “it's not possible” statement in math and the Axiom of Choice

This question actually consists 3 related pieces of text, which I've gathered under this title about which I would like your opinion (they rather contain the implicit question "is this the right way ...
8
votes
4answers
496 views

Why isn't this a valid argument to the “proof” of the Axiom of Countable Choice?

I am having a little trouble identifying the problem with this argument: Let $\{A_1, A_2, \ldots, A_n, \ldots\}$ be a sequence of sets. Let $X:= \{n \in \mathbb{N} : $ there is an element of the set ...
11
votes
1answer
510 views

Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?

Math people: It is my understanding that set theorists/logicians compare cardinalities of sets using injections rather than surjections. Wikipedia defines countable sets in terms of injections. ...
1
vote
3answers
99 views

A generic argument in Kuratowski-Zorn Lemma

Many applications of Kuratowski-Zorn Lemma exhibit a common principle, that I could best summarise as: If one defines a structure by "nice" conditions, then Kuratowski-Zorn shows a maximal ...
5
votes
2answers
115 views

How does Fraenkel's urelement proof show choice is independent of ZF?

I understand the actual proof Fraenkel gives but I can't see how it proves choice independent of the full ZF because he works in a very restricted universe. Can anyone show how to connect one to the ...
1
vote
2answers
201 views

Question on independent equivalent set

On Page 28, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Say that a set $\Sigma_1$ of wffs(short for well-formed formulas) is equivalent to a set $\Sigma_2$ of wffs iff for any ...
8
votes
3answers
258 views

Does negation of Axiom of Choice imply symmetry?

It seems that every construction of a model in which the Axiom of Choice fails involves some kind of symmetry. Is there an example of a construction of a model where AC fails but no argument involving ...
4
votes
1answer
117 views

Is this theory $\kappa$-categorical when $\kappa$ is infinite and not $\le \aleph_0$?

Let $\mathcal L$ be a language with only a binary predicate $E$, and let $T$ be a theory of structures in which $E$ is an equivalence relation which partitions the structure into two infinite ...
2
votes
2answers
202 views

Is the negation of Gödel's completeness theorem consistent with $ZF$ without AC?

The proof of compactness and completeness of $\mathscr{FOL}$ (with Hilbert system) used Zorn's lemma. And Zorn's lemma is equivalent to the Axiom of choice in $ZF$. So my question is can they be ...
8
votes
1answer
408 views

Intuitionistic Banach-Tarski Paradox

While the Banach-Tarski paradox is a counter-intuitive result which requires the Axiom of Choice, leading some people to argue specifically against Choice, and others to argue for constructive ...
3
votes
1answer
136 views

Does (Infer $\phi$ from $\psi$) imply (Infer $\phi^L$ from $\psi^L$)?

I am studying set theory on my own on Drake's famous book and I'm stuck on the (finitary) prove of the relative consistency of the Axiom of Choice. Is it true that a if we were able to infer $\xi$ ...
12
votes
4answers
542 views

Number Theory in a Choice-less World

I was reading this article on the axiom of choice (AC) and it mentions that a growing number of people are moving into school of thought that considers AC unacceptable due to its lack of constructive ...
25
votes
2answers
660 views

A few questions about intuitionistic mathematics

I have to write a paper on Intuitionism for my Philosophy of Science class and I'm struggling with a few concepts I have encountered in my self-study. The (intuitive) characterization of valid ...
12
votes
1answer
207 views

Are sets constructed using only ZF measurable using ZFC?

Suppose $S$ is a subset of $\mathbb{R}$ which can be defined without using the axiom of choice, i.e. which can be proved to exist using only the axioms of ZF. Does it follow that $S$ is measurable? ...
4
votes
1answer
202 views

Proof with axiom of choice implies proof without?

Is there a theorem that guarantees the existence of a proof not using AC given there is a proof using AC, at least under some circumstances? What is its name (if there is one) and its most general ...
17
votes
6answers
650 views

Implication and Interpretation of Banach Tarski

As I understand, the Banach-Tarski paradox says a ball in 3-space may be decomposed into finitely many pieces and reassembled into two balls each of the same size as the original. Despite being called ...
4
votes
2answers
289 views

Open Sets of $\mathbb{R}^1$ and axiom of choice

In the proof of 'Every open set in $\mathbb{R}^1$ is a countable union of disjoint open intervals', we need to pick one rational representative from each of the intervals hence establish the ...
3
votes
2answers
512 views

How do I choose an element from a non-empty set?

Suppose I have a non-empty set $A$. How do I choose an element $x\in A$? More precisely, I believe I would like to find a formula $P(x,y)$ of ZF such that for every non-empty set $y$ there is ...
10
votes
3answers
1k views

Axiom of choice, non-measurable sets, countable unions

I have been looking through several mathoverflow posts, especially these ones http://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice , ...