Properties of the logical consequence operation and its relationship with the independence of propositional logic
We investigate the properties of the logical consequence operation and the characteristic features of independent sets of formulas. Further, we apply these results to propositional logic. Finally, we show under what conditions the results of addition of a formula to independent sets of formulas and...
Saved in:
| Date: | 2018 |
|---|---|
| Main Authors: | , , , , , |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematics, NAS of Ukraine
2018
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/1600 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507410635948032 |
|---|---|
| author | Öner, G. Öner, T. Şentürk, İ. Онер, Г. Онер, Т. Сентюрк, І. |
| author_facet | Öner, G. Öner, T. Şentürk, İ. Онер, Г. Онер, Т. Сентюрк, І. |
| author_sort | Öner, G. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T09:19:59Z |
| description | We investigate the properties of the logical consequence operation and the characteristic features of independent sets
of formulas. Further, we apply these results to propositional logic. Finally, we show under what conditions the results of
addition of a formula to independent sets of formulas and the union of two independent sets of formulas are also independent,
by using the operation of logical consequence, i.e., we establish a relationship between the logical consequence and the
preservation of independence in propositional logic. |
| first_indexed | 2026-03-24T02:08:52Z |
| format | Article |
| fulltext |
UDC 517.5
T. Öner, İ. Şentürk (Ege Univ., Izmir, Turkey),
G. Öner (Dokuz Eylul Univ., Izmir, Turkey)
PROPERTIES OF THE LOGICAL CONSEQUENCE OPERATION
AND ITS RELATIONSHIP WITH THE INDEPENDENCE
OF PROPOSITIONAL LOGIC
ВЛАСТИВОСТI ОПЕРАЦIЇ ЛОГIЧНОГО НАСЛIДКУ
ТА ЇЇ ЗВ’ЯЗОК З НЕЗАЛЕЖНIСТЮ ПРОПОЗИЦIЙНОЇ ЛОГIКИ
We investigate the properties of the logical consequence operation and the characteristic features of independent sets
of formulas. Further, we apply these results to propositional logic. Finally, we show under what conditions the results of
addition of a formula to independent sets of formulas and the union of two independent sets of formulas are also independent,
by using the operation of logical consequence, i.e., we establish a relationship between the logical consequence and the
preservation of independence in propositional logic.
Вивчаються властивостi операцiї логiчного наслiдку та характернi особливостi незалежних множин формул. Отри-
манi результати застосовуються до пропозицiйної логiки. Крiм того, встановлено, за яких умов результат додавання
формули до незалежних множин формул та об’єднання двох незалежних множин формул також є незалежним за
операцiєю логiчного наслiдку, тобто встановлено спiввiдношення мiж логiчним наслiдком та збереженням незалеж-
ностi у пропозицiйнiй логiцi.
1. Introduction. The logical consequence undisputedly is the central concept of logic. The main
purpose of logic is to tell us what follows logically from what. Logical consequence is a relation
between a given set of formulas and the formulas that logically follow. But this concept has a long
story before the adoption of its validity. In a series of papers, published early 1930’s [14], Tarski
describes his logical perspective as follows: our goal is to study the properties of deductive systems.
A deductive system, or a formal theory, is the set of all formulas which follows formally from a set
of formulas; more precisely, the formal theory T includes a set of axioms A and a set of inference
rules R. Then the set of logical consequences of a formula \varphi in T was defined as the smallest set of
formulas of T that contains \varphi and the axioms in A, and is closed under the rules in R.
The need for semantic definitions of the same concepts arose when Tarski realized that there was
a serious gap between the proof theoretical definitions and the intuitive concepts: many intuitive
consequences of the formal theories were undetectable by standard system of proof. His conclusion
was that proof theory can provide only a partical account of the metalogic [5].
Tarski described the intuitive content of the concept logical consequence as follows. Let \Sigma be a
set of formulas and \varphi be a formula that follows from \Sigma .
(C) If \varphi is a logical consequence of \Sigma , then \varphi is a necessary consequence of \Sigma in the sense
that it cannot be the case that all formulas in \Sigma are true and \varphi is false.
Further, he introduced the notion of model and proposed the formal definition of logical conse-
quence in terms of models.
(LC) The sentence \varphi follows logically from \Sigma if and only if every model of \Sigma is also a model
of \varphi .
Now the definition of logical truth immediately follows:
c\bigcirc T. ÖNER, İ. ŞENTÜRK, G. ÖNER, 2018
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6 857
858 T. ÖNER, İ. ŞENTÜRK, G. ÖNER
(LT) The sentence \varphi of a formal theory T is logically true if and only if every model of T is a
model of \varphi .
That (LC) satisfies (C) is a very simple observation [10]:
Suppose that \varphi is a logical consequence of \Sigma , i.e., \varphi is true in all models in which all the
formulas in \Sigma are true. Now assume that \varphi is not a necessary consequence of \Sigma . Then it is possible
that all the elements of \Sigma are true and \varphi is false. But in that case there is a model in which all the
members of \Sigma come out true and \varphi happens to be false. Contradiction.
From now on \Sigma \vdash \varphi will mean that \varphi is a logical consequence of \Sigma . More on logical consequence
can be found, for instance, in [1, 4, 7 – 9, 16]; works in [6] and [11] can be considered as main sources
on the subject.
In this work, we deal with properties of the logical consequence operation and its relationship
with independence of propositional logic. We prove that under which conditions the addition of a
formula to independent sets of formulas, and the union of two independent sets of formulas are also
independent by using the logical consequence operation. Briefly, we establish a relationship between
logical consequence and the preservation of independence in propostional logic.
2. Properties of logical consequence \bfitC \bfitn . In this section, we give definitions about conse-
quence operation Cn. Further, we indicate basic properties of consequence operation. As we shall
see in the remaining sections, they are the basis of this work.
Definition 2.1. Let L be any formal language. A consequence operation on L is a function
Cn : 2L \rightarrow 2L such that the following holds:
(i) \Sigma \subseteq Cn(\Sigma ), all \Sigma \subseteq L (reflexivity),
(ii) for all \Sigma 1, \Sigma 2 \subseteq L, if \Sigma 1 \subseteq \Sigma 2 then Cn(\Sigma 1) \subseteq Cn(\Sigma 2) (monotonacity),
(iii) for all \Sigma \subseteq L, Cn(Cn(\Sigma )) = Cn(\Sigma ) (idempotency).
Definition 2.2. Cn is a structural consequence operation if and only if f(Cn(\Sigma )) \subseteq Cn(f(\Sigma ))
for every endomorphism f of L.
Definition 2.3. Cn is a finite (or algebraic) consequence operation if and only if Cn(\Sigma ) =
=
\bigcup
\{ Cn(\nabla ) : \nabla \subseteq \Sigma ,\nabla finite\} , where \Sigma is the subset of any formal language L.
Definition 2.4. If Cn is finite and structural, then Cn is standart.
Definition 2.5 [3]. (i) Cn is stronger than Cn\prime (Cn\prime \leq Cn) if and only if for all \Sigma , Cn\prime (\Sigma ) \subseteq
\subseteq Cn(\Sigma ).
(ii) Cn is properly stronger than Cn\prime (Cn\prime < Cn) if and only if Cn is stronger than Cn\prime and
there is a \Sigma such that Cn\prime (\Sigma ) \subset Cn(\Sigma ).
Definition 2.6 [3]. (i) Cn is consistent if and only if Cn\varnothing ) \not = L.
(ii) Cn is compact if and only if for each \Sigma \subseteq L : if Cn(\Sigma ) = L, then there exists a finite
\Sigma \prime \subseteq \Sigma such that Cn(\Sigma \prime ) = L.
(iii) \Sigma is a Cn-theory if and only if Cn(\Sigma ) = \Sigma .
(iv) \Sigma is Cn-consistent if and only if Cn(\Sigma ) \not = L.
(v) \Sigma is Cn-complete if and only if for all A : if \Sigma \cup \{ A\} is consistent, then A \in Cn(\Sigma ).
(vi) \Sigma is Cn-maximally consistent if and only if \Sigma is consistent, and there does not exist a
consistent \Sigma \prime such that \Sigma \subset \Sigma \prime .
(vii) \Sigma is Cn-axiom system for \Sigma \prime if and only if Cn(\Sigma ) = Cn(\Sigma \prime ).
(viii) A is Cn-independent in \Sigma if and only if A \in \Sigma and A /\in Cn(\Sigma - \{ A\} ).
(ix) A is Cn-tautology if and only if A \in Cn(\varnothing ).
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
PROPERTIES OF THE LOGICAL CONSEQUENCE OPERATION AND ITS RELATIONSHIP . . . 859
Definition 2.7 [3]. A set \Omega is a closure system if and only if it is closed intersection. Namely, if
\Gamma \subseteq \Omega , then
\bigcap
\Gamma \in \Omega .
Let \langle L,Cn\rangle denote a logic on a language L and a consequence operation Cn. Also, (Cn \cap
Cn\prime )(\Sigma ) = Cn(\Sigma ) \cap Cn\prime (\Sigma ) and (Cn \cup Cn\prime )(\Sigma ) = Cn(\Sigma ) \cup Cn\prime (\Sigma ) for all \Sigma \subseteq L. Now we can
give some results on Cn.
Lemma 2.1. Let \Sigma 1 and \Sigma 2 be sets in \langle L,Cn\rangle . Then the following identities hold:
(i) Cn(Cn(\Sigma 1) \cup Cn(\Sigma 2)) = Cn(\Sigma 1 \cup \Sigma 2),
(ii) Cn(Cn(\Sigma 1) \cap Cn(\Sigma 2)) = Cn(\Sigma 1) \cap Cn(\Sigma 2).
Lemma 2.2. Let \langle L,Cn\rangle and \langle L,Cn\prime \rangle be consistent. Then \langle L,Cn \cap Cn\prime \rangle is also consistent.
Remark 2.1. In general the union of \langle L,Cn\rangle and \langle L,Cn\prime \rangle is not consistent. For example, let
Cn(\varnothing ) = \Psi (\varnothing \not = \Psi \not = L) and Cn\prime (\varnothing ) = L - \Psi . We get Cn(\varnothing ) \cup Cn\prime (\varnothing ) = L. Therefore,
\langle L,Cn \cup Cn\prime \rangle is not consistent.
Lemma 2.3. Let \langle L,Cn\rangle and \langle L,Cn\prime \rangle be compact. Then \langle L,Cn \cap Cn\prime \rangle and \langle L,Cn \cup Cn\prime \rangle
are also compact.
Lemma 2.4. If \Sigma 1 and \Sigma 2 are Cn-theory, then Cn(\Sigma 1) \cap Cn(\Sigma 2) = Cn(\Sigma 1 \cap \Sigma 2).
Definition 2.8. A set T \subseteq L is closed under Cn if and only if T = Cn(T ).
Lemma 2.5. Every Cn-theory is closed.
In this study, the class of all closed sets in a logic \langle L,Cn\rangle is denoted by \Im = \{ T \in 2L :
T = Cn(T )\} . We can easily show that (\Im ,\subseteq ) is a partial order structure. At the same time, for
every \Gamma \subseteq \Im , \mathrm{S}\mathrm{u}\mathrm{p}(\Gamma ) = \mathrm{C}\mathrm{n}(
\bigcup
\Gamma ) \in \Im and \mathrm{I}\mathrm{n}\mathrm{f}(\Gamma ) = \mathrm{C}\mathrm{n}(
\bigcap
\Gamma ) \in \Im . Every subset of \Im has a \mathrm{S}\mathrm{u}\mathrm{p}
and \mathrm{I}\mathrm{n}\mathrm{f}. Hence, (\Im ,\subseteq ) is a complete lattice.
Lemma 2.6. Let A be the any subset of tautologies set (it means that Cn(A) = Cn(\varnothing )). L is
the maximal element and Cn(A) is the minimal element in \Im .
Lemma 2.7. Let \Sigma \not = L. \Sigma is closed Cn-complete if and only if \Sigma is Cn-maximally consistent.
Proof. Let \Sigma be closed Cn-complete. For all A, if \Sigma \cup \{ A\} is Cn-consistent, then \{ A\} \subseteq \Sigma .
Therefore, \Sigma is Cn-maximally consistent. We assume that \Sigma is Cn-maximally consistent. For all
A, if \Sigma \cup \{ A\} is Cn-consistent, then \{ A\} \subseteq \Sigma and also A \in Cn(\Sigma ), because \Sigma is Cn-maximally
consistent. Hence, \Sigma is Cn-complete. If A \in Cn(\Sigma ), then \Sigma \cup \{ A\} is Cn-consistent. Since \Sigma is
Cn-maximally consistent, \{ A\} \subseteq \Sigma . So, A \in \Sigma . Therefore, Cn(\Sigma ) = \Sigma .
Lemma 2.8. If \Sigma 1 and \Sigma 2 are Cn-consistent, then \Sigma 1 \cap \Sigma 2 is also Cn-consistent.
Remark 2.2. The union of any two Cn-consistent sets is not in general Cn-consistent.
Lemma 2.9 [13]. Let Cn1 \leq Cn2 \leq Cn3 \leq . . . be an infinite chain of finite consequence
operations and Cn = \mathrm{S}\mathrm{u}\mathrm{p}\{ Cni : i = 1, 2, 3, . . .\} . Therefore
Cn(\Sigma ) =
\bigcup
i\in \BbbN
Cni(\Sigma )
for every \Sigma \subseteq L.
Lemma 2.10. Let Cn1 \leq Cn2 \leq Cn3 \leq . . . be an infinite chain of finite structural consequence
operations and Cn = \mathrm{S}\mathrm{u}\mathrm{p}\{ Cni : i = 1, 2, 3, . . .\} . Then Cn is also structural consequence operation.
Proof. Let f be any endomorphism and \Sigma \subseteq L :
f(Cn(\Sigma )) = f
\Biggl( \bigcup
i\in \BbbN
Cni(\Sigma )
\Biggr)
(by Lemma 2.9) =
\bigcup
i\in \BbbN
f(Cni(\Sigma )) (since f is an endomorphism) \subseteq
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
860 T. ÖNER, İ. ŞENTÜRK, G. ÖNER
\subseteq
\bigcup
i\in \BbbN
Cni(f(\Sigma )) (by Definition 2.2) = Cn(f(\Sigma )) (by Lemma 2.9).
Therefore, Cn is a structural consequence operation.
3. Properties of propositional logical consequence \bfitC \bfitn . The notion of propositional conse-
quence operation includes all systems of classical propositional logic [1, 12]. And, we use LPROP
for describing language of propostional logic which is generated by the connectives \neg , \wedge , \vee and
\rightarrow .
Throughout the study \varphi , \varphi 1, \varphi 2, . . . and \Sigma , \Sigma 1, \Sigma 2, . . . denote propositional logical formu-
las and sets of propositional logical formulas, respectively. Cn(\Sigma ) stands for the set of logical
consequences of \Sigma ; that is, \varphi \in Cn(\Sigma ) if and only if \Sigma \vdash \varphi .
Definition 3.1 [3]. A consequence operation Cn is a propositional consequence operation if
and only if for \varphi 1, \varphi 2 \in LPROP and \Sigma \subseteq LPROP :
(\neg ) \varphi 1 \in Cn(\Sigma ) if and only if Cn(\Sigma \cup \{ \neg \varphi 1\} ) = LPROP ,
(\wedge ) Cn(\Sigma \cup \{ \varphi 1 \wedge \varphi 2\} ) = Cn(\Sigma \cup \{ \varphi 1, \varphi 2\} ),
(\vee ) Cn(\Sigma \cup \{ \varphi 1 \vee \varphi 2\} ) = Cn(\Sigma \cup \{ \varphi 1\} ) \cap Cn(\Sigma \cup \{ \varphi 2\} ),
(\rightarrow ) \varphi 1 \rightarrow \varphi 2 \in Cn(\Sigma ) if and only if \varphi 2 \in Cn(\Sigma \cup \{ \varphi 1\} ).
Definition 3.2. A set of formulas \Sigma is said to be independent if for all \varphi belonging to \Sigma , \varphi is
not a logical consequence of \Sigma \setminus \{ \varphi \} ; in symbols, if \Sigma \setminus \{ \varphi \} \nvdash \varphi . Equivalently, \Sigma is independent if
there is a model for (\Sigma \setminus \{ \varphi \} ) \cup \{ \neg \varphi \} , where \neg is the negation operation.
Definition 3.3. Two set of formulas are said to be equivalent if any formula of the one set is a
consequence of the other set and conversely. Equivalently, two sets are equivalent when they have
the same models.
We recall the following results.
Lemma 3.1 [11]. Given \varphi 1, \varphi 2, \varphi 3 and \Sigma 1,\Sigma 2, we have
(i) \varphi 1 \vdash \varphi 1;
(ii) if \Sigma 1 \vdash \varphi 1, then \Sigma 1 \cup \Sigma 2 \vdash \varphi 1;
(iii) if \Sigma 1 \cup \{ \varphi 2\} \vdash \varphi 1, and \Sigma 2 \vdash \varphi 2, then \Sigma 1 \cup \Sigma 2 \vdash \varphi 1;
(iv) \Sigma 1 \vdash \varphi 1 if and only if \Sigma 2 \vdash \varphi 1 for some finite subset \Sigma 2 of \Sigma 1;
(v) \Sigma 1 \cup \{ \varphi 1\} \vdash \varphi 2 if and only if \Sigma 1 \vdash \varphi 1 \rightarrow \varphi 2;
(vi) \Sigma 1 \cup \{ \varphi 1, \varphi 2\} \vdash \varphi 3 if and only if \Sigma 1 \cup \{ \varphi 1 \wedge \varphi 2\} \vdash \varphi 3.
Note that we can write \Sigma 1, \varphi 1, \varphi 2 \vdash \varphi 3 for \Sigma 1 \cup \{ \varphi 1, \varphi 2\} \vdash \varphi 3.
In this section, we prove some results on Cn in propositional logic, which are of set theoretical
nature.
Lemma 3.2. Given \Sigma 1 and \Sigma 2, we have
Cn(\Sigma 1) \cup Cn(\Sigma 2) \subseteq Cn(\Sigma 1 \cup \Sigma 2).
Proof. Let \varphi \in Cn(\Sigma 1) \cup Cn(\Sigma 2). Then \varphi \in Cn(\Sigma 1) or \varphi \in Cn(\Sigma 2). If \varphi \in Cn(\Sigma 1), then
\Sigma 1 \vdash \varphi , hence \Sigma 1 \cup \Sigma 2 \vdash \varphi by Lemma 2.1 (ii). It follows that \varphi \in Cn(\Sigma 1 \cup \Sigma 2). If \varphi \in Cn(\Sigma 2),
then exactly the same way we obtain \varphi \in Cn(\Sigma 1 \cup \Sigma 2), so
Cn(\Sigma 1) \cup Cn(\Sigma 2) \subseteq Cn(\Sigma 1 \cup \Sigma 2).
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
PROPERTIES OF THE LOGICAL CONSEQUENCE OPERATION AND ITS RELATIONSHIP . . . 861
Corollary 3.1. For a family of formulas \Sigma k, we have
n\bigcup
k=1
Cn(\Sigma k) \subseteq Cn
\Biggl(
n\bigcup
k=1
\Sigma k
\Biggr)
.
Proof. Just use induction on n.
The following result is obvious.
Result 3.1. Given \Sigma 1 and \Sigma 2, we have
\Sigma 1 \cup \Sigma 2 \subseteq Cn(\Sigma 1) \cup Cn(\Sigma 2).
Corollary 3.2. For a family of formulas \Sigma k, we have
n\bigcup
k=1
\Sigma k \subseteq
n\bigcup
k=1
Cn(\Sigma k).
Thus, we get the following inclusions:
n\bigcup
k=1
\Sigma k \subseteq
n\bigcup
k=1
Cn(\Sigma k) \subseteq Cn
\Biggl(
n\bigcup
k=1
\Sigma k
\Biggr)
.
Let \Sigma 1 and \Sigma 2 be any set of formulas in LPROP . By the definition of Cn, we have that
if \Sigma 1 \subseteq \Sigma 2, then Cn(\Sigma 1) \subseteq Cn(\Sigma 2).
Lemma 3.3. Given \Sigma 1 and \Sigma 2, we have
Cn(\Sigma 1 \cap \Sigma 2) \subseteq Cn(\Sigma 1) \cap Cn(\Sigma 2).
From the above results, we obtain the following inclusions:
n\bigcap
k=1
\Sigma k \subseteq Cn
\Biggl(
n\bigcap
k=1
\Sigma k
\Biggr)
\subseteq
n\bigcap
k=1
Cn(\Sigma k).
Lemma 3.4. Let \Sigma 1 and \Sigma 2 be sets of formulas and A be any subset of a set which includes
only tautologies. If Cn(\Sigma 1) \cap Cn(\Sigma 2) = Cn(\varnothing ), then \Sigma 1 \cap \Sigma 2 = (\varnothing ) or \Sigma 1 \cap \Sigma 2 = A.
Proof. Assume that \varphi is any formula which is not a tautology and \varphi \in \Sigma 1 \cap \Sigma 2. Then
\varphi \in Cn(\Sigma 1) \cap Cn(\Sigma 2). We obtain the conclusion Cn(\Sigma 1) \cap Cn(\Sigma 2) \not = Cn(\varnothing ). It is contradiction.
Remark 3.1. The converse of this theorem does not hold. To see this, consider the following
formulas from formal number theory:
\varphi 1 : \forall xy(x\prime = y\prime \rightarrow x = y),
\varphi 2 : \forall xy(x+ y\prime = (x+ y)\prime ),
\varphi 3 : \forall xy(xy\prime = xy + x\prime ).
where \prime is the successor function on \BbbN . Then let \Sigma 1 = \{ \varphi 1 \wedge \varphi 2\} and \Sigma 2 = \{ \varphi 1 \wedge \varphi 3\} . Now
\Sigma 1 \cap \Sigma 2 = \varnothing , but Cn(\Sigma 1) \cap Cn(\Sigma 2) \not = Cn(\varnothing ), since \Sigma 1 \vdash \varphi 1 and \Sigma 2 \vdash \varphi 1.
Theorem 3.1. Let \Sigma be Cn-complete and \varphi /\in Cn(\Sigma ). Then for all \psi \in LPROP , \varphi \rightarrow \psi \in
\in Cn(\Sigma ).
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
862 T. ÖNER, İ. ŞENTÜRK, G. ÖNER
Proof. Assume that \Sigma is Cn-complete and \varphi /\in Cn(\Sigma ). Then \Sigma \cup \{ \varphi \} is not consistent. So,
we hold that \Sigma \cup \{ \varphi \} \vdash \psi . By the Lemma 3.1 (v), \Sigma \vdash \varphi \rightarrow \psi .
Theorem 3.2. Any theory is complete in LPROP if and only if it is maximal consistent.
Proof. (\Rightarrow ) Let \Sigma be theory and complete. If \varphi /\in Cn(\Sigma ), then \Sigma \cup \{ \varphi \} is not consistent. As
\Sigma = Cn(\Sigma ), \Sigma is maximal consistent.
(\Leftarrow ) It is clear.
4. Independent sets of propositional logical formulas and \bfitC \bfitn . In this section, we state and
prove some results on independent sets of propositional logical formulas related to logical conse-
quence.
First of all, let \Sigma be an independent set of propositional logical formulas and \varphi be a formula. If
we add a formula \varphi to \Sigma , and \varphi is pairwise independent with each member of \Sigma , it is possible that
\Sigma \cup \{ \varphi \} is not independent. And the union of two independent sets of propositional logical formulas
could not be independent. In the first instance, we ask that ”under which conditions is \Sigma \cup \{ \varphi \}
independent?”. Further, ”when is the union of two independent sets of propositional logical formulas
independent?”.
These observations allows us to deduce some results on independent sets of propositional logical
formulas with respect to logical consequence operation.
Theorem 4.1. Let \Sigma be an independent set of propositional logical formulas. If Cn((\Sigma \cup
\{ \varphi n+1\} ) \setminus \{ \varphi k\} ) = Cn(\Sigma \setminus \{ \varphi k\} ) \cup Cn(\{ \varphi n+1\} ), where the union of each \varphi k \in \Sigma and \{ \varphi n+1\} is
independent set, then
\Sigma \cup \{ \varphi n+1\} is independent if and only if \Sigma \nvdash \varphi n+1.
Proof. Set \Sigma = \Sigma \cup \{ \varphi n+1\} and suppose that \Sigma is independent. Then \Sigma \setminus \{ \varphi n+1\} \nvdash \varphi n+1. As
\Sigma \setminus \{ \varphi n+1\} = \Sigma , we have \Sigma \nvdash \varphi n+1. Thus condition is necessary.
For the converse, assume \Sigma \nvdash \varphi n+1. Then
\Sigma \setminus \{ \varphi n+1\} \nvdash \varphi n+1. (4.1)
Suppose that \Sigma \cup \{ \varphi n+1\} \setminus \{ \varphi k\} \nvdash \varphi k for each \varphi k \in \Sigma . Since \Sigma is independent, we have
\Sigma \setminus \{ \varphi k\} \nvdash \varphi k, (4.2)
and as \{ \varphi k, \varphi n+1\} is independent for every \varphi k \in \Sigma it follows that
\{ \varphi n+1\} \nvdash \varphi k. (4.3)
From (4.2) and (4.3), we get \Sigma \setminus \{ \varphi k\} \nvdash \varphi k and \{ \varphi n+1\} \nvdash \varphi k. Thus by the hypothesis
\varphi k /\in Cn(\Sigma \setminus \{ \varphi k\} ) and \varphi k /\in Cn(\{ \varphi n+1\} ) \Rightarrow \varphi k /\in Cn(\Sigma \setminus \{ \varphi k\} ) \cup Cn(\{ \varphi n+1\} )) \Rightarrow
\Rightarrow \varphi k /\in Cn(\Sigma \setminus \{ \varphi k\} \cup \{ \varphi n+1\} ) \Rightarrow \varphi k /\in Cn((\Sigma \cup \{ \varphi n+1\} ) \setminus \{ \varphi k\} ).
Thereby we obtain
(\Sigma \cup \{ \varphi n+1\} ) \setminus \{ \varphi k\} \nvdash \varphi k. (4.4)
From (4.1) and (4.4), we conclude that \Sigma \cup \{ \varphi n+1\} is independent.
Theorem 4.1 is proved.
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
PROPERTIES OF THE LOGICAL CONSEQUENCE OPERATION AND ITS RELATIONSHIP . . . 863
Theorem 4.2. Let \Sigma 1 and \Sigma 2 be disjoint independent sets of propositional logical formulas and
let
Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) =
\Biggl\{
Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2), if \varphi k \in \Sigma 1,
Cn(\Sigma 1) \cup Cn(\Sigma 2 \setminus \{ \varphi k\} ), if \varphi k \in \Sigma 2.
Then for \Sigma = \Sigma 1 \cup \Sigma 2 to be independent it is necessary and sufficient that \Sigma 1 \nvdash \varphi k for every
\varphi k \in \Sigma 2 and \Sigma 2 \nvdash \varphi l for each \varphi l \in \Sigma 1.
Proof. (\Rightarrow ) Let \Sigma be independent. Then, \Sigma \setminus \{ \varphi m\} \nvdash \varphi m for all \varphi m \in \Sigma . As \Sigma 1 \cap \Sigma 2 = \varnothing ,
either \varphi m \in \Sigma 1 or \varphi m \in \Sigma 2 is hold.
Suppose that \varphi m \in \Sigma 2. As \Sigma is independent, we obtain \Sigma 1 \cup \Sigma 2 \setminus \{ \varphi m\} \nvdash \varphi m. From hence, we
get (\Sigma 1 \setminus \{ \varphi m\} ) \cup (\Sigma 2 \setminus \{ \varphi m\} ) \nvdash \varphi m. Therefore, we find \Sigma 1 \setminus \{ \varphi m\} \nvdash \varphi m and \Sigma 2 \setminus \{ \varphi m\} \nvdash \varphi m.
As \Sigma 1 \cap \Sigma 2 = \varnothing and \varphi m \in \Sigma 2, we get \Sigma 1 \setminus \{ \varphi m\} = \Sigma 1. Thus, \Sigma 1 \nvdash \varphi m is hold for all \varphi m \in \Sigma 2.
Similarly it is proved the condition of \varphi m \in \Sigma 1.
(\Leftarrow ) Suppose that \Sigma 1 \nvdash \varphi k for every \varphi k \in \Sigma 2 and \Sigma 2 \nvdash \varphi l for each \varphi l \in \Sigma 1 and \Sigma = \Sigma 1 \cup \Sigma 2.
Then either \varphi m \in \Sigma 1 or \varphi m \in \Sigma 2 is hold.
Suppose that \varphi m \in \Sigma 2. We obtain \Sigma 1 \nvdash \varphi m because of the hypothesis. Therefore, \Sigma 2 \setminus
\{ \varphi m\} \nvdash \varphi m and \Sigma 1 \nvdash \varphi m. It means that \varphi m /\in Cn(\Sigma 2 \setminus \{ \varphi m\} ) and \varphi m /\in Cn(\Sigma 1). So, \varphi m /\in
/\in (Cn(\Sigma 2 \setminus \{ \varphi m\} )\cup Cn(\Sigma 1)). We obtain \varphi m /\in (Cn(\Sigma 2 \setminus \{ \varphi m\} )\cup \Sigma 1) from the hypothesis. Thus
\varphi m /\in (Cn(\Sigma 2 \cup \Sigma 1) \setminus \{ \varphi m\} ) namely,
((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi m\} ) \nvdash \varphi m.
For \varphi m \in \Sigma 1, we get ((\Sigma 1\cup \Sigma 2)\setminus \{ \varphi m\} ) \nvdash \varphi m by using same method. Therefore, \Sigma is independent.
Theorem 4.2 is proved.
Theorem 4.3. Let \{ \Sigma i : i \in \BbbN \} be a family of independent sets. Let Cn((
\bigcup n
i=1\Sigma i) \setminus \{ \varphi k\} ) =
=
\bigcup n
i=1Cn(\Sigma i \setminus \{ \varphi k\} ) and \Sigma i \cap \Sigma j = \varnothing for i \not = j, i, j \in \BbbN . Then for
\bigcup n
i=1\Sigma i to be independent
it is necessary and sufficient that for each \varphi k \in (
\bigcup n
i=1\Sigma i) \setminus \Sigma j , \Sigma j \nvdash \varphi k.
Proof. It is proved by using induction on sets of propositional logical formulas.
Theorem 4.4. Let \Sigma 1 and \Sigma 2 be independent sets of propositional logical formulas such that
Cn(\Sigma 1) \cap Cn(\Sigma 2) = Cn(\varnothing ). Then in order to have
Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) =
\Biggl\{
Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2), if \varphi k \in \Sigma 1,
Cn(\Sigma 1) \cup Cn(\Sigma 2 \setminus \{ \varphi k\} ), if \varphi k \in \Sigma 2,
it is necessary and sufficient that \Sigma 1 \cup \Sigma 2 is independent.
Proof. (\Rightarrow ) Let Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) = Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2) for all \varphi k \in \Sigma 1. If
\varphi k \in Cn(\Sigma 1) and \Sigma 1 \setminus \{ \varphi k\} \nvdash \varphi k, then \varphi k is not a tautology and \varphi k /\in Cn(\Sigma 2) because of
Cn(\Sigma 1) \cap Cn(\Sigma 2) = Cn(\varnothing ). Thus \varphi k /\in Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2). By the hypothesis, \varphi k /\in
/\in Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ). Therefore, (\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} \nvdash \varphi k.
It is similarly showed that for all \varphi m \in \Sigma 2. As a conclusion, (\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} \nvdash \varphi k for all
\varphi \in \Sigma 1 \cup \Sigma 2. It means that \Sigma 1 \cup \Sigma 2 is independent.
(\Leftarrow ) Let \Sigma 1\cup \Sigma 2 be independent. If \Sigma 1\cup \Sigma 2 is independent then \Sigma 1 and \Sigma 2 are also independent.
If \varphi k /\in Cn(\Sigma 1 \setminus \{ \varphi k\} ) for \varphi k \in \Sigma 1, then \varphi k is not a tautology. And also \varphi k /\in Cn(\Sigma 2) because
Cn(\Sigma 1) \cap Cn(\Sigma 2) = Cn(\varnothing ). As \Sigma 1 \cup \Sigma 2 is independent, therefore \varphi k /\in Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} )
for \varphi k \in \Sigma 1. It means that Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) \subseteq Cn((\Sigma 1) \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2). We use similar
argument for \varphi k \in \Sigma 2. After that we obtain Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) \subseteq Cn(\Sigma 1) \cup Cn(\Sigma 2 \setminus \{ \varphi k\} ).
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
864 T. ÖNER, İ. ŞENTÜRK, G. ÖNER
Namely,
Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) \subseteq
\Biggl\{
Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2), if \varphi k \in \Sigma 1,
Cn(\Sigma 1) \cup Cn(\Sigma 2 \setminus \{ \varphi k\} ), if \varphi k \in \Sigma 2.
(4.5)
As Cn(\Sigma 1) \cap Cn(\Sigma 2) = Cn(\varnothing ), \Sigma 1 \cap \Sigma 2 does not include any formula without tautology.
Thereby ((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) = ((\Sigma 1 \setminus \{ \varphi k\} ) \cup \Sigma 2) for \varphi k \in \Sigma 1 and ((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) =
= (\Sigma 1 \cup (\Sigma 2 \setminus \{ \varphi k\} )) for \varphi k \in \Sigma 2 since \varphi k is not a tautology. By using Lemma 3.2 we obtain
Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) \supseteq
\Biggl\{
Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2), if \varphi k \in \Sigma 1,
Cn(\Sigma 1) \cup Cn(\Sigma 2 \setminus \{ \varphi k\} ), if \varphi k \in \Sigma 2.
(4.6)
Therefore, by using (4.5) and (4.6), we get
Cn((\Sigma 1 \cup \Sigma 2) \setminus \{ \varphi k\} ) =
\Biggl\{
Cn(\Sigma 1 \setminus \{ \varphi k\} ) \cup Cn(\Sigma 2), if \varphi k \in \Sigma 1,
Cn(\Sigma 1) \cup Cn(\Sigma 2 \setminus \{ \varphi k\} ), if \varphi k \in \Sigma 2.
Theorem 4.4 is proved.
5. Conclusion. In this paper, we give some results on consequence operation and indepen-
dent sets of propositional logical formulas by means of logical consequence operation. It turns out
that there is a bridge between propositional logical consequence operation and independent sets of
logical formulas. Our main results in here answer the question under which conditions the sets of
propositional logical formulas preserve independence.
References
1. Tarski A. On some fundamental concepts of metamathematics // Logic, Semantics and Metamathematics. – Oxford:
Clarendon Press, 1969.
2. Tarski A. Logic, semantics, metamathematics. – 2nd ed. – Indianapolis: Hackett Publ., 1983.
3. Wallmann C. A shared framework for consequence operations and abstract model theory // Log. Univers. – 2013. –
7. – P. 125 – 145.
4. Priest G. Etchemendy and logical consequence // Can. J. Phil. – 1995. – 25. – P. 283 – 292.
5. Sher G. Tarski’s logical consequence // Pacif. Phil. Quart. – 1989. – 70. – P. 341 – 368.
6. Reznikoff I. Tout Ensemble de Formules de la Logique Classique est Equivalent à un EnsembleIndependent // C. R.
Acad. Sci. Paris. – 1965. – 260. – P. 2385 – 2388.
7. Senturk I. On the independence of sets of formulas of first order: Master Thesis (in Turkish) – Ege Univ., 2012.
8. Senturk I., Oner T. On the some set theoretical properties of logical consequence // 13th Serb. Math. Congr. – 2014.
9. Senturk I., Oner T., Nuriyev U. An algebraic approach to categorical syllogisms by using bilateral diagrams // 5th
Intern. Sci. Conf. Students and Young Sci. Theor. and Appl. Aspects Cybernetics (TAAC-2015). – 2015.
10. Etchemendy J. Tarski, model theory and logical truth: Ph. D. Thesis. – Stanford Univ., 1982.
11. Wojtylak P. Independent axiomatizability of sets of sentences // Ann. Pure and Appl. Logic. – 1983. – 44. – P. 259 – 299.
12. Wojcicki R. Theory of logical calculi. – Dordrecht: Kluwer Acad. Publ., 1988.
13. Bloom S. L. Some theorems on structural consequence operations // Stud. Log. – 1975. – 34. – P. 1 – 9.
14. Givant S. R., McKenzie R. N. Alfred Tarski’s collected papers. – Birkhäuser, 1986.
15. Shapire S. The philosophy of mathematics today. – Oxford: Clarendon Press, 1998.
16. Oner T., Terziler M. Independence of countable sets of formulas of the propositional logic // Ars Combin. – 2013. –
112. – P. 73 – 80.
Received 20.10.16
ISSN 1027-3190. Укр. мат. журн., 2018, т. 70, № 6
|
| id | umjimathkievua-article-1600 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:08:52Z |
| publishDate | 2018 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/a7/194c0a3edf37292b0502d1bfa3cfd6a7.pdf |
| spelling | umjimathkievua-article-16002019-12-05T09:19:59Z Properties of the logical consequence operation and its relationship with the independence of propositional logic Властивостi операцiї логiчного наслiдку та її зв’язок з незалежнiстю пропозицiйної логiки Öner, G. Öner, T. Şentürk, İ. Онер, Г. Онер, Т. Сентюрк, І. We investigate the properties of the logical consequence operation and the characteristic features of independent sets of formulas. Further, we apply these results to propositional logic. Finally, we show under what conditions the results of addition of a formula to independent sets of formulas and the union of two independent sets of formulas are also independent, by using the operation of logical consequence, i.e., we establish a relationship between the logical consequence and the preservation of independence in propositional logic. Вивчаються властивостi операцiї логiчного наслiдку та характернi особливостi незалежних множин формул. Отри- манi результати застосовуються до пропозицiйної логiки. Крiм того, встановлено, за яких умов результат додавання формули до незалежних множин формул та об’єднання двох незалежних множин формул також є незалежним за операцiєю логiчного наслiдку, тобто встановлено спiввiдношення мiж логiчним наслiдком та збереженням незалеж- ностi у пропозицiйнiй логiцi. Institute of Mathematics, NAS of Ukraine 2018-06-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/1600 Ukrains’kyi Matematychnyi Zhurnal; Vol. 70 No. 6 (2018); 857-864 Український математичний журнал; Том 70 № 6 (2018); 857-864 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/1600/582 Copyright (c) 2018 Öner G.; Öner T.; Şentürk İ. |
| spellingShingle | Öner, G. Öner, T. Şentürk, İ. Онер, Г. Онер, Т. Сентюрк, І. Properties of the logical consequence operation and its relationship with the independence of propositional logic |
| title | Properties of the logical consequence operation and its
relationship with the independence of propositional logic |
| title_alt | Властивостi операцiї логiчного наслiдку
та її зв’язок з незалежнiстю пропозицiйної логiки |
| title_full | Properties of the logical consequence operation and its
relationship with the independence of propositional logic |
| title_fullStr | Properties of the logical consequence operation and its
relationship with the independence of propositional logic |
| title_full_unstemmed | Properties of the logical consequence operation and its
relationship with the independence of propositional logic |
| title_short | Properties of the logical consequence operation and its
relationship with the independence of propositional logic |
| title_sort | properties of the logical consequence operation and its
relationship with the independence of propositional logic |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/1600 |
| work_keys_str_mv | AT onerg propertiesofthelogicalconsequenceoperationanditsrelationshipwiththeindependenceofpropositionallogic AT onert propertiesofthelogicalconsequenceoperationanditsrelationshipwiththeindependenceofpropositionallogic AT senturki propertiesofthelogicalconsequenceoperationanditsrelationshipwiththeindependenceofpropositionallogic AT onerg propertiesofthelogicalconsequenceoperationanditsrelationshipwiththeindependenceofpropositionallogic AT onert propertiesofthelogicalconsequenceoperationanditsrelationshipwiththeindependenceofpropositionallogic AT sentûrkí propertiesofthelogicalconsequenceoperationanditsrelationshipwiththeindependenceofpropositionallogic AT onerg vlastivostioperaciílogičnogonaslidkutaíízvâzokznezaležnistûpropozicijnoílogiki AT onert vlastivostioperaciílogičnogonaslidkutaíízvâzokznezaležnistûpropozicijnoílogiki AT senturki vlastivostioperaciílogičnogonaslidkutaíízvâzokznezaležnistûpropozicijnoílogiki AT onerg vlastivostioperaciílogičnogonaslidkutaíízvâzokznezaležnistûpropozicijnoílogiki AT onert vlastivostioperaciílogičnogonaslidkutaíízvâzokznezaležnistûpropozicijnoílogiki AT sentûrkí vlastivostioperaciílogičnogonaslidkutaíízvâzokznezaležnistûpropozicijnoílogiki |