2
  1. A relation, R, is euclidean iff ∀x∀y∀z((Rxy & Rxz) → Ryz). Prove that identity is euclidean.

  2. Give a derivation for ~(Fa ↔ Fb) ⊢ a≠b

4) Not sure what to do next.

5) I know that to get to the conclusion, I would have to use a RAA rule. But I don't know how to convert the premise into an easier sentence, using sentential logic.

2

Problem 4:

-        1.   ∀x[∀y[Rxy ↔ x=y]]                Definition of Identity
{2}      2.   Rab & Rac                         Assum.
{2}      3.   Rab                               2 &E
-        4.   ∀y[Ray → a=y]                    1 UE
-        5.   Rab → a=b                        4 UE
{2}      6.   a=b                              3,5 MP
{2}      7.   Rac                              2 &E
{2}      8.   Rbc                              6,7 =E
-        9.   (Rab & Rac) → Rbc                4,8 CP
-        10.  ∀z[(Rab & Raz) → Rbz]            9 UI
-        11.  ∀y[∀z[(Ray & Raz) → Ryz]]        10 UI
-        12.  ∀x[∀y[∀z[(Rxy & Rxz) → Ryz]]]    12 UI

Here's another version:

{1}      1.   a=b & a=c                        Assum.
{1}      2.   a=b                              1 &E
{1}      3.   a=c                              1 &E
{1}      4.   b=c                              2,3 =E
-        5.   (a=b & a=c) → b=c                1,4 CP
-        6.   ∀z[(a=b & a=z) → b=z]            5 UI
-        7.   ∀y[∀z[(a=y & a=z) → y=z]]        6 UI
-        8.   ∀x[∀y[∀z[(x=y & x=z) → y=z]]]    7 UI

Problem 5:

{1}      1.   ~(Fa ↔ Fb)                       Prem.
{2}      2.   a=b                              Assum.
{3}      3.   Fa                               Assum.
-        4.   Fa → Fa                          3,3 CP
{2}      5.   Fa → Fb                          2,4 =E
{2}      6.   Fb → Fa                          2,4 =E
{2}      7.   (Fa → Fb) & (Fb → Fa)            5,6 &I
{2}      8.   Fa ↔ Fb                          7 ↔I
{1,2}    9.   ~(Fa ↔ Fb) & (Fa ↔ Fb)           1,8 &I
{1}      10.  a≠b                              2,9 RAA
  • For problem 4, shouldn't line 2,3 be "UI" instead of "UE"? Also, shouldn't line 8,9,10 be "UE" instead of "UI"? – K.Wong Dec 2 '16 at 18:00
  • Also, what is the name for the rule "=E"? Is it the same as the substitution rule for predicate logic? – K.Wong Dec 2 '16 at 18:05
  • @K.Wong. UE stands for universal quantifier elimination which is what took place on lines 2 and 3. Likewise, UI is universal introduction for introducing the quantifiers on 8,9 and 10. And =E would be substitution. Different systems of logic label the rules differently. You'll have to adapt it to whatever system your using. – user3017 Dec 2 '16 at 18:12
  • Ahh okay. My professor labeled UI as "universal instantiation," and UE as "universal generalization." One last question. For problem 4, since it is asking to prove that the identity is euclidean, would it be " ⊢ ∀x∀y∀z((Rxy & Rxz) → Ryz) "? Therefore, the last sentence has to depend on the null set? – K.Wong Dec 2 '16 at 18:20
  • @K.Wong. I just updated my answer by defining Rxy as an identity. I think that's the best approach to take. – user3017 Dec 2 '16 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.