2
$\begingroup$

This is probably an unusual case for this site. I have to note that I'm not a complete beginner in mathematics. I have seriously studied abstract algebra and analysis. Most of my studies have been successful. Before now.

However, my interests have required of me to learn set theory a little more seriously.

And I encountered that my proof skills are not that perfect, even though they were enough for more "concerete" subjects.

For example, if I want to prove that

For any function $f: X \to Y$ for any family $\{ A_i \}_{i \in I}$ of subsets of $X$ the following is true:

$f( \bigcup_{i \in I} A_i ) = \bigcup_{ i \in I} f( A_i ) $

The proof should go like this:

First, we check for the case $I = \varnothing$. Then, we assume that $I \neq \varnothing$ and go like this:

$y \in f( \bigcup_{i \in I} A_i ) \Leftrightarrow \exists x \in \bigcup_{i \in I} A_i \Leftrightarrow \exists x \in X, ( \exists i \in I, x \in A_i ) : f(x) = y$

To prove the equivalence, I need to prove the following:

$\exists i \in I: (\exists x \in A_i: y = f(x))$

So, how do I deal with similar situations in general? Note that I'm not only asking about how to prove the aformentioned case, I want to be prepared if something else arises involving multiple quatifiers in the future. Is there a particular set of such properties?

Another problem is that I'm not currently interested in mathematical logic. I only want to know the bare minimum needed for proofs in other areas of mathematics. So, please, don't reference me to long books on logic itself.

$\endgroup$

2 Answers 2

0
$\begingroup$

In your case : To prove your final equivalence here, you need to see that you can switch the order of two quantifiers of the same kind (see https://en.wikipedia.org/wiki/First-order_logic#Provable_identities), and then you can use the equivalence of expressions https://en.wikipedia.org/wiki/Quantifier_(logic)#Equivalent_expressions

You are right, you do not need to read a full book of logic in order to know what you need for most proofs. The basic axioms and identities are enough. The maths teacher I had in my first year after high school taught the class only the necessary stuff so that we wouldn't make logical errors any more. It worked well (it is not that hard to understand if taught well). I suggest you look for lessons on the subject, many can be found online.

As for proofs, you have to get used to a more analytic approach to mathematics than a visual one. You will be asked to prove theorems that are not very easy to visualise. Of course, experience helps. But I suggest you start thinking in an analytical way, look for ways to get the right sombols in the right order, rather than visualizing the concepts.

$\endgroup$
0
$\begingroup$

Short answer: Practice, practice, and more practice. It's the same answer to "How do I become better at ______?" in general. There are some good resources out there but I'm not aware of any that specifically focus on multiple quantifiers. Try How to Prove It: A Structured Approach by Velleman. I have two MS in math and I still found this to be helpful in the last few months, perhaps since I've never taken a formal course that deals specifically with proof writing. There are also several problem books available, such as Berkeley Problems in Mathematics and Problems in Real Analysis.

Longer answer: I find it unusual that this issue is coming up now if you've studied analysis before, since the definitions of various types of continuity deal with multiple quantifiers. For example:

$\forall x \ \forall y \ \forall \epsilon > 0 \ \exists \delta > 0 $ such that $|x-y| < \delta \implies |f(x) - f(y)| < \epsilon$

In any case, based on what you wrote in your question it sounds like you're relying too much on quantifiers. Not sure if that's how you approach proofs in general or if that's only how you wrote this question. But my suggestion is to write things out in English sentences rather than by using quantifiers.

For example, if I wanted to prove the example in your question:

For any function $f: X \to Y$ for any family $\{ A_i \}_{i \in I}$ of subsets of $X$ the following is true:

$f( \bigcup_{i \in I} A_i ) = \bigcup_{ i \in I} f( A_i ) $

I would proceed, at least for a rough draft, as follows for one part of the proof (and I'm using $\iota$ [iota] instead of $i$ since the browser's autocorrect is very stubborn and obnoxious with the lowercase "i").

Fix a function $f : X \to Y$. $\color{red}{\text{("Fix such-and-such" is typically paired with the $\forall$ quantifier.)}}$

Fix a family $\{A_\iota\}_{\iota \in I}$ of subsets of $X$. $\color{red}{\text{(There it is again.)}}$

Let $y \in f\left(\bigcup_{\iota \in I} A_\iota\right)$. Then there is some $x \in \bigcup_{\iota \in I} A_\iota$ such that $f(x) = y$. Since $x \in \bigcup_{\iota \in I} A_\iota$, then there must be some $\kappa \in I$ such that $x \in A_\kappa$. Therefore $y = f(x) \in f(A_\kappa)$, and so $y \in \bigcup_{\iota \in I} f(A_\iota)$. Thus $f\left(\bigcup_{\iota \in I} A_\iota\right) \subseteq \bigcup_{\iota \in I} f(A_\iota)$.

Again, that's just a rough draft and only for one part of the proof. But the point here is that writing things out in English (or whatever one's native language is) can help make things much more clear as opposed to relying mainly on quantifiers.

$\endgroup$

You must log in to answer this question.

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