New answers tagged

1 vote

Proving a set is a Borel Set

That set is neither closed nor open. On the other hand, if $n\in\Bbb N$ and$$A_n=\left\{(x,y,z)\in\Bbb R^3\,\middle|\,0<x<1+\frac1n,0<y^2+z^2<x+\frac1n\right\},$$then each $A_n$ is open ...
1 vote
Accepted

A confusion the definition of a function when proving split monic(split epic) implies injective (surjective)

Uniqueness of preimage matters in the first case, but not in the second. In the first case, you want to define $\psi$ so that $\psi(\phi(a)) = a$. If there were $a \ne a'$ such that $\phi(a) = \phi(a')...
  • 30.5k
3 votes

$ZF + AC_\omega$ prove the propositional compactness theorem for arbitrary languages

The answer to the first question is negative, even if you strengthen $AC_\omega$ to $DC$ (dependent choice). Solovay's model for "all sets of reals are Lebesgue measurable" gives a ...
0 votes
Accepted

ZFC and the Axiom of Choice.

I know I should have split this question, but since I have my solutions which were accepted by my teacher (less rigorously), I will end posting this as the full answer to the 5 questions. Let $S$ be ...
7 votes

The proof of the Keisler-Shelah theorem

I attended a course taught by Tom Scanlon in Spring 2015, in which we actually went through all the gory details of Keisler-Shelah in class (this is even more astonishing when you consider that the ...
3 votes

Senses in which ZFC consistency is or isn't provable

You mixed the "Confusing Point 2" and "An informal, 'mathematical' proof of the consistency of ZFC". The reduction of Con(ZFC) to a concrete Diophantine equation is not meant to ...
  • 9,001
6 votes
Accepted

Applying Martin's Axiom to Families of functions

One of the key points in using forcing axioms is identifying a suitable forcing notion, and a suitable collection of dense open sets. Here, the forcing notion is easy: Hechler reals. Namely, a forcing ...
  • 375k
3 votes

Does $\Sigma_1$-separation over $L_\alpha$ admissibility?

In fact we can get $\Sigma_1$-collection directly! The following argument is pulled from a set of handwritten notes by Ronald Jensen, which seems to be called "Admissible Sets". Jensen ...
  • 544
1 vote

Equivalence of two formulations of the axiom of infinity

This may be an alternative approach: Let $X=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\ldots\}$. Define recursively $$ f(x)=\begin{cases}\emptyset&\text{if }x\in X\setminus\...
1 vote

First-order formula of rational numbers

According to one common set of implementation choices: A set is inductive if it contains $\varnothing$ (which we denote by $0$) and is closed under the operation $S(x) = x\cup \{x\}$. A natural ...
2 votes

First-order formula of rational numbers

One common approach is to view rationals as equivalence classes of elements of $\{0,1\}\times\omega\times(\omega\setminus \{0\})$, where intuitively the triple $(i,a,b)$ represents the number $(-1)^i\...
2 votes
Accepted

Can ultrapowering add choice?

If $M^\mathcal{U} \models$ extensionality, then the answer is "no". I claim the following are equivalent: $M^\mathcal{U} \models$ extensionality $M \models$ "For all families $\{A_i\}_{...
  • 23.4k
7 votes
Accepted

Equivalence of two formulations of the axiom of infinity

This is not true. Consider the set $X=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\dots\}$. Let $M$ be the closure of $X\cup\{X\}$ under the operations of taking subsets, ...
1 vote
Accepted

confusion about models, the universe and inaccessible cardinals

An explanation for the comment thread, some of this is based on Carl Mummert's answer here. I argue that any discussion about "the universe of ZFC" is actually about $V$. When people say &...
  • 544
4 votes
Accepted

Is non-emptiness equivalent to an equation in ZFC?

Sure: the function $$f(x)=\begin{cases} x & \mbox{ if }x\not=\emptyset\\ \{x\} & \mbox{ if }x=\emptyset\\ \end{cases}$$ is definable in an obvious way, so we can add a symbol for it as an ...
7 votes

Why can't a class model serve as a witness of the consistency of a theory?

This is a very subtle point which requires careful understanding of precisely how the basic definitions and proofs about the satisfaction relation in a model work (and in particular, how recursion is ...
6 votes

Why can't a class model serve as a witness of the consistency of a theory?

The big issue with proper-class-sized structures is that they're too large in general to "use $\models$ properly." This is a bit subtle, so let's look at an example: Let's use a "...
0 votes

confusion about models, the universe and inaccessible cardinals

Two things: Some details on working in $V_k$: $k$ is not an actual object we have access to when working within $V_k$. In particular, how would we formalize "$k$ exists"? We could try doing ...
4 votes
Accepted

Why does this meta-theorem about relativization directly speak of the elements in the model rather than the constants available in the language?

The quantifiers in Proposition Scheme 6.1 are all ordinary quantifiers, not "meta-theoretic" quantifiers. The only "meta" quantifier here is over the formulas $\varphi$ (which is ...
3 votes
Accepted

Konig's tree lemma without using axiom of dependent choice

Your proof will not work, as said in the comments, since it is essentially assuming the existence of a branch. Indeed, it is consistent without the axiom of choice that there is a family of non-empty ...
  • 375k
0 votes
Accepted

Is every infinite countable limit ordinal of form $\beta+ \omega$?

Take α=ω·ω and note that for every x ∈ α, there exists y ∈ α such that x < y and the interval [x,y] is infinite. It is clear that this fails for β + ω (Take x = β, then for every y ∈ β+ω, [x,y] is ...
0 votes

Is every infinite countable limit ordinal of form $\beta+ \omega$?

If $\omega^2 = \beta + \omega$, then $\beta< \omega^2 = \{a\omega+b: a,b\in\omega\}$. But then $\beta = a\omega+b$ for some $a, b\in \omega$. Therefore $\beta+\omega = (a+1)\omega<\omega^2$. ...
  • 1,107
3 votes
Accepted

Is the comparison of well-orders theorem true for classes?

Your proof does not work in NBG. It does, however, go through in the stronger MK. It is valid to discuss, for each $x \in X$, the well-ordered class $X_{< x}$. However, this class could be proper; ...
  • 23.4k
1 vote
Accepted

Other important results of class/set distinction?

Cantor’s theorem which implies that there is no bijection between a set and it’s power set is false for the class of all sets. Another example is that if the class of all sets were a set then by Zorn’...
  • 4,133
5 votes

Where is choice used in "Every category monadic over Set is regular"

I will assume that you are treating $C$ as a regular category with the regular Grothendieck topology. Thus, preserving covers is equivalent to preserving regular epis. For question 1: Set has an ...
  • 23.4k
6 votes
Accepted

Where is choice used in "Every category monadic over Set is regular"

By the axiom of choice, every epimorphism in $\textbf{Set}$ is split. Any functor preserves split epimorphisms, hence every monad on $\textbf{Set}$ preserves regular epimorphisms. Thus the theorem ...
  • 83.7k
2 votes
Accepted

A few questions about class and set.

Yes. For example, consider the minimal model of ZFC (call it $X$). By the Lowenheim-Skolem theorem, $X$ is countable, which by replacement implies that $X$ is a set and not a proper class. Then, try ...
  • 544
2 votes
Accepted

Do indecomposable abelian groups of inacessible cardinal rank exist?

According to Theorem 2.1 of the following paper, there are indecomposable torsion-free abelian groups of any infinite cardinality. Shelah, Saharon, Infinite Abelian groups, Whitehead problem and some ...
4 votes
Accepted

Existence of a bijective choice function $f:\tau\rightarrow \mathbb{R}$

Here is a "back-and-forth" construction that uses AC. I assume there is a less wacky approach out there, but this is the first thing that comes to mind. Enumerate all reals as $\{r_\alpha: \...
2 votes
Accepted

In forcing, would a generic extension $M[G]$ also extend sentences satisfiable by $M$ that are not provable in ZF?

Certainly not, even if we don't change the language at all! In fact the whole utility of forcing (as Daniel Schepler points out below) is based on the fact that many things aren't "forcing-stable....
0 votes
Accepted

problem 3.48 of Enderton's "Elements of Set Theory"

Your answer and analysis is correct and shows that you have a good understanding of the definitions being used by the author in your textbook. In particular that of ordered pairs and set operations ...
  • 72.9k
0 votes

Cannot there be more Partitions or Equivalence Relations than the other?

In set theory, we say that two sets are of equal size if you can construct a bijection between them, i.e. if we can exactly match each element in one set with a unique element from the other and vice ...
  • 15.5k
2 votes

I dont understand induction on well-orders

First, your statement of the induction principle is wrong. It should be Suppose $<$ is a well-order on $A$. Suppose $\phi(x)$ is a formula such that for every $y\in A$, if $\phi(x)$ holds for all $...
  • 1,678
5 votes
Accepted

I dont understand induction on well-orders

Line your classmates and look for the first one that isn't wearing a green shirt. Say it was the fifth person in the line. Do you see why the first four people were wearing a green shirt? Now, suppose ...
  • 375k
4 votes

Definition of a set: „conceived as a whole“

The idea is that if you think about infinity in a pre-19th century mindset, you most likely think of it as somehow a progression that is unbounded. As though you are computing something, and the ...
  • 375k
1 vote
Accepted

Equivalent definitions of Dedekind-finite sets

The two definitions are certainly not equivalent. Suppose that $A$ is any infinite Dedekind-finite set. Let $S$ be the set of finite injective sequences from $A$, namely, all the injective functions ...
  • 375k
0 votes

Preservation of cardinality under ordinal exponentiation.

Here is a proof that follows Kunen's hint. Let $\max\{|\alpha|,|\beta|\}=\kappa$. Fix ordinal $\delta$, s.t. $\delta>\alpha$, $\delta>\beta$ and $|\delta|=\kappa$ (e.g. $\delta=\max\{\alpha,\...
  • 173
3 votes

Failing to understand set-theoretic issue in Borceux

I think Borceux's argument is wrong. Recall Comprehension scheme 1.1.8 from Volume I: "If $\phi(x_1,...,x_n)$ is a formula where quantification just occurs on set variables, there exists a class $...
1 vote
Accepted

Can someone explain the axiom of separation for ZF Set Theory

I'll answer them in reverse order. What is an axiom schema? Well, a single axiom is a single property that we would like our universe of sets to have. For example, the axiom of infinity asserts that ...
-1 votes

Is it possible to prove that every discrete topology is an order topology without the axiom of choice?

Answer may depend of your definition of order topology. Definition variant 1: For partially ordered set $(X, \leq)$ we define order topology as one generated by subbase consisting of intervals, that ...
  • 1,090
6 votes

Is it possible to prove that every discrete topology is an order topology without the axiom of choice?

If I’m reading your proof right, I don’t think it’s correct. You seem to be saying to “shift everything up by one”, a starting from each limit ordinal. Inasmuch as this mental operation makes sense, ...
1 vote
Accepted

Find the boundary of the set of a circle and $y\leq x$

The boundary of your given set is isotopic to a 180 degree arc with a ray connecting the endpoints. Your potential answer $B$ counts the points in the $(-x, +y)$ quadrant of the circle - but those ...
1 vote
Accepted

Are there any relatively consistent proofs based on forcing that cannot be proven outside of the AC?

Sometimes, but not quite. You don't need to assume $\sf AC$ in order to get forcing to work. You also don't need to assume $\sf AC$ in the meta-theory order to get forcing to work over countable ...
  • 375k
0 votes

how to proof if A × B ≠∅ then range(A × B)=B

ran($A \times B$) is by definition contained in $B$. So you need to show that $B$ is contained in ran($A \times B$). Well, let $y \in B$, and $x \in A$ be arbitrary. Notice that an $x$ does exist in $...
0 votes

Is $\{z: (z = u \cup v) \wedge (u \in U) \wedge (v \in V) \}$ a set?

I believe I have found a way to prove what I intended via the ZFC axioms I'm allowed to use: Using the axiom of union $\cup U$ and $\cup V$ are both sets (because $U$ and $V$ are sets by hypothesis) ...
  • 281
1 vote

if $\omega^{\alpha} =A \cup B$ then $A$ or $B$ has order type $\omega^{\alpha}$

Let us consider the case $\alpha=3$ and assume that our theorem holds for $\alpha=1,2$. You can generalize my argument to any successor cases. Let $\omega^3=A\cup B$. For $X\subseteq \omega^3$ define $...
  • 25.9k
2 votes

For $A_1, A_2 \in {^\omega 2}$, if $ \langle A_1, A_2 \rangle$ is Cohen generic over $N$ then so is $\langle A_1'', A_2 \rangle$.

The map that transforms $(A,B)$ into $(A'',B)$ is a homeomorphism of $2^\omega\times2^\omega$ that exists in $N$. In particular, the preimage of a meager set is meager. If $(A_1'', A_2)$ is not Cohen ...
3 votes
Accepted

Can the plane be covered by fewer than continuum many injective curves?

It's consistent with ZFC that $\operatorname{cov}(\mathcal B)\lt2^{\aleph_0}$, i.e., $\mathbb R$ is the union of fewer than continuum many meager sets. Suppose $\mathbb R$ is the union of $\kappa$ ...
  • 71.4k
3 votes

A element can be a set?

The empty set is a subset of itself. Indeed, the empty set is a subset of any set. This is proven as follows. Given a set $X$, suppose that $\varnothing\not\subset X$. This means that exists some ...

Top 50 recent answers are included