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,112 questions
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}$ ?
- 1,133
12
votes
1
answer
648
views
Can $\mathcal{L}_{\omega_1,\omega}$ detect $\mathcal{L}_{\omega_1,\omega}$-equivalence?
Roughly speaking, say that a logic $\mathcal{L}$ is self-equivalence-defining (SED) iff for each finite signature $\Sigma$ there is a larger signature $\Sigma'\supseteq\Sigma\sqcup\{A,B\}$ with $A,B$ ...
- 20.5k
12
votes
2
answers
3k
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....
- 427
9
votes
2
answers
1k
views
Relationship between fragments of the axiom of choice and the dependent choice principles
The dependent choice principle ${\rm DC}_\kappa$ states that if $S$ is a nonempty set and $R$ is a binary relation such that for every $s\in S^{\lt\kappa}$, there is $x\in S$ with $sRx$, then there ...
- 2,240
9
votes
2
answers
1k
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}$ ...
- 18.6k
9
votes
1
answer
838
views
Bijective-equivalent collections of proper classes in set theory
In ZFC set theory (or better in NBG set theory, where the language is more flexible with proper classes), we have that every unbounded class of ordinal numbers is a proper subclass of the class On of ...
- 2,655
6
votes
0
answers
424
views
Is this internalization of a bijection between a set and its powerset possible?
From $\sf L-S$ theorems we can have an external bijection $j$ from a set to its powerset. Obviously, $j$ cannot be fully internalized (used in all instances of Replacement). However, partial ...
- 11.3k
2
votes
1
answer
427
views
What is the strength of adding limitation of size and a simple version of reflection to Ackermann set theory?
The following theory is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ denoting the class ...
- 11.3k
2
votes
3
answers
758
views
Mutually non-isomorphic connected graphs on $\kappa$ points
For any set $X$, let $[X]^2 = \big\{\{a,b\}: a, b\in X \land a\neq b\big\}$. Let $\kappa$ be an infinite cardinal. Is there a set ${\cal E} \subseteq {\cal P}([\kappa]^2)$ such that
for all $E \in {\...
- 48.9k
102
votes
21
answers
15k
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 (Wayback Machine). At first, I was excited to see a variant proof (as it did not ...
- 2,855
75
votes
4
answers
24k
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 ...
- 7,442
46
votes
3
answers
3k
views
Does an existence of large cardinals have implications in number theory or combinatorics?
Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
- 1,699
45
votes
5
answers
3k
views
How many rearrangements must fail to alter the value of a sum before you conclude that none do?
This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...
38
votes
4
answers
6k
views
Could groups be used instead of sets as a foundation of mathematics?
Sets are the only fundamental objects in the theory $\sf ZFC$. But we can use $\sf ZFC$ as a foundation for all of mathematics by encoding the various other objects we care about in terms of sets. The ...
- 3,137
38
votes
5
answers
9k
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 ...
- 1,035
34
votes
4
answers
3k
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 ...
- 32.1k
28
votes
11
answers
7k
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 ...
- 2,383
26
votes
7
answers
6k
views
What "forces" us to accept large cardinal axioms?
Large cardinal axioms are not provable using usual mathematical tools (developed in $\text{ZFC}$).
Their non-existence is consistent with axioms of usual mathematics.
It is provable that some of ...
user47697
26
votes
2
answers
3k
views
Sizes of bases of vector spaces without the axiom of choice
Assuming the axiom of choice does not hold we have that there is a vector space without a basis. The situation can be, in some sense, worse. It is consistent that there are vector spaces that have two ...
- 39.8k
22
votes
4
answers
10k
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 ?
- 1,190
20
votes
3
answers
3k
views
On statements independent of ZFC + V=L
Let $V=L$ denote the axiom of constructibility. Are there any interesting examples of set theoretic statements which are independent of $ZFC + V=L$? And how do we construct such independence proofs? ...
- 9,641
20
votes
2
answers
2k
views
What is $\omega_1^{CK}(\mathsf{Ord})$?
We know that if $\alpha<\omega_1^{CK}$ then there is some recursive $R$ such that $(\omega,R)$ has order type $\alpha$.
Let's consider now the ordinals, $\mathsf{Ord}$ with their natural order. ...
- 39.8k
19
votes
1
answer
4k
views
Injectivity of cardinality of power set
For two sets $A$ and $B$. Suppose $|2^A| = |2^B|$ (cardinality of power sets of $A$ and $B$). Does this imply $|A|=|B|$?
(It is easy to see that $|A|=|B|$ if we assume generalized continuum hypothesis....
- 283
18
votes
4
answers
3k
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 ...
- 30.1k
15
votes
3
answers
1k
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 $\...
- 18.6k
15
votes
2
answers
1k
views
Does foundation/regularity have any categorical/structural consequences, in ZF?
(Prompted by reflection on this old answer, and its suggestion of the “harmlessness” of the axiom of regularity.)
In ZFC, one may justify the axiom of foundation (AF, aka the axiom of regularity) as ...
- 21.3k
14
votes
4
answers
2k
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 ...
- 39.8k
13
votes
1
answer
639
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 ...
- 48.9k
13
votes
1
answer
532
views
extending elementary embeddings from initial segments of V to all of V
Suppose $j:V_\lambda \rightarrow V_\eta$ is (elementary and) cofinal. Can $j$ be extended to all of $V$?
(Subsidiary question: What conditions are there on an ultrafilter/extender/whatever so that ...
- 354
12
votes
4
answers
1k
views
Is this theory synonymous with PA?
Language: Mono-sorted first order logic with equality.
Extralogical Primitives: $<, \in$
Define: $x \leq y \iff x < y \lor x=y$
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
- 11.3k
12
votes
3
answers
4k
views
Existence of prime ideals and Axiom of Choice.
One of the must obvious equivalences of Axiom of Choice is the converse of Krull Theorem.
Bernhard Banaschewski in the Article titled by A New Proof that “Krull implies Zorn” showed a very simple ...
- 1,788
12
votes
5
answers
6k
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 ...
- 32.1k
11
votes
4
answers
2k
views
Failure of the GCH
What is the (currently known) consistency strength of global failure of the GCH?
I do not have access to the exact statement of the original Foreman-Woodin result. My searches seem to indicate that ...
- 113
11
votes
2
answers
709
views
Which forcings preserve (some) determinacy?
The question is exactly as in the title. I'm interested in general in all questions of the form "which forcings preserve property P?" for any P, but determinacy assumptions occupy a special place in ...
- 20.5k
11
votes
5
answers
3k
views
Minimal subset of axioms for ZFC
Hello all, one may look for "minimal system of axioms" for ZFC (or any other
theory) in the following (unusual) sense : say that a subset S of ZFC is
"sufficient" if there is an explicit procedure ...
- 3,595
11
votes
2
answers
981
views
Elementary equivalence of ordinals
What is the smallest ordinal alpha which is elementarily equivalent to some smaller ordinal beta with the signature (<)?
What is the corresponding ordinal beta?
What if we instead require that ...
user5810
5
votes
0
answers
647
views
Forcing with c.c.c forcing notions, Cohen reals and Random reals
I think the following question is due to Prikry:
Question. Is it consistent that any non-trivial c.c.c forcing notion adds a Cohen real or a Random real?
Is the question still open? What partial ...
- 32.1k
3
votes
1
answer
541
views
Are all constructible from below sets parameter free definable?
Lets take the intersection of the theory of $L_{\omega_1^{CK}}$ and $\sf ZF + [V=L]$, this is equivalent to the theory of constructability from below + limit stages.
Can this theory prove the ...
- 11.3k
52
votes
3
answers
5k
views
What the heck is the Continuum Hypothesis doing in Weibel's Homological Algebra?
On page 98 of Weibel's An Introduction to Homological Algebra he mentions that the ring $R = \prod_{i=1}^\infty \mathbb{C}$ has global dimension $\geq 2$ with equality iff the continuum hypothesis ...
- 30.3k
169
votes
1
answer
17k
views
Ultrafilters and automorphisms of the complex field
It is well-known that it is consistent with $ZF$ that the only automorphisms of the complex field $\mathbb{C}$ are the identity map and complex conjugation. For example, we have that $\vert\...
- 8,298
74
votes
11
answers
12k
views
Why hasn't mereology succeeded as an alternative to set theory?
I have recently run into this Wikipedia article on mereology. I was surprised I had never heard of it before and indeed it seems to be seldom mentioned in the mathematical literature. Unlike set ...
- 5,902
64
votes
15
answers
7k
views
Unnecessary uses of the axiom of choice
What examples are there of habitual but unnecessary uses of the axiom of
choice, in any area of mathematics except topology?
I'm interested in standard proofs that use the axiom of choice, but where
...
59
votes
13
answers
8k
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 ...
- 5,759
50
votes
4
answers
6k
views
Do set-theorists use informal set theory as their meta-theory when talking about models of ZFC?
Here, Noah Schweber writes the following:
Most mathematics is not done in ZFC. Most mathematics, in fact, isn't done axiomatically at all: rather, we simply use propositions which seem "intuitively ...
- 509
45
votes
5
answers
64k
views
How large is TREE(3)?
Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation ...
- 3,630
42
votes
2
answers
6k
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 ...
- 6,215
42
votes
2
answers
3k
views
Measurability and Axiom of choice
In some situations, you need to show Lebesgue-measurability of some function on $\mathbb{R}^n$ and the verification is kind of lengthy and annoying, and even more so because measurability is "obvious" ...
- 9,853
42
votes
7
answers
3k
views
How would one even begin to try to prove that a simple number-theoretic statement is undecidable?
This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other ...
- 29k
41
votes
1
answer
5k
views
Dual Schroeder-Bernstein theorem
This question was motivated by the comments to Dual of Zorn's Lemma?
Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement
For any sets $A$ and $B$, if there are surjections ...
- 32.5k
41
votes
6
answers
13k
views
Can we prove set theory is consistent?
Disclaimer
Of course not, I'm aware of Gödel's second incompleteness theorem. Still there is something which does not persuade me, maybe it's just that I've taken my logic class too long ago. On the ...
- 14.7k