6

Is there a difference between properties and sets? To me, it would seem that the property of being non-self-identical is the same thing as the empty set, and the property of being (identical to x OR identical to y) is the same thing as the set {x,y}. So, what is the difference, if any, between properties and sets?

J D
  • 19,541
  • 3
  • 18
  • 83
user107952
  • 4,798
  • 21
  • 36
  • 1
    Intuitively, yes. Every property identifies a set: the set of all and only those objects satisfying the property. But... – Mauro ALLEGRANZA Oct 25 '20 at 17:07
  • 2
    ... [Russell’s Paradox](https://plato.stanford.edu/entries/russell-paradox/) – Mauro ALLEGRANZA Oct 25 '20 at 17:07
  • +1 Excellent question! – J D Oct 25 '20 at 19:00
  • The property x = x does not characterize a set. Its extension is too big. – user4894 Oct 26 '20 at 06:34
  • @user4894: That is not correct. "Too big" is no more than an artifact of some set theories. In alternative foundational systems that have a universal set/type U, the trivially true property **does** characterize U. The Russell property, on the other hand, does not characterize a set/type with boolean membership, but it may still characterize a set/type (depending on the system). It is worth noting is that the powerset/powertype in these systems are strictly smaller than U, because of Cantor's theorem. It is actually not size, but complexity. – user21820 Nov 14 '20 at 14:51
  • @user21820 Not size but complexity? I don't follow that at all. Complexity theory has nothing at all to do with this. Are you saying it does? Explanation or reference please. Or correction of your misstatement. "Too big" I agree is a casual locution that has no actual technical meaning in set theory, but it's commonly used. – user4894 Nov 25 '20 at 20:09
  • Why so aggressive? As I said, in foundational systems with a universal set, the trivially true property characterizes a set, contrary to your comment. If Cantor's theorem holds as well, then existence of injection from non-empty A to B does not imply surjection from B to A. So unlike ZFC, **size** is captured by injection but not by surjection. Surjections capture **complexity**. For example, with the obvious axiomatization of λ-terms over FOL, interpreting λ-functions as types gives the universal type U = λx.true and the Russell type λx.¬(x(x)), and λx.x injects from total λ-functions into U. – user21820 Nov 26 '20 at 03:05
  • There are many many complexity-related phenomena involving the disparity between injections and surjections that you would see if you look for it. Even wikipedia's page on injections has [this footnote](https://en.wikipedia.org/wiki/Injective_function#cite_note-6) regarding this disparity in constructive analysis, and it fits into the same complexity-based view: Given c∈A and an injection f from A to B, the obvious surjection from B to A is ( B x ↦ x∈Ran(f) ? ( y where f(y) = x ) : c ), which clearly is at least as complex as membership in Ran(f), for any good notion of complexity. @user4894 – user21820 Nov 26 '20 at 03:23
  • @user21820 By complexity I understand complexity theory as in computer science, ie the rate of growth (in time or space) of functions. Is that the way you're using it? Not being particularly aggressive, I already conceded that my use of "too big" was a casual imprecision. Mostly curious if we're both using complexity the same way. My response indicated confusion rather than aggression so apologies if I could have worded it better. – user4894 Nov 27 '20 at 07:12
  • @user21820 ps ... the linked footnote said nothing at all about complexity theory as I understand the term. I'm familiar with the fact that AC is equivalent to the proposition that every surjection has a right inverse, but far less conversant with constructive versions of same. – user4894 Nov 27 '20 at 07:24
  • @user21820 I see the footnote refers back to the proposition that every injection has a left inverse, which does not require choice. I'm familiar with that also. Not at all familiar with the claim in the footnote that {0,1} → R does not have a left inverse in constructive math. Regardless, I truly don't see any connection with complexity theory as I understand the term. – user4894 Nov 27 '20 at 07:30
  • @user21820 Googling around I see that the obvious left inverse g: R -> {0,1} that maps 1 to 1 and everything else to 0 is *verboten* in constructive math because it partitions the reals into two disjoint nonempty pieces. I can see that. But I truly and honestly and not at all aggressively, but frankly humbly, don't see how this relates to complexity theory in computer science. – user4894 Nov 27 '20 at 07:42
  • @user4894: Thanks for clarifying. It was your "correction of your misstatement" that caused me to get the impression that you were pushing me to 'admit some mistake', but it's not an issue now since you said you didn't intend aggression. The point is, in my first comment I used the term "complexity", which is a plain English word and used in a very wide variety of ways in mathematics, going well beyond "complexity theory" (which you are the only one who brought up). Just for a single example, we have arithmetical complexity, which is related to the Turing jump and hence what I said. – user21820 Nov 27 '20 at 10:37
  • If you read carefully my explanation of why the surjection from B to A built from an injection from non-empty A to B is at least as complex as membership in Ran(f), you would see that this truly holds for *any good notion of complexity*. For complexity in terms of Turing degrees: If Ran(f) is uncomputable relative to A, then so is the surjection (intensionally). This relativizes to any oracle as well. For constructive mathematics of almost any flavour: If Ran(f) is not constructive, then the surjection as stated does not provide a constructive witness to the existence of a surjection. – user21820 Nov 27 '20 at 10:47
  • @user21820 So not complexity theory in the CS sense. Thanks for clarifying. But complexity theory has a very well-defined technical definition. If you're using the word in an everyday sense that explains my confusion. Also "today I learned" that constructive mathematicians don't think {0,1} -> R has a left inverse because the left inverse is necessarily discontinuous. – user4894 Nov 27 '20 at 20:47
  • @user21820 As far as why I heard complexity and thought CS, that's from reading too much Scott Aaronson. I'll adjust my sensors appropriately. – user4894 Nov 27 '20 at 20:57
  • @user4894: Ok! Actually modern constructivists (of the appropriate type) don't think that discontinuous functions don't exist; rather they would just say it is not constructive. Unlike in the past with Brouwer and others, it is rare nowadays to find logicians who actually believe that nonconstructive things are meaningless. Ironically, Brouwer is famous for his fixed-point theorem even though he did not believe his own (non-constructive) proof... By the way, Scott Aaronson is great; his blog inspired [this post](https://math.stackexchange.com/q/2486348/21820)! – user21820 Nov 28 '20 at 03:15

1 Answers1

6

I suppose you are looking for reasons not to identify properties to sets.

(1) A set is a particular ( an abstract particular) , but properies are often considered as universals .

(2) A property is something an object possesses, shares; it is also the case for a set? I mean, could I say that an apple " possesses" the set of red objecs?

(3) Suppose you eat a red apple; the set of red things that existed before you ate the apple no longer exists; ti is replaced by a totally new set ( due to the extensionality principle) ; but the property " being red" remains unchanged.

(4) Two properties can be distinct in spite of the fact they are expressed by 2 terms referring to the same set. ( There is a conceptual / intensional aspect in the definition of a property).

(5) Not all properties determine a set , as is shown by Russell's paradox.

Reference : Marmodoro & Mayr, Metaphysics ( Oxford).

Floridus Floridi
  • 872
  • 2
  • 8