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 ...

learn more… | top users | synonyms

0
votes
2answers
459 views

How far do known ordinal notations span?

What is the largest known ordinal number $\alpha$ such that a uniform notation scheme has been developed for all ordinals up to $\alpha$ (there should be no "gaps" in what ordinals are representable), ...
2
votes
1answer
176 views

Function $f\colon 2^{\mathbb{N}}\to 2^{\mathbb{N}}$ preserving intersections and mapping sets to sets which differs only by finite number of elements

Define on $2^{\mathbb{N}}$ equivalence relation $$ X\sim Y\Leftrightarrow \text{Card}((X\setminus Y)\cup(Y\setminus X))<\aleph_0 $$ Is there exist a function $f\colon 2^{\mathbb{N}}\to ...
8
votes
1answer
432 views

For every $n < \omega$, $\aleph_n^{\aleph_0} = \max(\aleph_n,\aleph_0^{\aleph_0})$

I have proved that if $\aleph_n \leq \aleph_0^{\aleph_0}$, then $\aleph_n^{\aleph_0} \leq \max(\aleph_n,\aleph_0^{\aleph_0})$. Clearly $\aleph_n \leq \aleph_n^{\aleph_0}$ and $\aleph_0^{\aleph_0} \leq ...
2
votes
4answers
284 views

Union of Uncountably Infinite Sets

How does one notationally describe the set which is the union of uncountably many other sets. For instance, for each x such that a < x < b, where a and b are real numbers, if there is assigned ...
1
vote
0answers
82 views

What is the name of this equivalence relation?

Given any sets $X \subseteq Y$, the relation given by: $$1_Y \; \cup \; (X \times X) \;\; \subseteq Y \times Y$$ (where $1_Y = \{ (y, y): y \in Y \}$ ) is an equivalence relation. Is there a name ...
2
votes
2answers
1k views

A proper formal definition of the Ordinal numbers?

Maybe I'm just being a bit stupid with where I'm searching here, but I can't actually find a proper definition of these things wherever I look, books or online. The definition I find most is that it's ...
15
votes
1answer
895 views

Proofs given in undergrad degree that need Continuum hypothesis?

Or alternative you need to assume CH is false. I know several proofs that use axiom of choice. Heine Borel theorem is the best example I can think off. Zorns lemma is heavily used in the non ...
11
votes
2answers
923 views

Is the axiom of universes 'harmless'?

Usually when you start studying category theory you see the usual definition: a category consists of a class $Ob(\mathcal{C})$ of objects, etc. If you take ZFC to be your system of axioms, then a ...
5
votes
2answers
584 views

Countable or uncountable set 8 signs

Let S be a set of pairwise disjoint 8-like symbols on the plane. (The 8s may be inside each other as well) Prove that S is at most countable. Now I know you can "map" a set of disjoint intervals in R ...
9
votes
1answer
590 views

Surreal numbers without the axiom of infinity

Let $ZF^\times$ denote the set of axioms of Zermelo-Fraenkel set theory without the axiom of infinity. The set $V_\omega$ of all hereditarily finite sets is a model of $ZF^\times$, and ...
1
vote
1answer
113 views

Another question on saturated models of ZFC

Let $M$ be a saturated model of ZFC and let $\kappa$ be any cardinal in $M$. Now let $$\begin{align*} p_\kappa(f) &= \{ “f \text{ 1-1 function”} \wedge \operatorname{dom}(f) \subseteq \omega ...
6
votes
1answer
248 views

Probabilistic proof of existence of an integer

The prime number theorem (PNT) says that an integer $n$ is prime with probability $\frac{1}{\ln n}$. Using only PNT, it's conceivable that each integer upto $10^{10^{10}}$ is non-prime. However using ...
3
votes
1answer
326 views

Properties of computable numbers

If we enumerate* all the computable numbers, those for which there exist a turing machine that outputs its digits to arbitrary precision. What is known about the asymptotic density of rationals, ...
14
votes
1answer
790 views

Is it true that a connected graph has a spanning tree, if the graph has uncountably many vertices?

I found a proof that every connected graph (possibly infinite) has a spanning tree in Diestel's Graph Theory (Fourth Edition), Ch. 8 that uses Zorn's Lemma, but at a crucial step it seems to be ...
1
vote
1answer
313 views

iterate random forcing

I am studying Kunen's article Random and Cohen forcing [1], and I meet a problem. On page 904, Theorem 3.13 states that if $M$ is a countable transitive model of ZFC, $I,J,K \in M$ such that $I$ is a ...
10
votes
3answers
1k views

Axiom of choice, non-measurable sets, countable unions

I have been looking through several mathoverflow posts, especially these ones http://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice , ...
1
vote
0answers
214 views

Is there a ccc but not separable space $X$ with a zeroset-diagonal, that isn't submetrizable?

Is there a ccc but not separable space $X$ with a zeroset-diagonal, that isn't submetrizable? separable = $X$ has a countable dense subset. A space $X$ has a zeroset-diagonal when there is a ...
13
votes
2answers
326 views

Does $2^X \cong 2^Y$ imply $X \cong Y$ without assuming the axiom of choice?

A friend of mine told me that $X \cong Y \Rightarrow 2^X \cong 2^Y$ ($X$ and $Y$ being sets), which is very easy to prove, but he was wondering about the converse in ZF, i.e., can one take logarithms? ...
7
votes
1answer
349 views

Can forcing push the continuum above a weakly inacessible cardinal?

There is a famous quote of Paul Cohen which reads $\lt\lt$ A point of view which the author feels may eventually come to be accepted is that the continuum hypothesis is obviously false ... The ...
7
votes
2answers
396 views

Implications of continuum hypothesis and consistency of ZFC

I've been a bit confused whilst doing some reading. I think the confusion arises because I am trying to read Wikipedia on topics without being able to work along. Anyway, I have read that, of course, ...
7
votes
4answers
598 views

Fractional cardinalities of sets

Is there any extension of the usual notion of cardinalities of sets such that there is some sets with fractional cardinalities such as 5/2, ie a set with 2.5 elements, what would be an example of such ...
1
vote
3answers
202 views

Equivalence relations and bijections without ordered pairs

Is it correct that — opposed to general relations and functions — equivalence relations and bijective functions can be defined without reference to ordered pairs? Especially, do the ...
2
votes
1answer
99 views

Permutation without fixed finite set

Let $X$ be an arbitrary infinite set, can we always find a bijective map $T: X\rightarrow X$ such that for any finite (nonempty) subset $F\subset X$, $T(F)\neq F$ ? This question is related to another ...
4
votes
1answer
152 views

CH for tilings of the plane

Given any set of jordan curves that can tile the plane, how to prove that the number of possible tilings using tiles from this set is either in bijection with the real numbers or a (possibly infinite) ...
2
votes
2answers
358 views

Confused about Wikipedia definition of NP

I've been checking my understanding of the definitions of NP and NP-complete and I am confused by some of the definitions given on Wikipedia; for example, the article about NP-complete describes NP ...
3
votes
1answer
174 views

Can we collapse $\omega_1$ without adding a dominating real?

The question is exactly that in the title: is there a forcing which collapses $\omega_1$ to $\omega$ but does not add a dominating real ("real" here meaning "element of $\omega^\omega$")? It seems ...
23
votes
1answer
4k views

Cardinality of Borel sigma algebra

It seems it's well known that if a sigma algebra is generated by countably many sets, then the cardinality of it is either finite or $c$ (the cardinality of continuum). But it seems hard to prove it, ...
8
votes
1answer
755 views

Uncountable Sets that can not be expressed as a disjoint union of two Uncountable sets

"There does not exist an uncountable subset of the real numbers which can not be expressed as the union of two uncountable sets which are disjoint from one another" is obviously true assuming choice. ...
10
votes
3answers
1k views

Is the class of cardinals totally ordered?

In a Wikipedia article http://en.wikipedia.org/wiki/Aleph_number#Aleph-one I encountered the following sentence: "If the axiom of choice (AC) is used, it can be proved that the class of cardinal ...
9
votes
2answers
1k views

Set theoretic construction of the natural numbers

I'm trying to tie some loose ends here. My lecturer didn't bother to go into details, so I have to work it out myself. I usually hate to be pedantic, but these questions have been bugging me for a ...
1
vote
2answers
604 views

NFA to DFA conversion, half the power set

Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
2
votes
1answer
124 views

Existence of compact Hausdorff topologies

Consider the following statement $(C_2)$: For every set $X$ there exists a compact Hausdorff topology on $X$. $C_2$ is a theorem of $ZFC$, because Choice gives us a bijection between any ...
5
votes
3answers
357 views

Using Axiom of Choice To Find Decreasing Sequences in Linear Orders

Suppose I have a set along with a relation which is a total order. The set has no minimum element. Now, I want to create an infinite decreasing sequence of elements in this set. For this I have to use ...
3
votes
1answer
128 views

Variant of the Lévy hierarchy on formulas

Consider the following variant of the Lévy hierarchy on formulas : let $\Phi$ be the set of all meaningful formulas on the alphabet $\in,=,\vee,\wedge,(,),\neg,\exists,\forall$ and a countable set of ...
2
votes
0answers
261 views

Point-set topology and set theory

In the standard second-order, but single-sorted setting of point-set topology one has a base set $X$ and the property of being open on its powerset $P$ obeying the usual axioms. Proofs in point-set ...
4
votes
2answers
155 views

Is $\operatorname{Hom}_A(M,N)$ a set without axiom of choice?

Let $M$ and $N$ be $A$-modules, $\operatorname{Hom}_A(M,N)$ the set of all $A$-module homomorphisms $M\rightarrow N$. $\operatorname{Hom}_A(M,N)$ can be viewed as a subset of the cartesian product ...
10
votes
1answer
770 views

Are there statements that are undecidable but not provably undecidable

This is a variant of Is there a statement whose undecidability is undecidable? and Can it be shown that ZFC has statements which cannot be proven to be independent, but are? (but is not asked or ...
11
votes
4answers
273 views

Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?

It is known that given an infinite poset, it always contains an infinite chain or antichain; moreover, there is a constructive proof that we can find a continuous chain in $P(\mathbb{N})$; so, in ...
5
votes
1answer
310 views

Can the power set be axiomatised?

I want to consider many-sorted first order logic with distinguished sorts $U$ and $P$. Can I state a (finite?) set of first order formulae such that any model $M = (D^U, D^P, I)$ interprets the sort ...
5
votes
3answers
504 views

Finite choice without AC

Can anyone explain how we choose one sock from each of finitely many pairs without the axiom of choice? I mean the following quote: To choose one sock from each of infinitely many pairs of socks ...
14
votes
2answers
559 views

Comparing countable models of ZFC

Let us consider the class $\cal C$ of countable models of ZFC. For ${\mathfrak A}=(A,{\in}_A)$ and ${\mathfrak B}=(B,{\in}_B)$ in $\cal C$ I say that ${\mathfrak A}<{\mathfrak B}$ iff there is a ...
2
votes
3answers
377 views

Truth Value of Theorems in Axiomatic Set Theory

I encountered set theory these past couple of days in discrete mathematics, and my professor was talking about the axiom of choice and ZFC. He said that depending on which axiom you started from, you ...
7
votes
4answers
684 views

Example of a model in set theory where the axiom of extensionality does not hold?

I recently started a course in set theory and it was said that a model of set theory consists of a nonempty collection $U$ of elements and a nonempty collection $E$ of ordered pairs $(u,v)$, the ...
2
votes
2answers
143 views

Undecidable countable structure built on decidable relation?

My question is, is there a relation $R$ on the integers that's decidable (i.e. the function ${\mathbb Z}^2 \to \lbrace \text{true},\text{false} \rbrace, \ (i,j) \mapsto i R j$ is computable) , but ...
4
votes
1answer
224 views

Equivalent formulations of Global Choice in NBG (without Foundation)

Recently I was looking for various formulations of strong Global Choice in NBG (not assuming Foundation, necessarily), apart from the existence of a well-ordering on the universe or the guarantee of a ...
2
votes
1answer
208 views

Alternate definition of ordinal sets

Going through some personal notes from several years ago I stumbled upon a loose thread which I obviously had not resolved at the time, and which I would like to lay to rest: Assuming some standard ...
1
vote
1answer
229 views

About a ordinal-based definition of fast-growing functions

I try to understand the Löb-Wainer-hierarchy and one definition just doesn't open. I hope someone could clarify this to me. A fundamental sequence to limit ordinal $\alpha$ is $\omega$-sequence ...
10
votes
3answers
698 views

Difference between undecidable statements in set-theory and number theory?

Do all statements about the integers have a definite truth value? For instance: Goodstein's theorem is clearly true, otherwise we could find a finite counterexample thus it would be possible to ...
2
votes
1answer
364 views

Is there an axiom scheme exhausting all types of Mahlo cardinals?

Is there an axiom scheme exhausting all types of Mahlo cardinals? Mahlo cardinals may be considered as the first stage in the following construction : let $C_{0,0}$ be the class of all inacessible ...
2
votes
2answers
198 views

Can a 1-1 function be implied from a two-way onto pair of functions?

In DC Proof I've defined equal cardinality to mean there are two onto functions $g:A\to B$ and $h:B\to A$. I want to prove this means there exists a function $f:A\to B$ that is both 1-1 and onto ...