1

Suppose we have a countable set $X$, say $X=\mathbb{N}$, and let $Q \colon X \rightarrow \{0,1\}$ be a function. Is $$\min \{x \in X \colon Q(x)=1\}$$ the same as $$ \inf \{x \in X \colon Q(x)=1\}.$$

What about $\max$ and $\sup$? And for uncountable sets it is not the same?

Thanks for your help.

user136457
  • 2,560
  • 1
  • 22
  • 41
  • I think they'd be the same; you're basically comparing the minimum of a bunch of $1$s and $0$s, and the infimum of a bunch of $1$s and $0$s. In any finite set, the minimum is the same as the infimum, right? – Akiva Weinberger Aug 05 '15 at 06:07
  • I am not sure whether my notation is wrong, but this is not what I wanted to express. I want the minimum $x \in X$ such that $Q(x)=1$, so the smallest element such that $Q(x)=1$ – user136457 Aug 05 '15 at 06:10
  • Oh, I see. I got confused because $Q(x)$ isn't a property. You probably should've written $Q(x)=1$ instead. (Or written "let $Q:X\to{\mathit{true},\mathit{false}}$," I guess.) Sorry. – Akiva Weinberger Aug 05 '15 at 06:12
  • Yes, I detected and changed it. Sorry for the confusion and thanks for the hint! – user136457 Aug 05 '15 at 06:12

2 Answers2

3

This has less to do with countable vs. uncountable as with the question whether $X$ well-ordered. In a well-ordered set, every non-empty subset has a minimal element. On the other hand for example $X:=\{\,\frac1n:n\in\mathbb N\,\}$ does not have a minimal element (nor does any infinite subset of $X$) even though it is countable.

Hagen von Eitzen
  • 374,180
2

It depends on the ordering of $X$. If $X$ is well ordered, I.E. Every subset has a least element, then inf and min agree in general. The naturals are a canonical example of a well ordering. But if $X$ is something like the integers or reals, then the minimum or inf might not always be defined. In the real case, for example, if $Q$ is the characteristic function of $(0,1)$, then you have an inf but no min.

The above discussion works with sup and max as well.

Zach Stone
  • 5,701
  • The reals aren't countable (but your argument works unchanged for "rationals" instead of "reals"). – Akiva Weinberger Aug 05 '15 at 06:14
  • True. I was addressing his question about uncountable sets. Although your point highlights the fact that this doesn't depend on cardinality at all. There are uncountable well ordering, and countable Ill-founded orderings. – Zach Stone Aug 05 '15 at 06:16