Why is this true? $(exists x)(P(x) Rightarrow (forall y) P(y))$












39












$begingroup$


Why is this true?



$(exists x)(P(x) Rightarrow (forall y) P(y))$






logic quantifiers predicate-logic







share|cite|improve this question











$endgroup$








  • 4




    $begingroup$
    Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
    $endgroup$
    – MJD
    Jun 5 '13 at 21:14








  • 1




    $begingroup$
    See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com
    $endgroup$
    – Dan Christensen
    Jun 3 '14 at 20:56
















39












$begingroup$


Why is this true?



$(exists x)(P(x) Rightarrow (forall y) P(y))$






logic quantifiers predicate-logic







share|cite|improve this question











$endgroup$








  • 4




    $begingroup$
    Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
    $endgroup$
    – MJD
    Jun 5 '13 at 21:14








  • 1




    $begingroup$
    See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com
    $endgroup$
    – Dan Christensen
    Jun 3 '14 at 20:56














39












39








39


12



$begingroup$


Why is this true?



$(exists x)(P(x) Rightarrow (forall y) P(y))$






logic quantifiers predicate-logic







share|cite|improve this question











$endgroup$




Why is this true?



$(exists x)(P(x) Rightarrow (forall y) P(y))$






logic quantifiers predicate-logic




logic quantifiers predicate-logic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jun 17 '13 at 20:32









Peter Smith

40.6k340120




40.6k340120










asked Jun 5 '13 at 20:46









MatsMats

447510




447510








  • 4




    $begingroup$
    Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
    $endgroup$
    – MJD
    Jun 5 '13 at 21:14








  • 1




    $begingroup$
    See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com
    $endgroup$
    – Dan Christensen
    Jun 3 '14 at 20:56














  • 4




    $begingroup$
    Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
    $endgroup$
    – MJD
    Jun 5 '13 at 21:14








  • 1




    $begingroup$
    See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com
    $endgroup$
    – Dan Christensen
    Jun 3 '14 at 20:56








4




4




$begingroup$
Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
$endgroup$
– MJD
Jun 5 '13 at 21:14






$begingroup$
Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
$endgroup$
– MJD
Jun 5 '13 at 21:14






1




1




$begingroup$
See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com
$endgroup$
– Dan Christensen
Jun 3 '14 at 20:56




$begingroup$
See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com
$endgroup$
– Dan Christensen
Jun 3 '14 at 20:56










11 Answers
11






active

oldest

votes


















27












$begingroup$

Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $phi$, either $phi$ or $lnotphi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $phi to psi$ is true if and only if either $phi$ is false or $psi$ is true.



By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:




  • If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.

  • If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.


Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.



Alternatives



Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($phi lor lnotphi$); and the material conditional ($(phi to psi) equiv (lnotphi lor psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.




  • Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $exists x.(P(x) to forall y.P(y))$ should be vacuously false.


  • Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $phi$ or $lnotphi$.”

  • There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
    $endgroup$
    – Thomas Andrews
    Jun 5 '13 at 21:09






  • 1




    $begingroup$
    @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
    $endgroup$
    – Joshua Taylor
    Jun 5 '13 at 21:27








  • 1




    $begingroup$
    @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
    $endgroup$
    – Joshua Taylor
    Jun 5 '13 at 21:37








  • 1




    $begingroup$
    Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
    $endgroup$
    – Thomas Andrews
    Jun 5 '13 at 22:24






  • 1




    $begingroup$
    @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
    $endgroup$
    – Joshua Taylor
    Jun 5 '13 at 23:56



















10












$begingroup$

Hint: The only way for $Aimplies B$ to be false is for $A$ to be true and $B$ to be false.



I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $forall y: P(y)$ is true "vacuously," but $exists x: Q$ is not true for any $Q$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
    $endgroup$
    – Mats
    Jun 5 '13 at 20:54






  • 2




    $begingroup$
    Instead of $A Rightarrow B$, think of $lnot A lor B$.
    $endgroup$
    – copper.hat
    Jun 5 '13 at 20:56








  • 1




    $begingroup$
    That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
    $endgroup$
    – Thomas Andrews
    Jun 5 '13 at 20:57












  • $begingroup$
    So in my case, there exists something that isn't a person, hence the whole statement is true?
    $endgroup$
    – Mats
    Jun 5 '13 at 21:00






  • 4




    $begingroup$
    @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
    $endgroup$
    – Joshua Taylor
    Jun 5 '13 at 21:03





















5












$begingroup$

The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:Xrightarrow{0,1}$. Does the following proposition seem strange and unintuitive?



Theorem. There is an element $min X$ such that, if $f(m)=1$, then $f(x)=1$ for all $xin X$.



Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.



Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
    $endgroup$
    – Ryan Reich
    Jun 5 '13 at 23:39










  • $begingroup$
    In mathematics, there's no such thing as an uniform description.
    $endgroup$
    – justt
    Jun 17 '13 at 14:35



















3












$begingroup$

In classical logic the following equivalence is logically valid:
$$
exists x (varphiRightarrowpsi)Longleftrightarrow(forall xvarphiRightarrowpsi)
$$
providing that $x$ is a variable not free in $psi$. So the formula in question is logically equivalent to $forall xP(x)Rightarrowforall yP(y)$.



Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $neg P(a)$ is true. In (i) $P(x)Rightarrowforall y P(y)$ must be true, so $exists x(P(x)Rightarrowforall y P(y))$ is true. In (ii) $P(a)Rightarrowforall y P(y)$ must be true, therefore the sentence in question must be true as well.






share|cite|improve this answer









$endgroup$





















    3












    $begingroup$

    In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes



    $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



    or equivalently



    $$exists x(xin U wedge (P(x) Rightarrow forall y(yin URightarrow P(y))))$$
    Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:



    For non-empty $U$, consider two cases:



    $$forall yin U (P(y))lor negforall yin U (P(y))$$



    In each case, obtain



    $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$
    For empty U, assume to the contrary that



    $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



    and obtain a contradiction.



    Full text of formal proof at http://dcproof.com/Mats.htm






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
      $endgroup$
      – Dan Christensen
      Oct 9 '18 at 18:52












    • $begingroup$
      @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
      $endgroup$
      – Dan Christensen
      Oct 10 '18 at 3:38



















    3












    $begingroup$

    Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$quad$
    $$
    ((forall y)P(y)) lor (lnot (forall x) P(x)) \
    ((forall y)P(y)) lor ((exists x)lnot P(x))\
    (text{anything} Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow text{anything})) \
    ((forall x)P(x) Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
    ((exists x)(P(x) Rightarrow (forall y)P(y))) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
    (exists x)(P(x) Rightarrow (forall y)P(y))
    $$






    share|cite|improve this answer











    $endgroup$





















      1












      $begingroup$

      The location of the parentheses is crucial here. Note that $(exists x)(P(x) Rightarrow (forall y) P(y))$ is very different from $(exists x)(P(x)) Rightarrow (forall y) P(y))$. To see why the former statement is true, consider its negation which is



      $$forall x (P(x) wedge neg forall P(x)) equiv forall x(P(x) wedge exists x neg P(x))$$



      which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.






      share|cite|improve this answer











      $endgroup$





















        1












        $begingroup$

        Translate it to english:




        In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.




        For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)




        • If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) Rightarrow (forall y) P(y)$ is vacuously true, because $P Rightarrow Q$ is true whenever $P$ is false.


        • If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) Rightarrow (forall y) P(y)$ is then true because $P(a)$ is true, and $(forall y) P(y)$ is true.


        • If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) Rightarrow (forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.



        But let's look at it by taking the contradiction and seeing where it leads: $neg(exists x)(P(x) Rightarrow (forall y) P(y))$




        In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.




        we can move the negative inside: $(forall x)neg(P(x) Rightarrow (forall y) P(y))$




        In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.




        Then we can integrate the $neg$ into the formula by way of $neg (Q rightarrow P) = Q landneg P$ to arrive at: $(forall x)(P(x) landneg (forall y) P(y))$



        But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.






        share|cite|improve this answer









        $endgroup$





















          1












          $begingroup$

          To add a proof in Fitch style, natural deduction:



          2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
          
3  | | |________ Pa                New Subproof for -> Introduction
          
4  | | | |_____b                   variable for Universal Introduction
          
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
          
6  | | | | | |__ Pb                New Subproof for -> Introduction
          
7  | | | | | |   _|_               5,6 _|_ Introduction
          
8  | | | | | |   VyPy              7 _|_ Elimination
          
.  | | | | | <-------------------- end subpproof
          
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
          
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
          
11 | | | | |     _|_               2,10 _|_ Introduction
          
.. | | | | <---------------------- end subpproof
          
12 | | | |       ~~Pb              5-11 ~ Introduction
          
13 | | | |       Pb                12 ~~ Elimination
          
.. | | | <------------------------ end subpproof
          
14 | | |         VyPy              4-13 Universal Introduction
          
.. | | <-------------------------- end subpproof
          
15 | |           Pa -> VyPy        3-14 -> Introduction
          
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
          
17 | |          _|_                2,16 _|_ Introduction
          
.. | <---------------------------- end subpproof
          
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
          
19 |            Ex(Px -> VyPy)     18 ~~ Elimination


          This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist



          For explanation I compare this "paradox" with:



          If the last person has left the room, all people have left the room.



          Therefore



          There is a person if he has left the room, all people have left the room.



          The first statement is a truism , so how can the last statement not be one?






          share|cite|improve this answer









          $endgroup$





















            1












            $begingroup$

            $tag 1 exists x ; [P(x) Rightarrow forall y , P(y)]$



            Claim: (1) is a tautology, since it leads to an equivalence chain that ends in a well-known tautology:



            $tag 2 exists x ; [ neg P(x) , text{ or } , forall y , P(y)]$



            $tag 3 exists x ; [ neg P(x)] , text{ or } , forall y , P(y)$



            $tag 4 neg , forall x , P(x) , text{ or } , forall y , P(y)$



            $tag 5 neg , [forall z , P(z)] , text{ or } , [forall z , P(z)]$



            The equivalence chain ends with a tautology, so (1) must also be one.



            We can go from (2) to (3) since the existential qualifier distributes over disjunction and $( exists x) (forall y) , P(y) equiv forall y , P(y) $.



            In (5) the $[;]$ brackets were put around identical expressions. It was not necessary to change both $x$ and $y$ to $z$ - they both were 'quantified away' and can be viewed as just logical placeholders.



            Finally, this paradox can be viewed as a contortion of counterexample logic. The only useful tautology is (3); you can replace the $text{or-disjunction}$ with $text{XOR}$ (exclusive or).






            share|cite|improve this answer











            $endgroup$





















              0












              $begingroup$

              Here is a sequent calculus style proof:



                     ------------ (Id)
              
       P(y) |- P(y)
              
    --------------------- (Weak Right)
              
    P(y) |- P(y), ∀yP(y)
              
    --------------------- (⇒ Right)
              
    |- P(y), P(y)⇒∀yP(y)
              
   ------------------------- (∃ Right)
              
   |- P(y), ∃x(P(x)⇒∀yP(y))
              
  --------------------------- (∀ Right)
              
  |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
              
------------------------------- (Weak Left)
              
P(z) |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
              
-------------------------------- (⇒ Right)
              
|- P(z)⇒∀yP(y), ∃x(P(x)⇒∀yP(y))
              
------------------------------------- (∃ Right)
              
|- ∃x(P(x)⇒∀yP(y)), ∃x(P(x)⇒∀yP(y))
              
------------------------------------- (Contr Right)
              
      |- ∃x(P(x)⇒∀yP(y))


              It uses a multi-consequent sequent calculus, so possibly
              cannot be reduced to intuitionistic logic. Also the
              contraction structural rule shows that a substructural
              logic would possibly not do. These speculations could
              possibly substantiated by some non-classical logic model
              theoretic considerations.






              share|cite|improve this answer









              $endgroup$













                Your Answer





                StackExchange.ifUsing("editor", function () {
                return StackExchange.using("mathjaxEditing", function () {
                StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
                StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
                });
                });
                }, "mathjax-editing");

                StackExchange.ready(function() {
                var channelOptions = {
                tags: "".split(" "),
                id: "69"
                };
                initTagRenderer("".split(" "), "".split(" "), channelOptions);

                StackExchange.using("externalEditor", function() {
                // Have to fire editor after snippets, if snippets enabled
                if (StackExchange.settings.snippets.snippetsEnabled) {
                StackExchange.using("snippets", function() {
                createEditor();
                });
                }
                else {
                createEditor();
                }
                });

                function createEditor() {
                StackExchange.prepareEditor({
                heartbeatType: 'answer',
                autoActivateHeartbeat: false,
                convertImagesToLinks: true,
                noModals: true,
                showLowRepImageUploadWarning: true,
                reputationToPostImages: 10,
                bindNavPrevention: true,
                postfix: "",
                imageUploader: {
                brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
                contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
                allowUrls: true
                },
                noCode: true, onDemand: true,
                discardSelector: ".discard-answer"
                ,immediatelyShowMarkdownHelp:true
                });


                }
                });














                draft saved

                draft discarded


















                StackExchange.ready(
                function () {
                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f412387%2fwhy-is-this-true-exists-xpx-rightarrow-forall-y-py%23new-answer', 'question_page');
                }
                );

                Post as a guest















                Required, but never shown

























                11 Answers
                11






                active

                oldest

                votes








                11 Answers
                11






                active

                oldest

                votes









                active

                oldest

                votes






                active

                oldest

                votes









                27












                $begingroup$

                Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $phi$, either $phi$ or $lnotphi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $phi to psi$ is true if and only if either $phi$ is false or $psi$ is true.



                By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:




                • If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.

                • If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.


                Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.



                Alternatives



                Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($phi lor lnotphi$); and the material conditional ($(phi to psi) equiv (lnotphi lor psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.




                • Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $exists x.(P(x) to forall y.P(y))$ should be vacuously false.


                • Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $phi$ or $lnotphi$.”

                • There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.






                share|cite|improve this answer











                $endgroup$









                • 1




                  $begingroup$
                  What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 21:09






                • 1




                  $begingroup$
                  @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:27








                • 1




                  $begingroup$
                  @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:37








                • 1




                  $begingroup$
                  Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 22:24






                • 1




                  $begingroup$
                  @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 23:56
















                27












                $begingroup$

                Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $phi$, either $phi$ or $lnotphi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $phi to psi$ is true if and only if either $phi$ is false or $psi$ is true.



                By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:




                • If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.

                • If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.


                Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.



                Alternatives



                Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($phi lor lnotphi$); and the material conditional ($(phi to psi) equiv (lnotphi lor psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.




                • Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $exists x.(P(x) to forall y.P(y))$ should be vacuously false.


                • Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $phi$ or $lnotphi$.”

                • There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.






                share|cite|improve this answer











                $endgroup$









                • 1




                  $begingroup$
                  What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 21:09






                • 1




                  $begingroup$
                  @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:27








                • 1




                  $begingroup$
                  @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:37








                • 1




                  $begingroup$
                  Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 22:24






                • 1




                  $begingroup$
                  @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 23:56














                27












                27








                27





                $begingroup$

                Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $phi$, either $phi$ or $lnotphi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $phi to psi$ is true if and only if either $phi$ is false or $psi$ is true.



                By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:




                • If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.

                • If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.


                Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.



                Alternatives



                Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($phi lor lnotphi$); and the material conditional ($(phi to psi) equiv (lnotphi lor psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.




                • Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $exists x.(P(x) to forall y.P(y))$ should be vacuously false.


                • Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $phi$ or $lnotphi$.”

                • There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.






                share|cite|improve this answer











                $endgroup$



                Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $phi$, either $phi$ or $lnotphi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $phi to psi$ is true if and only if either $phi$ is false or $psi$ is true.



                By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:




                • If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.

                • If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.


                Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.



                Alternatives



                Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($phi lor lnotphi$); and the material conditional ($(phi to psi) equiv (lnotphi lor psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.




                • Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $exists x.(P(x) to forall y.P(y))$ should be vacuously false.


                • Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $phi$ or $lnotphi$.”

                • There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Jun 5 '13 at 21:48

























                answered Jun 5 '13 at 21:00









                Joshua TaylorJoshua Taylor

                2,004830




                2,004830








                • 1




                  $begingroup$
                  What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 21:09






                • 1




                  $begingroup$
                  @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:27








                • 1




                  $begingroup$
                  @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:37








                • 1




                  $begingroup$
                  Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 22:24






                • 1




                  $begingroup$
                  @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 23:56














                • 1




                  $begingroup$
                  What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 21:09






                • 1




                  $begingroup$
                  @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:27








                • 1




                  $begingroup$
                  @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:37








                • 1




                  $begingroup$
                  Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 22:24






                • 1




                  $begingroup$
                  @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 23:56








                1




                1




                $begingroup$
                What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
                $endgroup$
                – Thomas Andrews
                Jun 5 '13 at 21:09




                $begingroup$
                What if your domain is empty? That is, if $exists x: Q$ is false for all statements $Q$?
                $endgroup$
                – Thomas Andrews
                Jun 5 '13 at 21:09




                1




                1




                $begingroup$
                @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 21:27






                $begingroup$
                @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $cal I$ and a variable mapping $nu$ (which maps each variable to an element of the domain) that says that a sentence $forall x. phi(x)$ is true if and only if the interpretation function and every variable mapping $nu'$ (which is the same as $nu$ for each variable excepting that it may differ on $x$) make $phi(x)$ true.
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 21:27






                1




                1




                $begingroup$
                @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 21:37






                $begingroup$
                @ThomasAndrews Regarding $exists x.(P(x) lor lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $lnotexists x.(P(x) lor lnot P(x))$. Then $forall x.lnot(P(x) lor lnot P(x)$, and this is equivalent to $forall x.(lnot P(x) land lnotlnot P(x))$, which is equivalent to $forall x.(lnot P(x) land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $exists x.(P(x) lor lnot P(x))$.
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 21:37






                1




                1




                $begingroup$
                Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
                $endgroup$
                – Thomas Andrews
                Jun 5 '13 at 22:24




                $begingroup$
                Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct.
                $endgroup$
                – Thomas Andrews
                Jun 5 '13 at 22:24




                1




                1




                $begingroup$
                @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 23:56




                $begingroup$
                @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues.
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 23:56











                10












                $begingroup$

                Hint: The only way for $Aimplies B$ to be false is for $A$ to be true and $B$ to be false.



                I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $forall y: P(y)$ is true "vacuously," but $exists x: Q$ is not true for any $Q$.






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 20:54






                • 2




                  $begingroup$
                  Instead of $A Rightarrow B$, think of $lnot A lor B$.
                  $endgroup$
                  – copper.hat
                  Jun 5 '13 at 20:56








                • 1




                  $begingroup$
                  That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 20:57












                • $begingroup$
                  So in my case, there exists something that isn't a person, hence the whole statement is true?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 21:00






                • 4




                  $begingroup$
                  @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:03


















                10












                $begingroup$

                Hint: The only way for $Aimplies B$ to be false is for $A$ to be true and $B$ to be false.



                I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $forall y: P(y)$ is true "vacuously," but $exists x: Q$ is not true for any $Q$.






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 20:54






                • 2




                  $begingroup$
                  Instead of $A Rightarrow B$, think of $lnot A lor B$.
                  $endgroup$
                  – copper.hat
                  Jun 5 '13 at 20:56








                • 1




                  $begingroup$
                  That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 20:57












                • $begingroup$
                  So in my case, there exists something that isn't a person, hence the whole statement is true?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 21:00






                • 4




                  $begingroup$
                  @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:03
















                10












                10








                10





                $begingroup$

                Hint: The only way for $Aimplies B$ to be false is for $A$ to be true and $B$ to be false.



                I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $forall y: P(y)$ is true "vacuously," but $exists x: Q$ is not true for any $Q$.






                share|cite|improve this answer











                $endgroup$



                Hint: The only way for $Aimplies B$ to be false is for $A$ to be true and $B$ to be false.



                I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $forall y: P(y)$ is true "vacuously," but $exists x: Q$ is not true for any $Q$.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Jun 5 '13 at 21:09

























                answered Jun 5 '13 at 20:50









                Thomas AndrewsThomas Andrews

                130k11146297




                130k11146297












                • $begingroup$
                  I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 20:54






                • 2




                  $begingroup$
                  Instead of $A Rightarrow B$, think of $lnot A lor B$.
                  $endgroup$
                  – copper.hat
                  Jun 5 '13 at 20:56








                • 1




                  $begingroup$
                  That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 20:57












                • $begingroup$
                  So in my case, there exists something that isn't a person, hence the whole statement is true?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 21:00






                • 4




                  $begingroup$
                  @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:03




















                • $begingroup$
                  I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 20:54






                • 2




                  $begingroup$
                  Instead of $A Rightarrow B$, think of $lnot A lor B$.
                  $endgroup$
                  – copper.hat
                  Jun 5 '13 at 20:56








                • 1




                  $begingroup$
                  That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
                  $endgroup$
                  – Thomas Andrews
                  Jun 5 '13 at 20:57












                • $begingroup$
                  So in my case, there exists something that isn't a person, hence the whole statement is true?
                  $endgroup$
                  – Mats
                  Jun 5 '13 at 21:00






                • 4




                  $begingroup$
                  @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
                  $endgroup$
                  – Joshua Taylor
                  Jun 5 '13 at 21:03


















                $begingroup$
                I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
                $endgroup$
                – Mats
                Jun 5 '13 at 20:54




                $begingroup$
                I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
                $endgroup$
                – Mats
                Jun 5 '13 at 20:54




                2




                2




                $begingroup$
                Instead of $A Rightarrow B$, think of $lnot A lor B$.
                $endgroup$
                – copper.hat
                Jun 5 '13 at 20:56






                $begingroup$
                Instead of $A Rightarrow B$, think of $lnot A lor B$.
                $endgroup$
                – copper.hat
                Jun 5 '13 at 20:56






                1




                1




                $begingroup$
                That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
                $endgroup$
                – Thomas Andrews
                Jun 5 '13 at 20:57






                $begingroup$
                That's the problem with implication in logic. $Aimplies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)implies Q$ for any statement $Q$. So $exists x: P(x)implies Q$.
                $endgroup$
                – Thomas Andrews
                Jun 5 '13 at 20:57














                $begingroup$
                So in my case, there exists something that isn't a person, hence the whole statement is true?
                $endgroup$
                – Mats
                Jun 5 '13 at 21:00




                $begingroup$
                So in my case, there exists something that isn't a person, hence the whole statement is true?
                $endgroup$
                – Mats
                Jun 5 '13 at 21:00




                4




                4




                $begingroup$
                @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 21:03






                $begingroup$
                @Matts Not quite. $forall x.(P(x) to forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person."
                $endgroup$
                – Joshua Taylor
                Jun 5 '13 at 21:03













                5












                $begingroup$

                The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:Xrightarrow{0,1}$. Does the following proposition seem strange and unintuitive?



                Theorem. There is an element $min X$ such that, if $f(m)=1$, then $f(x)=1$ for all $xin X$.



                Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.



                Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.






                share|cite|improve this answer









                $endgroup$









                • 2




                  $begingroup$
                  The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
                  $endgroup$
                  – Ryan Reich
                  Jun 5 '13 at 23:39










                • $begingroup$
                  In mathematics, there's no such thing as an uniform description.
                  $endgroup$
                  – justt
                  Jun 17 '13 at 14:35
















                5












                $begingroup$

                The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:Xrightarrow{0,1}$. Does the following proposition seem strange and unintuitive?



                Theorem. There is an element $min X$ such that, if $f(m)=1$, then $f(x)=1$ for all $xin X$.



                Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.



                Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.






                share|cite|improve this answer









                $endgroup$









                • 2




                  $begingroup$
                  The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
                  $endgroup$
                  – Ryan Reich
                  Jun 5 '13 at 23:39










                • $begingroup$
                  In mathematics, there's no such thing as an uniform description.
                  $endgroup$
                  – justt
                  Jun 17 '13 at 14:35














                5












                5








                5





                $begingroup$

                The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:Xrightarrow{0,1}$. Does the following proposition seem strange and unintuitive?



                Theorem. There is an element $min X$ such that, if $f(m)=1$, then $f(x)=1$ for all $xin X$.



                Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.



                Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.






                share|cite|improve this answer









                $endgroup$



                The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:Xrightarrow{0,1}$. Does the following proposition seem strange and unintuitive?



                Theorem. There is an element $min X$ such that, if $f(m)=1$, then $f(x)=1$ for all $xin X$.



                Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.



                Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Jun 5 '13 at 21:53







                user75900















                • 2




                  $begingroup$
                  The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
                  $endgroup$
                  – Ryan Reich
                  Jun 5 '13 at 23:39










                • $begingroup$
                  In mathematics, there's no such thing as an uniform description.
                  $endgroup$
                  – justt
                  Jun 17 '13 at 14:35














                • 2




                  $begingroup$
                  The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
                  $endgroup$
                  – Ryan Reich
                  Jun 5 '13 at 23:39










                • $begingroup$
                  In mathematics, there's no such thing as an uniform description.
                  $endgroup$
                  – justt
                  Jun 17 '13 at 14:35








                2




                2




                $begingroup$
                The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
                $endgroup$
                – Ryan Reich
                Jun 5 '13 at 23:39




                $begingroup$
                The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f cong 1$, the description of a deciding element is the same.
                $endgroup$
                – Ryan Reich
                Jun 5 '13 at 23:39












                $begingroup$
                In mathematics, there's no such thing as an uniform description.
                $endgroup$
                – justt
                Jun 17 '13 at 14:35




                $begingroup$
                In mathematics, there's no such thing as an uniform description.
                $endgroup$
                – justt
                Jun 17 '13 at 14:35











                3












                $begingroup$

                In classical logic the following equivalence is logically valid:
                $$
                exists x (varphiRightarrowpsi)Longleftrightarrow(forall xvarphiRightarrowpsi)
                $$
                providing that $x$ is a variable not free in $psi$. So the formula in question is logically equivalent to $forall xP(x)Rightarrowforall yP(y)$.



                Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $neg P(a)$ is true. In (i) $P(x)Rightarrowforall y P(y)$ must be true, so $exists x(P(x)Rightarrowforall y P(y))$ is true. In (ii) $P(a)Rightarrowforall y P(y)$ must be true, therefore the sentence in question must be true as well.






                share|cite|improve this answer









                $endgroup$


















                  3












                  $begingroup$

                  In classical logic the following equivalence is logically valid:
                  $$
                  exists x (varphiRightarrowpsi)Longleftrightarrow(forall xvarphiRightarrowpsi)
                  $$
                  providing that $x$ is a variable not free in $psi$. So the formula in question is logically equivalent to $forall xP(x)Rightarrowforall yP(y)$.



                  Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $neg P(a)$ is true. In (i) $P(x)Rightarrowforall y P(y)$ must be true, so $exists x(P(x)Rightarrowforall y P(y))$ is true. In (ii) $P(a)Rightarrowforall y P(y)$ must be true, therefore the sentence in question must be true as well.






                  share|cite|improve this answer









                  $endgroup$
















                    3












                    3








                    3





                    $begingroup$

                    In classical logic the following equivalence is logically valid:
                    $$
                    exists x (varphiRightarrowpsi)Longleftrightarrow(forall xvarphiRightarrowpsi)
                    $$
                    providing that $x$ is a variable not free in $psi$. So the formula in question is logically equivalent to $forall xP(x)Rightarrowforall yP(y)$.



                    Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $neg P(a)$ is true. In (i) $P(x)Rightarrowforall y P(y)$ must be true, so $exists x(P(x)Rightarrowforall y P(y))$ is true. In (ii) $P(a)Rightarrowforall y P(y)$ must be true, therefore the sentence in question must be true as well.






                    share|cite|improve this answer









                    $endgroup$



                    In classical logic the following equivalence is logically valid:
                    $$
                    exists x (varphiRightarrowpsi)Longleftrightarrow(forall xvarphiRightarrowpsi)
                    $$
                    providing that $x$ is a variable not free in $psi$. So the formula in question is logically equivalent to $forall xP(x)Rightarrowforall yP(y)$.



                    Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $neg P(a)$ is true. In (i) $P(x)Rightarrowforall y P(y)$ must be true, so $exists x(P(x)Rightarrowforall y P(y))$ is true. In (ii) $P(a)Rightarrowforall y P(y)$ must be true, therefore the sentence in question must be true as well.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Jun 5 '13 at 21:03









                    Mad HatterMad Hatter

                    481213




                    481213























                        3












                        $begingroup$

                        In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        or equivalently



                        $$exists x(xin U wedge (P(x) Rightarrow forall y(yin URightarrow P(y))))$$
                        Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:



                        For non-empty $U$, consider two cases:



                        $$forall yin U (P(y))lor negforall yin U (P(y))$$



                        In each case, obtain



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$
                        For empty U, assume to the contrary that



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        and obtain a contradiction.



                        Full text of formal proof at http://dcproof.com/Mats.htm






                        share|cite|improve this answer











                        $endgroup$













                        • $begingroup$
                          @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
                          $endgroup$
                          – Dan Christensen
                          Oct 9 '18 at 18:52












                        • $begingroup$
                          @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
                          $endgroup$
                          – Dan Christensen
                          Oct 10 '18 at 3:38
















                        3












                        $begingroup$

                        In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        or equivalently



                        $$exists x(xin U wedge (P(x) Rightarrow forall y(yin URightarrow P(y))))$$
                        Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:



                        For non-empty $U$, consider two cases:



                        $$forall yin U (P(y))lor negforall yin U (P(y))$$



                        In each case, obtain



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$
                        For empty U, assume to the contrary that



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        and obtain a contradiction.



                        Full text of formal proof at http://dcproof.com/Mats.htm






                        share|cite|improve this answer











                        $endgroup$













                        • $begingroup$
                          @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
                          $endgroup$
                          – Dan Christensen
                          Oct 9 '18 at 18:52












                        • $begingroup$
                          @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
                          $endgroup$
                          – Dan Christensen
                          Oct 10 '18 at 3:38














                        3












                        3








                        3





                        $begingroup$

                        In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        or equivalently



                        $$exists x(xin U wedge (P(x) Rightarrow forall y(yin URightarrow P(y))))$$
                        Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:



                        For non-empty $U$, consider two cases:



                        $$forall yin U (P(y))lor negforall yin U (P(y))$$



                        In each case, obtain



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$
                        For empty U, assume to the contrary that



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        and obtain a contradiction.



                        Full text of formal proof at http://dcproof.com/Mats.htm






                        share|cite|improve this answer











                        $endgroup$



                        In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        or equivalently



                        $$exists x(xin U wedge (P(x) Rightarrow forall y(yin URightarrow P(y))))$$
                        Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:



                        For non-empty $U$, consider two cases:



                        $$forall yin U (P(y))lor negforall yin U (P(y))$$



                        In each case, obtain



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$
                        For empty U, assume to the contrary that



                        $$exists xin U (P(x) Rightarrow forall yin U (P(y))$$



                        and obtain a contradiction.



                        Full text of formal proof at http://dcproof.com/Mats.htm







                        share|cite|improve this answer














                        share|cite|improve this answer



                        share|cite|improve this answer








                        edited Jun 17 '13 at 19:55

























                        answered Jun 17 '13 at 17:09









                        Dan ChristensenDan Christensen

                        8,60321833




                        8,60321833












                        • $begingroup$
                          @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
                          $endgroup$
                          – Dan Christensen
                          Oct 9 '18 at 18:52












                        • $begingroup$
                          @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
                          $endgroup$
                          – Dan Christensen
                          Oct 10 '18 at 3:38


















                        • $begingroup$
                          @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
                          $endgroup$
                          – Dan Christensen
                          Oct 9 '18 at 18:52












                        • $begingroup$
                          @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
                          $endgroup$
                          – Dan Christensen
                          Oct 10 '18 at 3:38
















                        $begingroup$
                        @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
                        $endgroup$
                        – Dan Christensen
                        Oct 9 '18 at 18:52






                        $begingroup$
                        @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $xin U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set.
                        $endgroup$
                        – Dan Christensen
                        Oct 9 '18 at 18:52














                        $begingroup$
                        @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
                        $endgroup$
                        – Dan Christensen
                        Oct 10 '18 at 3:38




                        $begingroup$
                        @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $in U$ is just another predicate.
                        $endgroup$
                        – Dan Christensen
                        Oct 10 '18 at 3:38











                        3












                        $begingroup$

                        Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$quad$
                        $$
                        ((forall y)P(y)) lor (lnot (forall x) P(x)) \
                        ((forall y)P(y)) lor ((exists x)lnot P(x))\
                        (text{anything} Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow text{anything})) \
                        ((forall x)P(x) Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                        ((exists x)(P(x) Rightarrow (forall y)P(y))) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                        (exists x)(P(x) Rightarrow (forall y)P(y))
                        $$






                        share|cite|improve this answer











                        $endgroup$


















                          3












                          $begingroup$

                          Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$quad$
                          $$
                          ((forall y)P(y)) lor (lnot (forall x) P(x)) \
                          ((forall y)P(y)) lor ((exists x)lnot P(x))\
                          (text{anything} Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow text{anything})) \
                          ((forall x)P(x) Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                          ((exists x)(P(x) Rightarrow (forall y)P(y))) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                          (exists x)(P(x) Rightarrow (forall y)P(y))
                          $$






                          share|cite|improve this answer











                          $endgroup$
















                            3












                            3








                            3





                            $begingroup$

                            Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$quad$
                            $$
                            ((forall y)P(y)) lor (lnot (forall x) P(x)) \
                            ((forall y)P(y)) lor ((exists x)lnot P(x))\
                            (text{anything} Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow text{anything})) \
                            ((forall x)P(x) Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                            ((exists x)(P(x) Rightarrow (forall y)P(y))) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                            (exists x)(P(x) Rightarrow (forall y)P(y))
                            $$






                            share|cite|improve this answer











                            $endgroup$



                            Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$quad$
                            $$
                            ((forall y)P(y)) lor (lnot (forall x) P(x)) \
                            ((forall y)P(y)) lor ((exists x)lnot P(x))\
                            (text{anything} Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow text{anything})) \
                            ((forall x)P(x) Rightarrow (forall y)P(y)) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                            ((exists x)(P(x) Rightarrow (forall y)P(y))) lor ((exists x)(P(x) Rightarrow (forall y)P(y))) \
                            (exists x)(P(x) Rightarrow (forall y)P(y))
                            $$







                            share|cite|improve this answer














                            share|cite|improve this answer



                            share|cite|improve this answer








                            edited Oct 9 '18 at 18:51









                            j4n bur53

                            1,4091330




                            1,4091330










                            answered Jun 5 '13 at 22:28









                            Joe KJoe K

                            1,410710




                            1,410710























                                1












                                $begingroup$

                                The location of the parentheses is crucial here. Note that $(exists x)(P(x) Rightarrow (forall y) P(y))$ is very different from $(exists x)(P(x)) Rightarrow (forall y) P(y))$. To see why the former statement is true, consider its negation which is



                                $$forall x (P(x) wedge neg forall P(x)) equiv forall x(P(x) wedge exists x neg P(x))$$



                                which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.






                                share|cite|improve this answer











                                $endgroup$


















                                  1












                                  $begingroup$

                                  The location of the parentheses is crucial here. Note that $(exists x)(P(x) Rightarrow (forall y) P(y))$ is very different from $(exists x)(P(x)) Rightarrow (forall y) P(y))$. To see why the former statement is true, consider its negation which is



                                  $$forall x (P(x) wedge neg forall P(x)) equiv forall x(P(x) wedge exists x neg P(x))$$



                                  which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.






                                  share|cite|improve this answer











                                  $endgroup$
















                                    1












                                    1








                                    1





                                    $begingroup$

                                    The location of the parentheses is crucial here. Note that $(exists x)(P(x) Rightarrow (forall y) P(y))$ is very different from $(exists x)(P(x)) Rightarrow (forall y) P(y))$. To see why the former statement is true, consider its negation which is



                                    $$forall x (P(x) wedge neg forall P(x)) equiv forall x(P(x) wedge exists x neg P(x))$$



                                    which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.






                                    share|cite|improve this answer











                                    $endgroup$



                                    The location of the parentheses is crucial here. Note that $(exists x)(P(x) Rightarrow (forall y) P(y))$ is very different from $(exists x)(P(x)) Rightarrow (forall y) P(y))$. To see why the former statement is true, consider its negation which is



                                    $$forall x (P(x) wedge neg forall P(x)) equiv forall x(P(x) wedge exists x neg P(x))$$



                                    which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.







                                    share|cite|improve this answer














                                    share|cite|improve this answer



                                    share|cite|improve this answer








                                    edited Jun 5 '13 at 21:43

























                                    answered Jun 5 '13 at 21:14









                                    InkInk

                                    4,46611017




                                    4,46611017























                                        1












                                        $begingroup$

                                        Translate it to english:




                                        In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.




                                        For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)




                                        • If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) Rightarrow (forall y) P(y)$ is vacuously true, because $P Rightarrow Q$ is true whenever $P$ is false.


                                        • If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) Rightarrow (forall y) P(y)$ is then true because $P(a)$ is true, and $(forall y) P(y)$ is true.


                                        • If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) Rightarrow (forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.



                                        But let's look at it by taking the contradiction and seeing where it leads: $neg(exists x)(P(x) Rightarrow (forall y) P(y))$




                                        In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.




                                        we can move the negative inside: $(forall x)neg(P(x) Rightarrow (forall y) P(y))$




                                        In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.




                                        Then we can integrate the $neg$ into the formula by way of $neg (Q rightarrow P) = Q landneg P$ to arrive at: $(forall x)(P(x) landneg (forall y) P(y))$



                                        But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.






                                        share|cite|improve this answer









                                        $endgroup$


















                                          1












                                          $begingroup$

                                          Translate it to english:




                                          In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.




                                          For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)




                                          • If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) Rightarrow (forall y) P(y)$ is vacuously true, because $P Rightarrow Q$ is true whenever $P$ is false.


                                          • If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) Rightarrow (forall y) P(y)$ is then true because $P(a)$ is true, and $(forall y) P(y)$ is true.


                                          • If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) Rightarrow (forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.



                                          But let's look at it by taking the contradiction and seeing where it leads: $neg(exists x)(P(x) Rightarrow (forall y) P(y))$




                                          In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.




                                          we can move the negative inside: $(forall x)neg(P(x) Rightarrow (forall y) P(y))$




                                          In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.




                                          Then we can integrate the $neg$ into the formula by way of $neg (Q rightarrow P) = Q landneg P$ to arrive at: $(forall x)(P(x) landneg (forall y) P(y))$



                                          But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.






                                          share|cite|improve this answer









                                          $endgroup$
















                                            1












                                            1








                                            1





                                            $begingroup$

                                            Translate it to english:




                                            In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.




                                            For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)




                                            • If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) Rightarrow (forall y) P(y)$ is vacuously true, because $P Rightarrow Q$ is true whenever $P$ is false.


                                            • If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) Rightarrow (forall y) P(y)$ is then true because $P(a)$ is true, and $(forall y) P(y)$ is true.


                                            • If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) Rightarrow (forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.



                                            But let's look at it by taking the contradiction and seeing where it leads: $neg(exists x)(P(x) Rightarrow (forall y) P(y))$




                                            In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.




                                            we can move the negative inside: $(forall x)neg(P(x) Rightarrow (forall y) P(y))$




                                            In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.




                                            Then we can integrate the $neg$ into the formula by way of $neg (Q rightarrow P) = Q landneg P$ to arrive at: $(forall x)(P(x) landneg (forall y) P(y))$



                                            But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.






                                            share|cite|improve this answer









                                            $endgroup$



                                            Translate it to english:




                                            In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.




                                            For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)




                                            • If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) Rightarrow (forall y) P(y)$ is vacuously true, because $P Rightarrow Q$ is true whenever $P$ is false.


                                            • If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) Rightarrow (forall y) P(y)$ is then true because $P(a)$ is true, and $(forall y) P(y)$ is true.


                                            • If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) Rightarrow (forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.



                                            But let's look at it by taking the contradiction and seeing where it leads: $neg(exists x)(P(x) Rightarrow (forall y) P(y))$




                                            In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.




                                            we can move the negative inside: $(forall x)neg(P(x) Rightarrow (forall y) P(y))$




                                            In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.




                                            Then we can integrate the $neg$ into the formula by way of $neg (Q rightarrow P) = Q landneg P$ to arrive at: $(forall x)(P(x) landneg (forall y) P(y))$



                                            But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.







                                            share|cite|improve this answer












                                            share|cite|improve this answer



                                            share|cite|improve this answer










                                            answered Jun 5 '13 at 21:55









                                            KazKaz

                                            6,24311328




                                            6,24311328























                                                1












                                                $begingroup$

                                                To add a proof in Fitch style, natural deduction:



                                                2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
                                                
3  | | |________ Pa                New Subproof for -> Introduction
                                                
4  | | | |_____b                   variable for Universal Introduction
                                                
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
                                                
6  | | | | | |__ Pb                New Subproof for -> Introduction
                                                
7  | | | | | |   _|_               5,6 _|_ Introduction
                                                
8  | | | | | |   VyPy              7 _|_ Elimination
                                                
.  | | | | | <-------------------- end subpproof
                                                
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
                                                
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
                                                
11 | | | | |     _|_               2,10 _|_ Introduction
                                                
.. | | | | <---------------------- end subpproof
                                                
12 | | | |       ~~Pb              5-11 ~ Introduction
                                                
13 | | | |       Pb                12 ~~ Elimination
                                                
.. | | | <------------------------ end subpproof
                                                
14 | | |         VyPy              4-13 Universal Introduction
                                                
.. | | <-------------------------- end subpproof
                                                
15 | |           Pa -> VyPy        3-14 -> Introduction
                                                
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
                                                
17 | |          _|_                2,16 _|_ Introduction
                                                
.. | <---------------------------- end subpproof
                                                
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
                                                
19 |            Ex(Px -> VyPy)     18 ~~ Elimination


                                                This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist



                                                For explanation I compare this "paradox" with:



                                                If the last person has left the room, all people have left the room.



                                                Therefore



                                                There is a person if he has left the room, all people have left the room.



                                                The first statement is a truism , so how can the last statement not be one?






                                                share|cite|improve this answer









                                                $endgroup$


















                                                  1












                                                  $begingroup$

                                                  To add a proof in Fitch style, natural deduction:



                                                  2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
                                                  
3  | | |________ Pa                New Subproof for -> Introduction
                                                  
4  | | | |_____b                   variable for Universal Introduction
                                                  
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
                                                  
6  | | | | | |__ Pb                New Subproof for -> Introduction
                                                  
7  | | | | | |   _|_               5,6 _|_ Introduction
                                                  
8  | | | | | |   VyPy              7 _|_ Elimination
                                                  
.  | | | | | <-------------------- end subpproof
                                                  
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
                                                  
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
                                                  
11 | | | | |     _|_               2,10 _|_ Introduction
                                                  
.. | | | | <---------------------- end subpproof
                                                  
12 | | | |       ~~Pb              5-11 ~ Introduction
                                                  
13 | | | |       Pb                12 ~~ Elimination
                                                  
.. | | | <------------------------ end subpproof
                                                  
14 | | |         VyPy              4-13 Universal Introduction
                                                  
.. | | <-------------------------- end subpproof
                                                  
15 | |           Pa -> VyPy        3-14 -> Introduction
                                                  
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
                                                  
17 | |          _|_                2,16 _|_ Introduction
                                                  
.. | <---------------------------- end subpproof
                                                  
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
                                                  
19 |            Ex(Px -> VyPy)     18 ~~ Elimination


                                                  This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist



                                                  For explanation I compare this "paradox" with:



                                                  If the last person has left the room, all people have left the room.



                                                  Therefore



                                                  There is a person if he has left the room, all people have left the room.



                                                  The first statement is a truism , so how can the last statement not be one?






                                                  share|cite|improve this answer









                                                  $endgroup$
















                                                    1












                                                    1








                                                    1





                                                    $begingroup$

                                                    To add a proof in Fitch style, natural deduction:



                                                    2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
                                                    
3  | | |________ Pa                New Subproof for -> Introduction
                                                    
4  | | | |_____b                   variable for Universal Introduction
                                                    
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
                                                    
6  | | | | | |__ Pb                New Subproof for -> Introduction
                                                    
7  | | | | | |   _|_               5,6 _|_ Introduction
                                                    
8  | | | | | |   VyPy              7 _|_ Elimination
                                                    
.  | | | | | <-------------------- end subpproof
                                                    
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
                                                    
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
                                                    
11 | | | | |     _|_               2,10 _|_ Introduction
                                                    
.. | | | | <---------------------- end subpproof
                                                    
12 | | | |       ~~Pb              5-11 ~ Introduction
                                                    
13 | | | |       Pb                12 ~~ Elimination
                                                    
.. | | | <------------------------ end subpproof
                                                    
14 | | |         VyPy              4-13 Universal Introduction
                                                    
.. | | <-------------------------- end subpproof
                                                    
15 | |           Pa -> VyPy        3-14 -> Introduction
                                                    
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
                                                    
17 | |          _|_                2,16 _|_ Introduction
                                                    
.. | <---------------------------- end subpproof
                                                    
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
                                                    
19 |            Ex(Px -> VyPy)     18 ~~ Elimination


                                                    This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist



                                                    For explanation I compare this "paradox" with:



                                                    If the last person has left the room, all people have left the room.



                                                    Therefore



                                                    There is a person if he has left the room, all people have left the room.



                                                    The first statement is a truism , so how can the last statement not be one?






                                                    share|cite|improve this answer









                                                    $endgroup$



                                                    To add a proof in Fitch style, natural deduction:



                                                    2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
                                                    
3  | | |________ Pa                New Subproof for -> Introduction
                                                    
4  | | | |_____b                   variable for Universal Introduction
                                                    
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
                                                    
6  | | | | | |__ Pb                New Subproof for -> Introduction
                                                    
7  | | | | | |   _|_               5,6 _|_ Introduction
                                                    
8  | | | | | |   VyPy              7 _|_ Elimination
                                                    
.  | | | | | <-------------------- end subpproof
                                                    
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
                                                    
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
                                                    
11 | | | | |     _|_               2,10 _|_ Introduction
                                                    
.. | | | | <---------------------- end subpproof
                                                    
12 | | | |       ~~Pb              5-11 ~ Introduction
                                                    
13 | | | |       Pb                12 ~~ Elimination
                                                    
.. | | | <------------------------ end subpproof
                                                    
14 | | |         VyPy              4-13 Universal Introduction
                                                    
.. | | <-------------------------- end subpproof
                                                    
15 | |           Pa -> VyPy        3-14 -> Introduction
                                                    
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
                                                    
17 | |          _|_                2,16 _|_ Introduction
                                                    
.. | <---------------------------- end subpproof
                                                    
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
                                                    
19 |            Ex(Px -> VyPy)     18 ~~ Elimination


                                                    This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist



                                                    For explanation I compare this "paradox" with:



                                                    If the last person has left the room, all people have left the room.



                                                    Therefore



                                                    There is a person if he has left the room, all people have left the room.



                                                    The first statement is a truism , so how can the last statement not be one?







                                                    share|cite|improve this answer












                                                    share|cite|improve this answer



                                                    share|cite|improve this answer










                                                    answered May 24 '14 at 12:16









                                                    WillemienWillemien

                                                    3,49531859




                                                    3,49531859























                                                        1












                                                        $begingroup$

                                                        $tag 1 exists x ; [P(x) Rightarrow forall y , P(y)]$



                                                        Claim: (1) is a tautology, since it leads to an equivalence chain that ends in a well-known tautology:



                                                        $tag 2 exists x ; [ neg P(x) , text{ or } , forall y , P(y)]$



                                                        $tag 3 exists x ; [ neg P(x)] , text{ or } , forall y , P(y)$



                                                        $tag 4 neg , forall x , P(x) , text{ or } , forall y , P(y)$



                                                        $tag 5 neg , [forall z , P(z)] , text{ or } , [forall z , P(z)]$



                                                        The equivalence chain ends with a tautology, so (1) must also be one.



                                                        We can go from (2) to (3) since the existential qualifier distributes over disjunction and $( exists x) (forall y) , P(y) equiv forall y , P(y) $.



                                                        In (5) the $[;]$ brackets were put around identical expressions. It was not necessary to change both $x$ and $y$ to $z$ - they both were 'quantified away' and can be viewed as just logical placeholders.



                                                        Finally, this paradox can be viewed as a contortion of counterexample logic. The only useful tautology is (3); you can replace the $text{or-disjunction}$ with $text{XOR}$ (exclusive or).






                                                        share|cite|improve this answer











                                                        $endgroup$


















                                                          1












                                                          $begingroup$

                                                          $tag 1 exists x ; [P(x) Rightarrow forall y , P(y)]$



                                                          Claim: (1) is a tautology, since it leads to an equivalence chain that ends in a well-known tautology:



                                                          $tag 2 exists x ; [ neg P(x) , text{ or } , forall y , P(y)]$



                                                          $tag 3 exists x ; [ neg P(x)] , text{ or } , forall y , P(y)$



                                                          $tag 4 neg , forall x , P(x) , text{ or } , forall y , P(y)$



                                                          $tag 5 neg , [forall z , P(z)] , text{ or } , [forall z , P(z)]$



                                                          The equivalence chain ends with a tautology, so (1) must also be one.



                                                          We can go from (2) to (3) since the existential qualifier distributes over disjunction and $( exists x) (forall y) , P(y) equiv forall y , P(y) $.



                                                          In (5) the $[;]$ brackets were put around identical expressions. It was not necessary to change both $x$ and $y$ to $z$ - they both were 'quantified away' and can be viewed as just logical placeholders.



                                                          Finally, this paradox can be viewed as a contortion of counterexample logic. The only useful tautology is (3); you can replace the $text{or-disjunction}$ with $text{XOR}$ (exclusive or).






                                                          share|cite|improve this answer











                                                          $endgroup$
















                                                            1












                                                            1








                                                            1





                                                            $begingroup$

                                                            $tag 1 exists x ; [P(x) Rightarrow forall y , P(y)]$



                                                            Claim: (1) is a tautology, since it leads to an equivalence chain that ends in a well-known tautology:



                                                            $tag 2 exists x ; [ neg P(x) , text{ or } , forall y , P(y)]$



                                                            $tag 3 exists x ; [ neg P(x)] , text{ or } , forall y , P(y)$



                                                            $tag 4 neg , forall x , P(x) , text{ or } , forall y , P(y)$



                                                            $tag 5 neg , [forall z , P(z)] , text{ or } , [forall z , P(z)]$



                                                            The equivalence chain ends with a tautology, so (1) must also be one.



                                                            We can go from (2) to (3) since the existential qualifier distributes over disjunction and $( exists x) (forall y) , P(y) equiv forall y , P(y) $.



                                                            In (5) the $[;]$ brackets were put around identical expressions. It was not necessary to change both $x$ and $y$ to $z$ - they both were 'quantified away' and can be viewed as just logical placeholders.



                                                            Finally, this paradox can be viewed as a contortion of counterexample logic. The only useful tautology is (3); you can replace the $text{or-disjunction}$ with $text{XOR}$ (exclusive or).






                                                            share|cite|improve this answer











                                                            $endgroup$



                                                            $tag 1 exists x ; [P(x) Rightarrow forall y , P(y)]$



                                                            Claim: (1) is a tautology, since it leads to an equivalence chain that ends in a well-known tautology:



                                                            $tag 2 exists x ; [ neg P(x) , text{ or } , forall y , P(y)]$



                                                            $tag 3 exists x ; [ neg P(x)] , text{ or } , forall y , P(y)$



                                                            $tag 4 neg , forall x , P(x) , text{ or } , forall y , P(y)$



                                                            $tag 5 neg , [forall z , P(z)] , text{ or } , [forall z , P(z)]$



                                                            The equivalence chain ends with a tautology, so (1) must also be one.



                                                            We can go from (2) to (3) since the existential qualifier distributes over disjunction and $( exists x) (forall y) , P(y) equiv forall y , P(y) $.



                                                            In (5) the $[;]$ brackets were put around identical expressions. It was not necessary to change both $x$ and $y$ to $z$ - they both were 'quantified away' and can be viewed as just logical placeholders.



                                                            Finally, this paradox can be viewed as a contortion of counterexample logic. The only useful tautology is (3); you can replace the $text{or-disjunction}$ with $text{XOR}$ (exclusive or).







                                                            share|cite|improve this answer














                                                            share|cite|improve this answer



                                                            share|cite|improve this answer








                                                            edited Sep 10 '17 at 3:31

























                                                            answered Sep 9 '17 at 2:14









                                                            CopyPasteItCopyPasteIt

                                                            4,1481628




                                                            4,1481628























                                                                0












                                                                $begingroup$

                                                                Here is a sequent calculus style proof:



                                                                       ------------ (Id)
                                                                
       P(y) |- P(y)
                                                                
    --------------------- (Weak Right)
                                                                
    P(y) |- P(y), ∀yP(y)
                                                                
    --------------------- (⇒ Right)
                                                                
    |- P(y), P(y)⇒∀yP(y)
                                                                
   ------------------------- (∃ Right)
                                                                
   |- P(y), ∃x(P(x)⇒∀yP(y))
                                                                
  --------------------------- (∀ Right)
                                                                
  |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                
------------------------------- (Weak Left)
                                                                
P(z) |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                
-------------------------------- (⇒ Right)
                                                                
|- P(z)⇒∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                
------------------------------------- (∃ Right)
                                                                
|- ∃x(P(x)⇒∀yP(y)), ∃x(P(x)⇒∀yP(y))
                                                                
------------------------------------- (Contr Right)
                                                                
      |- ∃x(P(x)⇒∀yP(y))


                                                                It uses a multi-consequent sequent calculus, so possibly
                                                                cannot be reduced to intuitionistic logic. Also the
                                                                contraction structural rule shows that a substructural
                                                                logic would possibly not do. These speculations could
                                                                possibly substantiated by some non-classical logic model
                                                                theoretic considerations.






                                                                share|cite|improve this answer









                                                                $endgroup$


















                                                                  0












                                                                  $begingroup$

                                                                  Here is a sequent calculus style proof:



                                                                         ------------ (Id)
                                                                  
       P(y) |- P(y)
                                                                  
    --------------------- (Weak Right)
                                                                  
    P(y) |- P(y), ∀yP(y)
                                                                  
    --------------------- (⇒ Right)
                                                                  
    |- P(y), P(y)⇒∀yP(y)
                                                                  
   ------------------------- (∃ Right)
                                                                  
   |- P(y), ∃x(P(x)⇒∀yP(y))
                                                                  
  --------------------------- (∀ Right)
                                                                  
  |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                  
------------------------------- (Weak Left)
                                                                  
P(z) |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                  
-------------------------------- (⇒ Right)
                                                                  
|- P(z)⇒∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                  
------------------------------------- (∃ Right)
                                                                  
|- ∃x(P(x)⇒∀yP(y)), ∃x(P(x)⇒∀yP(y))
                                                                  
------------------------------------- (Contr Right)
                                                                  
      |- ∃x(P(x)⇒∀yP(y))


                                                                  It uses a multi-consequent sequent calculus, so possibly
                                                                  cannot be reduced to intuitionistic logic. Also the
                                                                  contraction structural rule shows that a substructural
                                                                  logic would possibly not do. These speculations could
                                                                  possibly substantiated by some non-classical logic model
                                                                  theoretic considerations.






                                                                  share|cite|improve this answer









                                                                  $endgroup$
















                                                                    0












                                                                    0








                                                                    0





                                                                    $begingroup$

                                                                    Here is a sequent calculus style proof:



                                                                           ------------ (Id)
                                                                    
       P(y) |- P(y)
                                                                    
    --------------------- (Weak Right)
                                                                    
    P(y) |- P(y), ∀yP(y)
                                                                    
    --------------------- (⇒ Right)
                                                                    
    |- P(y), P(y)⇒∀yP(y)
                                                                    
   ------------------------- (∃ Right)
                                                                    
   |- P(y), ∃x(P(x)⇒∀yP(y))
                                                                    
  --------------------------- (∀ Right)
                                                                    
  |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                    
------------------------------- (Weak Left)
                                                                    
P(z) |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                    
-------------------------------- (⇒ Right)
                                                                    
|- P(z)⇒∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                    
------------------------------------- (∃ Right)
                                                                    
|- ∃x(P(x)⇒∀yP(y)), ∃x(P(x)⇒∀yP(y))
                                                                    
------------------------------------- (Contr Right)
                                                                    
      |- ∃x(P(x)⇒∀yP(y))


                                                                    It uses a multi-consequent sequent calculus, so possibly
                                                                    cannot be reduced to intuitionistic logic. Also the
                                                                    contraction structural rule shows that a substructural
                                                                    logic would possibly not do. These speculations could
                                                                    possibly substantiated by some non-classical logic model
                                                                    theoretic considerations.






                                                                    share|cite|improve this answer









                                                                    $endgroup$



                                                                    Here is a sequent calculus style proof:



                                                                           ------------ (Id)
                                                                    
       P(y) |- P(y)
                                                                    
    --------------------- (Weak Right)
                                                                    
    P(y) |- P(y), ∀yP(y)
                                                                    
    --------------------- (⇒ Right)
                                                                    
    |- P(y), P(y)⇒∀yP(y)
                                                                    
   ------------------------- (∃ Right)
                                                                    
   |- P(y), ∃x(P(x)⇒∀yP(y))
                                                                    
  --------------------------- (∀ Right)
                                                                    
  |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                    
------------------------------- (Weak Left)
                                                                    
P(z) |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                    
-------------------------------- (⇒ Right)
                                                                    
|- P(z)⇒∀yP(y), ∃x(P(x)⇒∀yP(y))
                                                                    
------------------------------------- (∃ Right)
                                                                    
|- ∃x(P(x)⇒∀yP(y)), ∃x(P(x)⇒∀yP(y))
                                                                    
------------------------------------- (Contr Right)
                                                                    
      |- ∃x(P(x)⇒∀yP(y))


                                                                    It uses a multi-consequent sequent calculus, so possibly
                                                                    cannot be reduced to intuitionistic logic. Also the
                                                                    contraction structural rule shows that a substructural
                                                                    logic would possibly not do. These speculations could
                                                                    possibly substantiated by some non-classical logic model
                                                                    theoretic considerations.







                                                                    share|cite|improve this answer












                                                                    share|cite|improve this answer



                                                                    share|cite|improve this answer










                                                                    answered Oct 12 '18 at 8:41









                                                                    j4n bur53j4n bur53

                                                                    1,4091330




                                                                    1,4091330






























                                                                        draft saved

                                                                        draft discarded




















































                                                                        Thanks for contributing an answer to Mathematics Stack Exchange!


                                                                        • Please be sure to answer the question. Provide details and share your research!

                                                                        But avoid …



                                                                        • Asking for help, clarification, or responding to other answers.

                                                                        • Making statements based on opinion; back them up with references or personal experience.


                                                                        Use MathJax to format equations. MathJax reference.


                                                                        To learn more, see our tips on writing great answers.




                                                                        draft saved


                                                                        draft discarded














                                                                        StackExchange.ready(
                                                                        function () {
                                                                        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f412387%2fwhy-is-this-true-exists-xpx-rightarrow-forall-y-py%23new-answer', 'question_page');
                                                                        }
                                                                        );

                                                                        Post as a guest















                                                                        Required, but never shown





















































                                                                        Required, but never shown














                                                                        Required, but never shown












                                                                        Required, but never shown







                                                                        Required, but never shown

































                                                                        Required, but never shown














                                                                        Required, but never shown












                                                                        Required, but never shown







                                                                        Required, but never shown







                                                                        Popular posts from this blog

                                                                        MongoDB - Not Authorized To Execute Command

                                                                        Image
                                                                        .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
                                                                        Read more

                                                                        in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith

                                                                        Image
                                                                        1 I tried to upgrade a yummy sandwich made of two test slices (@JsonTest and @JdbcTest in my case, crunchy test code in between) adding spring boot 2.1 flavour to it. But it seems it was not much of a success. I cannot annotate my tests with many @...Test since they are now each bringing their own XxxTestContextBootstrapper. It used to work when they all used same SpringBootTestContextBootstrapper. @RunWith(SpringRunner.class) @JdbcTest @JsonTest public class Test { @Test public void test() { System.out.printn("Hello, World !"); } } The error I get from BootstrapUtils is illegalStateException : Configuration error: found multiple declarations of @BootstrapWith for test class I understand I might be doing something wrong here but is there an easy way I could load both Json and Jdbc contex...
                                                                        Read more

                                                                        Npm cannot find a required file even through it is in the searched directory

                                                                        Image
                                                                        up vote 0 down vote favorite I got that error: users-Air:pdfuploader user$ npm run start client@0.1.0 start /Users/user/Documents/pdfuploader react-scripts start Could not find a required file. Name: index.html Searched in: /Users/user/Documents/pdfuploader/public npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! client@0.1.0 start: `react-scripts start` npm ERR! Exit status 1 npm ERR! npm ERR! Failed at the client@0.1.0 start script. npm ERR! This is probably not a problem with npm. There is likely additional logging output above. npm ERR! A complete log of this run can be found in: npm ERR! /Users/user/.npm/_logs/2018-11-19T10_19_14_555Z-debug.log users-Air:pdfuploader user$ And the file is in /Users/user/Documents/pdfuploader/public as you can see in my github repository: https://github.c...
                                                                        Read more