0

Does ∧ still mean intersection when using predicate logic?

This is one of the questions asked in class.

Is the sentence valid? (∃xQ(x) ∧ ∃xR(x)) → ∃x(Q(x) ∧ R(x))

If it is, explain why. If it isn’t, give an interpretation under which it is false.

Answer

It’s not. Think of the interpretation where Q(x) is “x is even”, R(x) is “x is odd” and x ranges over the integers. Then ∃xQ(x) ∧ ∃xR(x) is true because ∃xQ(x) is true (there is an even integer) and ∃xR(x) is true (there is an odd integer). But ∃x(Q(x) ∧ R(x)) is false (there does not exist an integer that is both even and odd). So the statement (∃xQ(x) ∧ ∃xR(x)) → ∃x(Q(x) ∧ R(x)) is false under this interpretation and the sentence is not valid.

In predicate logic, does ∧ simply mean 'and' rather than intersection?

Handsome Woman
  • 105
  • So with this sentence "∃xQ(x) ∧ ∃xR(x) is true because ∃xQ(x) is true (there is an even integer) and ∃xR(x) is true (there is an odd integer)." Q(x) and R(x) are referring to 2 different completely different numbers? – Handsome Woman Jun 15 '18 at 07:01
  • If you're interpreting predicates as sets, then the fact a proposition is a nullary predicate means that you can interpret "false" as being the empty set and "true" as being a specified one-element set, and then $\wedge$ will once again be interpreted as intersection. –  Jun 15 '18 at 07:08

2 Answers2

1

In predicate logic the connectives are the same of propositional logic :

$∧$ is "and" and $∨$ is "or".

It is intersection (between sets) that is defined with "and" :

$x ∈ A∩B \text { iff } x∈A \text { and } x∈B$.

The antecedent of the formula reads :

"there is an object that is $Q$ and there is an object (not necessarily the same) that is $R$ ",

while the consequent reads :

"there is an object that is $Q$ and is $R$".

Mauro ALLEGRANZA
  • 94,169
1

Does ∧ still mean intersection when using predicate logic?

No. It means 'conjunction', though more often simply read as 'and'.

However, this is closely related to the concept of intersection.   The definition for intersection, is that for any $x$ we have $x\in A\cap B$ if and only if $(x\in A)\wedge(x\in B)$.   That says, of course, that everything in the intersection of $A$ and $B$ is in $A$ and in $B$, and vice versa.

Alternatively, using set construction notation, then $A\cap B:=\{x\mid (x\in A)\wedge (x\in B)\}$.

Is the sentence valid? $(∃x~Q(x) ∧ ∃x~R(x)) → ∃x~(Q(x) ∧ R(x))$

Indeed it is not generally valid.   Letting $Q(x)$ stand for "$x$ is odd" and $R(x)$ stand for "$x$ is even", is a very classic counter example.   As you observed, it is clearly not true that "If there are some numbers which are odd and there are some numbers which are even, then there are some numbers which are both odd and even."   Good job.

Graham Kemp
  • 129,094