I Proof of ##\cap_{i\in \cup F}A_i=\cap_{x\in F}(\cap_{i\in X}A_i)##?

elias001
Messages
389
Reaction score
26
TL;DR Summary
Quantifier rules of inferences questions in the proof of ##\cap_{i\in \cup F}A_i=\cap_{x\in F}(\cap_{i\in X}A_i)##?
The screenshots below are taken from the 2nd editon of the book How to Prove it A structured approach By: Daniel Velleman and and 3rd edition of the book's solution manual. (Page 5)

The question on page 4 exercise 5b corresponds to the solution in page 5 exercise 6b

Page 1
Velleman 1.webp

Page 2
Velleman 2.webp

Page 3
Velleman 3.webp

Page 4
Velleman 4.webp

Page 5
Velleman 5.webp


Questions

In the above screenshots, pages one to three lists the inference rules for proving with universal quantifier. But for the exercise 5b in screenshot page 4, the solution exercise 6b shown on page 5 in that screenshot where it says:

Let ##X\in F## be arbitrary. ##i\in X## be arbitrary.

Is the author using using universal instantiation for both ##X## and ##i##?
 
Physics news on Phys.org
Dye to the possibility of the screenshots for pages 4 and 5 being not displaying clearly. I have typed out the relevant protion of the exercise and its proof below.

Exercise (Screenshot Page 4)


5. Suppose ##\mathcal{F}## is a nonempty family of sets. Let ##I=\cup\mathcal{F}## and ##J=\cap\mathcal{F}.## SUppose that also that ##J\neq \emptyset##, and notice that it follows that for every ##X\in \mathcal{F}, X\neq\emptyset,## and also that ##I\neq\emptyset.## Finally, suppose that ##\{A_i\mid i\in I\}## is an indexed family of sets.

(a) Prove that ##\cup_{i\in I}A_i=\cup_{X\in F}(\cup_{i\in X}A_i).##

(b) Prove that ##\cap_{i\in I}A_i=\cap_{X\in F}(\cap_{i\in X}A_i).##

Solution (Screenshot Page 5)

6 (b) Suppose ##x\in \cap_{i\in I}A_i.## Let ##X\in \mathcal{F}## be arbitrary. Let ##i\in X## be arbitrary. Then since ##i\in X## and ##X\in \mathcal{F}##, ##i\in \cup\mathcal{F}=I.## Since ##x\in \cap_{i\in I}A_i,## it follows that ##x\in A_i##, Since ##i## was arbitrary, we can conclude that ##x\in \cap_{i\in X}A_i.## Since ##X## was arbitrary, it follows that ##x\in \cap_{X\in \mathcal{F}}(\cap_{i\in X}A_i).##

Now suppose ##x\in \cap_{X\in \mathcal{F}}(\cap_{i\in X}A_i).## Let ##i\in I## be arbitrary. Since ##I=\cup \mathcal{F}##, this means that we can choose ##X_0\in \mathcal{F}## such that ##i\in X_0.## Since ##x\in \cap_{X\in \mathcal{F}}(\cap_{i\in X}A_i)## and ##X_0\in \mathcal{F},x\in \cap_{i\in X_0}A_i.## But then since ##i\in X_0, x\in A_i.## Since ##i## was arbitrary, we can conclude that ##x\in \cap_{i\in I}A_i.##

In the above proof for the following cases where ##X,i## were first introduced:

Forward direction:

Let ##X\in \mathcal{F},## be arbitrary,

Let ##i\in X,## be arbitrary,

Background direction:

Let ##i\in I## be arbitrary,

We can choose ##X_0\in \mathcal{F}##,

which quantifier rule of inferences were used?
 
Since no one else has responded, I'll give you my answer.

I don't know whether universal instatiation covers the case of selecting an arbitrary element from a set. Or, whether this is another law of axiomatic set theory. It's not clear to me from the text alone.
 
@PeroK the reason I ask this question is because the quantifier statement is the exact same as the following: ##\bigcap_{f\in {\bigcup_{\alpha\in I}S_{\alpha}}}V(f)=\bigcap_{\alpha\in I}\bigcap_{f\in S_{\alpha}}V(f)## from beginning commutative algebra text in the topic of algebraic variety. In Many beginning commutative algebra texts where that statement is introduced, the author would simply state: it is obvious from the definition. If you try to prove it the algebraically like how one would prove Demorgan's law, you would find that the algebraic calulational steps needs inference rule from prenex normal form.
 
Thread 'Determine whether ##125## is a unit in ##\mathbb{Z_471}##'
This is the question, I understand the concept, in ##\mathbb{Z_n}## an element is a is a unit if and only if gcd( a,n) =1. My understanding of backwards substitution, ... i have using Euclidean algorithm, ##471 = 3⋅121 + 108## ##121 = 1⋅108 + 13## ##108 =8⋅13+4## ##13=3⋅4+1## ##4=4⋅1+0## using back-substitution, ##1=13-3⋅4## ##=(121-1⋅108)-3(108-8⋅13)## ... ##= 121-(471-3⋅121)-3⋅471+9⋅121+24⋅121-24(471-3⋅121## ##=121-471+3⋅121-3⋅471+9⋅121+24⋅121-24⋅471+72⋅121##...
Back
Top