Skip to main content
added 64 characters in body
Source Link
Will Brian
  • 18.6k
  • 3
  • 79
  • 106

To every increasing function $f: \mathbb N \rightarrow \mathbb N$, associate a sequence $\langle x_n \rangle$ as follows. The sequence is of the form $1,1,\dots,1,1/2,1/2,\dots,1/2,1/3,1/3,\dots,1/3,\dots$, with the first 1/2 occurring in spot $f(1)$, and the first 1/3 occurring in spot $f(2)$, etc. Now let $D$$B$ be a dominating family of functions $\mathbb N \rightarrow \mathbb N$ as described in the definition of $\mathfrak b$, with $|D| = \mathfrak d$$|B| = \mathfrak b$, and let $X$ be the corresponding family of sequences. I claim that this $X$ works. To see this, fix an arbitrary unbounded sequence $\langle y_n \rangle$. Now you can write downDefine a function $h$ such that $h(1)$ tells you the least $n$ with $y_n > 1$, and $h(2)$ tells you the least $n$ with $y_n > 4$, and generally, $h(i)$ tells you the least $n$ with $y_n > i^2$. ThereBy our choice of the family $B$, there is some $f \in D$$f \in B$ that dominatesis not dominated by $h$. But then the corresponding sequence $\langle x_n \rangle$ will make the product $\langle x_ny_n \rangle$ unbounded. The reason is that we have $f(i) > h(i)$ for infinitely many values of $i$. Given some such $i$, if $f(i) = n$ then $x_ny_n > x_ni^2 \geq (1/i)i^2 = i$, because $x_n \geq 1/i$ if $f(i) > h(i)$.

To every increasing function $f: \mathbb N \rightarrow \mathbb N$, associate a sequence $\langle x_n \rangle$ as follows. The sequence is of the form $1,1,\dots,1,1/2,1/2,\dots,1/2,1/3,1/3,\dots,1/3,\dots$, with the first 1/2 occurring in spot $f(1)$, and the first 1/3 occurring in spot $f(2)$, etc. Now let $D$ be a dominating family of functions $\mathbb N \rightarrow \mathbb N$, with $|D| = \mathfrak d$, and let $X$ be the corresponding family of sequences. I claim that this $X$ works. To see this, fix an arbitrary unbounded sequence $\langle y_n \rangle$. Now you can write down a function $h$ such that $h(1)$ tells you the least $n$ with $y_n > 1$, and $h(2)$ tells you the least $n$ with $y_n > 4$, and generally, $h(i)$ tells you the least $n$ with $y_n > i^2$. There is some $f \in D$ that dominates $h$. But then the corresponding sequence $\langle x_n \rangle$ will make the product $\langle x_ny_n \rangle$ unbounded. The reason is that we have $f(i) > h(i)$ for infinitely many values of $i$. Given some such $i$, if $f(i) = n$ then $x_ny_n > x_ni^2 \geq (1/i)i^2 = i$, because $x_n \geq 1/i$ if $f(i) > h(i)$.

To every increasing function $f: \mathbb N \rightarrow \mathbb N$, associate a sequence $\langle x_n \rangle$ as follows. The sequence is of the form $1,1,\dots,1,1/2,1/2,\dots,1/2,1/3,1/3,\dots,1/3,\dots$, with the first 1/2 occurring in spot $f(1)$, and the first 1/3 occurring in spot $f(2)$, etc. Now let $B$ be a family of functions $\mathbb N \rightarrow \mathbb N$ as described in the definition of $\mathfrak b$, with $|B| = \mathfrak b$, and let $X$ be the corresponding family of sequences. I claim that this $X$ works. To see this, fix an arbitrary unbounded sequence $\langle y_n \rangle$. Define a function $h$ such that $h(1)$ tells you the least $n$ with $y_n > 1$, and $h(2)$ tells you the least $n$ with $y_n > 4$, and generally, $h(i)$ tells you the least $n$ with $y_n > i^2$. By our choice of the family $B$, there is some $f \in B$ that is not dominated by $h$. But then the corresponding sequence $\langle x_n \rangle$ will make the product $\langle x_ny_n \rangle$ unbounded. The reason is that we have $f(i) > h(i)$ for infinitely many values of $i$. Given some such $i$, if $f(i) = n$ then $x_ny_n > x_ni^2 \geq (1/i)i^2 = i$, because $x_n \geq 1/i$ if $f(i) > h(i)$.

edited body
Source Link
Will Brian
  • 18.6k
  • 3
  • 79
  • 106

Proof that $\kappa \leq \mathfrak d$$\kappa \leq \mathfrak b$:

Proof that $\kappa \leq \mathfrak d$:

Proof that $\kappa \leq \mathfrak b$:

added 470 characters in body
Source Link
Will Brian
  • 18.6k
  • 3
  • 79
  • 106

Let $\kappa$ denote the smallest possible size of some set $X$ with the properties you've described. I claim that $\kappa$ is just another cardinal in disguise, the unbounding number $\mathfrak b$. I'll define $\mathfrak b$ in a moment, but let me first point out some consequences of this observation:

This question, and others like it, are used to define uncountable cardinal numbers known as cardinal characteristics of the continuum. Both of my claims above follow from comparing $\kappa$ to two other cardinals numbers that are well known to people who've studied cardinal characteristics, the unbounding number $\mathfrak b$ and the dominating number $\mathfrak d$. The point is that $$\mathfrak b \leq \kappa \leq \mathfrak d.$$ Claim $(1)$ then follows from the factsknown fact that $\mathfrak b$ is uncountable and $\mathfrak d \leq \mathfrak c$$\mathfrak b \leq \mathfrak c$. Claim $(2)$ follows from the fact that it is known to be consistent to have $\mathfrak b = \mathfrak d$, with their common value$\mathfrak b$ be whatever you like, while $\mathfrak c$ is any larger value you like (subject to the ZFC-provable constraint that neither$\mathfrak b$ is a regular cardinal, and $\mathfrak c$ does not have countable cofinality).

If $f,g$ are functions $\mathbb N \rightarrow \mathbb N$, we say that $g$ dominates $f$ if $g(n) \geq f(n)$ for all sufficiently large values of $n$. The unbounding number $\mathfrak b$ is defined to be the smallest size of a family $B$ of functions $\mathbb N \rightarrow \mathbb N$ such that no single function $\mathbb N \rightarrow \mathbb N$ dominates every member of $B$. Equivalently, given any $g: \mathbb N \rightarrow \mathbb N$ (no matter how fast-growing), there is some $f \in B$ such that $f(n) > g(n)$ infinitely often.

To every increasing function $f: \mathbb N \rightarrow \mathbb N$, associate a sequence $\langle y_n \rangle$$\langle x_n \rangle$ as follows. The sequence is of the form $1,1,\dots,1,1/2,1/2,\dots,1/2,1/3,1/3,\dots,1/3,\dots$, with the first 1/2 occurring in spot $f(1)$, and the first 1/3 occurring in spot $f(2)$, etc. Now let $D$ be a dominating family of functions $\mathbb N \rightarrow \mathbb N$, with $|D| = \mathfrak d$, and let $X$ be the corresponding family of sequences. I claim that this $X$ works. To see this, fix an arbitrary unbounded sequence $\langle y_n \rangle$. Now you can write down a function $h$ such that $h(1)$ tells you the least $n$ with $y_n > 1$, and $h(2)$ tells you the least $n$ with $y_n > 4$, and generally, $h(i)$ tells you the least $n$ with $y_n > i^2$. There is some $f \in D$ that dominates $h$. But then the corresponding sequence $\langle x_n \rangle$ will make the product $\langle x_ny_n \rangle$ unbounded. The reason is that we have $h(i) > f(i)$$f(i) > h(i)$ for all sufficiently largeinfinitely many values of $i$. Given some such $i$, and this ensures thatif $x_ny_n > j$ whenever$f(i) = n$ then $y_n$ is the first member of the$x_ny_n > x_ni^2 \geq (1/i)i^2 = i$, because $y$-sequence above$x_n \geq 1/i$ if $j$$f(i) > h(i)$.

Let $\kappa$ denote the smallest possible size of some set $X$ with the properties you've described. I claim

This question, and others like it, are used to define uncountable cardinal numbers known as cardinal characteristics of the continuum. Both of my claims above follow from comparing $\kappa$ to two other cardinals numbers that are well known to people who've studied cardinal characteristics, the unbounding number $\mathfrak b$ and the dominating number $\mathfrak d$. The point is that $$\mathfrak b \leq \kappa \leq \mathfrak d.$$ Claim $(1)$ then follows from the facts that $\mathfrak b$ is uncountable and $\mathfrak d \leq \mathfrak c$. Claim $(2)$ follows from the fact that it is known to be consistent to have $\mathfrak b = \mathfrak d$, with their common value whatever you like, while $\mathfrak c$ is any larger value you like (subject to the ZFC-provable constraint that neither cardinal have countable cofinality).

To every increasing function $f: \mathbb N \rightarrow \mathbb N$, associate a sequence $\langle y_n \rangle$ as follows. The sequence is of the form $1,1,\dots,1,1/2,1/2,\dots,1/2,1/3,1/3,\dots,1/3,\dots$, with the first 1/2 occurring in spot $f(1)$, and the first 1/3 occurring in spot $f(2)$, etc. Now let $D$ be a dominating family of functions $\mathbb N \rightarrow \mathbb N$, with $|D| = \mathfrak d$, and let $X$ be the corresponding family of sequences. I claim that this $X$ works. To see this, fix an arbitrary unbounded sequence $\langle y_n \rangle$. Now you can write down a function $h$ such that $h(1)$ tells you the least $n$ with $y_n > 1$, and $h(2)$ tells you the least $n$ with $y_n > 4$, and generally, $h(i)$ tells you the least $n$ with $y_n > i^2$. There is some $f \in D$ that dominates $h$. But then the corresponding sequence $\langle x_n \rangle$ will make the product $\langle x_ny_n \rangle$ unbounded. The reason is that we have $h(i) > f(i)$ for all sufficiently large $i$, and this ensures that $x_ny_n > j$ whenever $y_n$ is the first member of the $y$-sequence above $j$.

Let $\kappa$ denote the smallest possible size of some set $X$ with the properties you've described. I claim that $\kappa$ is just another cardinal in disguise, the unbounding number $\mathfrak b$. I'll define $\mathfrak b$ in a moment, but let me first point out some consequences of this observation:

This question, and others like it, are used to define uncountable cardinal numbers known as cardinal characteristics of the continuum. Claim $(1)$ follows from the known fact that $\mathfrak b$ is uncountable and $\mathfrak b \leq \mathfrak c$. Claim $(2)$ follows from the fact that it is known to be consistent to have $\mathfrak b$ be whatever you like, while $\mathfrak c$ is any larger value you like (subject to the ZFC-provable constraint that $\mathfrak b$ is a regular cardinal, and $\mathfrak c$ does not have countable cofinality).

If $f,g$ are functions $\mathbb N \rightarrow \mathbb N$, we say that $g$ dominates $f$ if $g(n) \geq f(n)$ for all sufficiently large values of $n$. The unbounding number $\mathfrak b$ is defined to be the smallest size of a family $B$ of functions $\mathbb N \rightarrow \mathbb N$ such that no single function $\mathbb N \rightarrow \mathbb N$ dominates every member of $B$. Equivalently, given any $g: \mathbb N \rightarrow \mathbb N$ (no matter how fast-growing), there is some $f \in B$ such that $f(n) > g(n)$ infinitely often.

To every increasing function $f: \mathbb N \rightarrow \mathbb N$, associate a sequence $\langle x_n \rangle$ as follows. The sequence is of the form $1,1,\dots,1,1/2,1/2,\dots,1/2,1/3,1/3,\dots,1/3,\dots$, with the first 1/2 occurring in spot $f(1)$, and the first 1/3 occurring in spot $f(2)$, etc. Now let $D$ be a dominating family of functions $\mathbb N \rightarrow \mathbb N$, with $|D| = \mathfrak d$, and let $X$ be the corresponding family of sequences. I claim that this $X$ works. To see this, fix an arbitrary unbounded sequence $\langle y_n \rangle$. Now you can write down a function $h$ such that $h(1)$ tells you the least $n$ with $y_n > 1$, and $h(2)$ tells you the least $n$ with $y_n > 4$, and generally, $h(i)$ tells you the least $n$ with $y_n > i^2$. There is some $f \in D$ that dominates $h$. But then the corresponding sequence $\langle x_n \rangle$ will make the product $\langle x_ny_n \rangle$ unbounded. The reason is that we have $f(i) > h(i)$ for infinitely many values of $i$. Given some such $i$, if $f(i) = n$ then $x_ny_n > x_ni^2 \geq (1/i)i^2 = i$, because $x_n \geq 1/i$ if $f(i) > h(i)$.

Source Link
Will Brian
  • 18.6k
  • 3
  • 79
  • 106
Loading