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
22 views

Representing $\forall x\in \mathbb{N}$ via ZFC

Given some arbitrary predicate $\phi(x)$ (e.g. $\phi(x)="x$ is uneven" or "x is prime"), I was wondering if one can formally make sense out of statements like \begin{equation*}{\forall ...
5
votes
1answer
102 views

What is the “Prikry–Silver collapse” when CH fails?

We all know and love Cohen reals, and we can (and often do) define the Cohen forcing as partial functions $p\colon\omega\to 2$ with finite domain. The Prikry–Silver forcing is defined as partial ...
3
votes
0answers
108 views

A family of finite subsets of an infinite cardinal that is closed enough

I would like to ask the following question: Let $\lambda$ be an infinite cardinal (I am interested in the singular case). Can we construct a family $F$ of finite subsets of $\lambda$, such that $|F|=\...
0
votes
0answers
147 views

Can we put a ZFC world inside an NF world?

Recall the definitions of Lewisian set that I've introduced in this posting. In nutshell, working in Labeled Mereology, a set is Lewisian if and only if it is a Lewisian class that has a unique label. ...
6
votes
1answer
148 views

Models with fixed cardinality of non-Lebesgue measurable sets

In the usual $\mathsf{ZFC}$, we know that there are $2^\mathfrak{c}$ many subsets of $\mathbb{R}$ that are not (Lebesgue) measurable. On the other hand, the Solovay model also provides us a model of $\...
5
votes
3answers
209 views

Induced subgraphs of the almost-disjointness graph

Let $[\omega]^\omega$ denote the collection of infinite subsets on $\omega$, and let $$E=\big\{\{a, b\}:a,b\in [\omega]^\omega \text{ and } |a\cap b| \text{ is finite}\big\}.$$ Is every simple, ...
1
vote
0answers
211 views

Is this theory using defined notions of classes, sets, and membership interpretable in ZFC?

The main difference with this formal theory is that it depends in an essential manner on a defined notion of class, set, and set membership $\in$, rather than the usual appraoch of leaving them ...
10
votes
1answer
303 views

Elementary embeddings and replacement

Let $\alpha\not= 0$ be such that for every $\beta<\alpha$ there is $\beta<\gamma<\alpha$, where $V_\gamma$ is an elementary substructure of $V_\alpha$. In other words, $V_\alpha$ is a limit ...
5
votes
1answer
140 views

How similar are the c.e. degrees and the CEA(Cohen) degrees?

Given reals $A,B,X$, let $A\le_{T/X}B$ iff $A\oplus X\le_TB\oplus X$. For each real $X$ we can define a version of the c.e. degrees over $X$: we look at the preorder on $X$-c.e. reals given by $\le_{T/...
16
votes
1answer
290 views

Partitions of the real line into Borel subsets

Problem 1. Is it true that for every cardinal $\kappa\le\mathfrak c$ there exists a partition $(B_\alpha)_{\alpha\in\kappa}$ of the real line into $\kappa$ pairwise disjoint non-empty Borel subsets? ...
6
votes
0answers
99 views

Better scales and Failures of SCH

Assume $\mu$ is a singular cardinal of countable cofinality. Recall that a scale for $\mu$ consists of an increasing sequence $\vec{\mu}$ of regular cardinals $\langle \mu_n:n<\omega\rangle$ ...
5
votes
1answer
181 views

Dependent choices (DC) in ${\bf HOD}(\mathbb{R},X)$, where $X$ is a set of reals

In Turing invariant sets and the perfect set property, Math. Log. Quart. 66 (2020), Hamel, Horowitz and Shelah, the authors work in ZF + DC. They claim that DC can be dispensed with, asserting: if $V ...
5
votes
2answers
244 views

Extending contents

Suppose $\mu$ is a finitely additive measure on $X$ (aka “content”) with $\mu(X) < \infty$, defined on an algebra of sets $\mathcal A$. Let $$\mu^*(Y) = \inf \{ \mu(E) : E \in \mathcal A \wedge E \...
4
votes
1answer
215 views

Coloring almost-disjointness

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. Let $$E = \big\{\{A,B\}: A,B \in [\omega]^\omega \text{ and } |A\cap B| \text{ is finite}\big\}.$$ We consider the graph $G=...
0
votes
0answers
81 views

What is the exact consistency strength of this type-set theory?

Language: bi-sorted first order logic with equality and its axiom and additionally the extra-logical primitives: $ ``\tau, < , \in"$, the first is a total unary function on sets denoting is the ...
6
votes
0answers
148 views

Are initial segments of coherent measure sequences coherent?

This question is about the "old-fashioned" coherent sequences, in the style of Mitchell Mitchell, W. (1974). Sets constructible from sequences of ultrafilters. Journal of Symbolic Logic, 39(...
2
votes
0answers
106 views

Banach–Mazur game and mappings

The Banach-Mazur game on a nonempty space $X$ is defined as follows: two players, $I$ and $II$, alternately choose nonempty open sets \begin{matrix} I & U_0 && U_1 && \cdots ...
1
vote
0answers
84 views

Why $\beta S$ is not a semigroup when $S$ is a (directed) partial semigroup?

Given a semigroup $(S, *)$ we extend the semigroup operation $*$ of $S$ to a operation $*$ on $\beta S$ (the set of ultrafilters on $S$) defined as $$ \mathcal{U} * \mathcal{V} = \left\{ A \...
4
votes
1answer
162 views

How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?

This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence. The class of $[1]$-...
5
votes
2answers
205 views

Self-homeomorphism of Stone-Čech boundary with an isolated fixed point

$\DeclareMathOperator\bso{\beta^*\!\omega}\DeclareMathOperator\Homeo{Homeo}$Let $\bso$ be the complement of the countable discrete space $\omega$ in its Stone-Čech compactification $\beta\omega$ (some ...
2
votes
0answers
202 views

Can we have $\sf V=HTD$? How it relates to $\sf V=HOD$?

In my search for some type-set motivated line of thought that might prove axiom of choice, I was thinking of a concept that looks like $\sf V=HOD$, but in terms of types instead of ordinals, that is ...
0
votes
0answers
38 views

I have 2 very stupid questions about elements and subsets in ZFC [migrated]

Question 1: if X is a set, are its elements sets? (in ZFC) I believe the answer is yes. But where is the proof? Is it an axiom? Question 2: If X is a set, Y is an entity of unknow nature which has ...
3
votes
2answers
306 views

Can Z + Ranks + Successor cardinals + Ordinal inaccessibility be equal to ZF?

[EDIT: The axiom of successor cardinals was found by an answer by Greg Kirmayer, not to be capturing the intended meaning of it, which is simply reflected by its name, i.e. the existence of a ...
3
votes
0answers
60 views

On a connectivity property of set systems

Let $X\neq \emptyset$ be a set and let ${\cal A}\subseteq {\cal P}(X)$ with $\bigcup {\cal A}=X$. We say that $S\subseteq X$ is indivisible if for all $T\subseteq S$ with $\emptyset \neq T \neq S$ ...
14
votes
2answers
1k views

How many category structures are possible on two sets?

For two sets $O$ and $A$, we will call a category structure a collection of functions ${\sf dom}:A\to O,\ {\sf cod}:A\to O,\ {\sf 1}:O\to A,\ \circ:A\times_OA\to A$ satisfying the usual axioms for a ...
7
votes
0answers
160 views

How much is known about the consistency strength of toposes and topos-like categories?

It's a well-known fact that the theory of a well-pointed topos with a natural numbers object (NNO) has the same consistency strength as MacLane set theory (also known as bounded Zermelo). There are ...
3
votes
1answer
161 views

“Good limit” of an uncountable sequence of elements of an ultrafilter

Let $U$ be an ultrafilter on $\mathcal{P}(\omega)$ and $\langle \sigma _\alpha \mid \alpha < \omega_1 \rangle$ be a sequence of elements of $U$. I know that the limit sup of $\sigma _\alpha$'s ($= \...
0
votes
0answers
82 views

Dense refinement of $\omega$-cover

A collection $\{X_\alpha : \alpha\in\Lambda\}$ is said to be a $\omega$-cover of a space $X$ if for each finite $F\subseteq X$ there exists a $\beta\in\Lambda$ such that $F\subseteq X_\beta$. ($\{X_\...
1
vote
1answer
199 views

What does the Concordant constructible universe model?

Define a ranking function $\cal R$ as: $\mathcal{R}: V \to ON; \,\mathcal {R}(x)= \min \alpha \, \forall y \in x: \alpha > \mathcal {R}(y) $ Now the constructible rank $\mathcal R^c$ of a set $X$ ...
11
votes
1answer
395 views

“Drinking number” of a graph

Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half ...
10
votes
2answers
503 views

How far to find a well-order?

Consider a transitive set $M$. Let's call the well-ordering number for $M$ the smallest ordinal $\alpha$ so that $L_\alpha(M)$ contains as an element a well-order of $M$, and denote it as $\upsilon = \...
0
votes
0answers
34 views

Can all unions of sets above some level be constructible before the sets in some relative constructible universe?

Can we have some relative constructible universe $ L(A) \ (or \ L[A])$ such that for some infinite ordinal $\gamma \leq |A|$ we have: for every subset $u$ of $A$, if $u$ is the union of a set $\sf U$ ...
4
votes
1answer
112 views

Coloring the uncountable Lebesgue-measurable sets of $\mathbb{R}$

A hypergraph $H=(V,E)$ consists of a set $V$ and $E\subseteq {\mathcal P}(V)$, that is, $E$ consists of subsets of $V$ of arbitrary size. Obviously, a graph is a special kind of hypergraph. Let $H=(V,...
9
votes
1answer
269 views

Do saturated models require choice?

Let $T$ be a first-order theory, and suppose we want to build a saturated model $\mathbb U$ of $T$. That is, we want a model $\mathbb U$ of cardinality bigger than $|T|$, saturated in its own ...
8
votes
0answers
399 views

Ring of global sections of a functor $\mathbf{CRing} \to \mathbf{Set}$

Let $U : \mathbf{CRing} \to \mathbf{Set}$ be the forgetful functor. For any functor $F : \mathbf{CRing} \to \mathbf{Set}$ consider the class of natural transformations $$\mathcal{O}(F) := \mathrm{Hom}(...
0
votes
1answer
251 views

Can we choose a sequence of Hilbert spaces?

Let $n$ be a fixed natural number. Let $H$ be a complex Hilbert space and $H_1,\dotsc,H_n$ be closed subspaces of $H$. Set $H_0\mathrel{:=}H_1\cap H_2\cap\dotsb\cap H_n$ and let $P_i$ be the ...
11
votes
1answer
520 views

Does every countable set of Turing degrees have an upper bound, without AC?

It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle ...
1
vote
1answer
230 views

Is existence of this set consistent with Zermelo set theory minus choice?

Define a pre-ordinal as a transitive set of transitive sets. Is it consistent with Zermelo set theory (without choice) to have a nonempty set $S$ such that: for every element $s \in S$ there exists a ...
11
votes
2answers
785 views

How many finitely-generated-by-elements-of-finite-order-groups are there?

I do not know where this question is on the trivial to intractable spectrum. Consider the set of isomorphism classes of groups finitely generated by elements of finite order. What is the cardinality ...
12
votes
0answers
296 views

An internal notion of freeness for complete Boolean algebras

Background and Definition Gaifman and Hales showed that there are no infinite free complete Boolean algebras. But let a complete Boolean algebra $B$ be internally free if there is a set $X\subseteq B$ ...
2
votes
0answers
180 views

Can we have a “very strong” cone phenomenon in the Turing degrees (and a related question)?

By Borel determinacy + Martin's cone theorem, for every countable fragment $\mathcal{A}$ of $\mathcal{L}_{\omega_1,\omega}$ there is a turing degree ${\bf c}$ such that for all ${\bf d}\ge_T{\bf c}$ ...
1
vote
1answer
121 views

Scales and concentration

Let $S$ be a dominating subset of $[\mathbb{N}]^{\infty}$. Then $S=\{s_{\alpha} : \alpha<\mathfrak{d}\}$ is called a $\mathfrak{d}$-scale if for every $\alpha<\beta<\mathfrak{d}$, $s_{\beta}\...
4
votes
2answers
315 views

How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $M_i(x)$ denote a computation of an $i$-th ITTM, assuming that the input $x$ is a real (an infinite binary sequence). Then the ...
0
votes
1answer
439 views

Is a function needed here?

This question is related to my question Can we choose an element from a class?. However, I decided to create a separate question. Let $H$ be a complex Hilbert space and $H_1,\dotsc,H_n$ be closed ...
12
votes
1answer
638 views

Descriptive set theory for computer scientists?

It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the ...
2
votes
0answers
151 views

Showing that the procedure to generate an algebra does not generate a $\sigma$-algebra

A while ago I asked this question on mathstackexchange: Let $\mathscr{C}\subset \mathscr{P}(\Omega)$ be a class of subsets of a nonempty set $\Omega$ containing $\Omega$ and $\varnothing$. Define $\...
0
votes
0answers
85 views

Can this theory that internalize sets from external functions be consistent?

I want to know if the following theory stand a chance of being consistent? $Language:$ Mono-sorted first order predicate logic + primitives of equality $``="$ and class membership $``\in"$: Define: $...
6
votes
0answers
253 views

“Relative plausibility” of some infinitary theories

We work in $\mathsf{ZFC+V=L}$. Define a plausible theory to be a theory $T\subseteq\mathcal{L}_{\omega_1,\omega}$ in an $\omega_1$-finite language which is $\omega_1$-c.e. and $\omega_1$-finitely ...
3
votes
1answer
207 views

Candidate “AEC-yielding” fragments of bad logics

Previously asked and bountied on MSE without success: Given a logic $\mathcal{L}$ and a signature $\Sigma$, let the $\Sigma$-system of $\mathcal{L}$ be the pair $Sys_\Sigma(\mathcal{L})=(Struc(\Sigma),...
11
votes
1answer
288 views

Coding the universe into a real over better core models

One of the most incredible results in modern set theory, due to Jensen, is that given any model of $\sf ZFC$, there is a class forcing which adds a real number $r$ and in the extension $V=L[r]$. ...

1
2 3 4 5
84