Questions tagged [set-theory]

This tag is for set theory topics typically studied at the advanced undergraduate or graduate level. These include cofinality, axioms of ZFC, axiom of choice, forcing, set-theoretic independence, large cardinals, models of set theory, ultrafilters, ultrapowers, constructible universe, inner model theory, definability, infinite combinatorics, transfinite hierarchies; etc. More elementary questions should use the "elementary-set-theory" tag instead.

Filter by
Sorted by
Tagged with
2 votes
3 answers
37 views

If $A\subseteq B$, $B-A$ is infinite, A is countable, then $B-A\sim B$

Question is as stated in the title. Here $\sim$ means "as numerous as", which is a stronger condition compare to the just being "coutable/uncountable", i.e. different uncountable ...
  • 99
1 vote
1 answer
34 views

non-wellordered linear order that doesn't contain a copy of $\omega^*$ in ZF?

Obviously a wellorder cannot contain a copy of $\omega^*$ (the dual order of $\omega$), and this can be proven in ZF. In ZFC, it is easy to prove any linear order which is not a wellorder does contain ...
  • 378
-3 votes
0 answers
56 views

What is cardinality of $\mathbb{R}^{\mathbb{R}}$? [duplicate]

What is cardinality of $\mathbb{R}^{\mathbb{R}}$ ? I think it is $\aleph_1$ or is it just continuum? And what is the argumentation for it?
  • 21
0 votes
1 answer
72 views

Find all positive numbers $m$ and $n$ to satisfy properties

Find all positive integers $m$ and $n$ such that there exists finite sets of integers $X$ and $Y$ where, for every $x\in X$, $x+m \in Y$, and for every $x\in Y$, $x^2 - n \in X$. Currently, I have ...
3 votes
1 answer
78 views

Cantor's Diagonalization Process(CDP) and North-east to South-west Diagonalization Process(NSDP)

While looking at the function $f:\mathbb{N}\rightarrow \mathbb{N} \times \mathbb{N}$, I accidentally made an inversion in my labelling for $f(x)$ What I mean is, we go with a zig-zag path in CDP(...
0 votes
4 answers
48 views

Show $f^n=\mathrm{id}_A$ for some $n$ where $A$ is a finite set and $f : A \to A$ is a bijection

Let $A$ be a finite set and let $f: A \to A$ be a bijection. Show that $f^n=\mathrm{id}_A$ for some $n > 0$. I don't really understand how to prove it. And what does the notation $\mathrm{id}_A$ ...
  • 1
0 votes
1 answer
27 views

Prove that A\(A\B) is a subset of B for all subsets A and B of x

Let X be a set. For subsets C and D of X, we define C\D = { $x\in X$ : $x\in C$ but $x \notin D$ } Prove that A(A\B) is a subset of B for all subsets A and B of X. My try: x∈A(A\B)is equivalent to 𝑥 ∈...
  • 11
0 votes
0 answers
82 views

Questions about uncountable logics?

First of all, I would like to say that I've only recently started researching infinitary logics. I have read some segments of Barwise - related papers on the topic, and I could not find anything ...
  • 21
2 votes
1 answer
58 views

cardinals such that $\alpha < \alpha ^ \beta$

Let $F$ be a (class) function that assigns at each cardinal $\alpha$ the minimum cardinal $\beta$ such that $\alpha < \alpha ^ \beta$. I have to prove that $\beta \in \text{Im}(F)$ iff $\beta$ is ...
-1 votes
1 answer
92 views

Is it possible to define powersets without first defining the subset relation?

This ties back to a previous question I asked, which was about the notion of "to define $X$, you must first define $Y$". The current question is about a specific application of that notion. ...
  • 16.5k
0 votes
0 answers
74 views

Does the Pigeonhole Principle apply for sets of Infinity?

I once heard as a kid that any random assortment of letters is a name for some number. The thinking there was because there are infinite numbers, any random unnamed number would be labeled by an ...
  • 109
2 votes
1 answer
67 views

Proving that product of two-point sets is compact

I am reading Jech's Axiom of Choice, and I want to prove: For a non-empty set $I$, if $\{0,1\}^I$, the generalized Cantor space, is non-empty compact, then $\prod_{i\in I}A_i$ where $|A_i|=2$ for all ...
2 votes
0 answers
38 views

Problems with the exact formal definition of the Brauer group of a field [duplicate]

My question is not about the algebra of this thing, but related to formal set theory. I think that usually one will read that the Brauer group of the field K is made of equivalence classes of algebras ...
0 votes
0 answers
85 views

Square principle and continuum hypothesis

I know that the Jensen $\diamondsuit$-principle implies tha continuum hypothesis, but the $\square_{\omega_1}$ implies the continuum hypothesis? Searching about these principles I found the $\clubsuit$...
3 votes
1 answer
134 views

"Infinitely deep" sets

In the Von Neumann Universe, a generation such as $V_{\omega+\omega}$ seems to occur "after" applying the power set operation infinitely many times, so intuitively it feels like there must ...
4 votes
1 answer
72 views

How large is the supremum of all countable ordinals that have absolute definitions?

This answer contains the following statement: it's easy to check that $\omega^2$, $\omega^\omega$, $\epsilon_0$, and even "big" countable ordinals like $\omega_1^{CK}$ (= the first "...
12 votes
0 answers
129 views
+100

When does $|X^n|\leq |k^X|$ without the axiom of Choice?

We're working in $\sf{ZF}$ set theory, we assume $n$ is a finite cardinal, and the set $X$ is not finite. My question is: what's the smallest cardinal $k$ for which $\sf{ZF}$ proves $|X^n| \leq |k^X|$?...
0 votes
1 answer
66 views

$(\kappa \times 2,<_{lex}) \cong (\kappa,\in )$ for cardinal numbes $\kappa$.

A cardinal number $\alpha$ is a ordinal number such that $\forall \beta < \alpha : \beta \not\approx \alpha$. Now I want to show that for a cardinal number $\kappa$ the set $\kappa \times 2$ with ...
  • 921
0 votes
1 answer
75 views

Is this an example of an unprovably true statement in set theory? (A Corollary to the axiom schema of separation)

In ZFC, the axiom of separation is given as follows. Let $\phi(x, w_1,\ldots, w_n)$ be a wff formula in FOL, for free variables $w_1,\ldots,w_n$. Then, $$\forall w_1,\ldots,w_n\forall A \exists B\...
2 votes
2 answers
79 views

Sets with same members are member of same sets? Seeking deeper insights on link between extensionality and set equality, with or without FOL equality.

I have a question on the close links between extensionality and set equality in ZFC, with or without first order logic (FOL) equality as a primitive inherited by ZFC. The former seems clear and is ...
-5 votes
0 answers
55 views

Find finite sets with the following properties [closed]

Whenever x is in A, x + 1 is in B Whenever x is in B, $x^2 -4 is in Find all non-empty finite sets of integers A and B with the above properties
1 vote
1 answer
54 views

An infinite quantity divided up into infinite number of boxes?

I'm not sure how to phrase this in a proper set theory setting but let's say that one has a quantity which is infinitely large and then divides the quantity up so that it goes into a collection of ...
  • 1,158
0 votes
1 answer
88 views

In what sense, precisely, are free ultrafilters "not definable"?

Note: The following attempted summary consists of follow-up questions to this answer by Asaf Karagila to a related question on MathOverflow. These questions are too long for a comment on that answer, ...
0 votes
0 answers
31 views

What do you call a set that has recurring elements of another set?

Example: A = {1,2,3,4} B = {1,1,1,3,4,4} B contains some (or all) elements of A, some (or all) of which are recurring. What do you call this relationship and what is its mathematical notation?
  • 1
-2 votes
0 answers
57 views

how to prove that the cardinality of [0,1] is greater than Q

To prove that lexicographic preferences cannot be represented by utility functions, I was taught to prove that [0,1] cardinality is greater than Q. However, I cannot logically reason why that would be ...
  • 1
1 vote
1 answer
28 views

Cardinal inequality question used in proof of Silver's theorem [duplicate]

The cardinal inequality question that I would like to get some help about is a crucial inequality used in the proof of Lemma 8.14 (using Lemma 8.15) in Jech. If we assume $\aleph_\alpha^{\aleph_1}<\...
-5 votes
2 answers
104 views

Can the Continuum Hypothesis be proved using this tree argument?

See this continuum hypothesis proof on google drive: https://drive.google.com/file/d/17RNFPj2bzq-YDk_QpDuJuGDn6jw70ICT/view?usp=share_link. Briefly, assuming the continuum hypothesis false $\omega_2$ ...
4 votes
1 answer
64 views

Does the axiom of choice holds in $L(\mathcal{P}(\lambda))$?

Cantor's Attic claimed the following: However, Shelah proved that if λ is a strong limit cardinal of uncountable cofinality then $L(\mathcal{P}(\lambda))$ is a model of AC. If that's because there ...
0 votes
1 answer
82 views

Proposition: The union of two finite sets is finite. (proving without induction)

Is my proof correct? Notations: $\mathbb{N}$:=$\{1,2,3,.. \}$ = The set of all natural numbers. $J_q$:=$\{ y : 1\leq y \leq q, \text{ for some } q \in \mathbb{N}\}$ = The set of first $q$ natural ...
2 votes
2 answers
102 views

How to derive a function that maps a list to its possible "bracketings"? Recursion?

Let $[n] = \{m \in \mathbb{N}: m < n\}$. Suppose $\Sigma$ is a set and $\Sigma^*$ is the set of sequences on $\Sigma$. That is $\sigma \in \Sigma^*$ means there exists $n\in \mathbb{N}$ such that $\...
  • 1,172
1 vote
0 answers
55 views

G separable group, $\aleph_0 \leq \tau$. What is $l(X)$ and $\omega l(X) (\leq \tau)$? where $X \subseteq G$. And what is $\chi (G)$ (cardinal)?

Happy Chinese new year! I was reading (and translating) a Russian article "On the topological groups close to being Lindelöf". Where it is assumed G is a separable group and $\tau \geq \...
0 votes
1 answer
18 views

Barwise exercise: nonprojectibles are recursively Mahlo

In Barwise's Admissible Sets and Structures, there's an exercise to prove that every nonprojectible ordinal is recursively Mahlo. $\alpha$ is recursively Mahlo if every $\alpha$-recursive function $f:\...
  • 624
1 vote
1 answer
47 views

Cardinal inequality question used in Silver's theorem proof

In Jech's Set Theory, Theorem 8.13 states: If the Singular Cardinals Hypothesis holds for all singular cardinals with cofinality $\omega$, then it holds for all singular cardinals. And Lemma 8.14 ...
-1 votes
0 answers
24 views

Equipotent set and uncountably infinite set [duplicate]

All countably infinite sets are equipotent to each other (let $A$ denote such a set, we have: $A \approx \mathbb{N}$). My question is, can we make a similar statement for uncountably infinite sets ...
  • 115
1 vote
1 answer
31 views

Proof verification: Unique smallest topology on family of topologies containing all other topologies.

I have been trying to solve the following problem: Let $(T_\alpha)$ be a family of topologies on X. Show that there is a unique smallest topology on X containing all the topologies $T_\alpha$. The ...
  • 435
6 votes
1 answer
71 views

What's the groupification of the cardinal numbers (without using AC)?

The set-theoretic cardinal numbers form an abelian monoid under addition (ignoring size problems). Under the axiom of choice, given two cardinal numbers $c$ and $d$, there exists a cardinal number $e$ ...
  • 8,031
1 vote
1 answer
46 views

What types of $\varphi(x)$ would satisfy the axiom of Regularity

I just read in Bell Set Theory that the axiom of regularity can be written differently from the usual way as : $$ \forall x [ (\forall y \in x \text{ } \varphi(y)) \implies \varphi (x)] \implies \...
0 votes
0 answers
18 views

Modifying the axiom of reducibility in Friedman's K(W)

Let RED2 be the axiom schema $$\forall \bar{x} {\in} U (\phi \to \exists u {\in} U \phi[U := u])$$ where $\phi$ is a formula with free variables among $\bar{x}$. In Friedman's K(W), how does replacing ...
  • 5,537
-4 votes
1 answer
52 views

In the ZFC Set Theory. In the Axiom of Infinity, Why the emptyset must be an element of the set? What's the point of that? [closed]

$$\exists S(\emptyset\in S\land \forall y\in S((y\cup\{y\})\in S))$$ $$\exists S(\forall y\in S((y\cup\{y\})\in S))$$ Why must need the condition $\emptyset\in S$?
  • 1
-1 votes
1 answer
39 views

Proving that $\in_\alpha$ is transitive [closed]

In a proof my teacher used the following result without proving it: Let $\alpha$ be an ordinal and let $\in_\alpha \subseteq \alpha\times \alpha$ be a relation on $\alpha$ defined as: $$x\in_\alpha y\...
0 votes
1 answer
48 views

A generalization of Mostowski absoluteness theorem

Studying descriptive set theory, a found the Mostowski absoluteness theorem: if $\phi$ is $\Delta_{1}$, then $\forall x\in \omega^{\omega} \phi(x)$ is absolute between $V$ and $L$. I notice that $\...
-2 votes
1 answer
75 views

the strength of the axiom of choice used in forcing

I believe that Shelah's model gives a ZFC theorem of relative consistency results: $ZFC \vdash Con(ZFC + \text{there is a strongly inaccessible cardinal})\rightarrow Con(ZF+DC+ \text{all sets are ...
  • 29
1 vote
1 answer
58 views

after infinitely many row operations, the solution space stays the same?

Assume there is an $I\times J$ matrix $A$ with infinitely many rows ($I$ is an infinite set) and each row vector has finite support. Assume we are doing elementary row operations on the row vectors of ...
  • 1,685
0 votes
2 answers
83 views

Does replacement hold for $\omega_1$

I'm trying to decide which ZFC axioms hold for $\omega_1$, the first uncountable ordinal. I dont think replacement holds, and for that I'm considering the following function: $f(x)=|\mathscr{P}(x)|$, ...
1 vote
1 answer
37 views

$\mathcal{P}(\omega) \cap L \subseteq L_{\omega_1}$

I read in a question on here, that $\mathcal{P}(\omega) \cap L \subseteq L_{\omega_1}$. With replacement, $\mathcal{P}(\omega) \cap L$ has to be definable after some $\gamma$ because for all $x \in L$ ...
3 votes
1 answer
107 views

Is the dimension of the dual space independent of ZFC?

A popular MathOverflow answer (https://mathoverflow.net/a/13372) by Andrea Ferretti showed that for any infinite dimensional vector space $V$ over a field $F$, the dimension of the dual space $V'$ is ...
  • 378
1 vote
1 answer
61 views

Axiom of foundation implies that bottomless sets are empty?

In the notes that I am using to study Set Theory, the Axiom of Foundation is presented as follows: Axiom of Foundation: $$\forall x ( \exists y (y \in x) \rightarrow \exists y ((y \in x) \land \...
  • 2,393
3 votes
1 answer
78 views

Is this the Axiom of Infinity?

While studying elementary Set Theory, I came across the Axiom of Infinity. This comes before the section on ZFC, so I'm not convinced that it is necessarily the same as the typical definition. My ...
  • 2,393
2 votes
2 answers
47 views

Show that if $\delta$ is a ordinal number then $\bigcup{\delta} \neq \delta \iff \exists \gamma \in \mbox{Ord} : \gamma + 1 = \delta$.

An ordinal number $A$ is a pair $(A,<)$ with a well-ordering $<$ such that $\forall a \in A$ we have $a = A_a = \lbrace x \in A | x < a \rbrace$. Now I want to show that for an ordinal number ...
  • 921
3 votes
1 answer
214 views

How many axioms are in ZFC, and is ZFC a decidable language?

I am reading Jech's book Set Theory and he lists 9 "axioms": Extensionality Pairing Schema of Separation Union Power Set Infinity Schema of Replacement Regularity Choice Two of these are ...
  • 4,937

1
2 3 4 5
197