This tag is for set theory topics typically studied at the advanced undergraduate or graduate level. These include cofinality, axioms of ZFC, axiom of choice, forcing, set-theoretic independence, large cardinals, models of set theory, ultrafilters, ultrapowers, constructible universe, inner model ...

learn more… | top users | synonyms

18
votes
1answer
2k views

About a paper of Zermelo

This about the famous article Zermelo, E., Beweis, daß jede Menge wohlgeordnet werden kann, Math. Ann. 59 (4), 514–516 (1904), available here. Edit: Springer link to the ...
71
votes
1answer
5k views

How do we know an $ \aleph_1 $ exists at all?

I have two questions, actually. The first is as the title says: how do we know there exists an infinite cardinal such that there exists no other cardinals between it and $ \aleph_0 $? (We would have ...
29
votes
2answers
2k views

Continuity and the Axiom of Choice

In my introductory Analysis course, we learned two definitions of continuity. $(1)$ A function $f:E \to \mathbb{C}$ is continuous at $a$ if every sequence $(z_n) \in E$ such that $z_n \to a$ ...
34
votes
1answer
6k views

Cardinality of Borel sigma algebra

It seems it's well known that if a sigma algebra is generated by countably many sets, then the cardinality of it is either finite or $c$ (the cardinality of continuum). But it seems hard to prove it, ...
20
votes
3answers
1k views

Defining cardinality in the absence of choice

Under ZFC we can define cardinality $|A|$ for any set $A$ as $$ |A|=\min\{\alpha\in \operatorname{Ord}: \exists\text{ bijection } A \to \alpha\}. $$ This is because the axiom of choice allows any ...
22
votes
2answers
2k views

For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

How to prove the following conclusion: [For any infinite set $S$,there exists a bijection $f:S\to S \times S$] implies the Axiom of choice. Can you give a proof without the theory of ordinal numbers....
53
votes
13answers
22k views

Why is “the set of all sets” a paradox?

I've heard of some other paradoxes involving sets (ie, "the set of all sets that do not contain themselves") and I understand how paradoxes arise from them. But this one I do not understand. Why is "...
21
votes
2answers
2k views

Cardinality of a Hamel basis of $\ell_1(\mathbb{R})$

What is the cardinality of a Hamel basis of $\ell_1(\mathbb R)$? Is it deducible in ZFC that it is seemingly continuum? Does it follow from this that each Banach space of density $\leqslant 2^{\...
15
votes
1answer
728 views

Do sets, whose power sets have the same cardinality, have the same cardinality?

Is it generally true that if $|P(A)|=|P(B)|$ then $|A|=|B|$? Why? Thanks.
34
votes
7answers
10k views

Difference between a class and a set

I know what a set is. I have no idea what a class is. As best as I can make out, every set is also a class, but a class can be "larger" than any set. (A so-called "proper class".) This obviously ...
15
votes
2answers
804 views

Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF

Special Aleph Hypothesis AH(0) is the claim $2^{\aleph_0}=\aleph_1$, i.e. there is a bijection from $2^{\aleph_0}$ to $\aleph_1$. Continuum Hypothesis CH is the claim $\aleph_0 \leq \mathfrak{a}< ...
44
votes
2answers
8k views

Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
8
votes
1answer
1k views

Polish Spaces and the Hilbert Cube

I've been trying to prove that every Polish Space is homeomorphic to a $G_\delta$ subspace of the Hilbert Cube. There is a hint saying that given a countable dense subset of the Polish space $\{x_n : ...
33
votes
5answers
2k views

Advantage of accepting the axiom of choice

What is the advantage of accepting the axiom of choice over other axioms (for e.g. axiom of determinacy)? It seems that there is no clear reason to prefer over other axioms.. Thanks for help.
67
votes
6answers
4k views

Why is $\omega$ the smallest $\infty$?

I am comfortable with the different sizes of infinities and Cantor's "diagonal argument" to prove that the set of all subsets of an infinite set has cardinality strictly greater than the set itself. ...
39
votes
7answers
4k views

Why is the Continuum Hypothesis (not) true?

I'm making my way through Thomas W Hungerfords's seminal text "Abstract Algebra 2nd Edition w/ Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not ...
17
votes
2answers
1k views

The set of ultrafilters on an infinite set

After recently learning about filters and ultrafilters, we looked into further problems and properties. I am having trouble with this one: If $X$ is an infinite set, then the set of all ultrafilters ...
10
votes
1answer
1k views

Nonnegative linear functionals over $l^\infty$

My purpose is a clarification of the role of the axiom of choice in constructing limits for bounded sequences. Namely, we want a linear functional of norm 1 defined on the space of all bounded complex ...
5
votes
3answers
611 views

Finite choice without AC

Can anyone explain how we choose one sock from each of finitely many pairs without the axiom of choice? I mean the following quote: To choose one sock from each of infinitely many pairs of socks ...
34
votes
4answers
2k views

Does every set have a group structure?

I know that there is no vector space having precisely $6$ elements. Does every set have a group structure?
15
votes
4answers
1k views

Is there a statement whose undecidability is undecidable?

We know there are statements that are undecidable/independent of ZFC. Can there be a statement S, such that (ZFC $\not\vdash$ S and ZFC $\not\vdash$ ~S) is undecidable?
3
votes
2answers
1k views

Do $\omega^\omega=2^{\aleph_0}=\aleph_1$?

As we know, $2^{\aleph_0}$ is a cardinal number, so it is a limit ordinal number. However, it must not be $2^\omega$, since $2^\omega=\sup\{2^\alpha|\alpha<\omega\}=\omega=\aleph_0<2^{\aleph_0}$,...
18
votes
3answers
814 views

For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$

Let $A,B$ be any two sets. I really think that the statement $|A|\leq|B|$ or $|B|\leq|A|$ is true. Formally: $$\forall A\forall B[\,|A|\leq|B| \lor\ |B|\leq|A|\,]$$ If this statement is true, ...
12
votes
1answer
610 views

There's non-Aleph transfinite cardinals without the axiom of choice?

I can't find anything on this anywhere. The book I'm largely using at the moment is based around ZFC, so it makes no mention of anything other than the Aleph numbers, but according to Wikipedia on the ...
5
votes
2answers
2k views

Cantor-Bernstein-like theorem: If $f\colon A\to B$ is injection and $g\colon A\to B$ is surjective, can we prove there is a bijection as well?

I've been trying to find this proof: If there exists $f \colon A\to B$ injective and $g \colon A \to B$ surjective, prove there exists $h \colon A \to B$ bijective. I thought of using ...
33
votes
9answers
3k views

Where to begin with foundations of mathematics

I would like to know more about the foundations of mathematics, but I can't really figure out where it all starts. If I look in a book on axiomatic set theory, then it seems to be assumed that one ...
37
votes
3answers
12k views

First-Order Logic vs. Second-Order Logic

Wikipedia describes the first-order vs. second-order logic as follows: First-order logic uses only variables that range over individuals (elements of the domain of discourse); second-order logic ...
35
votes
3answers
2k views

Set Theoretic Definition of Numbers

I am reading the book by Goldrei on Classic Set Theory. My question is more of a clarification. It is on if we are overloading symbols in some cases. For instance, when we define $2$ as a natural ...
15
votes
7answers
1k views

Applications of ultrafilters

I'm looking for some interesting applications of ultrafilters and also everything of interest involving ultrafilters. Do you know some applications or interesting things involving ultrafilters? I'm ...
14
votes
6answers
3k views

Axiom of Choice and finite sets

So I am relatively familiar with the Axiom of Choice and a few of its equivalent forms (Zorn's Lemma, Surjective implies right invertible, etc.) but I have never actually taken a set theory course. I ...
18
votes
1answer
552 views

How to formulate continuum hypothesis without the axiom of choice?

Please correct me if I'm wrong but here is what I understand from the theory of cardinal numbers : 1) The definition of $\aleph_1$ makes sense even without choice as $\aleph_1$ is an ordinal number (...
12
votes
2answers
1k views

Uncountable subset with uncountable complement, without the Axiom of Choice

Let $X$ be a set and consider the collection $\mathcal{A}(X)$ of countable or cocountable subsets of $X$, that is, $E \in \mathcal{A}(X)$ if $E$ is countable or $X-E$ is countable. If $X$ is countable,...
7
votes
1answer
474 views

What is $\aleph_0$ powered to $\aleph_0$?

By definition $\aleph_1 = 2 ^{\aleph_0}$. And since $2 < \aleph_0$, then $2^{\aleph_0} = {\aleph_1} \le \aleph_0 ^ {\aleph_0}$. However, I do not know what exactly $\aleph_0 ^ {\aleph_0}$ is or how ...
6
votes
3answers
2k views

Unary intersection of the empty set

In MK (Morse-Kelley) set theory life is easy: $\forall X\forall y\left(y\in\bigcap X\leftrightarrow\forall x\left(x\in X\rightarrow y\in x\right)\right)$. If $X=\left\{\right\}$ then $\bigcap X=U$, ...
4
votes
1answer
242 views

Godel's pairing function and proving c = c*c for aleph cardinals

I have a few questions about Godel's pairing function and proving that c = c * c for aleph cardinals. Mostly, though, I'm concerned that most of the proofs I've seen are erroneous, and this concerns ...
85
votes
4answers
7k views

What are the Axiom of Choice and Axiom of Determinacy?

Would someone please explain: What does the Axiom of Choice mean, intuitively? What does the Axiom of Determinancy mean, intuitively, and how does it contradict the Axiom of Choice? as simple ...
18
votes
4answers
3k views

Cardinality of all cardinalities

Let $C = \{0, 1, 2, \ldots, \aleph_0, \aleph_1, \aleph_2, \ldots\}$. What is $\left|C\right|$? Or is it even well-defined?
15
votes
10answers
2k views

Neatest proof that set of finite subsets is countable?

I am looking for a beautiful way of showing the following basic result in elementary set theory: If $A$ is a countable set then the set of finite subsets of $A$ is countable. I proved it as ...
4
votes
3answers
452 views

Proving that for infinite $\kappa$, $|[\kappa]^\lambda|=\kappa^\lambda$

Initially assume ZFC. Let $\binom{\kappa}{\lambda}$ denotes $\left|[\kappa]^{\lambda}\right|$ where $[\kappa]^{\lambda}$ is the collection of all subsets of $\kappa$ with cardinality $\lambda$. That ...
7
votes
2answers
632 views

How does (ZFC-Infinity+“There is no infinite set”) compare with PA?

How does (ZFC-Infinity+"There is no infinite set") compare with (first order) PA? Intuitively, neither theory should be more powerful than the other.
15
votes
1answer
1k 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 ...
10
votes
3answers
1k views

Is the class of cardinals totally ordered?

In a Wikipedia article http://en.wikipedia.org/wiki/Aleph_number#Aleph-one I encountered the following sentence: "If the axiom of choice (AC) is used, it can be proved that the class of cardinal ...
6
votes
2answers
1k views

intersection of the empty set and vacuous truth

Let $\mathbb S = \varnothing$. Then from the definition: $ \bigcap \mathbb S = \left\{{x: \forall X \in \mathbb S: x \in X}\right\}$ Consider any $x \in \mathbb U$. Then as $\mathbb S = ...
6
votes
1answer
439 views

Is there a way to define the “size” of an infinite set that takes into account “intuitive” differences between sets?

The usual way to define the "size" of an infinite set is through cardinality, so that e.g. the sets $\{1, 2, 3, 4, \ldots\}$ and $\{0, 1, 2, 3, 4, \ldots\}$ have the same cardinality. However, is this ...
33
votes
5answers
3k views

Foundation for analysis without axiom of choice?

Let's say I consider the Banach–Tarski paradox unacceptable, meaning that I would rather do all my mathematics without using the axiom of choice. As my foundation, I would presumably have to use ZF, ...
23
votes
4answers
2k views

Algebraic closure for $\mathbb{Q}$ or $\mathbb{F}_p$ without Choice?

I know the usual proof of the existence of an algebraic closure for any field using Zorn's Lemma. The answer to this previous question makes it clear that in general, some nonconstructive axiom (not ...
13
votes
2answers
377 views

The relationship of ${\frak m+m=m}$ to AC

Two simple questions: (Of course ${\frak m}$ denotes a cardinal in the weak sense in the claims below.) Can we prove in ZF that $\aleph_0\le{\frak m\Rightarrow m+m=m}$? If not, what is the ...
14
votes
1answer
1k views

Can one construct a non-measurable set without Axiom of choice?

Is axiom of choice required to show the existence of non-measurable sets? Is there a Lebesgue non-measurable set that can be constructed without axiom of choice? Related question on MO says it is ...
77
votes
6answers
5k views

What are the issues in modern set theory?

This is spurred by the comments to my answer here. I'm unfamiliar with set theory beyond Cohen's proof of the independence of the continuum hypothesis from ZFC. In particular, I haven't witnessed ...
67
votes
8answers
20k views

Can you explain the “Axiom of choice” in simple terms?

As I'm sure many of you do, I read the XKCD webcomic regularly. The most recent one involves a joke about the Axiom of Choice, which I didn't get. I went to Wikipedia to see what the Axiom of ...