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.
1,110 questions
256
votes
16
answers
71k
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 ...
34
votes
2
answers
2k
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 partition ...
32
votes
2
answers
4k
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/...
297
votes
34
answers
53k
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 ...
113
votes
2
answers
16k
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
2
answers
6k
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 ...
41
votes
5
answers
11k
views
Do sets with positive Lebesgue measure have same cardinality as R?
I have been thinking about which kind of wild non-measurable functions you can define. This led me to the question:
Is it possible to prove in ZFC, that if a (Edit: measurabel) set $A\subset \mathbb{...
23
votes
1
answer
3k
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 ...
97
votes
10
answers
15k
views
Reflection principle vs universes
In category-theoretic discussions, there is often the temptation to look at the category of all abelian groups, or of all categories, etc., which quickly leads to the usual set-theoretic problems. ...
32
votes
5
answers
4k
views
How many of the true sentences are provable?
Is there a natural measure on the set of statements which are true in the usual model (i.e. $\mathbb{N}$) of Peano arithmetic which enables one to enquire if 'most' true sentences are provable or ...
23
votes
5
answers
4k
views
Morse-Kelley set theory consistency strength
I've come across several references to MK (Morse-Kelley set theory), which includes the idea of a proper class, a limitation of size, includes the axiom schema of comprehension across class variables (...
17
votes
2
answers
3k
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 ...
8
votes
2
answers
698
views
Order type of $\alpha$-computable well-orderings
One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\...
110
votes
10
answers
26k
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 $...
57
votes
6
answers
6k
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 ...
49
votes
0
answers
3k
views
Concerning proofs from the axiom of choice that ℝ³ admits surprising geometrical decompositions: Can we prove there is no Borel decomposition?
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 ...
40
votes
3
answers
5k
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 ...
18
votes
0
answers
895
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 ...
143
votes
12
answers
30k
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 ...
122
votes
4
answers
39k
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 ...
107
votes
9
answers
36k
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 ...
82
votes
5
answers
19k
views
Inaccessible cardinals and Andrew Wiles's proof
In a recent issue of New Scientist (16 Aug 2010), I was surprised to read that a part of Wiles' proof of Taniyama-Shimura conjecture relies on inaccessible cardinals.
Here's the article
Richard Elwes,...
67
votes
10
answers
14k
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 ...
63
votes
4
answers
7k
views
When size matters in category theory for the working mathematician
I think a related question might be this (Set-Theoretic Issues/Categories).
There are many ways in which you can avoid set theoretical paradoxes in dealing with category theory (see for instance ...
22
votes
1
answer
4k
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
16
answers
34k
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 ...
92
votes
3
answers
14k
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 ...
53
votes
1
answer
6k
views
Does $2^X=2^Y\Rightarrow |X|=|Y|$ imply the axiom of choice?
The Generalized Continuum Hypothesis can be stated as $2^{\aleph_\alpha}=\aleph_{\alpha+1}$. We know that GCH implies AC (Jech, The Axiom of Choice, Theorem 9.1 p.133).
In fact, a relatively weak ...
48
votes
5
answers
7k
views
What axioms are used to prove Gödel's Incompleteness Theorems?
I understand Gödel's Incompleteness Theorems to be statements about effectively generated formal systems, which basically makes them theorems about algorithms. This is cool, because despite being ...
29
votes
4
answers
3k
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 ...
23
votes
2
answers
3k
views
Is there any research on set theory without extensionality axiom?
In practice (say, in computer science), collections with many "labels" ("identities"), or collections which occur in many copies, are more frequently used than sets. Such collections do not satisfy ...
23
votes
1
answer
2k
views
Can we axiomatize Omnific Integers without the Surreal Number system?
Omnific integers are the counterpart in the Surreal numbers of the integers. The surreal numbers are usually defined using set theory, and then the omnific integers are defined as a particular subset (...
20
votes
7
answers
2k
views
Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)
Let us say that a set B admits a rigid binary relation, if there is a binary relation R such that the structure (B,R) has no nontrivial automorphisms.
Under the Axiom of Choice, every set is well-...
19
votes
9
answers
5k
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)...
19
votes
2
answers
2k
views
Woodin's unpublished proof of the global failure of GCH
An unpublished result of Woodin says the following:
Theorem. Assuming the existence of large cardinals, it is consistent that $\forall \lambda, 2^{\lambda}=\lambda^{++}.$
In the paper "The ...
19
votes
3
answers
5k
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α ...
16
votes
1
answer
2k
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}(...
15
votes
1
answer
3k
views
V=L and a Well-Ordering of the Reals
A fairly simple question: I've read in multiple sources that Godel proved that if we accept the axiom of constructibility in ZFC, then we can create an explicit formula that well-orders the real ...
6
votes
1
answer
298
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]=\...
185
votes
11
answers
52k
views
Knuth's intuition that Goldbach might be unprovable
Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really ...
157
votes
5
answers
28k
views
What makes dependent type theory more suitable than set theory for proof assistants?
In his talk, The Future of Mathematics, Dr. Kevin Buzzard states that Lean is the only existing proof assistant suitable for formalizing all of math. In the Q&A part of the talk (at 1:00:00) he ...
77
votes
8
answers
12k
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 ...
60
votes
8
answers
10k
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/...
47
votes
3
answers
7k
views
Clearing misconceptions: Defining "is a model of ZFC" in ZFC
There is often a lot of confusion surrounding the differences between relativizing individual formulas to models and the expression of "is a model of" through coding the satisfaction relation with ...
37
votes
6
answers
6k
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 \...
30
votes
3
answers
3k
views
Can there be an embedding j:V → L, from the set-theoretic universe V to the constructible universe L, when V ≠ 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
$...
28
votes
2
answers
7k
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 ...
21
votes
6
answers
3k
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 ...
14
votes
4
answers
2k
views
What can be preserved in mathematics if all constructions are carried out in ZF?
This is inspired by this discussion. I see that the debates about the necessity of the axiom of choice in this or that statement are still ongoing. In this regard, I became interested in whether there ...
12
votes
1
answer
517
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}$ ?