Proving $\bigcap B$ is an Inductive Set

[evinda]

Hello! (Wave)

A set $A$ is called inductive set, if $\varnothing$ is an element of $A$ and for each $x \in A$ its next element, $x'=x \cup \{ x \}$ belongs to $A$.

I want to show that if $B$ is a nonempty set of inductive sets, then $\bigcap B$ is an inductive set.That's what I have tried:$B$ is a nonempty set of inductive sets: $\forall b \in B: b \text{ is an inductive set}$

$$x \in \bigcap B \leftrightarrow \forall b \in B: x \in b$$

Is it right so far? How could we continue? (Thinking)

 

[Siron]

Correct. As $b$ is inductive, what does $x \in b$ implies?

 

[evinda]

Correct. As $b$ is inductive, what does $x \in b$ implies?

It means that $x'=x \cup \{ x \} \in b$, right? (Thinking)

But, what can we conclude from that? (Thinking)

 

[Siron]

It means that $x'=x \cup \{ x \} \in b$, right? (Thinking)

But, what can we conclude from that? (Thinking)

It means indeed that $x'=x \cup \{x\} \in b$ and this holds $\forall b \in B$. Therefore ...

 

[evinda]

It means indeed that $x'=x \cup \{x\} \in b$ and this holds $\forall b \in B$. Therefore ...

What could we conclude from that? (Thinking)

 

[Evgeny.Makarov]

I am willing to help you with this problem under one condition: in turn, you write a detailed description of what you do and don't understand and, once you know the solution, you can say what prevented you from seeing it in the first place.

So, to begin with, do you think about intersection of a family of set as a sequence of symbols:
\[
x \in \bigcap B \leftrightarrow \forall b \in B: x \in b
\]
or do you think about some real-life situations? For example, one may imagine employees of some company, which are divided into different groups: male and female; top management, middle management and workers; or sales and production departments. Then one can take several of such groups and consider people that belong to all of them (e.g., female sales mid-level managers). Do you view generalized intersection purely as a formula, or do you have an intuition like this in mind?

 

[evinda]

I am willing to help you with this problem under one condition: in turn, you write a detailed description of what you do and don't understand and, once you know the solution, you can say what prevented you from seeing it in the first place.

Ok.. (Wait)

So, to begin with, do you think about intersection of a family of set as a sequence of symbols:
\[
x \in \bigcap B \leftrightarrow \forall b \in B: x \in b
\]
or do you think about some real-life situations? For example, one may imagine employees of some company, which are divided into different groups: male and female; top management, middle management and workers; or sales and production departments. Then one can take several of such groups and consider people that belong to all of them (e.g., female sales mid-level managers). Do you view generalized intersection purely as a formula, or do you have an intuition like this in mind?

Yes, I think about intersection of a family of set as a sequence of symbols. I didn't have an intuition like this in mind.. Would this help? (Thinking)

 

[Evgeny.Makarov]

Yes, I think about intersection of a family of set as a sequence of symbols. I didn't have an intuition like this in mind..

Well, it's impossible to do mathematics this way. I cannot work with a mathematical concept until I get an intuition about it. I often imagine mathematical concepts as some geometric 3D objects, though not necessarily fully concrete ones. For example, I may think about a function as a row of arguments that disappears into the distance, and against each argument the corresponding value returned by the function is located.

Or consider the equivalence
\[
(\neg\forall x\,P(x))\leftrightarrow \exists x\,\neg P(x).
\]
When I am thinking why it is true, I don't think about a sequence of inference rules in mathematical logic that derives this formula. Rather, I imagine a multitude of, say, vertical poles in front of me. Those that satisfy $P$ are tall, and the others are short. The left-hand side says that all poles cannot be long. How can this happen? At least one pole must be short. On this level, this fact is obvious even to kindergartners. If you try to construct a formal proof of this statement written as a sequence of symbols, you may have some difficulty. But unless you are studying formal proofs, this is a wrong approach to understand this equivalence. So if you take this wrong approach and ask about it on the forum, what are helpers supposed to say? They are likely to think, "By the time a person learns to read, he or she is supposed to understand this fact. I have no idea what I can rely on to explain it. I don't know what preschool children find obvious."

Similarly, consider the intersection of two sets: it's the set of objects belonging to both sets. You know that $\varnothing$ belongs to both sets (since by assumption the sets are inductive). Does this imply that $\varnothing$ is in the intersection? Does the fact that $\varnothing$ belongs to both sets imply that it belongs to both sets? I do believe that if I replace $\varnothing$ with John and sets with two groups of children, any kindergartner would understand it. Then what are you asking us to rely on in explaining this?

Do you see now why $\varnothing\in\bigcap B$ where $B$ is a family of inductive sets? If so, then what prevented you from seeing it earlier?

 

[evinda]

Well, it's impossible to do mathematics this way. I cannot work with a mathematical concept until I get an intuition about it. I often imagine mathematical concepts as some geometric 3D objects, though not necessarily fully concrete ones. For example, I may think about a function as a row of arguments that disappears into the distance, and against each argument the corresponding value returned by the function is located.

Or consider the equivalence
\[
(\neg\forall x\,P(x))\leftrightarrow \exists x\,\neg P(x).
\]
When I am thinking why it is true, I don't think about a sequence of inference rules in mathematical logic that derives this formula. Rather, I imagine a multitude of, say, vertical poles in front of me. Those that satisfy $P$ are tall, and the others are short. The left-hand side says that all poles cannot be long. How can this happen? At least one pole must be short. On this level, this fact is obvious even to kindergartners. If you try to construct a formal proof of this statement written as a sequence of symbols, you may have some difficulty. But unless you are studying formal proofs, this is a wrong approach to understand this equivalence. So if you take this wrong approach and ask about it on the forum, what are helpers supposed to say? They are likely to think, "By the time a person learns to read, he or she is supposed to understand this fact. I have no idea what I can rely on to explain it. I don't know what preschool children find obvious."

I see... (Smile)

Similarly, consider the intersection of two sets: it's the set of objects belonging to both sets. You know that $\varnothing$ belongs to both sets (since by assumption the sets are inductive). Does this imply that $\varnothing$ is in the intersection? Does the fact that $\varnothing$ belongs to both sets imply that it belongs to both sets? I do believe that if I replace $\varnothing$ with John and sets with two groups of children, any kindergartner would understand it. Then what are you asking us to rely on in explaining this?

Do you see now why $\varnothing\in\bigcap B$ where $B$ is a family of inductive sets? If so, then what prevented you from seeing it earlier?

I just looked at the definition of $\bigcap B$: $x \in \bigcap B \leftrightarrow (\forall b \in B) x \in b$, but I didn't consider two inductive sets $C,D$ such that $B=C \cap D$.

Now, it is easier to see that $\varnothing \in C \wedge \varnothing \in D \rightarrow \varnothing \in B$.

$n \in B \rightarrow n \in C \cap D \rightarrow n \in C \wedge n \in D \rightarrow n' \in C \wedge n' \in D \rightarrow n' \in C \cap D \rightarrow n' \in B $

 

[Evgeny.Makarov]

This is correct, and the same idea works for the intersection of an arbitrary family of sets. The only remark is that in post #1, $B$ denotes a family of sets, while in the last post, $B$ denotes the intersection of this family. If $B=\{C,D\}$ then let's call $K=\bigcap B=C\cap D$. Then in the last two lines, every $B$ should be replaced by $K$. Again, similar proof works for arbitrary $B$.

A good idea is to make a syntactic distinction between sets and families of sets by choosing variables from different alphabets. For example, we can have $B,C,D,\dots$ range over sets and $\mathcal{B},\mathcal{C},\mathcal{D},\dots$ range over collections of sets. (Of course, the latter are also sets, but in our context they are viewed as sets whose elements are other sets and not, say, numbers). Then we could say,
\[
x\in\bigcap\mathcal{B}\implies \forall B\in\mathcal{B}\;x\in B\implies\forall B\in\mathcal{B}\;x'\in B\implies x'\in\bigcap\mathcal{B}.
\]

 

[evinda]

This is correct, and the same idea works for the intersection of an arbitrary family of sets. The only remark is that in post #1, $B$ denotes a family of sets, while in the last post, $B$ denotes the intersection of this family. If $B=\{C,D\}$ then let's call $K=\bigcap B=C\cap D$. Then in the last two lines, every $B$ should be replaced by $K$. Again, similar proof works for arbitrary $B$.

A good idea is to make a syntactic distinction between sets and families of sets by choosing variables from different alphabets. For example, we can have $B,C,D,\dots$ range over sets and $\mathcal{B},\mathcal{C},\mathcal{D},\dots$ range over collections of sets. (Of course, the latter are also sets, but in our context they are viewed as sets whose elements are other sets and not, say, numbers). Then we could say,
\[
x\in\bigcap\mathcal{B}\implies \forall B\in\mathcal{B}\;x\in B\implies\forall B\in\mathcal{B}\;x'\in B\implies x'\in\bigcap\mathcal{B}.
\]

So, can we justify like that the fact that $\bigcap \mathcal{B}$ is an inductive set? (Thinking)

$$x \in \bigcap \mathcal{B} \rightarrow (\forall B \in \mathcal{B} ) x \in B \rightarrow ( \forall B \in \mathcal{B} ) x' \in B \Leftrightarrow x \in \bigcap \mathcal{B} \rightarrow (\forall x \in \mathcal{B}) (x \in B \rightarrow x' \in B)$$

 

[Evgeny.Makarov]

$$x \in \bigcap \mathcal{B} \rightarrow (\forall B \in \mathcal{B} ) x \in B \rightarrow ( \forall B \in \mathcal{B} ) x' \in B \Leftrightarrow x \in \bigcap \mathcal{B} \rightarrow (\forall x \in \mathcal{B}) (x \in B \rightarrow x' \in B)$$

This is not entirely correct. Suppose that $\mathcal{B}$ is a collection of sets containing natural numbers. Then $\bigcap\mathcal{B}$ is a set of numbers, so $x\in\bigcap\mathcal{B}$ means that $x$ is a number. In contrast, in $\forall x\in\mathcal{B}$, $x$ is a set. Using the same variable to denote different things is possible, but preferably not in the same formula, and it makes understanding more difficult. Moreover, in $x\in B\to x'\in B$, $B$ is not defined. Is it an element of $\mathcal{B}$? Finally, the second occurrence of $x\in\bigcap\mathcal{B}$ should probably be $x'\in\bigcap\mathcal{B}$.

So, imagine that $\mathcal{B}$ is a family of sets whose elements are not themselves sets (e.g., $\mathcal{B}$ is a family of sets of numbers of a collection of groups of people) and for each object use are using ($x$, $B$ and so on) ask yourself what its "type" is: Is it a number, a set of numbers, or a family of sets?

I would also avoid being carried away with writing a proof using symbols only and avoiding words. More often than not, it complicates understanding instead of making it stricter. It's OK to repeatedly use arrow to mean "therefore":
\[
\text{claim 1}\implies\text{claim 2}\implies\text{claim 3}\implies\dots.
\]
However, when it is mixed with other connectives, as in
\[
\text{claim 1}\implies\text{claim 2}\iff\text{claim 3}
\]
it becomes confusing. Is claim 3 equivalent to the fact that claim 1 implies claim 2? Or does claim 1 imply claim 2, which is also equivalent to claim 3?

 

[evinda]

This is not entirely correct. Suppose that $\mathcal{B}$ is a collection of sets containing natural numbers. Then $\bigcap\mathcal{B}$ is a set of numbers, so $x\in\bigcap\mathcal{B}$ means that $x$ is a number. In contrast, in $\forall x\in\mathcal{B}$, $x$ is a set. Using the same variable to denote different things is possible, but preferably not in the same formula, and it makes understanding more difficult. Moreover, in $x\in B\to x'\in B$, $B$ is not defined. Is it an element of $\mathcal{B}$? Finally, the second occurrence of $x\in\bigcap\mathcal{B}$ should probably be $x'\in\bigcap\mathcal{B}$.

So, imagine that $\mathcal{B}$ is a family of sets whose elements are not themselves sets (e.g., $\mathcal{B}$ is a family of sets of numbers of a collection of groups of people) and for each object use are using ($x$, $B$ and so on) ask yourself what its "type" is: Is it a number, a set of numbers, or a family of sets?

I would also avoid being carried away with writing a proof using symbols only and avoiding words. More often than not, it complicates understanding instead of making it stricter. It's OK to repeatedly use arrow to mean "therefore":
\[
\text{claim 1}\implies\text{claim 2}\implies\text{claim 3}\implies\dots.
\]
However, when it is mixed with other connectives, as in
\[
\text{claim 1}\implies\text{claim 2}\iff\text{claim 3}
\]
it becomes confusing. Is claim 3 equivalent to the fact that claim 1 implies claim 2? Or does claim 1 imply claim 2, which is also equivalent to claim 3?

Would it be better to justify it like that? (Thinking)$$x \in \bigcap \mathcal{B} \leftrightarrow (\forall b \in \mathcal{B} ) x \in b $$

$b$ is an inductive set, so:

$$(\forall b \in \mathcal{B} ) ( \varnothing \in b )$$

So, we conclude that $\varnothing \in \bigcap \mathcal{B}$.

$$x \in \bigcap \mathcal{B} \rightarrow \forall b \in B: x \in b \overset{ \text{ b is an inductive set }}{\rightarrow} \forall b \in B: x' \in b \rightarrow x' \in \bigcap \mathcal{B}$$

Therefore, $\bigcap \mathcal{B}$ is an inductive set.

 

[Evgeny.Makarov]

Yes, this is OK.

$$x \in \bigcap \mathcal{B} \rightarrow \forall b \in B: x \in b \dots$$

This should say $\forall b\in\mathcal{B}$.

 

[evinda]

Yes, this is OK.

This should say $\forall b\in\mathcal{B}$.

Oh yes, you are right... (Nod)

Thank you very much! (Smile)