Hot answers tagged

24

You said: I can't fathom why it implies an order to $x$ and $y$ It doesn't really. The $x$ and $y$ in the ordered pair $(x, y)$ don't really have an order. Who's to say that the $x$ is first and the $y$ is second? If you read right-to-left, you'd say that the $y$ was first and the $x$ was second. The important thing isn't which is first. The ...


10

This is a very natural question, even if a little subjective (due to the inherent subjectivity of what does it mean "weird"). But the answer is that the axiom of choice is not the cause of weirdness. The axiom of choice is just a tool with which we can prove there is some uniform "mess" throughout the universe of sets. But it really helps us to rein down ...


5

Just how you define order pairs concretely is an "implementation detail". Whichever definition you adopt just has to meet a basic requirement: from $\langle x, y \rangle$, you must be able to uniquely recover each of $x$ and $y$ with (preferably simple) functions $first(z)$ and $second(z)$. The Kuratowski construction meets this criterion. $first((x,y)) ...


4

There is no explicit example of a non-principal ultrafilter over the natural numbers without appealing to choice. We know this because there are models of $\sf ZF$ where every ultrafilter over the natural numbers is principal. In fact there are models where every ultrafilter over any set is principal. The proofs are quite technical and require ...


3

No, it is not provable. Quite contrary, it is provably false. More precisely: A cardinal $\kappa$ is worldy iff $V_{\kappa} \models \operatorname{ZFC}$. We can prove that the least worldly cardinal (if any exist) has cofinality $\omega$ and hence is far from being inaccessible.


3

By compactness, if $\phi$ have models of arbitrarily large finite cardinality, then $\phi$ has an infinite model, and by Lowenheim-Skolem (upward and downward) you can find models of $\phi$ of any cardinality $\kappa\geq \aleph_0$. So, one can restrict the question to $S\subseteq \mathbb{N}\setminus \{0\}$, but I have the feeling that is a complicated ...


3

It is not strictly true that mathematics turns out the same in both theories. For instance, since NF refutes Choice, and it's unclear if something like the Ultrafilter Lemma is consistent, the Completeness Theorem for first order logic is not known to be provable in NF or any of its extensions. There are categories $\mathcal{C},\mathcal{D}$ that are "small" ...


3

Yes, the point is that $W=X$. The key to that is the last part of the conclusion of the lemma: $F(W)\in W$, which is the same as $\sigma(X\setminus W)\in W$. If $X\setminus W$ is nonempty, then this contradicts $\sigma$ being a choice function, so the only way we can have $\sigma(X\setminus W)\in W$ is if $X\setminus W=\varnothing$, in which case ...


2

Hint The proof assume that $b \ne 1$ and we can consider the case that $b=b'_n=\sup B_n$. By the R-S Th there is an homomorphism $h: \textbf{B}\rightarrow \textbf{2}$ such that: $h(b'_n)=\sup h(B_n)$. But - see proof of R-S Th, page 29 - an homomorphism between boolean algebras maps $0$ onto $0$ and $1$ onto $1$. This means that, if $b'_n=b \ne 1$, also ...


2

The question is what do you mean by large cardinals and what do you mean by useful? For example, it is consistent that there exists a set $A$ such that the cofinite filter on $A$ is an ultrafilter. We can even show that such ultrafilter is closed under intersection of ordinal-indexed sequences (mainly because under this assumption every such sequence is ...


2

Really what you're being asked to prove is that the finite product of Dedekind finite sets is Dedekind finite again. With induction it is enough to show that the product of two Dedekind finite sets is Dedekind finite. So now suppose that $X$ and $Y$ are Dedekind finite. If $X\times Y$ is not Dedekind finite, then it has a countably infinite subset (recall ...


2

HINT: Show by induction on $\alpha$ that the preimage of a $\Sigma^0_\alpha$ set under a continuous function is again $\Sigma^0_\alpha$. This uses continuity trivially for the base case, and for the induction step the fact that preimage commutes with $\cap $ and $\cup$; note that this is false for image! Note that by contrast, $\{(x, x): (x, x)\in A\}$ is ...


2

This one's tricky - I was convinced there was an error for a minute! First, let me sketch why I thought it was c.c.c. It's a $\Delta$-system argument. Let's look at $\mathbb{P}_0$. Suppose there were an uncountable antichain $A=\{p_\eta: \eta\in\omega_1\}$. Then by the $\Delta$-system lemma, we can assume WLOG that $A$ is a $\Delta$-system with root $r$, ...


2

Here's a forcing argument (not how Kunen wants you to do it since forcing is covered in chapter 4): First, by throwing away all the rational intervals in which $f[\omega_1]$ is countable, we can choose $X \subseteq \omega_1$ such that $\omega_1 \setminus X$ is countable and for every $x \in f[X]$, $|[x, \infty) \cap f[X]| = \omega_1$. Let $Q_0 = \{p \in P_0 ...


2

Say you have the ordered pairs $(x,y),(a,b)$, i.e, $\{\{x\},\{x,y\}\}$, idem for the other. What do you do if I ask them if they're equal? You test equality as sets. It turns out that they're equal iff $x=a$ and $y=b$ (why?).


2

In the comments (but not in the question), you clarify that you want the ultrapower to have an increasing sequence of length $\kappa$, but no decreasing sequence of length $\kappa$. I don't know if this is possible (for a general ultrapower of a well-order), but I'll explain why it seems hard. The following theorem is from Keisler's paper Ultraproducts which ...


1

You may need additional free variables in applications. For example in order to define $$ a\cap b:=\{\,x\in a:x\in b\,\}$$ you would want $\varphi$ to be $w\in b$, where both $w$ and $b$ are free.


1

With regard to the $\exists w_1(w_1\in v \vee v=0)$ clause, it's important to keep in mind that Suppes allows non-sets (also called urelements) into the universe. Now imagine we omit this clause. As I mention in the comments, it means that there could be extensionally equivalent abstracts whose identity we would be unable to prove, such as $\{x\in A: x\neq ...


1

The problematic part is that if $\kappa$ is singular, there might not be any definable first-order function witnessing this. So the only way to find it is essentially to just take the entire power set of $V_\kappa$, and hope to find a short cofinal sequence. If, however, you replace the schema of Replacement by the second-order statement "For every function ...


1

To answer your first question, Define a function $f(n)$ such that $f(0)$ maps to the first of the three finalmost elements, $f(1)$ maps to the second, and $f(2)$ to the third. For each positive integer greater than 2, let $f(n)$ map 3 as the first element of the first group, 4 as the first element of the second, 5 as the second element of the first, and so ...


1

(c) $3,5,7,9,\dots$, $4,6,8,10,\dots$, $0,1,2$. $\omega + 1 \longleftrightarrow 1,2,3,4,\dots,0$. That's how all those sets are countable.


1

The other answers address your first question; let me tackle the second. Note that if $\alpha$ is countable, so is $\alpha+1$ (Hilbert's hotel). So $\omega_1$ (this is the standard notation for the supremum of the countable ordinals) can't be countable, since otherwise $\omega_1+1$ would also be countable and we would therefore have to have ...


1

In this case you don’t need the axiom of choice to get a choice function: just pick the smaller member of each pair. Various other choice functions are explicitly definable: we could just as well pick the larger member of each pair, for instance. Or we could pick the member that is divisible by $3$ if there is one, and the smaller one otherwise. In general ...


1

The axiom of choice asserts there exists one choice function. However, like the problem with many vermin and pests, we usually have that if there is one then there are many (unless, all sets are singletons). Specifically for sets of natural numbers you don't need the axiom of choice in order to prove that there are continuum many choice functions. But ...


1

The answer is no. First of all, $\sf BPIT$ is strictly stronger than "every set can be linearly ordered", it is even stronger than "every partial order can be extended to a linear order". Secondly, in the paper David Pincus, The dense linear ordering principle, J. Symbolic Logic 62 (1997), no. 2, 438--456. MR 1464107 the author proves that the ...



Only top voted, non community-wiki answers of a minimum length are eligible