5

在几种编程语言中，存在集合集合，它们应该是有限集合的数学概念的实现。

但是，这不一定是正确的，例如在C#和中Java，这两种实现都HashSet<T>允许您将任何HashSet<T>集合添加为其自身的成员。根据数学集合的现代定义，这是不允许的。

背景：

根据朴素集合论，集合的定义是：

集合是不同对象的集合。

然而，这个定义导致了著名的罗素悖论以及其他悖论。为方便起见，罗素悖论是：

令 R 是所有不属于它们自己的集合的集合。如果 R 不是它自己的成员，那么它的定义表明它必须包含它自己，如果它包含它自己，那么它与它自己的定义相矛盾，它是所有不属于它自己的集合的集合。

所以根据现代集合论（参见：ZFC），集合的定义是：

集合是不同对象的集合，其中没有一个是集合本身。

具体来说，这是规律性公理的结果。

那么那又怎样？这意味着什么？为什么这个问题出现在 StackOverflow 上？

罗素悖论的含义之一是并非所有集合都是集合。此外，这也是数学家放弃将集合定义为通常的英语定义的地方。所以我相信这个问题在一般的编程语言设计方面有很大的分量。

问题）：

那么，为什么以某种形式在他们的设计中使用这些原则的编程语言在他们的语言库中实现 Set 时会忽略它呢？

其次，这在数学概念的其他实现中是否常见？

也许我有点挑剔，但如果这些是集合的真正实现，那么为什么会忽略定义的一部分呢？

更新

添加示例行为的 C# 和 Java 代码片段：

Java 片段：

Set<Object> hashSet = new HashSet<Object>();
hashSet.add(1);
hashSet.add("Tiger");
hashSet.add(hashSet);
hashSet.add('f');

Object[] array = hashSet.toArray();
HashSet<Object> hash = (HashSet<Object>)array[3];

System.out.println("HashSet in HashSet:");       
for (Object obj : hash)
    System.out.println(obj);

System.out.println("\nPrinciple HashSet:");
for (Object obj : hashSet)
    System.out.println(obj);

打印出来：

HashSet in HashSet:
f
1
Tiger
[f, 1, Tiger, (this Collection)]

Principle HashSet:
f
1
Tiger
[f, 1, Tiger, (this Collection)]

C# 代码段：

HashSet<object> hashSet = new HashSet<object>();
hashSet.Add(1);
hashSet.Add("Tiger");
hashSet.Add(hashSet);
hashSet.Add('f');

object[] array = hashSet.ToArray();
var hash = (HashSet<object>)array[2];

Console.WriteLine("HashSet in HashSet:");
foreach (object obj in hash)
     Console.WriteLine(obj);

Console.WriteLine("\nPrinciple HashSet:");
foreach (object obj in hashSet)
     Console.WriteLine(obj);

打印出来：

HashSet in HashSet:
1
Tiger
System.Collections.Generic.HashSet`1[System.Object]
f

Principle HashSet:
1
Tiger
System.Collections.Generic.HashSet`1[System.Object]
f

更新 2

关于Martijn Courteaux的第二点，它可以以计算效率的名义完成：

我在 C# 中制作了两个测试集合。它们是相同的，除了其中一个的 Add 方法 - 我添加了以下检查：添加到集合中的项目在if (this != obj)哪里。obj

我分别给他们两个计时，他们要添加 100,000 个随机整数：

带检查： ~ 28 毫秒

无检查： ~ 21 毫秒

这是一个相当显着的性能飞跃。

4

4 回答 4

9

编程语言集确实不像 ZFC 集，但原因与您想象的完全不同：

  1. 你不能通过理解形成一个集合（即所有对象的集合......）。请注意，这已经阻止了所有（我相信）天真的集合论悖论，因此它们是无关紧要的。

  2. 它们通常不可能是无限的。

  3. 存在不是集合的对象（在 ZFC 中只有集合）。

  4. 它们通常是可变的（即您可以在集合中添加/删除元素）。

  5. 它们包含的对象可以是可变的。

所以答案

那么，为什么以某种形式在他们的设计中使用这些原则的编程语言在他们的语言库中实现 Set 时会忽略它呢？

是语言不使用这些原则。

于 2013-09-01T07:02:53.173 回答
4

好吧，我认为这是因为一些原因：

  1. 出于非常特定的编程目的，您可能希望创建一个包含自身的集合。当您这样做时，您并不真正关心集合在数学上的含义，您只想享受 aSet提供的功能：在不创建重复条目的情况下向集合“添加”元素。（老实说，我想不出你想要这样做的情况。）

  2. 出于性能目的。您想要使用 Set 并让它包含自己的机会非常非常罕见。因此，每次尝试添加元素时检查它是否是集合本身将是对计算能力、能源、时间、性能和环境健康的浪费。

于 2013-08-31T21:32:43.323 回答
3

我不能代表 C#，但就 Java 而言，集合就是集合。如果您查看Set interface 的 javadoc，您将看到（强调我的）：

注意：如果将可变对象用作集合元素，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是集合中的一个元素，则不指定集合的​​行为。此禁令的一个特殊情况是不允许集合包含自身作为元素。

禁令是否被积极执行尚不清楚（例如，将 HashSet 添加到自身不会引发任何异常），但至少有明确的文件表明您不应该尝试，因为随后将未指定行为。

于 2013-08-31T20:56:47.343 回答
0

在java中，集合是数学集合。您可以插入对象，但集合中只能有一个。来自 javadoc 关于 set 的信息：

“一个不包含重复元素的集合。更正式地说，集合不包含一对元素 e1 和 e2，例如 e1.equals(e2)，并且最多包含一个空元素。正如其名称所暗示的那样，此接口模拟数学集合抽象。”

来源：http ://docs.oracle.com/javase/7/docs/api/

于 2013-08-31T20:51:32.323 回答