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
356 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
37 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
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 ...
6
votes
2answers
218 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
55 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
165 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 ...
5
votes
0answers
106 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
175 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
107 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
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 ...
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 ...
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 ...
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 ...
8
votes
1answer
155 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
116 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
126 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
123 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
126 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
182 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
212 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
215 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
142 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
251 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
132 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 ...
8
votes
2answers
319 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
477 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 ...
10
votes
1answer
463 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 ...
4
votes
2answers
108 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
193 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 ...
7
votes
3answers
233 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
115 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
196 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 ...
7
votes
1answer
370 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
133 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
528 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 ...
24
votes
2answers
612 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
201 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
199 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 ...
16
votes
6answers
613 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
286 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
463 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 ...
9
votes
3answers
952 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 , ...
6
votes
1answer
258 views

Simple functions and axiom of choice

The question I have is more of a curiosity, and that is why I decided to post here instead of Mathoverflow. Before posing the question, let me set up some background. Background: Let $\Omega$ be a ...
2
votes
3answers
340 views

Truth Value of Theorems in Axiomatic Set Theory

I encountered set theory these past couple of days in discrete mathematics, and my professor was talking about the axiom of choice and ZFC. He said that depending on which axiom you started from, you ...
15
votes
1answer
881 views

Infinite Set is Disjoint Union of Two Infinite Sets

A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite. In ZF, can you prove that every infinite set is the union of two ...
7
votes
1answer
509 views

Picking from an Uncountable Set: Axiom of Choice?

Question: Given the real numbers as a set, does it require the (non-finite) Axiom of Choice to pick out an arbitrary single element? What about if we wanted to pick out an integer? What about if we ...