Part II

Part II. Mathematical Logic

[425/81%]

Show

LaTeX

Show LaTeX

Chapter II.8Filtered Products[60/75%]

Problem II.8.1

Prove that if $D$ is a filter over $I$ , then $I \in D$ .

Problem II.8.2

Let $X \subseteq I$ . Prove that $\left\{ Y \mid Y \subseteq I \text{ and } X \subseteq Y\right\}$ is a filter over $I$ .

Problem II.8.3

Let $D$ be a filter over $I$ and $J \in D$ . Show that $D_{1} = \left\{ X \cap J \mid X \in D\right\}$ is a filter over $J$ , and also that if $D$ is a nonprincipal filter, then $D_{1}$ is also a nonprincipal filter.

Problem II.8.4

Prove that if some finite set belongs to a filter, then this filter is principal.

Problem II.8.5

Prove that every nonprincipal ultrafilter contains all sets having finite complements.

Problem II.8.6

Prove that a filter $D$ over $I$ is an ultrafilter if and only if $D$ is a maximal element in the set of all filters over $I$ , ordered by inclusion.

Problem II.8.7

Prove that in the set $\Phi$ of all filters over $I$ , ordered by inclusion, $\left\{ I\right\}$ is the least element. Show also that if $\left|I\right| \geq 2$ , then $\Phi$ has no greatest element.

Problem II.8.8

Prove that, for a filter over $I$ containing the set $S \subseteq \mathcal{P}(I)$ to exist, it is necessary and sufficient that the intersection of any finite number of elements of $S$ be nonempty.

Problem II.8.9

Let $I$ be an infinite set of cardinality $\alpha$ and

\Phi = \left\{ X \mid X \subseteq I \text{ and } \left|X\right| < \alpha \right\} .

Prove that $\Phi$ is a filter over $I$ .

Problem II.8.10

Prove that a system $\Psi$ of subsets of a set $I$ is contained in some Frechet filter if and only if every intersection of finitely many sets of the system $\Psi$ has cardinality equal to the cardinality of the set $I$ .

Problem II.8.11

Show that every nonprincipal ultrafilter over a countable set is a Frechet filter.

Problem II.8.12

Let $F$ be a filter over $I$ , $A \subseteq I$ , and $F_{A} = \left\{ X \cap A \mid X \in F\right\}$ . Prove that, for $F_{A}$ to be a filter over $A$ , it is necessary and sufficient that $X \cap A \neq \emptyset$ for every $X \in F$ .

Problem II.8.13

Let $F$ be an ultrafilter over $I$ , $A \subseteq I$ , and $F_{A} = \left\{ X \cap A \mid X \in F\right\}$ . Prove that, for $F_{A}$ to be an ultrafilter over $A$ , it is necessary and sufficient that $A$ belong to $F$ .

Problem II.8.14

Show that every filter can be extended to an ultrafilter.

Problem II.8.15

Prove that every filter is the intersection of all ultrafilters containing it.

Problem II.8.16

Let $F$ and $G$ be filters over $I$ . Prove that

F \cap G = \left\{ X \cup Y \mid X \in F \text{ and } Y \in G\right\} .

Problem II.8.17

Prove that if the union of a finite sequence $\left\{ A_{i}\right\}_{i \leq n}$ of subsets of a set $I$ belongs to an ultrafilter $F$ , then at least one of the sets $A_{i}$ belongs to $F$ .

Problem II.8.18

Let $F$ be an ultrafilter and $G_{1}, \ldots , G_{n}$ filters over $I$ . Prove that if $F \supseteq G_{1} \cap \ldots \cap G_{n}$ , then there exists $i$ ( $1 \leq i \leq n$ ) such that $F \supseteq G_{i}$ .

Problem II.8.19

Let the set $J$ be infinite. Construct an ultrafilter $F$ and a family of ultrafilters $\left\{ G_{j}\right\}_{j \in J}$ such that $F \supseteq \bigcap_{j \in J} G_{j}$ , but $F$ does not contain $G_{j}$ for any $j$ .

Problem II.8.20

Prove that $\bigcap_{X \in F} X$ , where $F$ is an ultrafilter, contains at most one point.

Problem II.8.21

(a)(b)(c)

Let $D$ be a filter over $I$ and $\sim$ some equivalence relation on $I$ . Let $D^{\sim } = \left\{ B \mid \exists A (A \in D \& B = \left\{ [x]_{\sim } \mid x \in A\right\} )\right\}$ . Prove that:

(a)

$D^{\sim }$ is a filter over $I / {\sim }$ ;

(b)

if $D$ is an ultrafilter, then $D^{\sim }$ is an ultrafilter;

(c)

if $D$ is an ultrafilter and $[x]_{\sim } \notin D$ for every $x$ , then $D^{\sim }$ is a nonprincipal ultrafilter.

Problem II.8.22

Prove that a filter $D$ over $I$ is countably complete if and only if there is no decreasing sequence $X_{0} \supset X_{1} \supset X_{2} \supset \ldots$ of elements $X_{i} \in D$ such that $\bigcap_{i \in \mathbb {N}} X_{i} = \emptyset$ .

Problem II.8.23

Prove that $\sim_{D}$ is an equivalence relation on $\prod_{i \in I} M_{i}$ .

Problem II.8.24

(a)(b)

Prove that if $f_{1} \sim_{D} g_{1}, \ldots , f_{n} \sim_{D} g_{n}$ , then:

(a)

$P^{n}(f_{1} / D, \ldots , f_{n} / D) = P^{n}(g_{1} / D, \ldots , g_{n} / D)$ ;

(b)

$F^{n}(f_{1}, \ldots , f_{n}) \sim_{D} F^{n}(g_{1}, \ldots , g_{n})$ .

Problem II.8.25

Prove that for every $I$ ,

\prod _{i \in I} \mathfrak {M}_{i} \cong \prod _{i \in I} \mathfrak {M}_{i} / D,

where $D = \left\{ I\right\}$ .

Problem II.8.26

Prove that the canonical mapping $\varphi : \prod_{i \in I} \mathfrak {M}_{i} \to \prod_{i \in I} \mathfrak {M}_{i} / D$ , where $\varphi (f) = f / D$ , is a homomorphism of $\prod_{i \in I} \mathfrak {M}_{i}$ onto $\prod_{i \in I} \mathfrak {M}_{i} / D$ . Show that, in general, this homomorphism is not a strong homomorphism.

Problem II.8.27

Prove that if a sentence containing neither $\neg$ nor $\supset$ is true on the direct product $\prod_{i \in I} \mathfrak {M}_{i}$ , then it is true on the filtered product $\prod_{i \in I} \mathfrak {M}_{i} / D$ with respect to any filter $D$ .

Problem II.8.28

Prove that if $D, D_{1}$ are filters over $I$ and $D \subseteq D_{1}$ , then the mapping $\varphi$ defined by $\varphi (f / D) = f / D_{1}$ is a homomorphism of $\prod_{i \in I} \mathfrak {M}_{i} / D$ onto $\prod_{i \in I} \mathfrak {M}_{i} / D_{1}$ .

Problem II.8.29

Let $J \in D$ , where $D$ is a filter over $I$ . Show that

\prod _{i \in I} \mathfrak {M}_{i} / D \cong \prod _{j \in J} \mathfrak {M}_{j} / D_{J},

where $D_{J}$ is the filter formed by the intersections of $J$ with the sets of the filter $D$ . In particular, if $D$ is a principal filter consisting of subsets of the set $J$ , then

\prod _{i \in I} \mathfrak {M}_{i} / D \cong \prod _{j \in J} \mathfrak {M}_{j}.

Problem II.8.30

Let $I$ be finite and $D$ a filter over $I$ . Prove that $\prod_{i \in I} \mathfrak {M}_{i} / D$ is isomorphic to the direct product of some of the systems $\mathfrak {M}_{i}$ .

Problem II.8.31

Let $\left\{ I_{k} \mid k \in K\right\}$ be a partition of $I$ , let filters $D_{k}$ be given over $I_{k}$ , and let a filter $D^{*}$ be given over $K$ . Show that

D = \left\{ X \subseteq I \mid \left\{ k \mid k \in K \text{ and } X \cap I_{k} \in D_{k}\right\} \in D^{*}\right\}

is a filter over $I$ and, for all $\mathfrak {M}_{i}$ ( $i \in I$ ),

\prod _{i \in I} \mathfrak {M}_{i} / D \cong \prod _{k \in K} \left( \prod _{i \in I_{k}} \mathfrak {M}_{i} / D_{k} \right) \Big/ D^{*}

(the associative law for filtered products).

Problem II.8.32

Prove that if the intersection $J$ of all sets of a filter $D$ over $I$ is nonempty and does not belong to $D$ , then

\prod _{i \in I} \mathfrak {M}_{i} / D \cong \prod _{j \in J} \mathfrak {M}_{j} \cdot \left( \prod _{k \in J'} \mathfrak {M}_{k} / D_{J'} \right),

where $J' = I \backslash J$ and $D_{J'}$ is the filter over $J'$ formed by the intersections of $J'$ with all sets of the filter $D$ .

Problem II.8.33

Let $\varphi_{i}: M_{i} \to N_{i}$ be homomorphisms, and let $\varphi (f / D) = (\varphi '(f)) / D$ , where $(\varphi '(f))(j) = \varphi_{j}(f(j))$ for $f \in \prod_{i \in I} M_{i}$ , $j \in J$ . Prove that then $\varphi$ is a homomorphism of $\prod_{i \in I} \mathfrak {M}_{i} / D$ into $\prod_{i \in I} \mathfrak {N}_{i} / D$ . Prove that if the $\varphi_{i}$ are strong homomorphisms (isomorphisms), then so is $\varphi$ .

Problem II.8.34

Let $\varphi$ be a one-to-one correspondence between $I$ and $J$ , let $D$ be a filter over $I$ , and $D_{1} = \left\{ \varphi (X) \mid X \in D\right\}$ . Prove that

\prod _{i \in I} \mathfrak {M}_{i} / D \cong \prod _{j \in J} \mathfrak {M}_{\varphi ^{-1}(j)} / D_{1}.

Problem II.8.35

Let $\left\{ C_{i} \mid i \in I\right\}$ be a family of sets, and let an equivalence relation $\sim$ be given on $I$ such that $i \sim j \Rightarrow C_{i} = C_{j}$ . Prove that for every ultrafilter $D$ over $I$ there exists an isomorphic embedding of $\prod_{\alpha \in I / {\sim }} C_{\alpha } / D^{\sim }$ into $\prod_{i \in I} C_{i} / D$ , where $D^{\sim }$ is constructed as in Problem II.8.21, and $C_{\alpha } = C_{i}$ for $\alpha \in I / {\sim }$ and $i \in \alpha$ .

Problem II.8.36

Let $\left\{ I_{k}\right\}_{k \in K}$ be the family of all finite nonempty subsets of $I$ , and let $\left\{ \mathfrak {M}_{i}\right\}_{i \in I}$ be a family of algebraic systems of signature $\sigma$ . Prove that there exists a filter $D$ over $K$ such that for every filter $D_{1} \supseteq D$ over $K$ there exists an isomorphic embedding of $\prod_{i \in I} \mathfrak {M}_{i}$ into $\prod_{k \in K} \left( \prod_{i \in I_{k}} \mathfrak {M}_{i} \right) \Big/ D_{1}$ .

Problem II.8.37

Prove that if $A$ and $B$ are conditionally filterable with respect to the filter $D$ over $I$ , then $(A \& B)$ , $\exists x \, B$ , $\forall x \, A$ are also conditionally filterable with respect to $D$ .

Problem II.8.38

Prove that if $A$ and $B$ are filterable with respect to the filter $D$ over $I$ , then $(A \& B)$ , $\exists x \, A$ are also filterable with respect to $D$ .

Problem II.8.39

Prove that atomic formulas are filterable with respect to every filter.

Problem II.8.40

Let $A$ be filterable with respect to the ultrafilter $D$ . Prove that $\neg A$ is filterable with respect to $D$ .

Problem II.8.41

Prove that every formula is filterable with respect to every ultrafilter (os's theorem).

Problem II.8.42

Let $A$ be filterable with respect to the filter $D$ over $I$ , and let $B$ be conditionally filterable with respect to $D$ . Prove that $(A \supset B)$ and $\neg A$ are conditionally filterable with respect to $D$ .

Problem II.8.43

Call a formula Horn if it is obtained from formulas of the form $\neg A$ , $(A \supset B)$ , $B$ , where $A$ is a conjunction of atomic formulas and $B$ is an atomic formula, by means of the operations of conjunction and adjoining quantifiers. Prove that Horn formulas are conditionally filterable with respect to every filter.

Problem II.8.44

Prove that the ultraproduct of linearly ordered sets is linearly ordered.

Problem II.8.45

Prove that the filtered product of preordered sets is preordered.

Problem II.8.46

Prove that the filtered product of partially ordered sets is partially ordered.

Problem II.8.47

Prove that the filtered product of groups is a group.

Problem II.8.48

Let a finite system $\mathfrak {M}$ contain $n$ elements. Prove that every ultrapower of $\mathfrak {M}$ also contains $n$ elements.

Problem II.8.49

Show that if the cardinalities of all the factors do not exceed a natural number $n$ , then the cardinality of the ultraproduct does not exceed $n$ .

Problem II.8.50

Prove that every filtered product of infinite systems is infinite.

Problem II.8.51

Suppose that for every $n$ the family $\left\{ \mathfrak {M}_{i}\right\}_{i \in I}$ contains only finitely many systems of cardinality $n$ . Prove that in this case the ultraproduct $\prod_{i \in I} \mathfrak {M}_{i} / D$ with respect to a nonprincipal ultrafilter $D$ is infinite.

Problem II.8.52

Prove that if $\left|M_{i}\right| \leq \left|N_{i}\right|$ for every $i \in I$ , then for every filter $D$ over $I$ ,

\left|\prod _{i \in I} \mathfrak {M}_{i} / D\right| \leq \left|\prod _{i \in I} \mathfrak {N}_{i} / D\right|.

Problem II.8.53

Let all the factors $\mathfrak {M}_{i}$ ( $i \in \mathbb {N}$ ) be finite, let $D$ be an ultrafilter over $\mathbb {N}$ , and let $\left\{ i \mid \left|M_{i}\right| = n\right\} \notin D$ for every $n \in \mathbb {N}$ . Prove that $\prod_{i \in \mathbb {N}} \mathfrak {M}_{i}$ has the cardinality of the continuum.

Problem II.8.54

Let all the factors $\mathfrak {M}_{i}$ ( $i \in \mathbb {N}$ ) be finite or countable, let $D$ be a nonprincipal ultrafilter over the set of natural numbers $\mathbb {N}$ , and let $\left\{ i \mid \left|M_{i}\right| = n\right\} \notin D$ for every natural number $n$ . Prove that the cardinality of $\prod_{i \in \mathbb {N}} \mathfrak {M}_{i} / D$ equals the continuum.

Problem II.8.55

Prove that if $D$ is not a countably complete ultrafilter over $I$ , and for every natural number $n$ we have $\left\{ i \mid \left|M_{i}\right| = n\right\} \notin D$ , then $\prod_{i \in I} \mathfrak {M}_{i} / D$ has cardinality at least the continuum.

Problem II.8.56

Let all $\mathfrak {M}_{i}$ ( $i \in I$ ) be countable, and let $D$ be a countably complete ultrafilter over $I$ . Prove that $\left|\prod_{i \in I} \mathfrak {M}_{i} / D\right| = \aleph_{0}$ .

Problem II.8.57

Let $\langle A_{i}; \leq \rangle$ be partially ordered sets ( $i \in \mathbb {N}$ ), where $A_{i}$ contains $i$ minimal elements. What is the cardinality of the set of minimal elements in the ultraproduct $\prod_{i \in \mathbb {N}} \mathfrak {A}_{i} / D$ , if $D$ is a nonprincipal ultrafilter over $\mathbb {N}$ ?

Problem II.8.58

Prove that for every infinite set $I$ there exists a filter $D$ over $I$ such that for every filter $D_{1}$ over $I$ containing $D$ , and every infinite system $\mathfrak {M}$ ,

\left|M^{I} / D_{1}\right| \geq 2^{\left|I\right|}.

Problem II.8.59

Prove that for every infinite algebraic system $\mathfrak {M}$ and every given cardinality $m$ , there exists an ultrapower of the system $\mathfrak {M}$ whose cardinality is greater than $m$ .

Problem II.8.60

Prove that if $D$ is a not countably complete ultrafilter over $I$ and the algebraic system $\mathfrak {M}$ is infinite, then the natural embedding $\varphi : M \to M^{I} / D$ , i.e., $\varphi (a) = f / D$ , where $f(i) = a$ for all $i \in I$ , is not a one-to-one correspondence between $M$ and $M^{I} / D$ .