Wronsonia8g

Answered

2022-07-10

Big intersection operation

$\mathrm{\varnothing}\ne A\subseteq B\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\bigcap B\subseteq \bigcap A.$

In each case, the proof is straightforward. For example, in the last case, we assume that every member of A is also a member of B. Hence if $x\in \bigcap B$, i.e., if x belongs to every member of B, then a fortiori x belongs to every member of the smaller collection A. And consequently $x\in \bigcap A$.

I wonder if the last part is really a proof. It is okay to assume $x\in \bigcap B$ and arrive at $x\in \bigcap A$. But can I use this reasoning "then a fortiori x belongs to every member of the smaller collection" in a proof exercise? It looks like just using intuition (it does not seem rigorous).

$\mathrm{\varnothing}\ne A\subseteq B\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\bigcap B\subseteq \bigcap A.$

In each case, the proof is straightforward. For example, in the last case, we assume that every member of A is also a member of B. Hence if $x\in \bigcap B$, i.e., if x belongs to every member of B, then a fortiori x belongs to every member of the smaller collection A. And consequently $x\in \bigcap A$.

I wonder if the last part is really a proof. It is okay to assume $x\in \bigcap B$ and arrive at $x\in \bigcap A$. But can I use this reasoning "then a fortiori x belongs to every member of the smaller collection" in a proof exercise? It looks like just using intuition (it does not seem rigorous).

Answer & Explanation

esperoanow

Expert

2022-07-11Added 11 answers

Step 1

I do not agree. It is a very rigorous argument, and I cannot see how it could be made more formal. Indeed, the proof assumes that $A\subseteq B$, which means that (I quote from the proof)

every member of A is also a member of B.

Step 2

From that and from the fact that "x belongs to every member of B", it follows immediately that, in particular, "x belongs to every member of A". It is just a syllogistic inference roughly of the form "if X implies Y and Y implies Z, then X implies Z", which does not require any further justification.

I do not agree. It is a very rigorous argument, and I cannot see how it could be made more formal. Indeed, the proof assumes that $A\subseteq B$, which means that (I quote from the proof)

every member of A is also a member of B.

Step 2

From that and from the fact that "x belongs to every member of B", it follows immediately that, in particular, "x belongs to every member of A". It is just a syllogistic inference roughly of the form "if X implies Y and Y implies Z, then X implies Z", which does not require any further justification.

Alissa Hancock

Expert

2022-07-12Added 4 answers

Step 1

In case it helps, here is a different style of proof of the same.

For all x, we have

$\begin{array}{rl}\phantom{\rule{1em}{0ex}}& x\in \bigcap A\\ \equiv \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\text{\u201c}{\textstyle \text{definition of}\phantom{\rule{thickmathspace}{0ex}}\bigcap \phantom{\rule{thickmathspace}{0ex}}}\text{\u201d}\\ \phantom{\rule{1em}{0ex}}& \u27e8\mathrm{\forall}S::S\in A\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}x\in S\u27e9\\ \Leftarrow \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\text{\u201c}{\textstyle \phantom{\rule{thickmathspace}{0ex}}A\subseteq B\phantom{\rule{thickmathspace}{0ex}}\text{, so by the definition of}\phantom{\rule{thickmathspace}{0ex}}\subseteq \phantom{\rule{thickmathspace}{0ex}}\text{,}}\\ \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\phantom{\text{\u201c}}{\textstyle \phantom{\rule{thickmathspace}{0ex}}T\in A\Rightarrow T\in B\phantom{\rule{thickmathspace}{0ex}}\text{for any}\phantom{\rule{thickmathspace}{0ex}}T\phantom{\rule{thickmathspace}{0ex}}\text{; logic}}\text{\u201d}\\ \phantom{\rule{1em}{0ex}}& \u27e8\mathrm{\forall}S::S\in B\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}x\in S\u27e9\\ \equiv \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\text{\u201c}{\textstyle \text{definition of}\phantom{\rule{thickmathspace}{0ex}}\bigcap \phantom{\rule{thickmathspace}{0ex}}}\text{\u201d}\\ \phantom{\rule{1em}{0ex}}& x\in \bigcap B\end{array}$

Step 2

Or equivalently, by the definition of $\phantom{\rule{thickmathspace}{0ex}}\subseteq \phantom{\rule{thickmathspace}{0ex}}$, $\phantom{\rule{thickmathspace}{0ex}}\bigcap B\subseteq \bigcap A\phantom{\rule{thickmathspace}{0ex}}$.

Note that weakening the antecedent of $\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}$ (from $\phantom{\rule{thickmathspace}{0ex}}S\in A\phantom{\rule{thickmathspace}{0ex}}$ to $\phantom{\rule{thickmathspace}{0ex}}S\in B\phantom{\rule{thickmathspace}{0ex}}$), causes the expression $\phantom{\rule{thickmathspace}{0ex}}S\in A\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}x\in S\phantom{\rule{thickmathspace}{0ex}}$ as a whole to be strengthened, and therefore the middle step uses $\phantom{\rule{thickmathspace}{0ex}}\Leftarrow \phantom{\rule{thickmathspace}{0ex}}$, 'flipping' the direction of the implication.

In case it helps, here is a different style of proof of the same.

For all x, we have

$\begin{array}{rl}\phantom{\rule{1em}{0ex}}& x\in \bigcap A\\ \equiv \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\text{\u201c}{\textstyle \text{definition of}\phantom{\rule{thickmathspace}{0ex}}\bigcap \phantom{\rule{thickmathspace}{0ex}}}\text{\u201d}\\ \phantom{\rule{1em}{0ex}}& \u27e8\mathrm{\forall}S::S\in A\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}x\in S\u27e9\\ \Leftarrow \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\text{\u201c}{\textstyle \phantom{\rule{thickmathspace}{0ex}}A\subseteq B\phantom{\rule{thickmathspace}{0ex}}\text{, so by the definition of}\phantom{\rule{thickmathspace}{0ex}}\subseteq \phantom{\rule{thickmathspace}{0ex}}\text{,}}\\ \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\phantom{\text{\u201c}}{\textstyle \phantom{\rule{thickmathspace}{0ex}}T\in A\Rightarrow T\in B\phantom{\rule{thickmathspace}{0ex}}\text{for any}\phantom{\rule{thickmathspace}{0ex}}T\phantom{\rule{thickmathspace}{0ex}}\text{; logic}}\text{\u201d}\\ \phantom{\rule{1em}{0ex}}& \u27e8\mathrm{\forall}S::S\in B\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}x\in S\u27e9\\ \equiv \phantom{\rule{1em}{0ex}}& \phantom{\rule{1em}{0ex}}\text{\u201c}{\textstyle \text{definition of}\phantom{\rule{thickmathspace}{0ex}}\bigcap \phantom{\rule{thickmathspace}{0ex}}}\text{\u201d}\\ \phantom{\rule{1em}{0ex}}& x\in \bigcap B\end{array}$

Step 2

Or equivalently, by the definition of $\phantom{\rule{thickmathspace}{0ex}}\subseteq \phantom{\rule{thickmathspace}{0ex}}$, $\phantom{\rule{thickmathspace}{0ex}}\bigcap B\subseteq \bigcap A\phantom{\rule{thickmathspace}{0ex}}$.

Note that weakening the antecedent of $\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}$ (from $\phantom{\rule{thickmathspace}{0ex}}S\in A\phantom{\rule{thickmathspace}{0ex}}$ to $\phantom{\rule{thickmathspace}{0ex}}S\in B\phantom{\rule{thickmathspace}{0ex}}$), causes the expression $\phantom{\rule{thickmathspace}{0ex}}S\in A\phantom{\rule{thickmathspace}{0ex}}\Rightarrow \phantom{\rule{thickmathspace}{0ex}}x\in S\phantom{\rule{thickmathspace}{0ex}}$ as a whole to be strengthened, and therefore the middle step uses $\phantom{\rule{thickmathspace}{0ex}}\Leftarrow \phantom{\rule{thickmathspace}{0ex}}$, 'flipping' the direction of the implication.

Most Popular Questions