Contents

Satallax is a higher-order
automated theorem prover.
Satallax won the THF division
of CASC-23 in 2011.

Automated Reasoning in Higher Order Logic

Impressum
Contact Person
Chad E Brown

Theorem

Let A be an object. Let φ(a) be a proposition depending on a member a of A. Assume ¬(∀a∈A⋅φ(a)). Then we have ∃a∈A⋅¬φ(a).

Background

The following background is necessary to understand this theorem.

(.) Let A and x be objects. Then x∈A is a proposition.

(.) Let φ be a proposition. Then ¬φ is a proposition.

(.) Let A be an object. Let φ(a) be a proposition depending on a member a of A. Then "∀a∈A⋅φ(a)" is a proposition.

(.) Let A be an object. Let φ(a) be a proposition depending on a member a of A. Then "∃a∈A⋅φ(a)" is a proposition.

Background for Proof

The following background is necessary for the proof.

(.) Let φ and ψ be propositions. Assume φ and ¬φ. Then we know ψ.

(.) "false" is a proposition.

(.) Let φ be a proposition. Assume ¬φ implies false. Then we know φ.

(.) Let A be an object. Let φ(a) be a proposition depending on a member a of A. Assume for all a ∈ A φ(a). Then we know ∀a∈A⋅φ(a).

(.) Let A be an object. Let φ(a) be a proposition depending on a member a of A. Let a be a member of A. Assume φ(a). Then we know ∃a∈A⋅φ(a).

Proof

It is enough to show ¬(∃a∈A⋅¬φ(a)) implies false. Assume ¬(∃a∈A⋅¬φ(a)). Using ¬(∀a∈A⋅φ(a)), it is enough to show ∀a∈A⋅φ(a). Let a be a member of φ. We will show ¬φ(a) implies false. Assume ¬φ(a). Thus ∃a∈A⋅¬φ(a). Using this and ¬(∃a∈A⋅¬φ(a)), we conclude false.

Click here to modify variable names (JavaScript Must Be Enabled).