Do you think you can prove that 1+1=2?
Hello guys. I've been trying to prove a sentence for over a week and I really don't know what else to do. I have tried to do direct proof and reductio ad absurdum several times, but I always reach a dead end. So, since I am already exhausted from this, I would like to propose the challenge of proving that the sentence is true. There it is:
[i]
The first sentence is the english paraphrase of "1+1=2", and the second and third are the corresponding formula. Both the second and the third are exactly the same formula, they differ only in notation (the former uses "?" for conjunction and "?" to inequality, while the latter uses "•" and "?=", and it's more spaced.).
The challenge is to prove by natural deduction that this sentence is true. Good luck.
(Oh, and it's not my homework or something, i'm just learning logic by myself. I took this example in the book "Introduction to Logic", by Harry Gensler (2ª edition: pg 207; 3ª edition: pg 294). I also sent him an e-mail asking for the solution, but he said he never tried to prove this, but that it's possible.)
[i]
? "If exactly one being is F and exactly one being is G and nothing is F-and-G, then exactly two beings are F-or-G."
? (((?x)(Fx?¬(?y)(y?x?Fy))?(?x)(Gx?¬(?y)(y?x?Gy)))?¬(?x)(Fx?Gx)) ? (?x)(?y)(((Fx?Gx)?(Fy?Gy))?(x?y)?¬(?z)((z?x?z?y)?(Fz?Gz)))
or
? (((?x)(Fx • ?(?y)(?y=x • Fy)) • (?x)(Gx • ?(?y)(?y=x • Gy))) • ?(?x)(Fx • Gx)) ? (?x)(?y)(((Fx ? Gx) • (Fy ? Gy)) • (?x=y • ?(?z)((?z=x • ?z=y) • (Fz ? Gz))))
The first sentence is the english paraphrase of "1+1=2", and the second and third are the corresponding formula. Both the second and the third are exactly the same formula, they differ only in notation (the former uses "?" for conjunction and "?" to inequality, while the latter uses "•" and "?=", and it's more spaced.).
The challenge is to prove by natural deduction that this sentence is true. Good luck.
(Oh, and it's not my homework or something, i'm just learning logic by myself. I took this example in the book "Introduction to Logic", by Harry Gensler (2ª edition: pg 207; 3ª edition: pg 294). I also sent him an e-mail asking for the solution, but he said he never tried to prove this, but that it's possible.)
Comments (65)
“1”, “+”, “=“, and “2” have specific meanings by convention. So, “1+1=2” is a tautology. It has to be true given the meanings of the terms used. There is nothing to prove.
We are complex beings in a complex mysterious universe, the workings of which we only have a vague clue.
So we use these complex mysterious minds/brains to perceive and understand the question 'is 1+1=2 true'........people often try to prove it is true by showing a person gather a single apple and the place it next to another apple....and I think 'are you serious?'..have you any idea how complex an apple is?
What exactly is an apple? It is the perception by a complex mind, in a complex universe of various components...we really can't be sure of the 'truth' of what is going on..are we supposed to build a model of reality, actually inside that reality, and compare the concept of adding two apples together and then counting the result, and the consider we have proved that 1 apple placed next to 1 apple leads to the conclusion that this process proves that 1+1=2 is a statement of truth somehow.
And as Noah Te Stoete said, it is just a statement that doesn't mean anything outside of maths....it is no different than saying that 1=1...or 683=683.. :)
Oh, and where did you get that tautology should not be proven? One thing is a self-evident tautology like 1=1 or p->p; another thing is something like "(((?x)(Fx?¬(?y)(y?x?Fy))?(?x)(Gx?¬(?y)(y?x?Gy)))?¬(?x)(Fx?Gx)) ? (?x)(?y)(((Fx?Gx)?(Fy?Gy))?(x?y)?¬(?z)((z?x?z?y)?(Fz?Gz)))", which you can't trivially say whether it's a valid inference or not only by reading it's terms and connectives.
You don't think either is worthwhile. Okay. So what am I supposed to do with that information now?
Would you seek to prove this tautology: “A bachelor is an unmarried man”?
I suppose you could try, but why?
Why not try to prove something that isn’t self-evident instead?
My objection was that self-evident equations shouldn’t have to be proven (given the meanings of the terms used). Why not prove something interesting?
I’m saying that “1” has a meaning. “+” has a meaning. “=“ has a meaning. “2” has a meaning. Given these meanings, “1+1=2” must be true all the time. You’re making something simple more complicated than it really is. What kind of nut goes about “proving” something that every child can show with apples as @wax suggested?
"exactly one being is F and exactly one being is G and nothing is F-and-G"
Because the conclusion permits (x or y) or (x & y) to be F & G.
How is it irrelevant when it is in the topic title?
I brushed over that the first time I read your post. That's an English paraphrase of 1=1=2 according to whom? It certainly bears no resemblance to anything at all that I think when I think about "1=1=2"
Why does the conclusion permits "(x or y) or (x & y) to be F & G" if it is said that nothing is simultaneously F and G?
The reference is in the text, just read. And it's not 1=1=2, it's 1+1=2.
Your stated conclusion
(?x)(?y)(((Fx?Gx)?(Fy?Gy))?(x?y)?¬(?z)((z?x?z?y)?(Fz?Gz)))
does not say that X or Y cannot simultaneously be F and G.
Therefore your conclusion is weaker than your premise.
Anyway, so I guess I'd need to ask Mr. Gensler what the heck he's talking about re that being an English translation.
This is said in the antecedent, not in the conclusion. Maybe this image can help the visualization.
Well, I guess it can be taken as a paraphrase that is an interpretation of the mathematical assertion. I really don't know, and I really don't care if it's really 1+1=2, I just wanted to see if someone could prove the validity. Anyway, he's e-mail is [email protected]. He usually answer quickly, so please let us know if you get an answer.
Correct, hence your conclusion permits a possibility denied by your premise.
? (((?x)(Fx • ?(?y)(?y=x • Fy)) • (?x)(Gx • ?(?y)(?y=x • Gy))) • ?(?x)(Fx • Gx)) ? (?x)(?y)(((Fx ? Gx) • (Fy ? Gy)) • (?x=y • ?(?z)((?z=x • ?z=y) • (Fz ? Gz))))
Only thing I can offer is that if the author didn't attempt it but knows that it is true, maybe the important thing to cultivate in the exercise is an intuition for why it must follow somehow. I imagine you already have this intuition - F is an exclusive property of x, G is an exclusive property of y, for some x Fx, for some y Gy; ie only x if F and only y is G. The only way for there to be a z such that Fz or Gz is if z=x or z=y, and the only way to be both is z=y=x. By eliminating the x=y case, you force the implication that (such a z exists implies z=x or z=y) which by the exclusivity of F and G we know can't be the case. Since we've exhausted the only way such a z can exist and it lead to a contradiction, no such z exists.
P?Q doesn't permit Q?¬P in a consistent logic. That case is different to the set-theoretic case, where Fx ? Gx permits Fx ? Gx and is therefore a weaker statement than the latter.
Of course, in a sense your antecedent might be said to contain your "conclusion" as a weaker premise, but i think it is a mistake to think of your right-hand side as a conclusion because it must forever remain tied to the antecedent if it isn't to be misinterpreted as allowing F and G to be overlapping sets containing multiple members... assuming of course, that you want to represent the number 2 as a union of pairwise disjoint singleton sets.
No. That's the definition of 2.
...at least as I'd say it.
The positive integers can be defined by repeated addition of the multiplicative identity (1).
Such things as 2 + 2 = 4 can be proved by the additive associative axiom.
Michael Ossipoff
10 F
Of course, but you were saying about the consequent only, not about the entire implication. That is why I said that in "P?Q", "Q", alone, permits "¬Q".
Quoting sime
Hm, I don't know if I understood. For instance, in the sentence "(¬(?x)(Fx?Gx) ? Fx) ? (Fx?Gx)", you would say that the consequent "Fx?Gx" permits "Fx?Gx"? (It's just an example for me to understand, I'm not saying this is the case)
Quoting sime
Well, why couldn't we treat it like so? I mean, I could say that the antecedent is the premise and the consequent is the conclusion, and since the conclusion follows from the premise, I could represent they in a conditional statement. I didn't understand part of your latter paragraph... English isn't my native language and i'm not familliar with a lot of terms you used.
The statement of "1+1=2" in Peano arithmetic is:
S0 + S0 = SS0
Because "1" means S0 and "2" means SS0. S is the 'successor' function.
That is not a tautology. It has to be proved. The proof, as I recall, is not long.
1+1=0
in binary arithmetic, and
1+1=1
in Boolean arithmetic.
Hello. Can you please state what you understand to be a tautology?
If someone asks a mathematician or logician to prove "1+1=2", they will do so using axioms and theorems of arithmetic. They will not take it as self-evident.
Hi. You could try breaking the implication into smaller expressions and treating them as an argument. You have 3 main conjuncts in the antecedent; treat them as your premises.
Treat your consequent as the conclusion you want to prove using the 3 premises.
"If exactly one object has property F and exactly one object has property G and no object has both properties, then there are exactly two objects that satisfy one or more of the two properties"
It sounds like it should be true.
I skipped symbolic logic in college because I didn’t need it to graduate. The joke about nerds and getting laid was just that, a joke.
The idea of mathematical tautologies was suggested to me by my professor who got his PhD from UCLA.
A theory T in a language L is a set of syntactically valid statements in L such that any statement that can be deduced from a finite collection of statements in T, using the deduction rules of L, is also in T.
We say a collection A of statements in L is a set of 'axioms' for T if T is the intersection of all theories containing A. We say 'T is generated by A'.
The set of tautologies in L is the theory generated by the empty set (ie no axioms).
I re expressed some of the formulas. Proving the conclusion using the 3 premises would be equivalent to proving that the initial implication is true.
P1: ?x(Fx ? ?y(Fy ? y=x) )
P2: ?x(Gx ? ?y(Gy ? y=x) )
P3: ?x(¬Fx ? ¬Gx )
C1: ?x?y[ (
( (Fx ? Gx) ? (Fy ? Gy) )
? (x?y) )
? ?z((Fz ? Gz) ? (z=x ? z=y) )]
I don’t understand what you mean by this.
the number of beings with an attribute combination which contains F or G is sum over all possible attribute combinations which contain F or G, of the number of beings with that combination.
The only possible attribute combinations which contain F or G are of the types
1) F not G
2) G not F
3) F and G
Define Nf as the number of beings with F only. Define Ng as the number of beings with G only. Define Nf&g as the number of beings with F and G. Define Nf|g as the number of beings with at least one of F or G. Then
Nf|g = Nf + Ng + Nf&g
for the special case that Nf = 1, Ng = 1, and Nf&g = 0, Nf|g=2
P1: ?x(Fx ? ?y(Fy ? y=x) )
P2: ?x(Gx ? ?y(Gy ? y=x) )
P3: ?x¬(Fx ? Gx )
C1: ?x?y[ (
(Fx ? Gx)
? (Fy ? Gy)
? (x?y) )
? ?z((Fz ? Gz) ? (z=x ? z=y) )]
We write ‘a’ for an object that satisfies P1 and ‘b’ for an object that satisfies P2.
So we have:
3: Fa ? ?y(Fy ? y=a) (? elimination, P1)
4: Gb ? ?y(Gy ? y=b) (? elimination, P2)
which we split into
5: Fa
6: ?y(Fy ? y=a)
7: Gb
8: ?y(Gy ? y=b)
9: ¬(Fa ? Ga ) (substitution of a into P3)
10: ¬(Fb ? Gb ) (substitution of b into P3)
Next:
11: ....Fb (Cond Hyp)
12: ....Fb ? Gb (9, 7)
13: ....Contradiction (10, 12)
14: ¬Fb (close Cond Proof, negating 11)
15: ....Ga (Cond Hyp)
16: ....Fa ? Ga (15, 5)
17: ....Contradiction (9, 16)
18: ¬Ga (close Cond Proof, negating 15)
We hypothesise that a and b are objects that satisfy the existence claim in C1.
We’ll prove the conjuncts in C1 in turn, for the case x=a, y=b.
19: Fa ? Ga (5, OR introduction) [1st conjunct proven]
20: Fb ? Gb (7, OR introduction) [2nd conjunct proven]
21: ....a=b (Cond Hyp)
22: ....Ga (7, 21, substitution on =)
23: ....Fa ? Ga
24: ....¬(Fa ? Ga) (P3, specification of x=a)
25: ....Contradiction (23, 24)
26: a ? b (close Cond Proof, negating 21) [3rd conjunct proven]
27: Fz ? z=a (specify y=z in 6)
28: z ? a ? ¬Fz (reversal of 27)
29: Gz ? z=b (specify y=z in 8)
31: .... Fz ? Gz (Cond Hyp)
32: ........ z ? a (Cond Hyp)
33: ........ ¬Fz (Modus Ponens 28, 32)
34: ........ Gz (31, 33, OR elimination)
35: ........ z=b (MP 29, 34)
36: .... ¬ (z=a) ? (z=b) (close Cond Proof 32-35)
37: .... z=a ? z=b
38: Fz ? Gz ? z=a ? z=b (close Cond Proof 31-37) [4th conjunct proven]
39: (Fa ? Ga) ? (Fb ? Gb) ? a ? b ? (Fz ? Gz ? z=a ? z=b) (AND introduction 19, 20, 26, 38)
40: ?x ?y (Fx ? Gx) ? (Fy ? Gy) ? x ? y ? (Fz ? Gz ? z=x ? z=y) (? introduction 39)
1- Fx' ? ?y(Fy ? y=x') Existential instantiation (P1)
2- Gy' ? ?y(Gy ? y=y') Existential instantiation (P2)
3- Fx' Simplification (1)
4- ?y(Fy ? y=x') Simplification (1)
5- Gy' Simplification (2)
6- ?y(Gy ? y=y') Simplification (2)
7- ¬Fx' ? ¬Gx' Universal instantiation (P3)
8- ¬Fy' ? ¬Gy' Universal instantiation (P3)
9- ¬Gx' Disjunctive syllogism (3,7)
10- ¬Fy' Disjunctive syllogism (5,8)
11- Fx' ? ¬Fy' Adjunction (3,10)
12- ¬(x' = y') Identity (11)
13- Fx' ? Gx' Addition (3)
14- Fy' ? Gy' Addition (5)
15- ?y(Fy ? y=x' ? y=y') Addition (4)
16- ?y(Gy ? y=x' ? y=y') Addition (6)
17- ?y(Fy ? y=x'?y=y') ? ?y(Gy ? y=x' ? y=y') Adjunction (15,16)
18- ?y[(Fy ? y=x'?y=y') ? (Gy ? y=x'?y=y')] Universal distribution (17)
19- ?y[(¬Fy ?(y=x'?y=y')) ? (¬Gy ? (y=x'?y=y'))] Implication (18)
20- ?y[(¬Fy ? ¬Gy) ? (y=x'?y=y')] Distribution law (19)
21- ?y[(Fy ? Gy) ? (y=x'?y=y')] Implication (20)
C - ?x?y[ ( ( (Fx ? Gx) ? (Fy ? Gy) ) ? (x?y) )
? ?z((Fz ? Gz) ? (z=x ? z=y) )] Existential Generalization (12,13,14,21)
[math]1 \overset{\text{def}}{\equiv} S(0) = 0 + 1[/math]
and
[math]2 \overset{\text{def}}{\equiv} S(1) = 1 + 1[/math]
and I'm done.
Yeah, as I said before, I just put this title because the book says that sentence is the representation of 1+1=2, but it isn't really important to what I was proposing. The title was just something that i thought it would call people's attention; maybe it's inadequate.
1+1 = 1+S(0) = S(1+0) = S(1) = 2
- where the S function = "the successor of".
In its long form, of course, it would require an exposition of the Peano Axioms, which goes beyond the scope of this post.
You mean aside from the answers by and ?
1 + 1 = 2 is True.
It is True in the sense of an indisputable fact of a mathematical operation... It as its own statement is its own means and ends.
Let those who wish to quibble over the foundation of maths, epistemic truth and semantic version of truth without substantiating any terms do so at their leisure.
Suppose 1 + 1 =/= 2
1 + 1 - 1 =/= 2 - 1
1 =/= 1
Contradiction
Therefore 1 + 1 = 2
Yes, once we have accepted the axioms and theorems of set theory, number theory and arithmetic, we find that "1 + 1 = 2" is defined to be true. It cannot but be true.
Philosophy?