1
$\begingroup$

I'm self studying proofs (reading 'How to Prove it') and am stuck on how to prove this one. I'm hoping someone can tell me how they would go about.

A little more background. This problem is in a chapter on Quantifiers. I often get stuck when the 'Givens' in a proof all have universal quantifiers and no proven elements that I can plug in. As I have read, you can only do universal instantiation if you have a particular value you can plug in.

Anyway, any help is MUCH appreciated :)

If F ⊆ G then ∩G ⊆ ∩F

$\endgroup$
  • $\begingroup$ What do you mean by $\cap G$? Are $F$ and $G$ just sets, or families of sets? You need more than one set to do an intersection. $\endgroup$ – Nick Feb 25 '16 at 16:27
  • $\begingroup$ @Nick Families of sets. It's standard notation. $\endgroup$ – BrianO Feb 25 '16 at 16:36
  • $\begingroup$ It's bad standard notation. One should really write something like $\bigcap_i G_i$. $\endgroup$ – D_S Feb 25 '16 at 16:46
  • $\begingroup$ It's great, classic, standard notation. There's no index set, none is needed. If you want to be silly, go ahead and write$$ \bigcup_{X\in G} X $$ $\bigcap, \bigcup$ don't only apply to functions. In ZF(C), the Union axiom isn't stated in terms of functions (indexed families); it states that for every set $A$, $\bigcup A$ exists, where $\bigcup A := \{x\mid (\exists a\in A)\,x\in a \}$. $\endgroup$ – BrianO Feb 25 '16 at 19:19
1
$\begingroup$

This is a very simple definition chase. Suppose $x\in \bigcap G$. Then $(\forall X\in G)\, x\in X$. Now for any $X\in F$, we have $X\in G$ because $F\subseteq G$, so $x\in X$. That is, $(\forall X\in F)\,x\in X$. Thus, by definition, $x\in \bigcap F$.

$\endgroup$
  • $\begingroup$ Thank you BrianO! I'm learning this stuff on my own 20 years after attending any formal college. Do you happen to know any good books on this subject. $\endgroup$ – maybedave Feb 25 '16 at 17:20
  • $\begingroup$ Good books on set theory? Sure. For starters, you could do much worse than Halmos' Naive Set Theory, 1st edition online here. I recall a nice little paperback by Alexander Abian that is nothing but definitions, theorems and (mostly?) exercises. Also, another, thin paperback that develops things up through inaccessible and Mahlo cardinals, using the "Moore method" i.e. you prove everything yourself; sadly I can't recall the author. None of these volumes discuss consistency/independence results. For those, see Jech or Kunen. $\endgroup$ – BrianO Feb 25 '16 at 19:16
  • $\begingroup$ Re books, were any of those references on target? $\endgroup$ – BrianO Feb 26 '16 at 5:55
  • $\begingroup$ Naive Set Theory looks right on target. Thanks for the help! $\endgroup$ – maybedave Feb 26 '16 at 13:35
  • $\begingroup$ Good. You're welcome! $\endgroup$ – BrianO Feb 26 '16 at 13:55
1
$\begingroup$

An intuitive explanation first. Do you agree that $$ E_1 \cap E_2 \cap E_3 \subseteq E_1 \cap E_2 \subseteq E_1\ ? $$ General case. If $F \subseteq G$, we get $$ \bigcap_{i \in F} E_i = \{ x \in E \mid \text{for all $i \in F$, $x \in E_i$}\} \text{ and } \bigcap_{i \in G} E_i = \{ x \in E \mid \text{for all $i \in G$, $x \in E_i$}\} $$ Thus if $x \in \bigcap_{i \in G} E_i$, one has $x \in E_i$ for all $i \in G$ and in particular, for all $i \in F$. The inclusion $\bigcap_{i \in G} E_i \subseteq \bigcap_{i \in F} E_i$ follows.

$\endgroup$
  • $\begingroup$ Thanks J.E.Pin. I will have to review this one more deeply to intake the notation but this helps! $\endgroup$ – maybedave Feb 25 '16 at 17:33
  • $\begingroup$ @maybedave The notation in this answer isn't exactly the same as in your question. Your $F,G$ are just sets of sets, but here they're treated as index sets, and the sets whose intersection is taken are these $E_i$ things that don't figure in your question at all. For starters, think $X$ not $i$, and $E_i = E_X = X$. Thus $\bigcap_{i\in G}E_i$ is just $\bigcap_{X\in G}X = \bigcap G$. $\endgroup$ – BrianO Feb 25 '16 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.