3
$\begingroup$

Say we have a collection $\Omega$ of sets, and a statement $P(s)$ which can be either true or false depending on the input set $s$. Say we take two arbitrary sets $a$ and $b$ in $\Omega$ and that for all $a,b\in\Omega$, $P(a) \land P(b) \implies P(a \cap b)$.

Does this then imply that $\displaystyle \forall a\in\Omega\; P(a) \implies P\left(\bigcap_{s\in\Omega}s\right)$? Intuitively I can see how it would be true for collections with a finite or even countably infinite sizes, as you could just keep appending intersections with another element until you "got them all", like say if $\Omega = \{s_0,s_1,s_2,\cdots\}$ then you can do $$\displaystyle P(s_0) \Rightarrow P(s_0 \cap s_1) \Rightarrow P(s_0 \cap s_1 \cap s_2) \Rightarrow \cdots \Rightarrow P\left(\bigcap_{i\in\mathbb{N}}s_i\right)$$ but I don't necessarily know if this generalises to collections with uncountably infinite sizes since there really isn't that sort of inductive reasoning you can do to recursively append intersections when you're in the uncountably infinite. Does this intuitive implication hold true for collections of any size?

$\endgroup$
2
  • 4
    $\begingroup$ I think probably "it" isn't even true for countably infinite intersections (it's a bit hard to say as your question is not very precise). You seem to be asking "does closure under finite intersections imply closure under infinite intersections", and the answer to that is "no". Some natural examples which I expect will have been discussed on this site before are $P(s)$ being "$s$ is a subset of $\Bbb N$ such that $\Bbb N \setminus s$ is finite", or "$s$ is an open subset of $\Bbb R$". Can you see why these properties are stable under finite but not infinite intersections? $\endgroup$ Apr 22 at 13:22
  • 1
    $\begingroup$ So, to get your conclusion, $P$ will need some additional "continuity" property. $\endgroup$
    – GEdgar
    Apr 22 at 13:50

5 Answers 5

10
$\begingroup$

This is not true, even for countable intersections. For instance, let $$\Omega=\left\{\left(-\frac{1}{n},\frac{1}{n}\right)\mid n\in\mathbb{N}\right\}$$ be a collection of open intervals in $\mathbb{R}$ which contain $0$. For $s\subset\mathbb{R}$ let $P(s)$ be true if $s$ is open and false otherwise. Hence $\left\{0\right\}$ is the intersection of all elements of $\Omega$ and $P(\left\{0\right\})$ is false, but $P(s)$ is true for all $s\in\Omega$.

$\endgroup$
1
  • 1
    $\begingroup$ +1 Good example. Note the definition of "topological space", where a finite intersection of open sets is open, an arbitrary intersection of closed sets is closed. $\endgroup$
    – GEdgar
    Apr 22 at 13:53
7
$\begingroup$

This fails even for countably infinite collections. Not only is there no "uncountably infinite induction", but there isn't even any "countably infinite induction" of the kind you are thinking about.

Take $P(s) = \exists s, x \in s$. Colloquially, $P(s) = $ "$s$ is not empty".

Define $R_n = \{k \in \mathbb N \mid k \ge n\}$ and take $\Omega = \{R_n \mid n \in \mathbb N\}$.

Then $P(a)$ is true for all $a \in \Omega$, and $P(a\cap b)$ is also true for all $a,b \in \Omega$, hence $P(a) \wedge P(b) \implies P(a \cap b)$ is true for all $a,b \in \Omega$.

But $\cap_{k \in \mathbb N} R_n = \emptyset$ and $P(\emptyset)$ is false.

$\endgroup$
2
  • $\begingroup$ This was the exact counterexample I was thinking of posting when I saw the question. Now I don't need to. Have a +1. :) $\endgroup$ Apr 22 at 22:09
  • $\begingroup$ Induction in general doesn't apply to limit ordinals. For instance, $\frac 1 n$ is positive for all $n>0$, but the limit is not. The induction step always goes from a finite index to another finite index, so you never get to an infinite one. There are transfinite versions of induction, but it requires the additional "continuity" induction hypothesis that $\lim P(a_n) \rightarrow P(\lim a_n)$. $\endgroup$ Apr 23 at 1:58
2
$\begingroup$

It's worth keeping in mind that proving something is true for finite collections of all sizes is not sufficient to prove that it is true for infinite collections, even if they are countable! That is, the usual indictive arguments don't get you "to infinity."

For example, consider the set $\mathcal{I}$ of all intervals of the form $$\left(0,\frac{1}{n}\right)$$ for some positive integer $n,$ and consider the statement $P(\mathcal{S})$ about families $\mathcal{S}$ of subsets of $\Bbb R$ given by $$\exists I\in\mathcal{I}:\forall S\in\mathcal{S},I\subseteq S,$$ or equivalently, $$\exists I\in\mathcal{I}:I\subseteq\bigcap_{S\in\mathcal{S}}S.$$

Then one can show that $P(\mathcal{S})$ for any finite subset $\mathcal{S}$ of $\mathcal{I},$ but that $\neg P(\mathcal{S})$ for any infinite subset of $\mathcal{I}.$

$\endgroup$
2
$\begingroup$

Small counterexample:

$\Omega=\{\{1,2\},\{1,3\},\{2,3\}\}$

$P(s): s\not=\emptyset$

$\endgroup$
1
1
$\begingroup$

For unions: the union of two finite sets is a finite set, but an infinite union of finite sets is infinite. An an uncountable union of measure zero sets can have nonzero measure.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .