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.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

On a particular proof of “if the sharp of every real exists and every club contains a club constructible from a real, then $\delta^1_2 = \omega_2$”

I am referring to the proof of (4) implies (1) in Theorem 3.16 of Woodin's The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. His proof leverages on the fact that if the sharp of ...
2
votes
1answer
41 views

Constructing a section of an equivalence relation compatible with the intersection

Let $X$ be a (countably) infinite set and define an equivalence relation $\sim$ on the power set $P(X)$ of $X$ by defining two subsets $A$ and $B$ of $X$ to be equivalent if they differ by at most ...
-2
votes
0answers
57 views

Wadge hierarchy on $\Delta^0_2$ sets [closed]

I'm studying the Wadge hierarchy on Baire space and Cantor space. I'm asking whether or not the $\Delta^0_2$ sets form a unique degree in these spaces and why the $\Sigma^0_2$-true (i.e. not Polish) ...
5
votes
0answers
149 views

Are there analogues of real-valued measurability for larger powersets?

Apologies if the question is somewhat naïve - I'm not a set theorist, just an enthusiast. One possible intuition we could have about the generalized continuum hypothesis is that power sets are so ...
16
votes
0answers
210 views

Čech functions and the axiom of choice

A Čech closure function on $\omega$ is a function $\varphi:\mathcal P(\omega)\to\mathcal P(\omega)$ such that (i) $X\subseteq\varphi(X)$ for all $X\subseteq\omega$, (ii) $\varphi(\emptyset)=\emptyset$,...
3
votes
1answer
212 views

NF and incompleteness

Are there any well-known statements independent of NF? And also, are there prerequisites suggesting that NF in any way, to one extent or another, are not covered by the incompleteness theorem?
-3
votes
0answers
92 views

Ackermann function is computable [closed]

I was researching about Ackermann function and head to the problem to prove that Ackermann function is computable (in CF). I know that I have to prove that graph of Ackermann is primitive recursive ...
43
votes
4answers
4k views

Category theory and set theory: just a different language, or different foundation of mathematics?

This is a question to research mathematicians, as well as to those concerned with the history and philosophy of mathematics. I am asking for a reference. In order to make the reference request as ...
6
votes
1answer
183 views

Can we recover an inner model of CH after forgetting some generic information?

Suppose $\kappa$ is an inaccessible cardinal. Let $G \times H$ be $\mathrm{Col}(\omega_1,{<}\kappa) \times \mathrm{Add}(\omega,\kappa)$-generic over $V$. Let $X \subseteq \kappa$ be $\mathrm{Add}(...
12
votes
1answer
433 views

How strong a set theory is necessary for practical purposes in sheaf theory?

Is it known how much of ZFC is actually necessary for the basic, familiar constructions and theorems in sheaf theory, along the lines of section II.1 (and its exercises) in Hartshorne's "Algebraic ...
15
votes
0answers
388 views
+400

Positive set theory and the “co-Russell” set

This is a more focused version of a question which was asked at MSE a couple years ago, but is still unanswered there. That question asks about a broad range of theories, whereas this version focuses ...
3
votes
0answers
37 views

Maximum partite subset of edges of a hypergraph

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if $\bigcup{\frak P} = X$, and $P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$. Let $H = (V,...
0
votes
0answers
64 views

At which large cardinal property Ackermann set theory + finitization rule would stop?

By the finitization rule I mean a rule that inputs a schema in the $V$ world and outputs a single statement in the $V$ world that serves to capture that schema! So in this sense we'll have for ...
0
votes
0answers
57 views

Is Separation in $V$ a theorem schema of Ackermann set theory minus subsets?

Working in Ackermann set theory minus axiom of subsets: is $V$- bounded separation a theorem scheme of it? $V$-Bounded Separation: if $\phi^V(y)$ is a formula in which all quantifiers are bounded ...
4
votes
0answers
142 views

Does $\mathbb{R}$ have a partite subbase?

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if $\bigcup{\frak P} = X$, and $P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$. Let $H = (V,...
2
votes
1answer
85 views

Centralizer of a single element in the monoid of self-maps of a set

This is a follow-up to this question: For what sets $X$ do there exist a pair of functions from $X$ to $X$ with the identity being the only function that commutes with both? Let $X$ be a set, and $X^...
4
votes
1answer
197 views

Implications of the existence of a pair of surjective functions, without Axiom of Choice

The classical Cantor-Schroder-Bernstein Theorem says that there exists a bijective function $X\leftrightarrow Y$ if and only if there exist injective functions $X\hookrightarrow Y$ and $Y\...
0
votes
0answers
164 views

Is there a formula with one free variable in NBG that defines a class that does not exist?

This question concerns Godel's Theorem on existence of classes in Set Theory of von Neumann–Bernays–Gödel. This theorem implies that for any formula $\varphi(x)$ with one free variable $x$ whose ...
2
votes
1answer
126 views

Atomless, c-additive measures in ZFC

This is a follow-up question to this one. Is there a ZFC example of an atomless measure that is $2^\omega$-additive, meaning, fewer than continuum many null sets have measurable union that is null?
3
votes
1answer
150 views

Finitely additive, $\kappa$-additive atomless measures in ZFC

Under Martin's Axiom (and non-CH) the Lebesgue measure is $2^\omega$-additive in the sense that unions of fewer than continuum ($2^\omega$) many null sets are measureable and null. In ZFC we may ...
11
votes
0answers
308 views

Isomorphic free groups have bijective generating sets

Let $F(X)$ be the free group on a set $X$. Classically, we can prove the statement: $F(X) \cong F(Y)$ if and only if $|X|=|Y|$. The proofs (that I have seen) consist of turning the group ...
5
votes
0answers
122 views

For which classes of metric spaces can we prove that quasi-isometry is an equivalence relation in ZF?

Given two metric spaces $(M_1, d_1)$ and $(M_2, d_2)$, a map $\phi \colon (M_1, d_1) \to (M_2, d_2)$ is a large-scale Lipschitz essentially surjective map if there exist constants $A \geq 1, B \geq 0$,...
10
votes
0answers
200 views

How wealthy are canonical inner models?

One of the way a person shows their wealth is by having many diamonds. The same can be said about models of $\sf ZFC$. We can add generic diamond sequences, while preserving the old ones, so in some ...
23
votes
1answer
2k views

Are Conway's combinatorial games the “monster model” of any familiar theory?

This is related to this question about a "mother of all" groups, and so seemed like it'd fit in better at MO than MSE. If I understand the answer to that question correctly, the surreal numbers have ...
5
votes
1answer
108 views

Preserve unbounded sets between different cofinality

Working in ZFC, let $\kappa,λ$ be cardinals with $\kappa>λ$, and assume that $\kappa$ is regular. We say that a function $F:\kappa^n→λ$, for some finite $n$, is preserving unbound, if for all $a⊆\...
13
votes
3answers
1k views

Tarski's truth theorem — semantic or syntactic?

I was reading the sketch of the proof of Tarski's theorem in Jech's "Set Theory", which appears as Theorem 12.7, thinking that it would be an interesting result to really understand. As stated in the ...
1
vote
2answers
129 views

Connected Hausdorff spaces with large collection of disjoint open sets

Is there for every infinite cardinal $\kappa$ a connected Hausdorff space $(X,\tau)$ with $|X| = \kappa$ and a collection ${\cal D}$ of mutually disjoint open sets with $|{\cal D}| = \kappa$?
16
votes
1answer
612 views

Has the exponentiation of ordinals a nice geometric model?

It is well known that the sum $\alpha+\beta$ of two ordinals $\alpha,\beta$ can be defined "geometrically" as the order type of the sum $(\{0\}\times \alpha)\cup(\{1\}\times\beta)$ endowed with the ...
7
votes
1answer
195 views

Is Axiom of Choice equivalent to its version for families of sets, indexed by ordinals? [duplicate]

Is Axiom of Choice equivalent to the following statement? Axiom of Ordinal Choice: For any ordinal $\lambda$ and any indexed family of sets $(X_\alpha)_{\alpha\in\lambda}$ there exists a function $...
8
votes
1answer
244 views

On the utility of Silver machines

This question arises out of having Devlin's Constructibility [1] in my collection of books at home during the lockdown. Chapter IX of the book deals with Silver machines, which are presented as ...
11
votes
2answers
559 views

For what sets $X$ do there exist a pair of functions from $X$ to $X$ with the identity being the only function that commutes with both?

It is not too difficult to show that if $X$ is an infinite set, then there exists a two-element subset of the group $\operatorname{Sym}(X)$ with trivial centralizer iff $\lvert X\rvert \leq \lvert\...
28
votes
2answers
2k views

Who introduced direct limits?

The general notion of a direct limit of a commuting system of embeddings, indexed by pairs in a directed set, has seen heavy use in set theory. It is the same notion as in category theory. I was ...
6
votes
1answer
173 views

Complexity of a combinatorial constraint

For two $k$-partitions $X,Y\in k^\omega$ of $\omega$ (seen as functions $\omega\rightarrow k$), we say $X,Y$ are almost disjoint iff $X^{-1}(i)\cap Y^{-1}(i)$ is finite for all $i<k$. Question: ...
6
votes
1answer
131 views

Regular limit points of possible cofinalities

Let $A$ be a non-empty set of regular cardinals such that $\vert A\vert <\text{min}\ A$, and $\{\nu_i\mid i<i_0\}\subseteq \text{pcf}\ A$ be a strict increasing sequence having limit length $i_0$...
5
votes
0answers
138 views

Selecting an almost disjoint family in a given family of sets

A family $\mathcal A$ of infinite subsets of $\omega$ is called almost disjoint if for any distinct sets $A,B\in\mathcal A$ the intersection $A\cap B$ is finite. Let $\mathfrak a'$ be the largest ...
2
votes
1answer
156 views

Collection of pairwise non-isomorphic infinite self-complementary graphs

For any set $X$ let $[X]^2 = \big\{\{a,b\}: a\neq b\in X\big\}$. We say that a graph $G$ is self-complementary if $G\cong \bar{G}$ where $\bar{G} = (V, [V]^2\setminus E)$. Given an infinite cardinal ...
2
votes
1answer
80 views

What is the smallest cardinality of a base of an ultrafilter on $\omega$ related to an almost disjoint family of cardinality $\mathfrak c$?

Let $(A_\alpha)_{\alpha\in\mathfrak c}$ be an almost disjoint family of infinite subsets of $\omega$. The almost disjointness of the family means that $A_\alpha\cap A_\beta$ is finite for any ordinals ...
4
votes
1answer
140 views

What is the smallest cardinality of a maximal ultrafamily of infinite subsets of $\omega$?

A family $\mathcal U$ of infinite subsets of $\omega$ is called an ultrafamily if for any sets $U,V\in\mathcal U$ one of the sets $U\setminus V$, $U\cap V$ or $V\setminus U$ is finite. By the ...
54
votes
4answers
5k views

Bourbaki's definition of the number 1

According to a polemical article by Adrian Mathias, Robert Solovay showed that Bourbaki's definition of the number 1, written out using the formalism in the 1970 edition of Théorie des Ensembles, ...
2
votes
0answers
107 views

ITTMs with higher types

What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set? ...
13
votes
1answer
347 views

History of well founded relations

I have changed the title in the hope of attracting the attention of someone who knows about the history of set theory as well as intuitionistic logic: Who was the first to state the definition of ...
2
votes
2answers
487 views

In the von Neumann–Bernays–Gödel axiomatic system, the Axiom of Transposition can be simplified

Looking at the von Neumann–Bernays–Gödel (NBG) axioms of Set Theory in Wikipedia I noticed that it has two axioms of permutation: one for circular permutations and another for transpositions. On the ...
1
vote
2answers
130 views

Covering dimension of uncountable union of compact spaces

It is well-known that the (covering) dimension of countable union of compact spaces is the superium dimension of these spaces. I would like to understand certain uncountable union of compact spaces as ...
4
votes
1answer
149 views

Function whose graph is a Borel relation

Suppose $f\colon\mathbb{R}^{\omega}\longrightarrow\mathbb{R}$ is a function such that $$G(f):=\{(x,y)\in\mathbb{R}^{\omega}\times\mathbb{R}\mid f(x)=y\}$$ is a Borel set. Does it necessarily follow ...
7
votes
0answers
158 views

“Local” compactness properties beyond $\mathcal{L}_{\omega_1,\omega}$?

Below, all languages are finite for simplicity. This question is about generalizations of Barwise compactness for logics more complicated than $\mathcal{L}_{\omega_1,\omega}$: properties of the form "...
0
votes
0answers
112 views

Can inaccessibility be captured in relational flat set theory?

Working in a first order theory of flat sets (axioms given below) , which is a theory with a single non-trivial tier of membership, that is all sets are nonempty sets of Quine atoms, plus having some ...
3
votes
0answers
89 views

Global choice for models of complete theories in $\mathsf{ZFC}$

This is a followup to a previous question of mine. To summarize the result of that question, by a result of Kanovei and Shelah, $\mathsf{ZFC}$ is enough to show that there is a uniform procedure for ...
1
vote
1answer
169 views

Borel hierarchy and tail sets

Let $A$ be a finite set, and let $A^\infty$ be the set of all sequences $(a_n)_{n=1}^\infty$ of elements of $A$. A set $B \subseteq A^\infty$ is a tail set if for every two sequences $\vec a, \vec b \...
0
votes
1answer
70 views

Lambda system generated by a non-atomic collection

Consider a probability space $(X,\Sigma,P)$. Let say that a collection $\mathcal{B}\subseteq\Sigma$ is non-atomic if for every $E\in\mathcal{B}$ and $\alpha\in(0,P(E))$ there exists $F\in\mathcal{B}$ ...
5
votes
0answers
161 views

Inner models with all sets generic

Question: Under large cardinal axioms, what is the intersection of all inner models $M$ of ZFC such that every set in $V$ is set-generic over $M$? Every set belongs to a generic extension of HOD, and ...

1
2 3 4 5
77