5
$\begingroup$

I have encountered set theory exclusively in the context of classical logic so far.

Negation in classical logic has both following properties due to its bivalence:

  • the negation of a truth value is some other truth value
  • the negation of a truth value is every other truth value

The law of excluded middle follows from the second property naturally.

In many-valued logics mathematicians have to chose between those two properties, and so far I have only found examples that implement the first property. $P \vee \neg P$ is not self-evident any more.

That said I wonder what it means for set theory in the context of many-valued logics. In classical logic, $\mathcal{P}(S)$, the power set of $S$ is bijective to ${\{0, 1\}}^S$, presumably again because of bivalence: $x \in S$ or $\neg(x \in S)$.

What about power sets in the context of e.g. three-valued logics? Is a bijection between $\mathcal{P}(S)$ and ${\{0, 1, 2\}}^S$ possible?

$\endgroup$
5
  • $\begingroup$ Presumably the definition of $\cal P(S)$ is related to the axiom of power set, so you need to specify which truth value we assign to the axiom and how the quantifiers are interpreted. Is there a standard way of doing that? $\endgroup$
    – Karl
    Mar 17, 2021 at 20:48
  • $\begingroup$ Good question, I found jstor.org/stable/44083479 but don't have access to it. $\endgroup$
    – Damian
    Mar 17, 2021 at 21:06
  • $\begingroup$ Relatedly, the definition of $A^S$ as the set of functions from $S$ to $A$ needs clarification. For which truth values of $x\in A$ is $f(x)$ defined? $\endgroup$
    – Karl
    Mar 17, 2021 at 21:09
  • $\begingroup$ It is fascinating how much I took for granted when I formulated my question. $\endgroup$
    – Damian
    Mar 17, 2021 at 21:28
  • $\begingroup$ Try Goldblatt's book 'Topoi'. $\endgroup$
    – Berci
    Mar 17, 2021 at 21:38

1 Answer 1

1
$\begingroup$

One could, technically, define a "set" theory based on many valued logics. Multisets can easily be defined using many-valued logics and are a great generalization to sets.

A few things to note: Firstly, the standard assumption is that the $\in$ relational operator has two truth values, say $\{\mathbb{T},\mathbb{F}\}$. Either $x \in S$ is true, or it is false, but not both. Secondly, other relators, such as $=$ or $\subseteq$, can be defined based only on the assumed truth value of $\in$ between many different objects.

If one uses many-valued logic, $x \in S$ could be neither true nor false. You can still have the plain old ZFC axioms, but you would need to redefine what conjunction, disjunction, implication and negation now are. The "for all" and "there exists" quantifiers are essentially "large operators" over and and or respectively. This is kind of like taking a(n infinite) sum over everything, but you "and", and "or" any arbitrary number of truth values instead.

For example, one can construct a set theory using three-valued logic. We will assume an undetermined/unknown/undecided, or in-between truth value, so our truth values are $\{\mathbb{T},\mathbb{F},\mathbb{U}\}$.

One defines conjunction (and) as:

$$\begin{array}{c|ccc} ∧ & \mathbb{T} & \mathbb{U} & \mathbb{F} \\ \hline \mathbb{T} & \mathbb{T} & \mathbb{U} & \mathbb{F} \\ \mathbb{U} & \mathbb{U} & \mathbb{U} & \mathbb{F} \\ \mathbb{F} & \mathbb{F} & \mathbb{F} & \mathbb{F} \\ \end{array}$$

One defines disjunction (or) as:

$$\begin{array}{c|ccc} ∨ & \mathbb{T} & \mathbb{U} & \mathbb{F} \\ \hline \mathbb{T} & \mathbb{T} & \mathbb{T} & \mathbb{T} \\ \mathbb{U} & \mathbb{T} & \mathbb{U} & \mathbb{U} \\ \mathbb{F} & \mathbb{T} & \mathbb{U} & \mathbb{F} \\ \end{array}$$

One defines implication (implies) as:

$$\begin{array}{c|ccc} \rightarrow & \mathbb{T} & \mathbb{U} & \mathbb{F} \\ \hline \mathbb{T} & \mathbb{T} & \mathbb{U} & \mathbb{F} \\ \mathbb{U} & \mathbb{T} & \mathbb{T} & \mathbb{F} \\ \mathbb{F} & \mathbb{T} & \mathbb{T} & \mathbb{T} \\ \end{array}$$

One defines negation (not) as:

$$\begin{array}{c|ccc} \neg & \\ \mathbb{T} & \mathbb{F} \\ \mathbb{U} & \mathbb{U} \\ \mathbb{F} & \mathbb{T} \\ \end{array}$$

One thing you will indeed notice is that some of the tautologies you noted, like $P ∨ \neg P$, no longer hold true.

Based solely on these truth tables, we can now review some of the ZFC axioms and see if they make sense.

Before going any further, one should construct a set notation, given the already defined logic. In classical set theory, one simply uses $\{\}$ and everything inside those brackets is in the set, while everything outside of those brackets is not in the set. Given $S=\{a,b,c\}$, we can say $a\in S$, $b\in S$, $c\in S$, while everything else $\notin S$ (e.g. $d\notin S$). However, when dealing with 3-valued logic, $\{\}$ is no longer sufficient notation for such a collection anymore. There are two possibilities for $d \in S$. Either it is undecided, or it is false. How do we distinguish between the two? One should instead use a double brackets, $\{\}\{\}$, or a pair of brackets, $(\{\},\{\})$. I will stick with the latter notation for convenience.

For example, the axiom of equality implies that

$\forall a \forall b (a=b) \rightarrow \forall c (c \in a) \leftrightarrow (c \in b)$.

Here $\leftrightarrow$ (if and only if) is what you think it means: $a \leftrightarrow b = (a \rightarrow b) ∧ (b \rightarrow a)$.

One important thing about this axiom is that it assumes everything is a set ("everything") in terms of a given universe of discourse that is. This is true of classical set theory as well. In classical set theory, one can say that either $a=b$ or $a≠b$. But in 3-valued logic, $a=b$ could be undecided.

$(\{a,b,c\},\{d,e\}) = (\{a,b,c\},\{d,e\})$

$(\{a,b,c\},\{d,e\}) = (\{a,b\},\{c,d,e\})$ is undetermined.

$(\{a,b,c\},\{d,e\}) ≠ (\{a,b,c\},\{d,e,f\})$

One defines the elements in the first bracket to be contained in that set, and the elements contained within the second bracket to have undecided set membership. So $S=(\{a,b,c\},\{d,e\})$. means that $a\in S$, $b\in S$, $c\in S$, $d\in S$ is undecided, $e\in S$ is undecided, everything else $f,g,...$ is $\notin S$.

One can see that basic set operations, like union and intersection, can be defined in the same manner for three valued logic as two valued logic (techincally, we should use the axiom of union here):

$x \in A \cup B \leftrightarrow (x \in A) ∨ (x \in B)$

$x \in A \cap B \leftrightarrow (x \in A) ∧ (x \in B)$

$x \in A / B \leftrightarrow (x \in A) ∧ (x \notin B)$

$x \in A \Delta B \leftrightarrow x \in (A / B) \cup (B / A)$

$...$

For example, the union of $(\{a,b\},\{c\})$ and $(\{e,c\},\{d\})$ would be $(\{a,b,c,e\},\{d\})$.

Since you were asking specifically about power sets, and subsets, one can still use the definition of a subset, and axiom of the Power set (from ZFC) to explicitly define them for our type of set:

$\forall a \forall b (a \subseteq b) \rightarrow \forall c (c \in a) \rightarrow (c \in b)$.

Here it is important to note again, that like equals, it is not always the case that either $a \subseteq b$ or $a \subsetneq b$. This becomes crucial for defining the power set of a set, since our powerset is no longer a classical set, but the one we defined. The axiom of the power set is:

$\forall a \exists p \forall x (x \in p) \leftrightarrow (x \subseteq a)$

Now that the power set exists, and is properly defined, we can construct the power set $\mathcal{P}(S)$ for any set $S$. For example, if $S=(\{a,b\},\{c\})$, then the possible subsets of $S$ are: $(\{a,b\},\{c\}), (\{b\},\{a,c\}), (\{b\},\{c\}), (\{a\},\{b,c\}), (\{\},\{a,b,c\}), (\{\},\{b,c\}) (\{a\},\{c\}), (\{\},\{a,c\}), (\{\},\{c\}), (\{a,b\},\{\}), (\{b\},\{a\}), (\{b\},\{\}), (\{a\},\{b\}), (\{\},\{a,b\}), (\{\},\{b\}) (\{a\},\{\}), (\{\},\{a\}), (\{\},\{\})$ Each of these 18 subsets are members of $\mathcal{P}(S)$. We still need to find all possible sets for which $\subseteq S$ is undetermined, which are: $(\{a,b,c\},\{\}), (\{b,c\},\{a\}), (\{b,c\},\{\}), (\{a,c\},\{b\}), (\{c\},\{a,b\}), (\{c\},\{b\}) (\{a,c\},\{\}), (\{c\},\{a\}), (\{c\},\{\})$

So our $\mathcal{P}(S) = (\{(\{a,b\},\{c\}), (\{b\},\{a,c\}), (\{b\},\{c\}), (\{a\},\{b,c\}), (\{\},\{a,b,c\}), (\{\},\{b,c\}) (\{a\},\{c\}), (\{\},\{a,c\}), (\{\},\{c\}), (\{a,b\},\{\}), (\{b\},\{a\}), (\{b\},\{\}), (\{a\},\{b\}), (\{\},\{a,b\}), (\{\},\{b\}) (\{a\},\{\}), (\{\},\{a\}), (\{\},\{\})\},\{(\{a,b,c\},\{\}), (\{b,c\},\{a\}), (\{b,c\},\{\}), (\{a,c\},\{b\}), (\{c\},\{a,b\}), (\{c\},\{b\}) (\{a,c\},\{\}), (\{c\},\{a\}), (\{c\},\{\})\})$.

Since cardinalities are definable for classical sets, it makes sense to define them for our type of set, which is an ordered pair of cardinal numbers. If $|S| = (a,b)$ it means that there are $a$ elements $\in S$, and $b$ elements such that $\in S$ is undetermined. So if $S=(\{a,b\},\{c\})$, it would have cardinality $(2,1)$, and $\mathcal P(S)$ would have cardinality $(18,9)$.

For some combinatorics, given $|S| = (a,b)$, what is $|\mathcal P(S)|$ ? Firstly, we see that for all $x \in S$, there are three choices for $x \in T$ where $T \subseteq S$, namely $\{\mathbb{T},\mathbb{F},\mathbb{U}\}$. If $x \in S$ is undetermined, then there are only two choices for $x \in T$, either $\{\mathbb{F},\mathbb{U}\}$.

Hence, the number of $x \in \mathcal P(S)$ is $3^a2^b$. One also needs to count the number of sets $T$ which $T \subseteq S$ is undecided. By definition of the power set, there must be at least one element $x \in T$ such that $x \in S$ is undecided. In fact, for all elements such that $x \notin S$ is not the case, there are three options for inclusion. So far, there are $3^{a+b}$ possible sets. However, we need to exclude those sets which fail to meet the criterion above. These are the sets which are already members of $\mathcal P(S)$. Hence, the number of possible sets with undetermined set relation are $3^{a+b}-3^a2^b$. The cardinality of the power set $\mathcal P(S)$ is $(3^a2^b, 3^{a+b}-3^a2^b)$.

In the special case where there are no undecided set relations $(b=0)$, it follows that $|S|=(a,0)$ and $|\mathcal P(S)| = (3^a, 0)$.

One can come up with many different generalizations of set-related concepts, such as von-Neumann ordinals, functions, domains/images, etc. But the important thing is we have to define what they are using axioms or derivation from axioms.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .