2
$\begingroup$

A question in Rudin's PMA is

Prove that the empty set is a subset of every set.

Of course, I know the proof goes something like this:

Proof: Let $S$ be any set. The proposition

$$\forall x: (x \in \varnothing \implies x \in S)$$

is true because for each $x,$ the proposition $x \in \varnothing$ is false, which makes the implication true. $\Box$

My question is about the quantifier. I have conveniently left out the domain for $x$, because I'm not really sure what it should be. My best guess is that it depends how formal we want to be. If we are informal, we would say something like "every object in the universe" or some weird thing like that. If we want to be a little more formal, we would say something like "all the objects in ZFC." (though I myself don't really know what this means, because I only know very basic set theory/logic).

So my main question is: what is the domain of $x$ in the above proof? Secondly, does the domain of a quantifier have to be a set, or not?

Thanks.

$\endgroup$
  • $\begingroup$ "every object in the universe" is pretty formal in itself; granted that your universe is a model of the theory you're studying, it is even the way to understand what the objects you're working with are. $\endgroup$ – Vsotvep Aug 24 '19 at 0:50
  • $\begingroup$ Interesting question, but the title could be more specific. $\endgroup$ – Rodrigo de Azevedo Apr 17 at 22:21
3
$\begingroup$

The "domain" is the class of all sets if you are working in the first-order theory of ZFC. Indeed, notation like $\forall x\in \mathbb R.P(x)$ in a set-theoretic context, is usually defined as shorthand for $\forall x.x\in\mathbb R \Rightarrow P(x)$. Here, again, the $\forall x$ is quantifying over every individual in our first-order theory. For ZFC, that is every "set". And this is the only option in a single-sorted, first-order theory. There is only one $\forall$ and one $\exists$ and they always quantify over everything.

(Multi-sorted first-order logic has different sorts of individuals and thus different quantifiers for each sort. Sorts, however, are not sets. They are just a way of constraining the language of the first-order theory. When we consider [traditional] semantics [in terms of sets], we'll assign a set to each sort, but different semantics will assign different sets to the same sorts.)

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

To answer your questions

First, you defined:

$$\forall x: (x \in \varnothing \implies x \in S)$$

Note that this is not a proposition. A proposition has a Truth value, either True or False. What you defined is an Universal quantification over An specified domain for which a predicate holds for the element in the domain. The elements of that domain are denoted by the variable name x and only exist inside that quantification.

The format of these quantification can be generalized to this: $$ Q v [ D : P]$$

Where Q is the quantifier for example $\forall$ or $\exists$

Where v is the variable name to denote the elements in a domain. Note this v only exists inside the [] of the quantification. This name can be anything you want but it's good practice to use distinct names for these variables when working with multiple quantifications.

Where D is the domain over which the quantification reaches and P is a predicate that is either true or false depending on a element in the domain. This is generally read as. "For D such that P".

The part inside of the [] can be written in multiple ways that in the end the quantification yields the same result. For the examples we use a universal quantification. Call the variables x, and the predicate P(x) be any predicate for the elements in the domain which yield True (What this predicate is exactly is not important for now. But most of the time if we need to prove a universal quantification we need to prove that the elements in some domain, all satisfy some predicate. The domain can be written in multiple ways which can be seen as a sort of predicate on "The universe" consisting of "everything" and narrowing this down to the desired domain.

The quantification will be in the order of the decreasing size of the specified domain.

So here some notations:

  1. $$\forall x[True: P(x)]$$

  2. $$\forall x[P(x)]$$

  3. $$\forall x[True: D(x) \implies P(x)]$$

  4. $$\forall x[D(x) : P(x)]$$

  5. $$\forall x[x \in D: P(x)]$$

  6. $$\forall x[x \in D \land (x \lor True) : P(x)]$$

  7. $$\forall x[D(x): P(x)]$$

  8. $$\forall x[x \in D \land (x = 1) : P(x)]$$

  9. $$\forall x[False : P(x)]$$

  • Notation 1* Domain = True : Predicate = P(x)

The domain being true can be seen as x in the "universe", since the universe consists of everything x will always be in the universe so this will be True. Hence we can write it as an implication: $x \in$ universe $\implies $ True. And because we know that $x \in$ universe, it is therefore allowed to omit the left hand site of the implication, So we end up with Domain: True.

Example: Since we said our predicate will always be true, think of it everything that exists, it wil always satisfy P(x). So would we use this to construct a set, we end up with the same result, thus not "filtering out" elements.

  • Notation 2* Domain = True : Predicate = P(x)

When we don't see a direct Domain that is defined we can assume the domain is True. The reason for this will become clear in the next notations.

  • Notation 3*

Domain = true : Predicate $D(x) \implies P(x)$

  • Notation 4*

Domain = D(x) : Predicate $P(x)$

  • Notation 5*

Domain: $x \in D$ : Predicate $P(x)$

So in notation 3 we still say that x is an element of the Universe. Since we said that our (universal) quantification would be true our predicate must always evaluate to true, which is always the case except when D(x) = true and P(x) = false, since False $/implies$ True = False.

Example: Since we said P(x) is always true we still havent filtered out element. But would P(x) be true or false and D(x) be a predicate to determine that is a number. Then we would up everything except when D(x) is True but P(x) = False. From now on we D(x) will be some predicate that determines that x is a number. Where it isn't important what the definition of "is a number" is.

Now we can narrow down the domain to the set of elements in the Universe where D(x) = True $ \equiv True \land D(x)$. This way we end up with notation 4. The main difference between these notations is that: Notation 3 includes the elements of the universe where D(x) and P(x) are both false and where D(x) is false and P(x) is true in it's domain. Notation 4 only includes the elements where D(x) holds as it's domain.

*Example: We now filtered everything from the previous notations + the cases that both P(x) and D(x) = false or P(x) = false and D(x) = true. So we filtered to the point Where we have all the elements that are a number and satisfy P(x). So from now on we say that set D is the set of numbers which satisfying P(X). So we can just mention D while meaning the above.

Now the quantification in notation 5 is always true. Because we defined D so it doesn't contain elements where P(x) = false. Now would we defined our set D to only contain element for which the predicate from 3 was false. Then the quantification in 5 would not be true, see why?

  • And so on we can finetune the elements that are in the domain and the predicate the elements either satisfy or not*

In general we can formulate the quantification in 2 ways which may end yielding a different truth value (as we've seen).

  1. take a full domain and use a implication. $Domain : D(X) \implies P(X)$

Or we can narrow down by saying our domain is defined as the full domain of elements that also satisfy D(X). Since we are narrowing down from the universe we can always omit the full domain from where we take a part of, since the part is always a subset of the full domain.

  1. Domain $\land$ D(X) : P(X) $\equiv$ D(X) : P(X)

Then lastly some some special cases:

Domain restricted to single element

Say we define a set D to contain all natural numbers . We can restrict our domain to even a single element like we did in notation 8. Constructing a set would yield a set with 1 element. This set is called the singleton set.

  • Domain being empty*

say we define a set D but it has no elements. This would be the case when we say that D is defined as all the elements in the universe that are in the $\emptyset$. Another example is when D is defined as the intersection of two sets that don't intersect (which is equivalent to the empty set). Then we would say eventually claim that all our elements called x are in $\emptyset$ but we know that this would always be false. Thus we have $x \in \emptyset \implies $ False and we can omit the left part of the implication. Hence our domain is now False (Empty). When this is the case we have that:

  1. $$\forall x[False: Q] \equiv True$$

  2. $$\exists x[False: Q] \equiv False$$

Think of it like saying our domain is an empty toybox.

  1. If we say that everything in this toybox is a toy. This is true because there is nothing(exists) in the toybox that is not a toy. So no matter the predicate over all the items in the toybox, we always make a statement that is true.

  2. Now if we would say there is something in the empty toybox, more precisely we say that there is a toy in this empty toybox. No matter the claim of something being(existing) in our toybox it will always be false.

So now to answer your questions.

what is the domain of x in the above proof?

reading the quantification again we don't see a domain defined thus we can read it as if the domain is "the universe" so we can read this quantification as:

$$\forall x: [ True : x \in \varnothing \implies x \in S]$$

Since you need to proof something over a $\forall$ quantification you must prove that all elements in the domain will be true for your predicate. In this case it is an implication with a lot of proofs.

Note the truth table of an implication: \begin{array}{ | m{5em} | m{1cm} | m{1cm}| } \hline p& q & p \to q \\ \hline F & F & T \\ \hline F & T & T \\ \hline T & F & F \\ \hline T & T & T \\ \hline \end{array}

So the only thing we needs to proof is that when the left side of our implication is true, that the right side of the implication is also true. Proving this shows/implies that the third case (P = true, Q = false) doesn't exist for your domain Thus the implication will be a tautology proving the quantification.

does the domain of a quantifier have to be a set, or not?

Yes because we make a claim about the quantity of things (elements) in our domain having a certain property. We do this by saying some predicate using that element will result in either true or false.

Think of the saying: * Every element in the universe either is or isn't *

So no matter over what we are quantifying. It is in either the empty set or the universe. Hence we always have a set.

Now the proof

First some definitions to understand the meaning of each.

According to the definition of subsets:

if A and B are sets and every element of A is also an element of B, then: A is a subset of B , denoted by $A \subseteq B$

According to the definitions of equality of 2 sets:

Two sets are equal if and only if they have the same elements. Formal speaking any sets A and B, A = B if and only if $$\forall x: [x \in A \iff x \in B]$$

According to the definition of the union of 2 sets:

The union of two sets A and B is the set of elements which are in A, in B, or in both A and B. Formal speaking $$A \cup B = {x : x \in A \lor x \in B}$$

Now to the proof:

Prove that the empty set is a subset of every set.

Proof: Let S be any set. Let T be a set that is equal to S.

Since all elements that are in S, are in S. S satisfies the predicate below. $$\forall x: [x \in S : x \in S]$$

Then by the definition of equality we could say that S is always equal to itself, so $S = S$. Thus according to the definition of subset we can say that S is always a subset of itself $S \subseteq S$. To show it holds for both ways around $S \subseteq T$ and $T \subseteq S$.

The empty set is defined as the unique set having no elements. So it's cardinality (count of elements in a set) is 0. A common notation of the empty set is $ \emptyset$ but to visualize the set we write it in usual set notation:

The empty set = {}

Then by the definition of equality, $\emptyset = \emptyset$. Hence $\emptyset$ is a subset of itself $\emptyset \subseteq \emptyset $.

Thus far we defined 3 sets which we can visualize like:

The arbitrary set T = {$x \in T: x \in T$}

The copy of T called S = {$x \in T: x \in S$}

The empty set = {}

Now let U be the union of S and the empty set. Since S has #S amount elements and the empty set has $\# \emptyset = 0$ elements we see that U has $\#S + \# \emptyset = S \pm 0$ elements $= \#S$. Thus the amount of elements is still the same. Then by the definition of equality we can say that $U = S$, thus $S \cup \emptyset = S $ Hence, since S was a subset with itself it follows that $S \cup \emptyset \subseteq S $

So we have that

  1. $S \subset S$

  2. $S = S = S \cup \emptyset$

  3. $\emptyset = \emptyset = \emptyset \cup \emptyset$

  4. $\emptyset \subset \emptyset$

  5. $\emptyset \subset S$

Hence, since any set being equal to taking that set with the union of the empty set, and any two equal sets being subsets of each other. The empty set is always a subset of any arbitrary set.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.