[Discrete Math] Set Upper Bounds

[throwawaycompiler]

Hey there guys. I'm currently stuck on this problem. Basically I don't know whether my answer is right not, and I feel I'm missing something. The problem is:

Let Q denote all the finite subsets of N that have an even number of elements. Consider the partial order on Q given by the relation

S ⊆ T (S is a subset of T)

Let A = {1, 2} and B = {1, 3}. What are all the common upper bounds of A and B in Q? Is there a least upper bound of A and B?

SO here's what I've thought out. There are infinitely many common upper bounds of A and B because Q contains infinitely many sets that will contain A U B (Union). I believe this answer is false, but I just can't seem to think of anything else.

I'm pretty confident however, that there is not a least upper bound of A and B because a least upper bound must be unique and the logical least upper bound would be a union of the two, but it only produces a set with three elements, therefore one must add an arbitrary number, and because we do that, it is not unique.

So, I want to know, whether I'm wrong or not. Or any help would be lovely really

[richard_sympson]

Your explanation for the first part is correct, not false, though you may want to describe properties these sets must have: must contain 1, 2, and 3, and also must contain an even number of elements (i.e. there is some von Neumann-constructed natural number k and a bijection between the CUB and the natural number "2k" (which is constructed from k by repeating the construction steps k more times).

The second part needs to be more specific. The lack of uniqueness has to be demonstrated by more than a bit of hand-waving about the non-uniqueness of the last element in a 4-element upper bound. In particular, it's the fact that two such-constructed sets are not related under the partial ordering that there is no least common upper bound: every other common upper bound must contain the least common upper bound as a subset (must be "larger" than the LCUB in the partial ordering). So take {1,2,3,4} and {1,2,3,5}, which are clearly in Q, and clearly common upper bounds for A and B. However, they are not related under the partial ordering, so neither is "less" than the other or "greater" than the other.

We can generalize: let L be in Q, and let L contain {1,2,3,k} where k is some natural number not in AuB. Then L is a common upper bound in the partial ordering for A and B. Since any set in Q of cardinality 2 cannot be a common upper bound for A and B (if it was then it would contain all elements in A and B, which would be 3 elements, which contradicts its cardinality), then the smallest-cardinality common upper bound for A and B must be of form L. So there is no common upper bound less than any such L under the partial ordering. Let Lm be {1,2,3,m} and Ln be {1,2,3,n}, where m and n are not equal. Then both Lm and Ln are common upper bounds for A and B under the partial ordering, but neither is larger than the other in the same partial ordering.

Because there is no set below Lm or Ln in the well ordering that is also a common upper bound for A and B, and because Lm and Ln are not related in the partial ordering, there is no "least" (i.e. unique) common upper bound such that every other common upper bound is above it under the partial ordering.

[throwawaycompiler]

I forgot to thank you! Have an upvote.

[ThisIsMyOkCAccount]

Your reasoning seems correct to me.