# Set-Theoretic Omniscience and Set Definition

It occurred to me the other day that a set can, in some sense, know more than I do. This is because a set does not contain duplicate objects, and yet if the same object is defined in two different ways it may be very difficult for me to realize that they are the same (it could even be NP-hard). That's what I'm calling "Omniscience."

I realize that there is no paradox here, and I'm not trying to create one. I'm just interested in various philosophies of set theory, in constructivism, alternate axioms, and related issues so I'm wondering if anyone has taken issue with the "omniscience" of sets and tried to go about set theory in a different way because of it.

Another thing about sets is that two sets defined differently may be equal in extensionality, but completely different as far as how I actually go about determining their membership. In fact there may be theorems from Complexity Theory about how hard it is for me to identify two sets as the same. Is there any approach to math which takes this into account, perhaps treating sets as processes rather than totalities?

• You may find something like light affine set theory (LAST) interesting, and perhaps implicit computational complexity in general. Sep 19, 2018 at 7:24

The distinction you're seeing is a very real one, and is treated seriously in both philosophical and mathematical logic; the prevalance of the extensional approach should be taken as a sign of its strength rather than the weakness/uninterestingness of intensional approaches.

You're getting at precisely the extensionality versus intensionality issue. The extensional perspective (as per the axiom) says that a set is determined entirely by its elements; the intensional view, by contrast, says that there is additional relevant data, and usually this data is taken to be some meaning or process assigned to the set.

It's important to note that this issue persists outside set theory. For a natural language example, "morningstar" and "eveningstar" are extensionally equivalent but are a priori different notions; so we can imagine an "intensional" universe of names sitting above an "extensional" universe of referents. This is a huge motivation in philosophical logic, and in particular modal logic; see e.g. here. It's also a natural aspect of intuitionism, or any philosophy of mathematics which views the mathematical universe as a "product of the mind" (or similar).

To be a bit more specific:

Your particular focus on how hard it is to "know" that two things are equal takes us to a very precise notion on logic, namely provable equality (or more generally "provable ---ness"). This is generally a hugely important idea, even when we're only interested in a semantic and extensional picture of things. I think the place this is most obvious is in Henkin's proof of the completeness theorem. Given a consistent theory $\Gamma$, Henkin (after perhaps modifying $\Gamma$ in a technical way) looks at the structure $\mathcal{T}(\Gamma)$ assigned to $\Gamma$ as follows:

• Elements of $\mathcal{T}(\Gamma)$ are equivalence classes of terms in the language of $\Gamma$, with the equivalence relation being "$\Gamma$-provable equality."

• The language of $\Gamma$ is then interpreted on this set of equivalence classes by saying that relations hold precisely when they provably hold: e.g. if $U$ is a unary relation symbol in the language of $\Gamma$ and $t$ is a term in the language of $\Gamma$, then $U$ holds of the equivalence class of $t$ in $\mathcal{T}(\Gamma)$ iff $\Gamma$ proves $U(t)$.

So the objects of $\mathcal{T}(\Gamma)$ are "really" just names for objects. Note that this is all taking place inside classical logic: the intensional perspective is useful even within extensional mathematics.

Conversely, one could always argue that "intensionality is extensionality in disguise" - whenever we move from an "extensional world of objects" to an "intensional world of objects-via-definitions," what we've really done is move to an "extensional world of definitions" - our new objects are definitions, and they're treated extensionally! This is of similar spirit to how many-valued logic can be situated inside first-order logic, or how classical logic can be embedded into intuitionistic logic, or ... Basically each perspective is so broad that it can simulate the other. This is a good thing for each (in my opinion).

• Another example of this phenomenon is the idea of "provable totality" in proof theory. Roughly speaking, a function is provably total relative to a given theory if it has some definition which the theory proves defines a total function: that is, the theory should prove $\forall x\exists !y\varphi(x,y)$. The actual notions of provable totality considered arise by restricting attention to definitions of certain forms, e.g. via Turing machines, and understanding what functions a theory proves are total (in a given sense) gives us lots of information about the theory as a whole. This is closely connected with a similar but more technical notion in proof theory: proof-theoretic ordinals.
• Oh yeah, I forgot to add in the OP that the equality of two sets may even be independent... which is the strangest case of all. What is "provable totality" in proof theory? Sep 18, 2018 at 22:54
• @DPatt I've added a bit. Does that help? Sep 18, 2018 at 22:58

It occurred to me the other day that a set can, in some sense, know more than I do. This is because a set does not contain duplicate objects...

Duplicate elements are only an issue in set-builder notation, e.g. $X=\{0, 1, 1\}$

Translating this set-builder notation into the language of standard set theory, we would have:

$\forall a: [a\in X \iff a=0 \lor a=1 \lor a=1]$

Dropping the second disjunction, it would then be trivial to prove that:

$\forall a: [a\in X \iff a=0 \lor a=1]$

Translating this back to set-builder notation, we would have:

$X=\{0, 1\}$

• This doesn't have anything to do with the actual question. The OP is asking how the difficulty of telling whether two definitions refer to the same object plays (or doesn't play) a role in set theory, not why sets don't have duplicate elements - "I'm wondering if anyone has taken issue with the "omniscience" of sets and tried to go about set theory in a different way because of it." Sep 19, 2018 at 3:08
• But rewriting those conjunctions is equivalent to rewriting the sets, and will be NP-complete in general Sep 19, 2018 at 3:59
• @NoahSchweber I am pointing out that the notion of duplicated elements in a set is a an artifact of set-builder notation. It does not come up in set theory. Sep 19, 2018 at 4:14
• @DPatt What do you meaning by "writing (or rewriting) a set?" It is not a notion defined in the ZFC axioms of set theory. See en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory. Sep 19, 2018 at 4:27
• I realize that. The question is hoping to take us outside of ZFC Sep 19, 2018 at 4:31