12

私は離散数学のクラスライブラリを設計していますが、無限集合を実装する方法を考えることはできません。

私がこれまでに持っているのは、インターフェイスISetを実装する抽象基本クラスSetがあります。有限集合の場合、各集合メソッドを実装するクラスFiniteSetを導出します。その後、次のように使用できます。

FiniteSet<int> set1 = new FiniteSet<int>(1, 2, 3);
FiniteSet<int> set2 = new FiniteSet<int>(3, 4, 5);
Console.WriteLine(set1); //{1, 2, 3}
Console.WriteLine(set2); //{3, 4, 5}

set1.UnionWith(set2);
Console.WriteLine(set1); //{1, 2, 3, 4, 5}

ここで、無限集合を表現したいと思います。セットから別の抽象クラスであるInfiniteSetを派生させるというアイデアがありました。その場合、ライブラリを使用する開発者は、独自のクラスを実装するためにInfiniteSetから派生する必要があります。N、Z、Q、Rなどの一般的に使用されるセットを提供します。

しかし、SubsetやGetEnumeratorなどのメソッドをどのように実装するのかわかりません。不可能だとさえ考え始めています。無限集合を実際的な方法で列挙して、別の無限集合と交差/結合できるようにするにはどうすればよいですか？コードで、NがRのサブセットであることをどのように確認できますか？そして、カーディナリティの問題に関しては..まあ、それはおそらく別の質問です。

これらすべてから、無限集合を実装するという私の考えはおそらく間違った方法であるという結論に至ります。ご意見をいただければ幸いです:)。

編集：明確にするために、私はまた、数え切れないほどの無限集合を表現したいと思います。

Edit2：最終的な目標はISetを実装することであるということを覚えておくことが重要だと思います。つまり、どのソリューションでもISetのすべてのメソッドを実装する方法を提供する必要があります。最も問題となるのは列挙メソッドとIsSubsetOfメソッドです。 。

4

5 に答える 5

7

ISet<T>数え切れないほどの無限集合を完全に実装することはできません。

これが証拠です（バートランドラッセルの礼儀）：

MySet<T>非可算集合を表すことができるクラスを作成したとします。MySet<object>次に、いくつかのオブジェクト について考えてみましょう。

特定のラベルを付け、それを「異常」MySet<object>と呼びます。instance

instance.Contains(instance)trueを返します。

同様に、次の場合instanceは「通常」のラベルを付けます。

instance.Contains(instance)falseを返します。

この区別は、すべてに対して明確に定義されていることに注意してくださいinstance。

MySet<MySet<object>>ここで、呼び出されたのインスタンスについて考えてみますparadox。

のすべての可能な通常のインスタンスを含むparadoxとして定義します。MySet<MySet<object>>MySet<object>

何をparadox.Contains(paradox)返す必要がありますか？

が返されるtrue場合paradoxは異常falseであり、呼び出されたときに返されるはずです。

それが戻る場合、falseそれparadoxは正常trueであり、それ自体で呼び出されたときに戻るはずです。

Containsこのパラドックスを解決するために実装する方法はないISet<T>ため、考えられるすべての非可算集合を完全に実装する方法はありません。

MySet<T>ここで、のカーディナリティを連続体のカーディナリティ（| R |）以下に 制限すると、このパラドックスを回避できるようになります。

Containsそれでも、停止性問題を解くことと同等であるため、実装または同様のメソッドを実行することはできません。（すべてのC#プログラムのセットのカーディナリティは| Z | <| R |に等しいことに注意してください。）

編集

もっと徹底的に言うと、「そうすることは停止性問題を解くことと同等である」という私の主張の説明がここにあります。

MySet<string>有限時間で停止するすべてのC＃プログラム（文字列として）で構成されていると考えてください（正確には、任意の入力に対して停止するとします）。それを呼び出しますparadox2。このセットは「帰納的可算」であり、実装できることを意味しますGetEnumerator（簡単ではありませんが、可能です）。これは、明確に定義されていることも意味します。ただし、このセットは、その補集合が帰納的可算ではないため、「決定可能」ではありません。 。

C＃プログラムを次のように定義します。

using ... //Everything;

public static class Decider {

    private MySet<string> _haltingSet = CreateHaltingSet();

    static void Main(string [] args) {
        Console.WriteLine(_haltingSet.Contains(args[0]));
    }
}

上記のプログラムをコンパイルし、それ自体への入力として渡します。何が起こるのですか？

メソッドが適切に実装されていればContains、停止性問題は解決しています。ただし、それは不可能であることがわかっているため、可算無限集合であっても、Contains適切に実装することは不可能であると結論付けることしかできません。

決定可能なすべてのセットMySet<T>で機能するようにクラスを制限できる場合があります。ただし、それでも、関数が有限の時間内に停止する ことはないという 、あらゆる種類の問題が発生します。

例として、と呼ばれる任意精度の実数型がRealあるとしましょうnonHalting。そのインスタンスにMySet<Real>、リーマンゼータ関数の自明でない零点がすべて含まれているとします（これは帰納的集合です）。実数部1/2のすべての複素数の集合（これも決定可能な集合）を通過したときに有限時間で戻るように適切に実装できれば、ミレニアム賞を獲得IsProperSubsetOfできます。nonHalting

于 2012-07-25T23:16:50.387 に答える
2

Setの意味を一般化する必要があります。

無限集合を作成する場合は、意味のある列挙を取得できないため、列挙操作を使用して集合操作を定義することはありません。

Set<f>メソッドの観点からを定義するbool IsMember(f obj)と、無限集合に使用できます。

2つのセットの和集合または共通部分を、2つのセットのIsMemberメソッドの論理積および/またはとして定義します。

于 2012-07-25T22:43:32.813 に答える
2

非可算集合を表す

実際にどのように行われるかという文脈でこのステートメントを調べてみましょう。たとえば、天気を尋ねる場合、セットAはセットZ（正の整数）のサブセットであり、対象はZではありません。Zのすべての数値は分析されません。分析されるのは、問題のセットAです。Ak（A sub k、kは1から| A |までの数値）をZのすべての値（無限大）と比較する方法がないため、Aのすべての値は次のようになります。 Zを構成するプロパティと比較します。Aのすべての値がZのプロパティを満たす場合、AはZのサブセットです。

コードRユニオンNでどのように表現できますか

上記と同じプロセス。Rのプロパティは「任意の実数」です。コードでは、これは「例外をスローしない任意のdouble」である可能性があります（明らかMath.Pow(-1,.5)に問題が発生し、結果としてRには含まれません）。Nのプロパティは「任意の整数」です。コードでは、これはMath.Floor！=Math.Ceilingの任意の数値にすることができます。これら2つの結合は、それらのプロパティの結合です。RまたはNのプロパティに準拠する任意の数値-コードでは、これは作成する例外をスローしない任意の数値、またはMath.Floor！=Math.Ceilingです。

概要

非可算無限集合を表すには、値ではなくプロパティを使用します。

編集

N⊆R？

それが私が追求するテーマなので、プロパティのアイデアに戻りましょう。NはRのサブセットですか？NがRのサブセットであるためには、NのプロパティがRのすべてのプロパティを満たす必要があります。プロパティのリストは正確である必要があります。無限大の数値を表すには、null許容のint型と通常のint型の符号を含むクラスを使用することをお勧めします。

public class Infinite
{
 public int? Number { get; set; }
 public int Sign { get; set; }
}

それらの線に沿った何か。Number.Value == nullは、無限を意味します。符号は、負（-1）、+-（0）、または正（1）を示すために使用できます。

RシチュエーションのNサブセットに戻ります。前述のプロパティとは別に、Nのプロパティの境界としてInfinite.Number==nullおよびInfinite.Sign==0もあります。Rと同様に、Nは境界プロパティを満たすことができます。次は、上記で定義したプロパティです。私は実際にここで立ち往生しました。.Floor==.Ceilingであるすべての数値が例外を引き起こさないことをコードで証明する方法がわかりません。ただし、これらのタイプのスーパーセット（有理数、無理数、整数、実数、複素数、虚数、超越数、代数、自然）は9つしかないため、それらの相互作用を無限スケールで特別に定義し、有限のより単純な実装を使用できます。比較。

于 2012-07-25T23:19:40.650 に答える
0

あなたはそれをどうするつもりですか。あなたはそれを列挙することはできません。

私はそれを普遍集合の子孫として扱っていると思います。

私はもう一方の端から始めると思います

Ismemberが常に真であるユニバーサルセットを定義する次に、自然数{1,2,3,4}の表現である場合、IsMemberが真である子孫はNのさらなる制限です。

とにかく考え

于 2012-07-25T23:00:26.810 に答える
0

シンボリック式の処理と同じように、多くの制限があります。

ここに小さな例があります：

class IntSet
{
    int m_first;
    int m_delta;

    public IntSet(int first, int delta)
    {
        m_first = first;
        m_delta = delta;
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();

        sb.Append('[');
        sb.Append(m_first);
        sb.Append(',');
        sb.Append(m_first + m_delta);
        sb.Append(',');
        sb.Append("...");
        sb.Append(']');

        return sb.ToString();
    }

    public IEnumerable<int> GetNumbers()
    {
        yield return m_first;

        int next = m_first;

        while (true)
        {
            next += m_delta;

            yield return next;
        }
    }
}
于 2012-07-26T00:36:59.783 に答える