1
$\begingroup$

i'm not sure i got this one right: i am supposed to check which of the propositions are logically true and to show why, and if not true then show a counter example.

the propositions:

1)$\vdash \forall x(P(x) \to Q(x)) \to (\exists x P(x) \to \exists x Q(x))$

2)$\vdash \forall x(P(x) \to Q(x)) \to (\forall x P(x) \to \forall x Q(x))$

3)$\vdash \forall x(P(x) \to P(c))$

4)$\vdash \exists x \forall y Q(x,y) \to \forall y \exists x Q(x,y)$

5)$\vdash \forall y \forall x Q(x,y) \to \forall x \forall y Q(x,y)$

what i did:

1)true i think. we'll mark $P(x) \to P(d)$, $Q(x) \to Q(d)$. using twice the deduction theorem on the last part, we'll get that $(\exists x P(x) \to \exists x Q(x))$ becomes $(\exists x (P(x) \to Q(x))$.it seems logical that if it works for all x, then it should work for any x, but i don't know exactly how to fill the missing part here.

2)not true. for instance, under the domain of real numbers, if i said that p(x) equals pi and q(x) equals is rational, then $∀x(P(x)→Q(x))$ means every number that equals pi is rational, whereas $(∀xP(x)→∀xQ(x))$ means that if every real number equals pi then every real number is rational. so one is true and the other is not.

3)incorrect, but i don't know how to select an appropriate example. it seems very logical to infer that not for every x, if p(x) is true then it will still hold for p(c).

4)true.if we define a structure A so that a function B is defined as $B(x)={y \in A| A \vDash Q(x,y)}$ we can see that $∃x∀yQ(x,y)$ implies $∀y∃xQ(x,y)$ because if we look at the intersection of all B(A) being not empty, it can be inferred that B(A) itself cannot be empty, i.e, the first implies the other.

5)false. it looks quite obvious to be true, but when i look at it further it seems it is more like 3) ($\forall x(P(x) \to P(c)$),but it 2 variables, to create Q(x,y).

tried to do my best and elaborate as much as i could. if i did something wrong, please correct me so i'll be able to see the correct way and improve.

thank you very much!

$\endgroup$
1
$\begingroup$

1) is indeed true, but your reasoning is a bit confusing. How about just looking at what the statement says: If all $P$'s are $Q$'s, then if there is a $P$, then there is a $Q$. Why yes! If there is something that is a $P$, then since all $P$'s are $Q$'s, that something is also a $Q$. Hence, there is something that is a $Q$.

2) is also true: If everything is a $P$, then given that all $P$'s are $Q$'s, everything must also be a $Q$.

3) is indeed false. Just find an example, where something is a $P$, and where $c$ is not a $P$. E.g. $c$ = pi, $P$ is rational. Since $2$ is rational, $P(2)$ is true, but $P(c)$ is false, and hence $P(2) \rightarrow P(c)$ is false, and hence you don;t have that $\forall x (P(x) \rightarrow P(c))$

4) is indeed true. Your reasoning is also correct ... though a bit complicated I find. Why not: If there is something (and let's call that something 'Bob') that stands in relation $Q$ to everything, then if I pick anything, can I find something that stands in relation $Q$ to it? Of course ! Bob!

5) is true! If everything stands in relation $Q$ to everything, then everything stands in relation $Q$ to everything

Here are formal proofs for 4) and 5) created in Fitch, a Fitch-style proof system:

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ thank you so much! studying your answer $\endgroup$ – BeginningMath Jun 2 '18 at 15:23
  • 1
    $\begingroup$ @BeginningMath You're welcome! Note how in most cases I translated in basic English, and went from there, rather than doing any kind of formal logical semantics; that's often a lot more understandable, and just as good for demonstrating these things ... unless someone explicitly asks for a formal semantic analysis .. $\endgroup$ – Bram28 Jun 2 '18 at 15:40
  • 1
    $\begingroup$ @BeginningMath: If you're interested in a purely formal proof, you can find a sample for a generalized version of (4) in a Fitch-style system here under "Example". In general, Fitch-style systems are the ones that can be actually used in mathematical reasoning, whereas what you typically find in a logic textbook is a Hilbert-style system, which is almost useless to use in reasoning but is extremely easy to study. My suggestion is to understand Fitch-style deduction, as via that understanding it is easy to understand all other deductive systems. $\endgroup$ – user21820 Jun 3 '18 at 16:30
  • 1
    $\begingroup$ Thank you! And I also like your included Fitch-style proofs. Is the software you used freely available? @BeginningMath: Just a note, Bram28's system is practically the same as mine except that his introduces an extra subcontext at (3) that represents "Let $a$ be such that $\forall y ( Q(a,y) )$.", and later uses the $\exists$-elim rule on "$\exists x \forall y ( Q(x,y) )$" (2) and "$\boxed{a} \forall y ( Q(a,y) ) \vdash \forall y \exists x ( Q(x,y) )$" (3−7) to get "$\forall y \exists x ( Q(x,y) )$" because (7) does not involve $a$. $\endgroup$ – user21820 Jun 4 '18 at 3:57
  • 1
    $\begingroup$ In English, (2) says "some $x$ satisfies $G$" and (3−7) says "given an $a$ that satisfies $G$, we can conclude $C$" and since this $C$ does not depend on the choice of $a$, we know that (2) must imply $C$. $\endgroup$ – user21820 Jun 4 '18 at 3:57

Your Answer

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

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