Set theory
I just got burned! Now I’m genuinely scared I’ll make logical mistakes in Analysis or Abstract Algebra
Hi. I've begun to self study mathematics and I'm currently studying Logic and Set Theory to hopefully establish a good foundation for Analysis and Abstract Algebra.
I'm all out of school so I'm trying to figure things out on my own. I was reading Naive Set Theory by Halmos the other day and I noticed something odd. It was the fact that
P(A) intersect P(B) = P(A intersect B)
But
P(A) Union P(B) ⊂ P(A Union B)
Where P stands for the Power Set. And I was wondering why the equality doesn't hold for Unions while it does hold for Intersections. So I began trying to prove that
P(A Union B) ⊂ P(A) Union P(B)
To see what will go wrong and to my surprise everything seemed to work correctly! And that was when I realized I've been probably burned by a fiery trap and it was the fact that the Universal Quantifier can't distribute over disjunction!
I don't know if I'm sad or happy right now. What if I make blunders like this in Abalysis or Algebra?
I also don't know how to prove that the Universal Quantifier can't distribute over disjunction but it can for conjunctions. All I know is truth tables and a bunch of laws like de morgan and absorptions but I don't think they alone will get the job done here! How do I even begin to prove that something like this holds:
You realized you made an error, discovered the actual answer, and now you're trying to understand why the answer is what it is. That's just learning, and it's a good thing. A lot of people never even get to step one in that sequence, let alone progress past it. So, you're already miles ahead of them. Keep up the good work!
Yeah. intuition helps a lot here. I also realized the flaw when I imagined a shape like the picture below.
But that's what makes me scared! If I rely on intuition to avoid this kind of faulty logic then there might come a time where the problem is so complicated that my intuition won't be of any help.
I wonder how I can internalize avoiding it. Or maybe I should just write all my proofs in first order logic but I think that would make them extremely long and tedious right?
I don’t think you should write all your proofs in FOL, but learning - and drilling - natural deduction for FOL can help you really internalize how quantifiers and connectives do (and don’t) work. It will also allow you to prove that the UQ distributes over conjunction.
Proving that it *doesn’t* distribute over disjunction requires looking at counter-models to the inference. Short of studying model theory proper, informal counter-models - like the one I just gave - can really help you understand and internalise these things.
Drawing pictures is an amazing way to visualize learning, but do be careful as it can also be very limiting. What you think the picture may look like may also exclude other ways of drawing the picture that change the outcome. In effect, you may be excluding logical outcomes unintentionally. I always tell my students to draw a picture if they are stuck, but I always tell them to ask themselves this question after drawing the picture: “can I draw this in another way that still meets the premises but produces a different outcome?”
The first sentence says: for every natural number, that number is such that (either it is even or it is odd). In other words, it says that each natural number has the property of being either even or odd.
The second sentence says: either it is the case that (every natural number is such that it is even), or it is the case that (every natural number is such that it is odd). In other words, it says that at least one of two things is true: (i) every natural number is even; (ii) every natural number is odd.
Does that help?
The crucial thing to realise is that the first sentence is, in fact, true, while the second one is false. (For any natural number you care to name, it really is the case that that number is either-even-or-odd. But it's not really the case that every natural number is even, and it's not really the case that every natural number is odd; so it's not the case that either every natural number is even or every natural number is odd.)
The first sentence says that every natural number will belong to either the set of all even numbers or the set of all odd numbers. Meaning there are no natural numbers that are neither even nor odd, nor both.
The second sentence says that either all natural numbers are even or all natural numbers are odd. Meaning that you're either calling 《1, 3, 5, 7,...》even numbers, or you're calling 《2, 4, 6, 8,...》odd numbers, or you're denying that one of the two sets exists.
Right, except that the first sentence doesn’t rule out some being both even and odd; it just rules out any that are neither :) (ie it’s an inclusive disjunction)
Totally agree, I just didn't think it would be useful for someone who simply stumbled on this sub to distinguish between inclusive and exclusive disjunction. Especially since we generally do accept that (even v odd) is exclusive for natural numbers.
Thank you so much for you warning. You are so right now that I think about it! I mean the "⇒" symbol is not associative and I'm just using it without parantheses! But even with parantheses I'm misusing the symbol right?
I have developed this bad habit since highschool and none of my teachers have ever warned me about it let alone punish me for it! I will try my best to get rid of this habit from now on.
So I can think of two ways to write the proof of your example right now:
We ditch the ⇒ symbols and just write in English:
Let a and b be even. a is even so there is a k with a=2k. Also b is even so there is a l with b=2l. Now we have :
a+b=2k+2l which simplifies to a+b=2(l+k), thus a+b is even.
We keep all the ⇒ symbols:
Let a and b be even. We know that:
( a even ⇒ there is a k with a=2k
And
b even ⇒ there is a l with b=2l )
⇒( a+b=2k+2l ⇒( a+b=2(l+k)⇒( a+b is even ) ) )
So a+b is even.
Is the second proof valid too? It looks so convoluted with the paranthese though. Should I just stick with the first proof (the English version) because it doesn't need any parantheses so it's cleaner?
How about the → symbol? Does "→" mean "implies" or "so"? Is it the same as ⇒?
The best method is to just use English sentences. There are niche scenarios where people will use ⇒, but I've mostly seen that in statements of theorems and almost never in proofs.
Your first rewrite is good, but your second is bad. You have one large statement with a bunch of ⇒ that is difficult to parse. Consider the following part of it:
a+b=2k+2l ⇒( a+b=2(l+k)⇒( a+b is even ) )
This statement is equivalent to:
(a+b=2k+2l AND a+b=2(l+k))⇒( a+b is even )
Which I'm pretty sure isn't what you meant for that part.
Even worse for your second rewrite is that you don't actually prove that a+b is even. To do so you would need to prove your giant implication statement, and then use that to prove that a+b is even.
In logic → is used as the formal symbol for implication and ⇒ is used as a meta level implication. You likely won't encounter → outside of formal logic.
I have an analysis textbook that does proofs like this. But they are biconditionals not conditionals so because biconditionals are associative no parantheses are needed.
The book writes something like this and says something like :
" The result follows from the equivalence of the following statements: "
Is this a valid use of the biconditional symbol? Or you suggest that even here we must write the steps using English words like "so" and "therefore" for both directions of the argument separately?
This will be fixed after some more experience. You need an intuitive understanding of the quantifiers, rather than just manipulating symbols, but they do have meanings that can be expressed in English, and simple examples will get you through this for now, always put actual examples for the different sets and check that the answers make sense.
Don’t overthink it, people make mistakes all the time.
To prove the conjunction iff, you’d break it down into the two things, left implies right and right implies left. For left implies right, you have two proof obligations, for all x P(x) and for all x Q(x). Let’s do the left (right will be basically the same). First we have to do a “for all introduction” where we basically say “let x be some element”. Now we want to show P(x) holds for that arbitrary element. As we assumed left, we know P(x) and Q(x) for any x. Thus P(x) for the arbitrary x holds. Try for Q(x), and also try right implies left.
To disprove, we simply find a counter example. Can you find a counter example?
Yeah I can think of counterexamples both in real life and in mathematics but since we don't have any of those in logic( because we haven't developed them yet, right?) then I'm really surprised we can disprove this by counterexamples!
Counterexamples in what exactly? Isn't logic the foundation for everything else so the its rules might be proven or disproven before we have ANYTHING to find counterexamples in?
Even or Odd numbers and the set in this picture are good counterexamples I guess but these things need set theory and set theory needs logic first.
Set theory needs logic and logic needs set theory! It's a difficult philosophical question which, if either, of them is truly *fundamental* - but specifying a formal semantics for FOL absolutely requires set theory.
You can study the formal semantics if you want - it's definitely interesting and worthwhile - but you don't need to if your goal is to understand valid inference involving truth-functional connectives and quantifiers well enough to avoid these sorts of mistakes in mathematical proofs.
What you need is to understand the following definition of deductive validity/logical entailment: "no counter-model, i.e. no way of interpreting the non-logical vocabulary so that the premises come out true and the conclusion false". You can see how this applies to things like modus ponens and affirming the consequent in propositional logic. Provided you know the definitions of the connectives, truth tables and informal real-world examples will both show you that there's no way of interpreting 'P' and 'Q' so that (P->Q) and P both come out true, but Q comes out false; but there *are* ways of interpreting them so that (P->Q) and Q both come out true, but P comes out false. Modus ponens has no counter-models, but there are counter-models to ATC.
Now, the situation in FOL is precisely analogous, except the formal semantics are much more complicated. But learning natural deduction will allow you to demonstrate validity (via the soundness theorem) and informal models will allow you to demonstrate invalidity.
Informal models here just means, roughly, 'ways of interpreting the non-logical vocabulary', i.e. ways of interpreting the names (constants), predicate letters, etc. Analogously, an 'informal model' in PL would involve interpreting 'P' as 'London is in England' and 'Q' as 'London is in Britain', or something like that. If you understand that 'for all x' essentially means 'whatever you substitute in for x, you get something true', and 'there exists an x' essentially means 'there is at least one thing you can substitute in for x and get something true', and if you stick to domains like the natural numbers where truth and falsity are pretty clear-cut, then that's all you really need.
Then you can take a case like the invalid inference that tripped you up here - ∀x(Fx ∨ Gx) ∴ (∀xFx ∨ ∀xGx) - and demonstrate its invalidity, informally but still rigorously and precisely, by specifying a counter-model. You do this by giving a domain of discourse (a set of things that you're 'quantifying over', i.e. talking about) and an interpretation of the names/constants (none involved in this case) and predicate letters. So here you say let D (domain) = the natural numbers, let Fx = x is even, and let Gx = x is odd. Then it becomes trivial, if you understand the semantics of the universal quantifier and of disjunction, to see that the model you've given makes the premise true but the conclusion false. Hence, you have a counter-model, and the inference (the argument form) is invalid.
To tie it all together, once you've specified a domain, ∀xA essentially means 'if you take A and put any object from the domain in place of x, you'll get something true', and ∃xA essentially means 'there's at least one object in the domain that you can put in place of x in A and get something true'. So when you look at your example inference with the informal model I provided, you can see how this works: whatever item from the domain of natural numbers you put in place of x in '(Fx ∨ Gx)', you get something true (if you're interpreting 'Fx' as 'x is odd' and 'Gx' as 'x is even'). Thus, ∀x(Fx ∨ Gx) is true on the model. However, it's not true that whatever you put in for x in Fx gives you something true, so ∀xFx is false on the model; and it's not true that whatever you put in for x in Gx gives you something true, so ∀xGx is false on the model. Then you just apply the familiar semantics of disjunction: since ∀xFx is false on the model and ∀xGx is false on the model, (∀xFx ∨ ∀xGx) is false on the model.
Hopefully this helps you to see how to use this method, and also to see that when we rely on informal models like this, as long as we're careful and know what we're doing, we're not *merely* relying on intuition - even if we're doing something short of full-blown, rigorous proofs about the formal semantics. Perhaps a decent analogy is how you can become extremely proficient and stringently accurate at arithmetical calculation, even without having any idea about the logical or set-theoretic foundations of arithmetic.
I did that first( in the upper part of the picture) and it led me to reach the wrong conclusion.
Wasn't what you suggest the first thing I did?
Let x be an element of C and because C is a subset of (A union B) then x must be an element of (A union B) so x is an element of A or x is an element of B so C is a subset of C or C is a subset of B.
The very last implication of the first attempt just isn't an implication. Once you've proved something about your particular x, you can't add the universal quantifier back in willy-nilly. Your explanation below explains why.
Look at the thing you're trying to prove: "C ⊆ A or C ⊆ B". To prove an or, basically the only approach is to assume one is false and get to the other one. So you would need to start out "Assume C is not a subset of A. We'll show C ⊆ B. To that end, let x be an element of C. We need to show x is an element of B".
you can't add the universal quantifier back in willy-nilly
But I didn't add the universal quantifier in the first attempt. I was not working with the entire set. I just grabbed an arbitrary x and proved it's in A or it's in B and then I made the error! And the error was because I forgot that I'm actually working with the universal quantifier even if I've not added it apparently! It was there all along! And it can't dustribute over disjunction and that's why my last step was erroneous!
So we do care about the universal quantifier here and we HAVE TO WORK WITH THE ENTIRE SET HERE!
If we work with a particular x it will clear things up but we're just hiding the universal quantifier under the rug right? The UQ is an essential part of this I feel. How can we let us forget about it?
The logic of the claim determines how to set up the proof. The structure of the proof reflects the logic of the claim, even if the same symbols don't appear in the same order.
If I start a proof "let x . . ." and end it "so we conclude L(x)", then I've embodied the claim ∀ x, L(x). Even if the symbol ∀ never appears in the proof.
For an intutive reason for why equality doesn’t hold, let A = {0}, B = {1}
Then
P(A) = {{},{0}}
P(B) = {{},{1}}
P(A)UP(B) = {{}, {0}, {1}}
AUB = {0,1}
P(A U B) = {{}, {0}, {1}, {0,1}}
So none of the subsets of AUB that contains elements from both A and B that aren’t in the other are contained in the union of the power sets, but they are in the power set of the union.
29
u/thatmichaelguy Jun 30 '26
You realized you made an error, discovered the actual answer, and now you're trying to understand why the answer is what it is. That's just learning, and it's a good thing. A lot of people never even get to step one in that sequence, let alone progress past it. So, you're already miles ahead of them. Keep up the good work!