# Cofusing partial order “implies”, on logic and that on sets

I feel confused comparing partial order on sets and that on logic.

$$x\ge 1 \implies x\ge 0$$

Here we see a smaller set "implies" a bigger set

But, if we know three facts, fact1,fact2,fact3, we know thus fact1, fact2, which can be written as

$$\{\text{fact1}, \text{fact2}, \text{fact3}\} \implies \{\text{fact1}, \text{fact2}\}$$

Here a bigger set "implies" a smaller set.

I feel thus confused facing the logic partial order "implies". What's my problem??

-
You seem to be confusing the fact that $\implies$ (or, to be more precise, $\vdash$) is a preorder on the set of propositions with the idea of reasoning about partially ordered sets. –  Zhen Lin Aug 2 '11 at 7:16

First we need to review the definition of "implies".

Suppose $P,Q$ are two sentences. $P\implies Q$ is exactly the case that if $P$ is true then $Q$ is also true.

In your example, $x\ge 1$ implies $x\ge 0$ because $1\ge 0$ and $\ge$ is transitive, that is if $x\ge y$ and $y\ge z$ then $x\ge z$.

Suppose now that you have $\mathcal P=\{P_1,\ldots\}$ a set of sentences (not necessarily finite), and $Q$ another sentence. We say that $\{P_1,\ldots\}\implies Q$ exactly if all the sentences in $\mathcal P$ are true, then $Q$ is also true.

An example is:

$$\{"x\ge2", "x\text{ is odd}"\}\implies x\ge 3$$

Neither $x\ge 2$ nor $x\text{ is odd}$ imply $x\ge 3$ on their own, however combine the two facts and you have that $x\ge 3$.

This can be extended into replacing $Q$ by some $\mathcal Q=\{Q_1,\ldots\}$ another set of sentences, in which case we say that $\mathcal P\implies\mathcal Q$ exactly whenever all the sentences in $\mathcal P$ are true, then all the sentences in $\mathcal Q$ are true as well.

For example:

$$\{"x\ge 1", "x\text{ is even}", "x\text{ can be divided by } 6"\}\implies\{"x\text{ can be divided by } 3", "x\ge 6"\}$$

There is no strict requirement that a "big" sets have to imply the truth of some "smaller" or "bigger" set than itself. One sentence can imply many sentences, and it may be the case that several sentences are required to imply a single sentence.

A mistake in your post is that $\implies$ is not a partial order, but rather a quasi-order. That means reflexive and transitive. It is not antisymmetric.

For example: $$"x<1 \text{ and } x>-1"\implies "x=0"$$ as well: $$"x=0"\implies "x<1 \text{ and } x>-1"$$

However formally speaking, $x=0$ is not the same sentence as $"x<1 \text{ and } x>-1"$.

-

($A$ or $B$) implies ($A$ or $B$ or $C$). ($A$ and $B$ and $C$) implies ($A$ and $B$).

$x\ge1$ is an "or": it's ($x=1$ or $x=2$ or $x=3$ or ...).

$\lbrace{\rm fact1,\ fact2,\ fact3}\rbrace$ is an "and": (fact1 and fact2 and fact3).

-
Gerry: What about the case $\{\text{fact}_n\mid n\in\mathbb N\}$? :-) –  Asaf Karagila Aug 2 '11 at 7:08
@Asaf, makes no difference. If it's preceded by "we know", it's "and": we know fact1 and we know fact2 and .... If it's preceded by "$x$ is in" then it's "or": $x$ is fact1 or $x$ is fact2 or .... –  Gerry Myerson Aug 2 '11 at 7:18
It was a semi-humourous remark, I was being a smartypants on my side. :-) –  Asaf Karagila Aug 2 '11 at 7:19
Yes, I think a quick answer would be: (Disjunctive_facts, ==>) corresponds to (Sets, \subset), whicle (Conjunctive_facts, ==>) correspoinds to (Sets, \supset). –  zell Aug 2 '11 at 7:22