User:IssaRice/Computability and logic/Semantic completeness - Revision history

IssaRice: /* Proof */

2019-10-17T22:27:53Z

Proof

← Older revision		Revision as of 22:27, 17 October 2019
Line 38:		Line 38:
	Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\mathfrak A \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.		Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\mathfrak A \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.

	Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) (with <math>\Gamma \cup \{\neg\phi\}</math> in place of "<math>\Gamma</math>") we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation ~~using~~ the logical system one is using.		Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) (with <math>\Gamma \cup \{\neg\phi\}</math> in place of "<math>\Gamma</math>") we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation in the logical system one is using.

	===Proof commentary===		===Proof commentary===

IssaRice: /* Proof */

2019-05-11T17:37:51Z

Proof

← Older revision		Revision as of 17:37, 11 May 2019
Line 36:		Line 36:
	Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.		Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.

	Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\~~Gamma~~ \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.		Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\mathfrak A \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.

	Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) (with <math>\Gamma \cup \{\neg\phi\}</math> in place of "<math>\Gamma</math>") we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation using the logical system one is using.		Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) (with <math>\Gamma \cup \{\neg\phi\}</math> in place of "<math>\Gamma</math>") we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation using the logical system one is using.

IssaRice: /* Alternative formulation */

2019-04-07T20:05:33Z

Alternative formulation

← Older revision		Revision as of 20:05, 7 April 2019
Line 38:		Line 38:
	Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.		Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.

	Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation using the logical system one is using.		Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) (with <math>\Gamma \cup \{\neg\phi\}</math> in place of "<math>\Gamma</math>") we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation using the logical system one is using.

	===Proof commentary===		===Proof commentary===

IssaRice: /* Alternative formulation */

2019-04-07T20:01:52Z

Alternative formulation

← Older revision		Revision as of 20:01, 7 April 2019
Line 43:		Line 43:

	In proving (1) ⇒ (2), we only needed that "if <math>\Gamma</math> is unsatisfiable, then <math>\Gamma\models\bot</math>". However, it is also possible to prove the converse, and show that if <math>\Gamma</math> is satisfiable, then <math>\Gamma \not\models\bot</math>. Some books factor out both sides of this implication as a lemma.		In proving (1) ⇒ (2), we only needed that "if <math>\Gamma</math> is unsatisfiable, then <math>\Gamma\models\bot</math>". However, it is also possible to prove the converse, and show that if <math>\Gamma</math> is satisfiable, then <math>\Gamma \not\models\bot</math>. Some books factor out both sides of this implication as a lemma.

			Similarly, in proving (2) ⇒ (1), we only needed that "if <math>\Gamma \models \phi</math>, then <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable", but the converse holds as well.

	==References==		==References==

	<references/>		<references/>

IssaRice: /* Alternative formulation */

2019-04-07T19:59:58Z

Alternative formulation

← Older revision		Revision as of 19:59, 7 April 2019
Line 38:		Line 38:
	Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.		Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.

	Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. ~~(The~~ exact details of the derivations in this paragraph will differ based on the logical system one is using.)		Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. Note that the exact details of the derivations in this paragraph will differ based on the logical system one is using. For instance, going from "<math>\Gamma \vdash \neg\phi\to\bot</math>" to "<math>\Gamma \vdash \phi</math>" is not automatic; one must provide an entirely syntactic derivation using the logical system one is using.

	===Proof commentary===		===Proof commentary===

IssaRice: /* Alternative formulation */

2019-04-07T19:56:14Z

Alternative formulation

← Older revision		Revision as of 19:56, 7 April 2019
Line 38:		Line 38:
	Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.		Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.

	Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math>, which means <math>\Gamma \vdash \phi</math>, which is what we wanted.		Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math> by the deduction theorem, which means <math>\Gamma \vdash \phi</math>, which is what we wanted. (The exact details of the derivations in this paragraph will differ based on the logical system one is using.)

	===Proof commentary===		===Proof commentary===

IssaRice: /* Alternative formulation */

2019-04-07T19:49:27Z

Alternative formulation

← Older revision		Revision as of 19:49, 7 April 2019
Line 35:		Line 35:

	Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.		Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.

			Now suppose (2) is true. Let <math>\Gamma</math> be a set of sentences, let <math>\phi</math> be a sentence, and suppose <math>\Gamma \models \phi</math>. We will first show that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable. Suppose for the sake of contradiction that <math>\Gamma \cup \{\neg\phi\}</math> is satisfiable. Then we would have a structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma \cup \{\neg\phi\}</math>. This means <math>\mathfrak A \models \Gamma</math> and <math>\mathfrak A \models \neg\phi</math>. Since <math>\Gamma \models \phi</math>, this means <math>\Gamma \models \phi</math>. So we have both <math>\mathfrak A \models \phi</math> and <math>\mathfrak A \models \neg\phi</math>, a contradiction. This proves that <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable.

			Since <math>\Gamma \cup \{\neg\phi\}</math> is unsatisfiable, by (2) we have that <math>\Gamma \cup \{\neg\phi\}</math> is inconsistent. This means <math>\Gamma \cup \{\neg\phi\} \vdash \bot</math>, so <math>\Gamma \vdash \neg\phi\to\bot</math>, which means <math>\Gamma \vdash \phi</math>, which is what we wanted.

	===Proof commentary===		===Proof commentary===

IssaRice: /* Proof commentary */

2019-04-07T19:34:01Z

Proof commentary

← Older revision		Revision as of 19:34, 7 April 2019
Line 37:		Line 37:

	===Proof commentary===		===Proof commentary===

			In proving (1) ⇒ (2), we only needed that "if <math>\Gamma</math> is unsatisfiable, then <math>\Gamma\models\bot</math>". However, it is also possible to prove the converse, and show that if <math>\Gamma</math> is satisfiable, then <math>\Gamma \not\models\bot</math>. Some books factor out both sides of this implication as a lemma.

	==References==		==References==

	<references/>		<references/>

IssaRice: /* Alternative formulation */

2019-04-07T19:30:51Z

Alternative formulation

← Older revision		Revision as of 19:30, 7 April 2019
Line 35:		Line 35:

	Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.		Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.

			===Proof commentary===

	==References==		==References==

	<references/>		<references/>

IssaRice: /* Alternative formulation */

2019-04-07T19:28:56Z

Alternative formulation

← Older revision		Revision as of 19:28, 7 April 2019
Line 33:		Line 33:

	===Proof===		===Proof===

			Suppose (1) is true. We will prove the contrapositive of (2). Let <math>\Gamma</math> be a set of sentences, and suppose <math>\Gamma</math> is unsatisfiable. Let <math>\bot</math> be a contradictory sentence, such as <math>\phi\wedge\neg\phi</math>. Now, since <math>\Gamma</math> is unsatisfiable, there is no structure <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>. This means that vacuously, for every <math>\mathfrak A</math> such that <math>\mathfrak A \models \Gamma</math>, we have <math>\mathfrak A \models \bot</math>. Thus we have <math>\Gamma \models \bot</math>. Now by (1) (with <math>\bot</math> serving the role of "<math>\phi</math>"), this means <math>\Gamma \vdash \bot</math>, which shows that <math>\Gamma</math> is inconsistent, as desired.

	==References==		==References==

	<references/>		<references/>