VERY simple C# Set implementation

Question

This is not meant to solve any insane real world problems. I just want to make sure my Set logic is right and the code looks okay. It feels weird implementing it with a Dictionary of dummy values but it seems that's how most languages do it anyway. What do you think?

public class Set : IEnumerable
    {
        private readonly Dictionary<object, bool> _items;

        public Set()
        {
            _items = new Dictionary<object, bool>();
        }

        public void Add(object item)
        {
            if (!_items.ContainsKey(item))
            {
                _items.Add(item, true);
            }
        }

        public void Remove(object item)
        {
            if (_items.ContainsKey(item))
            {
                _items.Remove(item);
            }
        }

        public bool Contains(object item)
        {
            return _items.ContainsKey(item);
        }

        public int Count()
        {
            return _items.Keys.Count;
        }

        public void Clear()
        {
            _items.Clear();
        }

        public void UnionWith(Set input)
        {
            foreach (var item in input.Cast<object>().Where(item => !_items.ContainsKey(item)))
            {
                _items.Add(item, true);
            }
        }

        public void IntersectWith(Set input)
        {
            var newSet = new Set();
            foreach (var item in _items.Keys.Where(input.Contains))
            {
                newSet.Add(item);
            }
            Clear();
            foreach (var item in newSet)
            {
                _items.Add(item, true);
            }
        }

        public void DifferenceWith(Set input)
        {
            var newSet = new Set();
            foreach (var item in _items.Keys.Where(item => !input.Contains(item)))
            {
                newSet.Add(item);
            }
            Clear();
            foreach (var item in newSet)
            {
                _items.Add(item, true);
            }
        }

        public bool IsSubsetOf(Set input)
        {
            return _items.Keys.All(input.Contains);
        }

        public IEnumerator GetEnumerator()
        {
            return _items.Keys.GetEnumerator();
        }
    }

Answer 1

I'm going to assume that you already know about HashSet and ISet in the following review and are just missing the reinventing-the-wheel tag.

ICollection

You've got Add, Remove, Clear, Count, and Contains. If you add a CopyTo(T[] array, int arrayIndex) and bool IsReadOnly { get { return false; } } to your implementation then you can implement ICollection.

Why Dictionary?

Perhaps you'd be better suited with a HashSet<T> implementation? Correct me if I'm wrong but it doesn't appear you're actually using the boolean value of the dictionary, so you'd be better suited with a Hashset<T>.

Generics

You could create a generic implementation Set<T> fairly easily. And if you wanted to still allow your existing functionality then you'd use Set<object>.

Set Operations

Perhaps consider having your operator functions return the new set from their actions?

For example,

public Set UnionWith(Set input)
{
    var unionedSet = new Set(_items); // See suggestion below.
    foreach (var item in input.Where(x => _items.ContainsKey(item)))
    {
        unionedSet.Add(item, true);
    }

    return unionedSet;
}

Constructor

Adding the ability to give IEnumerable or ICollection of items in a constructor could be really helpful, especially if you have your set operations return new sets as suggested above.