Countable Chains of Subsets in an Infinite Set

[evinda]

Hello! (Wave)

A family of sets is called chain if any two sets of the family are comparable, i.e. the first set contains the second or the second the first.
How many sets can a chain of subsets of an infinite set contain?
More specifically, is there an infinite set, each chain of which is countable?

 

[Evgeny.Makarov]

It would seem that any chain consisting of subsets of $A$ has cardinality no greater than that of $A$. In particular, any chain consisting of subsets of $\Bbb N$ is countable. But nothing prevents a chain from consisting of a single set.

Edit: This is wrong. For infinite $A$ there can be a chain $C$ such that $|A|<|C|\le\mathcal{P}(A)$. See https://driven2services.com/staging/mh/index.php?posts/73262/ in this thread.

 

[evinda]

It would seem that any chain consisting of subsets of $A$ has cardinality no greater than that of $A$. In particular, any chain consisting of subsets of $\Bbb N$ is countable. But nothing prevents a chain from consisting of a single set.

So does this mean that an infinite set, each chain of which is countable is a set that contains an infinite number of singletons, the elements of which are natural numbers? Or have I understood it wrong? (Thinking)

 

[Evgeny.Makarov]

So does this mean that an infinite set, each chain of which is countable is a set that contains an infinite number of singletons

A singleton is a one-element set. A set (whether infinite or not) does not have to contain singletons. If we are not talking about von Neumann encoding, numbers (or any other objects) can be considered as urelements. So you may have a set of triangles, or people, or flowers, etc.

the elements of which are natural numbers?

You started talking about an arbitrary set (with some restriction on chains) and arrived at natural numbers. Why would you possibly do that? Are natural numbers the only objects in mathematics?

 

[evinda]

It would seem that any chain consisting of subsets of $A$ has cardinality no greater than that of $A$. In particular, any chain consisting of subsets of $\Bbb N$ is countable. But nothing prevents a chain from consisting of a single set.

Could you maybe explain it further to me?

 

[Evgeny.Makarov]

Let me also ask a question: can you describe an example of an infinite chain that consists of subsets of $\Bbb N$?

 

[evinda]

Let me also ask a question: can you describe an example of an infinite chain that consists of subsets of $\Bbb N$?

Couldn't we consider the set $ k \mathbb{N}, \text{ where } k=3m, m \in \mathbb{Z} $ ?

 

[Evgeny.Makarov]

$k\Bbb N\in \mathcal{P}(\Bbb N)$, but if $C$ is a chain consisting of sets of natural numbers, then $C\subset\mathcal{P}(\Bbb N)$. Here $\mathcal{P}(\Bbb N)$ is the powerset of $\Bbb N$.

 

[evinda]

$k\Bbb N\in \mathcal{P}(\Bbb N)$, but if $C$ is a chain consisting of sets of natural numbers, then $C\subset\mathcal{P}(\Bbb N)$. Here $\mathcal{P}(\Bbb N)$ is the powerset of $\Bbb N$.

So do we want the chain not not be a subset of $\mathcal{P}(\Bbb N)$? If so, why is it like that?Could we consider $\mathbb{Q}$ as an example of an infinite chain that consists of subsets of $\mathbb{N}$? (Thinking)

 

[Evgeny.Makarov]

So do we want the chain not not be a subset of $\mathcal{P}(\Bbb N)$?

If by double negation you mean affirmative, then yes.

If so, why is it like that?

Because you said in post #1 that a chain is a "family of sets", and $\mathcal{P}(\Bbb N)$ is the largest family of sets of natural numbers.

Could we consider $\mathbb{Q}$ as an example of an infinite chain that consists of subsets of $\mathbb{N}$?

Is $\Bbb Q$ a family of sets of natural numbers?

 

[evinda]

$k\Bbb N\in \mathcal{P}(\Bbb N)$, but if $C$ is a chain consisting of sets of natural numbers, then $C\subset\mathcal{P}(\Bbb N)$. Here $\mathcal{P}(\Bbb N)$ is the powerset of $\Bbb N$.

The power set of $\mathbb{N}$ is a countable union of countable sets, so it's countable.
So we could pick $k \mathbb{N}$, where $k$ is a multiple of $3$ as an example of an infinite set, each chain of which is countable, right?

 

[Evgeny.Makarov]

The power set of $\mathbb{N}$ is a countable union of countable sets, so it's countable.

There is no countable union here. The powerset of $\Bbb N$ has the cardinality of continuum.

So we could pick $k \mathbb{N}$, where $k$ is a multiple of $3$ as an example of an infinite set, each chain of which is countable, right?

As I said in post #2, any chain consisting of subsets of $\Bbb N$ is at most countable. This goes, in particular, for chains consisting of subsets of $k\Bbb N$. In fact, we need to determine what is meant by "a chain of this set" (a chain of $k \mathbb{N}$ in your example). I used a clearer description "a chain consisting of subsets of this set".

You still have not described an example of a chain consisting of subsets of $\Bbb N$, so you may not understand the definition. I am reluctant to discuss sets, families of sets and the difference between the two. This is the level of first-year students.

 

[evinda]

There is no countable union here. The powerset of $\Bbb N$ has the cardinality of continuum.

Oh yes, right...

You still have not described an example of a chain consisting of subsets of $\Bbb N$, so you may not understand the definition. I am reluctant to discuss sets, families of sets and the difference between the two. This is the level of first-year students.

An example is the following: $\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}, \{1,2,3,4,5\}, \dots$, right?

 

[Evgeny.Makarov]

An example is the following: $\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}, \{1,2,3,4,5\}, \dots$, right?

Yes, this is one example.

I realized that my answer in post #2 is wrong: the cardinality of a chain can be larger than the cardinality of a set whose subsets form the chain. For an example see StackExchange. Sorry about the confusion. I'll edit that post with a link here.

 

[evinda]

Yes, this is one example.

I realized that my answer in post #2 is wrong: the cardinality of a chain can be larger than the cardinality of a set whose subsets form the chain. For an example see StackExchange. Sorry about the confusion. I'll edit that post with a link here.

I saw the link that you sent me.
Could you explain me why if we define the subset $\Gamma_r=\{ x \in \mathbb{Q} | x<r \}$ , this defines an injective order-preserving map from $\mathbb{R}$ to $\mathcal{P}(\mathbb{Q})$ ? (Thinking)

 

[evinda]

Suppose that we have an infinite set $B$.
Each chain of $B$ will be in $\mathcal{P}(B)$.
But $\mathcal{P}(B)$ will contain uncountable sets. We could deduce from the above that there is no infinite set, each chain of which is countable if we show that $\mathcal{P}(B)$ contains only the chains of $B$. But is this true? If so, how could we show this?

 

[Evgeny.Makarov]

Could you explain me why if we define the subset $\Gamma_r=\{ x \in \mathbb{Q} | x<r \}$ , this defines an injective order-preserving map from $\mathbb{R}$ to $\mathcal{P}(\mathbb{Q})$ ?

Injectivity follows from strict monotonicity, i.e., preservation of order. As for the latter, it should be clear that $r_1<r_2$ implies $\Gamma_{r_1}\subsetneq\Gamma_{r_2}$.

Suppose that we have an infinite set $B$.
Each chain of $B$ will be in $\mathcal{P}(B)$.

OK, since we are using the expression "a chain of $B$", it needs to be defined. I suppose that by it we mean a subset of $\mathcal{P}(B)$ that is a chain with respect to set inclusion. Then a chain $C$ of $B$ is not in $\mathcal{P}(B)$, in the sense it is not the case that $C\in\mathcal{P}(B)$. Rather, $C\subset\mathcal{P}(B)$.

But $\mathcal{P}(B)$ will contain uncountable sets.

Not necessarily. The powerset $\mathcal{P}(B)$ itself is uncountable if $B$ is infinite, but if $B$ is countable, then its subsets, i.e., elements of $\mathcal{P}(B)$, are at most countable.

We could deduce from the above that there is no infinite set, each chain of which is countable if we show that $\mathcal{P}(B)$ contains only the chains of $B$.

First, as I said, $\mathcal{P}(B)$ does nor contain chains of $B$; rather, chains are subsets of $\mathcal{P}(B)$, or elements of $\mathcal{P}(\mathcal{P}(B))$. And not all subsets of $\mathcal{P}(B)$ are chains when $B$ has more than one element: there are subsets of $\mathcal{P}(B)$ that contain incomparable subsets of $B$.

 

[evinda]

Suppose that we have an infinite set $B$.

Each chain of $B$ will be a subset of $\mathcal{P}(B)$ since $\mathcal{P}(B)$ is the set that contains all the elements of the chains of $B$.

If $B$ is uncountable, trivially $\mathcal{P}(B)$ will contain uncountable elements of chains of $B$.

Otherwise, we pick a bijective function between $\mathbb{N}$ and $\mathbb{Q}$ that gives us a bijective function between their powersets.

$\mathbb{Q} \subset \mathbb{R}$,so for each real number $r$ we can define the set $S_r=\{ x \in \mathbb{Q} | x<r\}$ .
This set defines a 1-1 and monotone function from $\mathbb{R}$ to $\mathcal{P}(\mathbb{Q})$ , $r \to S_r$ .Is it right so far? How do we continue?

 

[Evgeny.Makarov]

If $B$ is uncountable, trivially $\mathcal{P}(B)$ will contain uncountable elements of chains of $X$.

What is $X$? Which chains?

How do we continue?

What are you proving?

 

[evinda]

What is $X$? Which chains?

Sorry, I meant $B$. I edited my post.

What are you proving?

I thought that we had to prove that $\mathcal{P}(B)$ contains uncountable sets, in order to show that there is no infinite set each chain of which is countable.

But do we have to prove that $\mathcal{P} (\mathcal{P}(B))$ contains uncountable sets?

 

[Evgeny.Makarov]

I thought that we had to prove that $\mathcal{P}(B)$ contains uncountable sets, in order to show that there is no infinite set each chain of which is countable.

What exactly is the connection between

1. the presence of an uncountable set in $\mathcal{P}(B)$ (which is another way of saying that $B$ is uncountable), and
2. the length of chains of $B$?

1 is talking about possible elements of a chain, while 2 talks about a chain's length.

The connection exists, but it is not direct, I think.

So you need to prove that if $B$ is infinite, then there exist uncountable chains of $B$. (The definition of the term "chain of $B$" is in post #17.) You can consider a bijection between $\Bbb Q$ and a countable subset $B'$ of $B$ and then proceed as in the StackExchange link. You'll get an uncountable chain consisting of subsets of $B'$.

 

[evinda]

Let $B$ be an infinite set. It has an infinite countable subset $B'$.
Since $\mathbb{Q}$ in countable, we can take a bijection between $B'$ and $\mathbb{Q}$.
We define the set $\Gamma_r=\{x \in \mathbb{Q} \mid x<r\}, r \in \mathbb{R}$.
$\{\Gamma_r\}$ is a chain because if $r<s$ then $\{x\in\Bbb Q:x<r\}\subset\{ x\in\Bbb Q:x<s\}$ and it is uncountable because the $\Gamma_r$s are distinct and there are uncountably many reals.
We have a bijection between $B'$ and $\mathbb{Q}$, so there is also a bijection between $\mathcal{P}(B')$ and $\mathcal{P}(\mathbb{Q})$.
Since $\{\Gamma_r:r\in\Bbb R\}$ is an uncountable chain in $\mathcal{P}(\mathbb{Q})$, there is a corresponding uncountable chain in $\mathcal{P}(B')$ which is $\{\Gamma_r' :r \in \mathbb{R}\}$, where $\Gamma_r'=\{b\in B':f(b)<r\}$, where $f:B' \to \mathbb{Q}$ the bijection. In $\mathcal{P}(B')$ there is an uncountable chain. And $\mathcal{P}(B') \subset \mathcal{P}(B)$. That means that there is an uncountable chain in P(B). This implies that there is an uncountable family of subsets of B such that any any two sets of the family are comparable.

 

[Evgeny.Makarov]

This makes sense. Here is a sanity check: what do you mean by "in" in the phrase "$C$ is a chain in $\mathcal{P}(B)$"? Does it coincide with the meaning of "in" in the phrase "For every $x$ in $\Bbb R$..."?

 

[evinda]

This makes sense. Here is a sanity check: what do you mean by "in" in the phrase "$C$ is a chain in $\mathcal{P}(B)$"? Does it coincide with the meaning of "in" in the phrase "For every $x$ in $\Bbb R$..."?

$C$ is a subset of $\mathcal{P}(B)$ while $x$ is an element that belongs to the set of real numbers $\mathbb{R}$.

 

[Evgeny.Makarov]

Good. I am the first to say that sets of sets are confusing, but it is important to distinguish the type of each object: whether it's a set of urelements, a family of sets, a collection of families of sets (e.g., a collection of chains), etc. Correspondingly, the relationships between such objects, such as $\in$ or $\subseteq$, have to be stated correctly. This is the first step in writing a mathematical statement. When there is a mistake in the type of an object, the statement "is not even wrong": it simply does not make sense.

 

[evinda]

Good. I am the first to say that sets of sets are confusing, but it is important to distinguish the type of each object: whether it's a set of urelements, a family of sets, a collection of families of sets (e.g., a collection of chains), etc. Correspondingly, the relationships between such objects, such as $\in$ or $\subseteq$, have to be stated correctly. This is the first step in writing a mathematical statement. When there is a mistake in the type of an object, the statement "is not even wrong": it simply does not make sense.

I see... (Nod) Thank you very much! (Smile)