Results 1 to 3 of 3

Math Help - Finding a counterexample

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    32

    Finding a counterexample

    Find a domain for the quantifiers in \exists x\exists y(x\neq y \wedge \forall z(z\neq x \wedge z\neq y)) such that this statement is true.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    I doubt it is possible to find the same domain for all three quantifiers. How can one avoid instantiating z, in particular, to x?

    In fact, I used my favorite proof assistant program to prove the negation of this statement. The actual code (the proof is omitted) is the following.

    Code:
    Parameter T : Type.
    
    Theorem t :
      ~ (exists x : T, exists y : T, (x <> y /\ forall z : T, (z <> x /\ z <> y))).
    Proof. ... Qed.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2010
    Posts
    32
    Yeah, I was able to prove it after a couple of tries as well, on this website: The Logic Machine: Logic Software at Texas A&M University
    |-~$x$y(~x=y&@z(~z=x&~z=y))
    OK 1 (1) $x$y(~x=y&@z(~z=x&~z=y)) A
    OK 2 (2) $y(~a=y&@z(~z=a&~z=y)) A
    OK 3 (3) ~a=b&@z(~z=a&~z=b) A
    OK 3 (4) @z(~z=a&~z=b) 3&E
    OK 3 (5) ~a=a&~a=b 4@E
    OK 3 (6) ~a=a 5&E
    OK (7) a=a =I
    OK 3 (8) ~$y(~a=y&@z(~z=a&~z=y)) 6,7RAA(2)
    OK 2 (9) ~$y(~a=y&@z(~z=a&~z=y)) 2,8$E(3)
    OK 2 (10) ~$x$y(~x=y&@z(~z=x&~z=y)) 2,9RAA(1)
    OK 1 (11) ~$x$y(~x=y&@z(~z=x&~z=y)) 1,10$E(2)
    OK (12) ~$x$y(~x=y&@z(~z=x&~z=y)) 1,11RAA(1)
    Congratulations. Your proof is correct.
    I don't know why the book asks you to do something that's impossible. Thanks though.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counterexample Help
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 5th 2010, 08:24 AM
  2. Counterexample
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 26th 2010, 09:17 AM
  3. Counterexample
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: October 28th 2009, 03:06 PM
  4. counterexample for matrices
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 18th 2009, 11:22 PM
  5. A counterexample
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 1st 2006, 09:06 AM

Search Tags


/mathhelpforum @mathhelpforum