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,111 questions
3
votes
1
answer
736
views
Is there an analogue of Shoenfield's absoluteness theorem, but for $\mathrm{On}$?
From wikipedia:
Shoenfield's absoluteness theorem shows that $\Pi^1_2$ and $\Sigma^1_2$
sentences in the analytical hierarchy are absolute between a model $V$
of ZF and the constructible ...
- 3,793
3
votes
1
answer
207
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 ...
- 55
3
votes
2
answers
334
views
Preservation of measurable cardinals in mild extensions
I would like some help with the proof of the preservation of measurable cardinals in mild extensions, as I am a bit new with forcing.
By mild extensions, I mean the generic extension produced from a ...
3
votes
1
answer
492
views
Does the partition principle imply (DC)?
For sets $x, y$ we write $x\leq y$, if there is an injection $\iota: x \to y$, and we write $x \leq^* y$ if either $x = \emptyset$ or there is a surjection $s: y \to x$. In ${\sf (ZF)}$ we have that $...
- 48.9k
3
votes
1
answer
192
views
Co-analytic $Q$-sets
A subset $A\subseteq \mathbb{R}$ is said to be a $Q$-set if every subset $B\subseteq A$ is $F_\sigma$ wrt the subspace topology on $A$. For example $\mathbb{Q}$ is a $Q$-set. The first time I have ...
- 2,286
3
votes
1
answer
946
views
On statements provably independent of ZF + V=L
Are there any known statements that are provably independent of $ZF + V=L$? A similar question was asked here but focusing on "interesting" statements and all examples of statements given in that ...
- 33
3
votes
2
answers
880
views
Veblen function with uncountable ordinals & beyond
Disclaimer: I am not a professional mathematician.
Background: I have been researching large countable ordinals for awhile & I think the Veblen function is particularly eloquent. My understanding ...
- 81
3
votes
0
answers
192
views
Existence of function $g$ such that $f(x,y)\le g(x)+g(y)$ [closed]
Prove for each function $f:\mathbb Q\times\mathbb Q\to\mathbb R$ there exists a function $g:\mathbb Q\to\mathbb R$ such that $f(x,y)\le g(x)+g(y)\,\forall x,y\in\mathbb Q$.
Find a function $f:\...
3
votes
2
answers
157
views
Are complete regular linear hypergraphs on $\omega$ isomorphic?
If $H_i = (V_i, E_i)$ are hypergraphs for $i=1,2$ then we say they are isomorphic if there is a bijection $f: V_1 \to V_2$ such that for $A \subseteq V_1$ we have $$A\in E_1 \text{ if and only if } f(...
- 48.9k
3
votes
1
answer
366
views
Can you formulate a theory stating that a truth predicate does not exist for first order set theory?
A truth predicate for first order set theory would allow you to determine the truth of statements in first order set theory. A definition is given here.
My question is, can you formulate a statement ...
- 6,353
3
votes
1
answer
1k
views
About Grothendieck Universe and Tarski's A and A' Axioms
A-The addition of the Grothendieck Universe Axiom (for every set x, there exists a set y that is a universe and contains x as member element) to ZFC (ZFC+GU) is considered as giving an almost good ...
- 2,655
3
votes
1
answer
472
views
Path cardinality for random $(a+b)$-ary infinite trees
Consider a random infinite binary tree $T(a,b)$, so that $a$ denotes the probability of a left edge branching from any root-connected node,and $b$ denotes the probability of a right edge branching ...
- 995
3
votes
0
answers
231
views
Is $\sf ZFC + Classes$ finitely axiomatizable?
$\sf ZFC + Classes$ is a bi-sorted theory with lower cases standing for sets and upper cases for Classes; axioms include all $\sf ZFC - Extensionality$ axioms written in lower case, and the following ...
- 11.3k
2
votes
1
answer
215
views
Tiling relation on the set of partitions
Let $x\neq \emptyset$ be a set and let $\text{Part}(x)$ be the collection of
all partitions of $x$. We need the following notation. Let $P \in \text{Part}(x)$
and $t\subseteq x$. We set
$$P_{[t]} = \{...
user62017
2
votes
1
answer
118
views
Can a Boolean Set Algebra be Restricted in the Analytical hierarchy?
I want a comprehension principle to capture $\Pi^1_1$-sets from a domain as well as sets that are relative complements of or finite unions of sets already defined by comprehension. I want to use as ...
- 3,574
2
votes
0
answers
184
views
Infinite iterates of the contravariant hom endofunctors on sets
My recent answer to Is it possible to define higher cardinal arithmetics (about defining infinite tetrations) requires something I don't know. Here is the simplest case.
Take a set $S$ and consider
$$...
- 18.4k
2
votes
2
answers
252
views
When is the Minkowski sum of weighted compact sets $w_1 B_1 + w_2 B_2 + \ldots$ (with $w \in L^1$) closed?
Let $B_1,B_2,\ldots,$ be compact subsets of $\mathbb R^d$ and $w_1,w_2,\ldots$ be nonnegative numbers summing to $1$. Consider the set
$$
A := w_1 B_1 + w_2 B_2 + \ldots = \left\{\sum_{n=1}^\infty w_n ...
- 6,853
2
votes
3
answers
309
views
Non-isomorphic hypergraphs on $\omega$
Let $H_i = (V_i, E_i)$ be hypergraphs for $i=1,2$. Then we say that $H_1\cong H_2$ if there is a bijection $\varphi:V_1\to V_2$ such that $A\in E_1$ implies $\varphi(A) \in E_2$ and $B\in E_2$ implies ...
- 48.9k
2
votes
2
answers
479
views
Finitely nested Singletons and the axiom of Regularity
Let V be the universe (the class of all sets), let W(0)=V, W(1) be the class of all singletons whose unique member element is a member set of W(0), and for n>0 let W(n+1) be the class of all ...
- 2,655
2
votes
2
answers
1k
views
Downgrading from ZFC with universes to ZFC
Is the following correct?
If something is provable for small sets in ZFC with Axiom of Universes ("For any set x, there exists a universe U such that x∈U.") then it is provable for any sets in ZFC (...
- 765
2
votes
0
answers
195
views
"Very $L$-like" models, part 2: combinatorics
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ and having the finite use property and the strong downward Lowenheim-Skolem property together with, for each finite ...
- 20.5k
2
votes
1
answer
200
views
Some very weak statements on choice
This is a follow-up question to Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?
Consider the statements
$(\text{S}1)$ For any infinite set $X$ there is ...
- 48.9k
2
votes
1
answer
298
views
A question about computability and Turing machines
For any recursively enumerable set theory $T$ (of consistency strength at least superior to KP), if we want to calculate $F(n)=\{F(m)：m∈ω∧mEn\}$ and can determine each $F(n)$ for a Henkin model $(ω,E)$...
- 127
2
votes
2
answers
292
views
Substructure Argument for Chain Conditions
Once, someone showed me a nice argument using elementary substructures for proving chain conditions about forcings. It was a basic example, maybe that Cohen forcing is ccc. I've been trying to look up ...
- 23
2
votes
1
answer
141
views
Is this strengthening of the definition of weakly Shelah cardinals equivalent to being weakly Shelah?
The MathOverflow question A weak (?) form of Shelah cardinals by Trevor Wilson defines weakly Shelah cardinals as follows:
A cardinal $\kappa$ is weakly Shelah if for all $f : \kappa \to \kappa$ ...
- 1,097
2
votes
1
answer
170
views
Interweaving two indexed families of filters
Conjecture
Let $U$ be an (infinite) set. Let $f$ be an $N$-ary (where $N$ is an
arbitrary index set) relation on $U$ (that is a set of functions $N
\rightarrow U$).
Let $\mathcal{L}_0$, $\...
- 765
2
votes
1
answer
173
views
Chromatic number and taking duals of hypergraphs
If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e:...
- 48.9k
2
votes
0
answers
309
views
Set theory for category theory
Let $SC$ (sets and classes) denote the modification of Ackermann set theory laid out in F. A. Muller's Sets, Classes and Categories (denoted there by ARC -- a brief summary of the theory is given ...
- 10.1k
2
votes
1
answer
425
views
Is full Replacement provable in Z + Ordinal Replacement?
$\text{Ordinal Replacement:}$ if $\phi(x,y)$ is a formula in two free variables $x,y$, then:
$\forall x \ [ordinal(x) \to \exists! y \ (ordinal (y) \wedge \phi(x,y)) ]
\to
\forall A \ (\forall x \...
- 11.3k
2
votes
1
answer
126
views
Minimal dominating subsets in infinite graphs
Let $G=(V,E)$ be any simple, undirected graph. A dominating set is a set $D\subseteq V$ such that for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$.
Is there an infinite graph $G=...
- 48.9k
2
votes
0
answers
160
views
Meeting a set of lines in a generalization of $\mathbb{R}^n$
I was wondering whether there is a generalization of Martin Sleziak's excellent answer to this question:
Suppose that $S$ is an infinite set, and let ${\cal L}$ be a collection of subsets of $S$ such ...
- 48.9k
2
votes
0
answers
315
views
How slowly can the critical points of the Fibonacci terms grow?
Define the Fibonacci terms $t_{n}$ for all $n\geq 1$ by letting $t_{1}(x,y)=y,t_{2}(x,y)=x$, and $t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$ for all $n$. The Fibonacci terms are used in order to ...
2
votes
1
answer
256
views
Chains of maximum cardinality in distributive lattices
It's quite straightforward to construct a (complete) lattice in which no chain has maximum cardinality: for each $n\in \omega\setminus\{0\}$ let $C_n$ be a copy of $n$ with the chain ordering ...
- 48.9k
2
votes
1
answer
298
views
Self-containing graphs
[Second try, after this question failed.]
Let me sketch a notion of self-containing structures by a simple example. Consider the class $\Gamma$ of finite or countable digraphs ("graphs" for short) ...
- 9,720
2
votes
1
answer
282
views
Infima in the Rudin-Keisler ordering
Let $\text{NPU}(\omega)$ be the set of non-principal ultafilters on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by
$${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\exists f:...
- 48.9k
2
votes
1
answer
135
views
Compactifications with remainder $[0,\omega_1]$ and convergent sequences
Is the following statement consistent?
$(\star)$ Let $K$ be a separable compact Hausdorff space containing the space $[0,\omega_1]$ so that the complement $K\setminus[0,\omega_1]$ is discrete. Then ...
- 41.9k
2
votes
2
answers
705
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 ...
- 41.9k
2
votes
1
answer
503
views
A question on Sigma(n)-admissible ordinals
Are Sigma(n)-admissible ordinals for n>0, i.e. ordinals such that Gödelś constructible hierarchy at that level is a model of Sigma(n)-KP, recursively inaccessible? According to Wikipedia on large ...
- 3,574
2
votes
1
answer
587
views
Is there a strict limit on choice principles in $\sf ZFC$?
Is there a principle $\sf P$ that $\sf ZFC$ [or some suitable extension of it] proves to be a strict limit on choice principles?
By a choice principle I mean a sentence (or scheme) that is equivalent ...
- 11.3k
2
votes
1
answer
202
views
Finite $k$-set-respecting splitting of $\mathbb{N}$
Motivation. My sons participated in a large football tournament recently; everyone wanted to be in a team with everyone else at least once. Tricky!
Formulation of the question. For any positive ...
- 48.9k
2
votes
1
answer
445
views
Cardinal Register Machines
A cardinal register machine is like an ordinal register machine but with branching based on cardinal equality rather than ordinal equality. What is the complexity of the halting problem for cardinal ...
- 7,545
2
votes
1
answer
273
views
Is it always possible to partition $[a,b]\times[c,d]$ into disjoint blocks $D_{ij}$ s.t. $\left.f\right|_{D_{ij}}$ is bijective?
Consider the function given by $f:[a,b]\times[c,d]\to[0,1]^{2}$ such that $0\leq a < b \leq 1$, $0 \leq c < d \leq 1$.
Moreover, we do also have that $f\in C^{1}([a,b]\times[c,d],[0,1]^{2})$ and ...
user127351
2
votes
1
answer
141
views
Injective choice function for "lines" in an infinite cardinal
Let $\lambda$ be an infinite cardinal and suppose ${\cal L}$ is a collection of subsets of $\lambda$ such that
$|k| = \lambda$ for all $k\in {\cal L}$ and,
if $k_1\neq k_2\in {\cal L}$ then $|k_1\cap ...
- 48.9k
2
votes
0
answers
240
views
3 questions around the Stone space of the free $\sigma$-algebra on $\omega_1$ free generators
During my studies, I came across several different Stone spaces, e.g.:
(i) The Cantor cube $X=\{0,1\}^{\omega_1}$, which is the Stone space of the free Boolean algebra on $\omega_1$ free generators;
...
- 207
2
votes
1
answer
438
views
The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
In their paper "The Role of the Foundation Axiom in the Kunen Inconsistency" (arXiv:1311.0814 [Math.LO]), Daghighi, Golshani, Hamkins, and Jerabek show that the patterns of possibility for the ...
- 6,132
2
votes
1
answer
276
views
Does the minor graph of graphs on $\mathbb{N}$ have an uncountable independent set?
By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. We write $V(G) := V$.
If $S, T$ are disjoint subsets of $V(G)$ we say that $...
- 48.9k
2
votes
1
answer
652
views
Consistency of: "The continuum function is injective, and for all infinite cardinals $\kappa$ we have that $2^\kappa$ is weakly inaccessible."
I asked here about "large powerset axioms" and to my delight, learned that such axioms are being taken seriously. I've been toying with them ever since. My favourite is: "The continuum function is ...
- 3,793
2
votes
3
answers
680
views
Another adjoint pair: Definable sets and set-builder formulas
I see adjointness between the two concepts of "being a definable set" and "being a set-builder formula":
A set $X$ is definable when there is a formula $\phi(x)$ such that $X = \lbrace x : \phi(x)\...
- 9,720
2
votes
1
answer
329
views
Convergence of distance
Consider these sets
$$
A\equiv \bigcap_{\delta>0} \liminf_{n\rightarrow \infty} \{x \in X: d(p_n, [\ell(x), u(x)])\leq \delta\}
$$
$$
C_n(L_n)\equiv \{x \in X: d(p_n, [\ell(x), u(x)])=0\}
$$
where:
...
- 108
2
votes
1
answer
160
views
Is this theory finitary first order complete?
If we coin a theory in $\mathcal L_{\omega_1, \omega}$ that begins with constructing pure true well founded finite sets, then the set of all true well founded hereditarily finite sets, then builds up ...
- 11.3k