Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [set-theory]

forcing, large cardinals, descriptive set theory, infinite combinatorics, cardinal characteristics, forcing axioms, ultrapowers, measures, reflection, pcf theory, models of set theory, axioms of set theory, independence, axiom of choice, continuum hypothesis, determinacy, Borel equivalence relations, Boolean-valued models, embeddings, orders, relations, transfinite recursion, set theory as a foundation of mathematics, the philosophy of set theory.

30
votes
2answers
3k views

Similarities between Post's Problem and Cohen's Forcing

Remark: I have since learned that G.H. Moore addresses this question in the third reference listed at the end of this post, beginning on p. 157 in which he cites a letter from Kreisel to Gödel dated 4/...
27
votes
1answer
856 views

Are the Sierpiński cardinal $\acute{\mathfrak n}$ and its measure modification $\acute{\mathfrak m}$ equal to some known small uncountable cardinals?

This question was motivated by an answer to this question of Dominic van der Zypen. It relates to the following classical theorem of Sierpiński. Theorem (Sierpiński, 1921). For any countable ...
175
votes
15answers
42k views

Why worry about the axiom of choice?

As I understand it, it has been proven that the axiom of choice is independent of the other axioms of set theory. Yet I still see people fuss about whether or not theorem X depends on it, and I don't ...
40
votes
2answers
4k views

What interesting/nontrivial results in Algebraic geometry require the existence of universes?

Brian Conrad indicated a while ago that many of the results proven in AG using universes can be proven without them by being very careful (link). I'm wondering if there are any results in AG that ...
17
votes
1answer
2k views

Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?

Let the proof theoretic ordinal $\alpha$ of a theory $T$ be the least recursive ordinal such that $T$ does not prove that $\alpha$ is well-founded. This ordinal is intended to quantify in some sense ...
96
votes
2answers
9k views

Does every non-empty set admit a group structure (in ZF)?

It is easy to see that in ZFC, any non-empty set $S$ admits a group structure: for finite $S$ identify $S$ with a cyclic group, and for infinite $S$, the set of finite subsets of $S$ with the binary ...
49
votes
6answers
3k views

Is the non-triviality of the algebraic dual of an infinite-dimensional vector space equivalent to the axiom of choice?

If $V$ is given to be a vector space that is not finite-dimensional, it doesn't seem to be possible to exhibit an explicit non-zero linear functional on $V$ without further information about $V$. The ...
46
votes
8answers
5k views

Why should we believe in the axiom of regularity?

Today I started reading Maddy's Believing the axioms. As I knew beforehand, it includes some discussion of ZFC axioms. However, I really hoped for a more extensive discussion of axiom of foundation/...
36
votes
0answers
2k views

Concerning the various proofs from the axiom of choice that R^3 admits of surprising geometrical decompositions into circles, skew lines and so on: can we prove in any instance that there are no Borel such decompositions? Or that AC is required?

This question follows up on a comment I made on Joseph O'Rourke's recent question, one of several questions here on mathoverflow concerning surprising geometric partitions of space using the axiom of ...
15
votes
2answers
2k views

Does ZFC prove the universe is linearly orderable?

It is consistent with ZFC that the universe is well-ordered, e.g. in $V=L$ where global choice holds. I also know that it is consistent that global choice fails (although I have no immediate example ...
16
votes
3answers
4k views

Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?

Let ZF1 = ZF, ZFk+1 = ZF + the assumption that ZF1,...,ZFk are consistent, ZFω = ZF + the assumption that ZFk is consistent for every positive integer k, ... and similarly define ZFα ...
5
votes
1answer
254 views

Does the critical sequence for subalgebras of elementary embeddings with finitely many generators have order type $\omega$?

Suppose that $\lambda$ is a cardinal. Let $\mathcal{E}_{\lambda}$ be the set of all elementary embeddings from $V_{\lambda}$ to $V_{\lambda}$. If $j,k\in\mathcal{E}_{\lambda}$, then define $j[k]=\...
216
votes
31answers
30k views

What are some reasonable-sounding statements that are independent of ZFC?

Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC." For example, suppose A is an abelian group such that every ...
117
votes
11answers
20k views

Solutions to the Continuum Hypothesis

Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? ; Completion of ZFC ; Complete resolutions of GCH; How far wrong could the Continuum Hypothesis be?; When was ...
81
votes
4answers
21k views

Is the analysis as taught in universities in fact the analysis of definable numbers?

Ten years ago, when I studied in university, I had no idea about definable numbers, but I came to this concept myself. My thoughts were as follows: All numbers are divided into two classes: those ...
55
votes
9answers
10k views

Arguments against large cardinals

I started to learn about large cardinals a while ago, and I read that the existence, and even the consistency of the existence of an inaccessible cardinal, i.e. a limit cardinal which is additionally ...
17
votes
8answers
4k views

Forcing as a tool to prove theorems

It is often mentioned the main use of forcing is to prove independence facts, but it also seems a way to prove theorems. For instance how would one try to prove Erdös-Rado, $\beth_n^{+} \to (\aleph_1)...
24
votes
4answers
2k views

When $2^\alpha = 2^\beta$ implies $\alpha=\beta$ ($\alpha,\beta$ cardinals)

Sorry if this is a silly question. I was wondering, under what axioms of set theory is it true that if $\alpha$,$\beta$ are cardinals, and $2^\alpha=2^\beta$, then $\alpha=\beta$? Do people use these ...
14
votes
0answers
493 views

Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal number line is universal for all class linear orders, or in other words, that every linear order (including proper-class-sized) linear ...
89
votes
9answers
27k views

solving $f(f(x))=g(x)$

This question is of course inspired by the question How to solve f(f(x))=cosx and Joel David Hamkins' answer, which somehow gives a formal trick for solving equations of the form $f(f(x))=g(x)$ on a ...
57
votes
4answers
15k views

Non-Borel sets without axiom of choice

This is a simple doubt of mine about the basics of measure theory, which should be easy for the logicians to answer. The example I know of non Borel sets would be a Hamel basis, which needs axiom of ...
61
votes
8answers
9k views

Set theories without “junk” theorems?

Clearly I first need to formally define what I mean by "junk" theorem. In the usual construction of natural numbers in set theory, a side-effect of that construction is that we get such theorems as $...
66
votes
5answers
4k views

How do the compact Hausdorff topologies sit in the lattice of all topologies on a set?

This question is about the space of all topologies on a fixed set X. We may order the topologies by refinement, so that τ ≤ σ just in case every τ open set is open in σ. ...
34
votes
5answers
7k views

Completion of ZFC

I attended a talk given by W. Hugh Woodin regarding the Ultimate L axiom and I wanted to verify my current understanding of what the search for this axiom means. I find it to be a fascinating topic ...
24
votes
2answers
4k views

Large cardinal axioms and Grothendieck universes

A cardinal $\lambda$ is weakly inaccessible, iff a. it is regular (i.e. a set of cardinality $\lambda$ can't be represented as a union of sets of cardinality $<\lambda$ indexed by a set of ...
26
votes
11answers
5k views

Does the Axiom of Choice (or any other “optional” set theory axiom) have real-world consequences? [closed]

Or another way to put it: Could the axiom of choice, or any other set-theoretic axiom/formulation which we normally think of as undecidable, be somehow empirically testable? If you have a particular ...
24
votes
3answers
3k views

Who needs Replacement anyway?

The set theory ETCS famously comes without the Replacement axiom schema (or an equivalent) that is part of ZFC. One (to me, not apparently useful) set that one cannot build in ETCS is $\coprod_{n\in \...
26
votes
2answers
1k views

Can there be an embedding j:V to L, from the set-theoretic universe V to the constructible universe L, when V not= L?

Main Question. Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ to the constructible universe $L$, if $V\neq L$? By embedding here, I mean merely a proper class isomorphism from ...
29
votes
4answers
2k views

Is it possible to define higher cardinal arithmetics

In number theory there are several operators like ‎addition, ‎multiplication and ‎exponentiation defined from ‎$‎‎‎\omega‎‎\times‎‎\omega‎$ ‎to ‎‎$‎‎‎\omega‎$. Each ‎of ‎them ‎is defined as an ‎...
22
votes
6answers
2k views

Where in ordinary math do we need unbounded separation and replacement?

[I have updated the question after initial comments in the hope of clarifying it.] I do quite a bit of reasoning, typically about topology and metric spaces, in "non-standard" foundations, such as ...
21
votes
1answer
2k views

Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem)

Gödel's constructible universe ($L$) is defined using definable power set operator in first order logic ($\mathcal{L}_{\omega ,\omega}$). One can produce such a universe in infinitary logics in ...
16
votes
3answers
819 views

Singularizing forcing of “small” cardinality?

Can there be a large cardinal $\kappa$ and a forcing of size $\kappa$ that makes $\kappa$ a singular cardinal? The motivation is that the standard Prikry forcing does not have a dense set of size $\...
11
votes
3answers
1k views

How elementary can we go?

It is a theorem of A. Levy, if $\kappa$ is an inaccessible cardinal, then $V_\kappa\prec_{\Sigma_1} V$ namely $V_\kappa$ is an elementary submodel when considering only $\Sigma_1$ sentences. One ...
10
votes
2answers
2k views

How to construct a continuous finite additive measure on the natural numbers

I want to find some condition to construct a continuous finitely additive measure on the natural numbers, i.e. $f:P(\mathbb{N})\rightarrow [0,1]$ such that $f(\{n\})=0$, and $f$ is an additive measure....
5
votes
7answers
6k views

Uncountable family of infinite subsets with pairwise finite intersections

I am searching for a constructive proof of the following fact: If $X$ is an infinite set, there exists an uncountable family $(X_\alpha)_{\alpha \in A}$ of infinite subsets of $X$ such that $X_\alpha \...
19
votes
4answers
2k views

Why is there no Borel function mapping every countable set of reals outside itself?

A choice function maps every set (in its domain) to an element of itself. This question concerns existence of an anti-choice function defined on the family of countable sets of reals. In an answer to ...
9
votes
1answer
760 views

Resembling the Levy Collapse

Suppose $\kappa$ is a weakly compact cardinal. Is there a $\kappa$-c.c. forcing $\mathbb{P}$ such that $\mathbb{P} \subseteq V_\kappa$ and $\Vdash_{\mathbb{P}} \kappa = \aleph_1$, where $\mathbb{P}$ ...
10
votes
1answer
1k views

totally ordered chain in the powerset with big cardinality

Let $B$ be some set. The problem is to find a set $A\subset\mathcal{P}(B)$ of subsets of $B$ which is totally ordered by inclusion and such that there exists a bijection $A\leftrightarrow \mathcal{P}(...
13
votes
1answer
445 views

$T_2$-spaces where all non-empty open sets are homeomorphic

We say that a $T_2$-space $(X,\tau)$ has homeomorphic open sets if every non-empty open set $U\subseteq X$ endowed with the subspace topology is homeomorphic to $(X,\tau)$. The rationals with the ...
10
votes
1answer
237 views

Selective ultrafilter and bijective mapping

For arbitrary (selective) ultrafilter $\mathcal{F}$ does there exist bijection $\phi:[\omega]^2\to\omega$ with the property: $\forall B\in\mathcal{F} : \phi([B]^2)\in\mathcal{F}$ ?
69
votes
16answers
20k views

Most 'unintuitive' application of the Axiom of Choice?

It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even ...
75
votes
20answers
10k views

Proofs of the uncountability of the reals.

Recently, I learnt in my analysis class the proof of the uncountability of the reals via the Nested Interval Theorem. At first, I was excited to see a variant proof (as it did not use the diagonal ...
71
votes
2answers
8k views

Is every sigma-algebra the Borel algebra of a topology?

This question arises from the excellent question posed on math.SE by Salvo Tringali, namely, Correspondence between Borel algebras and topology. Since the question was not answered there after some ...
67
votes
8answers
8k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge: You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
43
votes
2answers
5k views

A question about ordinal definable real numbers

If ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice) is consistent, does it remain consistent when the following statement is added to it as a new axiom? "There exists a denumerably ...
40
votes
13answers
5k views

Cardinalities larger than the continuum in areas besides set theory

It seems that in most theorems outside of set theory where the size of some set is used in the proof, there are three possibilities: either the set is finite, countably infinite, or uncountably ...
30
votes
3answers
3k views

Is there a computable model of ZFC?

Background Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being ...
17
votes
4answers
6k views

Cardinality of the permutations of an infinite set

If you have an infinite set X of cardinality k, then what is the cardinality of Sym(X) - the group of permutations of X ?
12
votes
5answers
4k views

Subset of the plane that intersects every line exactly twice

In a comment to this question, Tim Gowers remarked that using the axiom of choice, one can show that there exists a subset of the plane that intersects every line exactly twice (although it has yet to ...
37
votes
3answers
1k views

Is the fixed point property for posets preserved by products?

Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point. Theorem. Suppose $P$ and $Q$ are posets ...