MHB Proving a Set Theory Statement Regarding Families of Sets

logan3
Messages
83
Reaction score
2
I was wondering if anyone could please check my work and reasoning for this problem. Thank-you! (Also, would this be considered a direct proof? How might a contradiction and IFF proof look like and compare?)

Problem: Suppose F, G1 and G2 are nonempty families of sets. Prove that if FG1G2, then ∩ G1 ∪ ∩ G2 ⊆ ∩ F.

Solution: Suppose F ⊆ G1 ∩ G2. Let A be an arbitrary element of F. Then since F ⊆ G1 ∩ G2 and A ∈ F, A ∈ G1 ∩ G2.

Let x be an arbitrary element of ∩ G1 and y be an arbitrary element of ∩ G2, which are defined since G1 and G2 are nonempty. Then by definition 2.3.5. (see below), ∀A (A ∈ G1 → x ∈ A) and ∀A (A ∈ G2 → y ∈ A). Thus, x, y ∈ A. Since A is an arbitrary element of F and x, y ∈ A, then x, y ∈ ∩ F, which is defined since F is nonempty. But x and y are arbitrary elements of ∩ G1 and ∩ G2, respectively, therefore ∩ G1 ∪ ∩ G2 ⊆ ∩ F.

Definition 2.3.5. Suppose F is a family of sets. Then the intersection is the set ∩ F and defined as: ∩ F = {x | ∀AF (xA)} = {x | ∀A (AFxA)} (Velleman, 2006, p. 77).
 
Physics news on Phys.org
Your proof is correct, but I would change one subtle point. Proofs of statements of the form $\forall x\,P(x)$ often have the following shape: fix some $x$; prove $P(x)$; since $x$ was arbitrary conclude $\forall x\,P(x)$. If you have several such lines of reasoning within one proof, they should be properly nested. For example:

Code:
fix some x
  fix some y
    prove Q(y)
  conclude ∀y Q(y)
  use ∀y Q(y) to prove P(x)
conclude ∀x P(x)

In your case you are proving $\bigcap G_1\cup\bigcap G_2\subseteq\bigcap F$, so you should start by fixing an arbitrary $x\in\bigcap G_1\cup\bigcap G_2$ and considering two cases: $x\in\bigcap G_1$ and $x\in\bigcap G_2$. (You are considering these cases simultaneously, which is fine.) Your next task is to prove $\forall A\;(A\in F\to x\in A)$, so you fix an arbitrary $A$ and assume $A\in F$. This implies $A\in G_1$ and $A\in G_2$, so $x\in A$. This concludes a subproof of $\forall A\;(A\in F\to x\in A)$, i.e., $x\in \bigcap F$. At this point $A$ does not exist because the subproof that considered a specific $A$ is closed, but $x$ still does. Finally, you conclude $\forall x\;(x\in \bigcap G_1\cup\bigcap G_2\to x\in \bigcap F)$ and close the scope of $x$.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
Back
Top