/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 12 Assume the universe satisfies th... [FREE SOLUTION] | 91Ó°ÊÓ

91Ó°ÊÓ

Assume the universe satisfies the axiom of choice. We are given an infinite cardinal \(\lambda\), an ordinal \(\alpha\), and a family of sets \(\left(X_{\beta}\right)_{b \in \alpha}\) indexed by \(\alpha\) that satisfies $$ \text { for every } \beta \in \alpha, \quad \operatorname{card}\left(X_{\beta}\right)<\lambda, $$ and for every \(\beta \in \alpha\) and \(\gamma \in \alpha\), if \(\beta<\gamma, X_{\beta} \subseteq X_{\gamma} .\) Show that card \(\left(\bigcup_{\beta \in \alpha} X_{\beta}\right) \leq \lambda .\)

Short Answer

Expert verified
By proving the base case, making an induction assumption, and then proving the statement true for \(\beta+1\) and limit ordinals, we have verified that card \(\left(\bigcup_{\beta \in \alpha} X_{\beta}\right) \leq \lambda .\)

Step by step solution

01

Prove the base case

We begin with the case when \(\alpha\) is the minimal ordinal, namely 0, so the union is empty. An empty set has a card of 0, and since \(0 \leq \lambda\), the base case holds.
02

Assume the statement is true for an arbitrary \(\beta\)

Assume that the union of the family \(X_{\gamma}\) for \(\gamma < \beta\) has a cardinality less than or equal to \(\lambda\). This is our induction hypothesis.
03

Prove the statement is true for \(\beta+1\)

Consider the case of \(\beta + 1\). We know that \(X_{\beta} \subseteq X_{\beta+1}\), so the card of the union of \(X_{\gamma}\) for \(\gamma < \(\beta + 1\)\) would be less than or equal to \(\lambda\). This fulfills the conditions of transfinite induction.
04

Prove for limit ordinals

We now consider limit ordinals, which are not of the form \(\beta + 1\). A limit ordinal \(\alpha\) can be seen as the union of all \(X_{\beta}\) for \(\gamma < \beta\). By the axiom of choice and the fact that each \(X_{\beta}\) has card less than \(\lambda\), it follows that the union of all such sets also has card less than or equal to \(\lambda\). This completes the proof by transfinite induction.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91Ó°ÊÓ!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Transfinite Induction
Transfinite induction is an extension of the familiar mathematical induction used for proving statements about numbers. It applies to ordinal numbers, which extend beyond finite numbers to account for different sizes of infinity. This form of induction works in stages:

1. **Base Case**: Start with the smallest ordinal, often 0. In our exercise, the proof begins with an empty union, where the cardinality is 0. This trivially satisfies the condition since 0 is less than any infinite cardinal (\(\lambda\)).
2. **Successor Case**: Assume the statement is true for some ordinal \(\beta\). Show it also holds for \(\beta + 1\), the next ordinal. Here, we ensure that if \(X_{\beta}\) is true, then so is every set formed with one more step.
3. **Limit Case**: Prove the statement for limit ordinals, which are not immediately after any single ordinal. Use existing truth from all smaller ordinals to establish the condition holds for the limit. The condition in our problem requires handling more complex infinite unions while leveraging the axiom of choice.

This technique is powerful for tackling problems involving infinite processes or structures. It systematically ensures a property holds for all infinite levels covered by the ordinal numbers.
Infinite Cardinality
Infinite cardinality is central to exploring sets that can be infinitely large. Standard cardinal numbers, like \(1, 2, 3\), measure finite sets. However, when dealing with infinite sets, cardinality expresses different "sizes" or "types" of infinity.

In the context of our exercise, each set \(X_{\beta}\) has a cardinality less than a specified infinite cardinal \(\lambda\).
When these are structured as increasing subsets, the union's cardinality remains controlled under \(\lambda\). The axiom of choice supports picking elements across infinite collections which helps in proving results that seem intuitive at finite levels.

Understanding infinite cardinality reveals how sets can be compared even when they stretch beyond numerical limits. It uncovers interesting insights about mathematical infinity and provides pathways to comprehend numbers that exceed the familiar realm.
Ordinal Numbers
Ordinal numbers extend beyond natural numbers to index sets and sequences in a way that captures both size and order. They are essential in understanding structured progressions or hierarchies, especially in infinite contexts.

The exercise provides a sequence \((X_{\beta})\) indexed by ordinals, ensuring order in which each \(X_{\beta} \subseteq X_{\gamma}\) for \(\beta < \gamma\). This naturally respects the flow from one stage to the next, like stepping through transitions beyond finite bounds.
  • **Minimal Ordinals**: The smallest, often considered to be 0.
  • **Successor Ordinals**: The next step from an ordinal, expressed \(\beta + 1\).
  • **Limit Ordinals**: Ordinals that cannot be reached by simply adding 1 to any earlier ordinal.

This stratification helps organize infinite sets so each phase builds on the last. Ordinals are more than just counting numbers; they express extended positions in both sequence and structure, opening up endless possibilities in mathematical reasoning.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Determine the cardinality of each of the following sets: $$ \begin{aligned} &a_{1}=\left\\{f \in \omega^{\omega}:(\forall n \in \omega)(\forall p \in \omega)(f(n) \leq p)\right\\} \\ &a_{2}=\left\\{f \in \omega^{\omega}:(\forall n \in \omega)(\exists p \in \omega)(f(n) \leq p)\right\\} \\ &a_{3}=\left\\{f \in \omega^{\omega}:(\exists n \in \omega)(\forall p \in \omega)(f(n) \leq p)\right\\} \\ &a_{4}=\left\\{f \in \omega^{\omega}:(\exists n \in \omega)(\exists p \in \omega)(f(n) \leq p)\right\\} \\ &a_{5}=\left\\{f \in \omega^{\omega}:(\exists p \in \omega)(\forall n \in \omega)(f(n) \leq p)\right\\} \\ &a_{6}=\left\\{f \in \omega^{\omega}:(\forall p \in \omega)(\exists n \in \omega)(f(n) \leq p)\right\\} \\ &b_{1}=\left\\{f \in \omega^{\omega}:(\forall n \in \omega)(\forall p \in \omega)(f(n) \geq p)\right\\} \\ &b_{2}=\left\\{f \in \omega^{\omega}:(\forall n \in \omega)(\exists p \in \omega)(f(n) \geq p)\right\\} \\ &b_{3}=\left\\{f \in \omega^{\omega}:(\exists n \in \omega)(\forall p \in \omega)(f(n) \geq p)\right\\} \\ &b_{4}=\left\\{f \in \omega^{\omega}:(\exists n \in \omega)(\exists p \in \omega)(f(n) \geq p)\right\\} \\ &b_{5}=\left\\{f \in \omega^{\omega}:(\exists p \in \omega)(\forall n \in \omega)(f(n) \geq p)\right\\} \\ &b_{6}=\left\\{f \in \omega^{\omega}:(\forall p \in \omega)(\exists n \in \omega)(f(n) \geq p)\right\\} \end{aligned} $$

In this exercise, we assume the axiom of choice. Let \(\lambda\) be an uncountable regular cardinal (see Definition 7.87). A subset \(X\) of \(\lambda\) is closed cofinal if (1) it is closed: this means that for every subset \(X_{0}\) of \(X\) that satisfies card \(\left(X_{0}\right)<\lambda_{1} \sup \left(X_{0}\right) \in X\) [note that because \(\lambda\) is regular, \(\sup \left(X_{0}\right)\) is an ordinal that is strictly less than \(\lambda\) ]. (2) it is colinal in \(\lambda_{i}\) this means that for every \(\alpha \in \lambda\), there exists \(\beta \in X\) such that \(\alpha \leq \beta\). (a) Show that the collection of closed cofinal subsets of \(\lambda\) forms a filterbase on \(\lambda\) (see Chapter 2). (b) Show that if \(I\) is a non-empty set whose cardinality is strictly less than \(\lambda\) and if \(\left(X_{i}: i \in I\right)\) is a family of closed cofinal subsets of \(\lambda\), then \(\bigcap_{i \in I} X_{i}\) is a closed cofinal subset of \(\lambda\). (c) A subset \(Y\) of \(\lambda\) is called stationary if it intersects every closed cofinal subset. Show that the following three properties are equivalent: (1) there exists a pair of disjoint stationary sets; (2) there exists at least one stationary set that does not include a closed cofinal set; (3) the filter \(\mathcal{F}\) generated by the collection of closed cofinal subsets is not an ultrafilter. (d) Let \(X=\left(X_{a}: \alpha \in \lambda\right)\) be a sequence of subsets of \(\lambda\). The set $$ \left\\{\alpha \in \lambda: \alpha \in X_{\alpha}\right\\} $$ is called the diagonal intersection of \(X\) and is denoted by \(\Delta(X)\). Show that if \(X\) satisfies the following three conditions, (1) for every \(\alpha \in \lambda, X_{\alpha}\) is closed cofinal; (2) for every \(\alpha \in \lambda\) and \(\beta \in \lambda\), if \(\alpha \in \beta\), then \(X_{\beta} \subseteq X_{\alpha}\); (3) for every \(\alpha \in \lambda\), if \(\alpha\) is a limit ordinal, then \(X_{\alpha \alpha}=\bigcap_{\beta \in \alpha} X_{\beta}\); then \(\Delta(X)\) is closed cofinal. (e) Prove the following theorem (known as Fodor's theorem). Theorem 7.93 Let \(f\) be a mapping from \(\lambda\) into \(\lambda\) such that \(\\{\alpha \in \lambda:\) \(f(\alpha)<\alpha\\}\) is stationary. Then there exists \(\gamma \in \lambda\) such that \(\bar{f}^{-1}(\gamma)\), the inverse image of \(\gamma\) under \(\bar{f}_{1}\) is stationary. (f) Assume that \(\lambda \geq N_{2}\). Show that the set of ordinals in \(\lambda\) that have cofinality \(\aleph_{0}\) (see Exercise 15 ) is stationary. Show that the set of ordinals in \(\lambda\) that have cofinality \(\mathbb{N}_{1}\) is also stationary and is disjoint from the preceding set. (g) Part (f) shows that for every regular cardinal \(\lambda\) strictly greater than \(\aleph{1}_{1}\), the conditions from part (c) are satisfied. The argument that we will offer in the next paragraph shows that these conditions are satisfied for \(\aleph_{1}\) (indeed, the argument works for any successor cardinal). For every denumerable ordinal \(\alpha\), let \(f_{\alpha}\) be a surjective mapping from \(\omega\) onto \(\alpha\) and, for every \(n \in \omega_{1}\) let \(h_{n}\) be the mapping from \(\aleph_{1}\) into \(N_{1}\) defined by \(h_{n}(0)=0\) and \(h_{n}(\alpha)=f_{\alpha}(n)\) if \(\alpha \neq 0\). Show that, for every \(n \in \omega\), there exists \(\beta_{n} \in \aleph_{1}\) and a stationary subset \(Y_{n}\) of \(\aleph_{1}\) such that, for every \(\gamma \in Y_{n}, f_{\gamma}(n)=\beta_{n} .\) Show that there exists an integer \(n\) such that \(Y_{n}\) does not include a closed cofinal set.

Assume that the universe satisfies the axiom of choice. Show that for every family \(\left(\lambda_{\alpha}\right)_{\alpha \in \kappa}\) of non-zero cardinals indexed by an infinite cardinal \(x\), we have $$ \sum_{\alpha \in K} \lambda_{\alpha}=\sup \left(\kappa, \sup _{\alpha \in K}\left(\lambda_{\alpha}\right)\right) $$

Assume that the universe satisfies the axiom of choice. Let \(a\) and \(b\) be two infinite sets whose cardinalities are \(\lambda\) and \(\mu\), respectively. Assume \(\lambda>\mu\). Let \(g\) be an injective mapping from \(b\) into \(a\). The reader should determine the cardinalities Assume that the universe satisfies the axiom of choice. Let \(a\) and \(b\) be two infinite sets whose cardinalities are \(\lambda\) and \(\mu\), respectively. Assume \(\lambda>\mu\). Let \(g\) be an injective mapping from \(b\) into \(a\). The reader should determine the cardinalities of each of the following sets: $$ \begin{aligned} &y_{1}=\left\\{f \in b^{a}: \operatorname{card}(\vec{f}(a))=1\right\\} \\ &y_{2}=\left\\{f \in b^{a}:(\mathrm{V} x \in \wp(a))(\mathrm{card}(\bar{f}(x)) \leq 1)\right\\} \\ &y_{3}=\left\\{f \in b^{a}: \operatorname{card}\left(\bar{f}^{-1}(b)\right)=\lambda\right\\} \\ &y_{4}=\left\\{f \in b^{a}: \operatorname{card}(\bar{f}(a))=2\right\\} \\ &y_{5}=a-\bar{g}(b) ; \\ &y_{6}=\left\\{f \in b^{a}:(\forall y \in b)(f(g(y))=y)\right\\} \\ &y_{7}=\left\\{f \in b^{a}: \operatorname{card}(\bar{f}(a))=\mu\right\\} \end{aligned} $$ [Recall that if \(f \in b^{a}\), then \(\bar{f}\) and \(\bar{f}^{-1}\) respectively denote the direct image mapping induced by \(f\) from \(\wp(a)\) into \(\rho(b)\) and the inverse image mapping from \(\wp(b)\) into \(\wp(a)\).]

Without using the axiom of choice, show that for every non-empty set \(a\), the following properties are equivalent: (1) \(a\) includes a denumerable subset. (2) \(a\) includes a denumerable subset \(b\) such that \(a\) and \(a-b\) are equipotent. (3) For every denumerable set \(b, a\) and \(a \cup b\) are equipotent. (4) For every finite set \(x, a\) and \(a \cup x\) are equipotent. (5) For every finite subset \(x\) of \(a, a\) and \(a-x\) are equipotent. (6) There exists a non-zero integer \(n\) such that, for every subset \(x\) of \(a\) that is subpotent to \(n, a\) and \(a-x\) are equipotent. (7) There exists a non-zero integer \(n\) such that, for every set \(x\) of cardinality \(n\), \(a\) and \(a \cup x\) are equipotent. (8) for every \(t, a\) and \(a \cup\\{t\\}\) are equipotent. (9) There exists an element \(t \in a\) such that \(a\) and \(a-\\{t\\}\) are equipotent. (10) There exists a subset of \(a\) that is non-empty, different from \(a\), and equipotent to \(a\). (11) There exists a subset \(b \subseteq a\) that is non-empty, different from \(a\), and such that \(a\) is subpotent to \(b\).

See all solutions

Recommended explanations on Math Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.