Subset definition: universal quantifier over which set?

In summary: B## if and only if the size of ##A## is the same as the size of ##B##'.Number ##1## is correct. It is over all possible ##x##, i.e. the set wherever ##x,A,B## live in.
  • #1
strauser
37
4
This is a somewhat trivial question, but I never managed to learn much logic back in the day...so:

The definition of a subset can be written as:

## A \subset B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) ##

However, over which set is ##\forall## supposed to quantify? It seems to me that the two possibilities are that:

1) it quantifies over a perhaps-unmentioned universal set, of which A and B are subsets - this makes the test look like it requires a lot of
redundant work, as we certainly don't need to check elements that are not in A.
or
2) it quantifies over A, which makes the definition look clunky - why not just use the notation ##\forall x \in A(x \in B)## or similar?
 
Physics news on Phys.org
  • #2
strauser said:
This is a somewhat trivial question, but I never managed to learn much logic back in the day...so:

The definition of a subset can be written as:

## A \subset B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) ##

However, over which set is ##\forall## supposed to quantify? It seems to me that the two possibilities are that:

1) it quantifies over a perhaps-unmentioned universal set, of which A and B are subsets - this makes the test look like it requires a lot of
redundant work, as we certainly don't need to check elements that are not in A.
or
2) it quantifies over A, which makes the definition look clunky - why not just use the notation ##\forall x \in A(x \in B)## or similar?
Number ##1## is correct. It is over all possible ##x##, i.e. the set wherever ##x,A,B## live in.

But what do you mean by test? There is no algorithm involved. The implication ##x\in A \Longrightarrow x\in B## is the crucial part here. If ##x\in A## then ##x\in B## automatically holds, if ##x\notin A## then nothing can be said. ##x## could still be an element of ##B##, or not.
 
  • Like
Likes sysprog
  • #3
fresh_42 said:
Number ##1## is correct. It is over all possible ##x##, i.e. the set wherever ##x,A,B## live in.
OK, thanks. That is how I would have interpreted it.

But what do you mean by test? There is no algorithm involved.
That's true, but it betrays the way I tend to think about the question: how would you automate the procedure in a programming language, say, or how would you manually check the subset status of two sets written in list notation, maybe.

To my mind, interpretation 1 is slightly odd, since it would require an automated procedure that works through all elements x in the universal set, evaluating the the truth value of the statements "x in A" and "x in B".

But I probably don't think like a logician here, I will concede.

The implication ##x\in A \Longrightarrow x\in B## is the crucial part here. If ##x\in A## then ##x\in B## automatically holds, if ##x\notin A## then nothing can be said. ##x## could still be an element of ##B##, or not.
I don't really understand the point that you are making here; for example, what is the significance of the word "automatically"?
 
  • #4
strauser said:
I don't really understand the point that you are making here; for example, what is the significance of the word "automatically"?
Whenever ##x## is an element of ##A##, it is always within ##B## as well. There is no way for ##x## being outside of ##B## if ##A\subseteq B##, which we have given, if we read the entire definition.

An alternative description would be
$$
A\subseteq B \Longleftrightarrow \;\forall_{x\in A}\,x\in B
$$
But if we write the RHS as ##x\in A \Longrightarrow x\in B##, then there is an "any" in front of the ##x##.
 
  • #5
strauser said:
This is a somewhat trivial question, but I never managed to learn much logic back in the day...so:

The definition of a subset can be written as:

## A \subset B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) ##

However, over which set is ##\forall## supposed to quantify? It seems to me that the two possibilities are that:

1) it quantifies over a perhaps-unmentioned universal set, of which A and B are subsets - this makes the test look like it requires a lot of
redundant work, as we certainly don't need to check elements that are not in A.
or
2) it quantifies over A, which makes the definition look clunky - why not just use the notation ##\forall x \in A(x \in B)## or similar?
The expression ##\forall x \in A(x \in B)## is not a sentence ##-##
it can be interpreted as
'for all members of ##A## that are also members of ##B##',
whereas the expression ## A \subset B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) ##
can be interpreted as
'##A## is a subset of ##B## if and only if every member of ##A## is also ipso facto a member of ##B##' ##-##
that expression could be rewritten without the universal quantifier as ##(A \subset B )\Leftrightarrow (|A \cap B| = |A|)##,
which can be interpreted as
'##A## is a subset of ##B## if and only if the cardinality of the intersection of ##A## with ##B## is equal to the cardinality of ##A##',
or as
##(A \subset B )\Leftrightarrow (|A \cup B| = |B|)##,
which can be interpreted as '##A## is a subset of ##B## if and only if the cardinality of the union of ##A## with ##B## is equal to the cardinality of ##B##' ##-##
to make it a more general 'definition', i.e. predicating upon all subsets and supersets; not just upon ##A## and ##B## in particular, we could use the universal quantifier, with a scope that designates any ##A## and ##B## such that ##A## is a subset of ##B##, like this:
##\forall(A,B) [(A \subset B) \Leftrightarrow (|A \cap B| = |A|)]##,
which we can interpret as
'for any subset and superset pair ##A## and ##B##, ##A## is a subset of ##B## if and only if the cardinality of the intersection of ##A## and ##B## is equal to the cardinality of ##A##',
or like this:
##\forall(A, B) [(A \subset B) \Leftrightarrow (|A \cup B| = |B|)]##,
which we can interpret as
'for any subset and superset pair ##A## and ##B##, ##A## is a subset of ##B## if and only if the cardinality of the union of ##A## and ##B## is equal to the cardinality of ##B##' ##-##
the universe of discourse here does not include non-finite sets.
 
Last edited:
  • #6
strauser said:
To my mind, interpretation 1 is slightly odd, since it would require an automated procedure that works through all elements x in the universal set, evaluating the the truth value of the statements "x in A" and "x in B".

The procedure need only consider the list of elements for ##A## since we use use interpretation 1 combined with the knowledge that ##x \in A \implies x \in B## is a True statement when ##x \notin A## is False.
 
  • Like
Likes sysprog
  • #7
Stephen Tashi said:
The procedure need only consider the list of elements for ##A## since we use use interpretation 1 combined with the knowledge that ##x \in A \implies x \in B## is a True statement when ##x \notin A## is False.
You mean using the false-implies-anything idea? If so, good point. If not, can you expand please?
 
  • #8
sysprog said:
The expression ##\forall x \in A(x \in B)## is not a sentence ##-##
it can be interpreted as
'for all members of ##A## that are also members of ##B##',
Slightly short of time right now but one question:

##x \in B## is a proposition, isn't it? So does ##\forall x \in A(x \in B)## not say "for all x in A, the proposition x is in B is true"?
 
  • Like
Likes sysprog
  • #9
strauser said:
Slightly short of time right now but one question:

##x \in B## is a proposition, isn't it? So does ##\forall x \in A(x \in B)## not say "for all x in A, the proposition x is in B is true"?
I suppose that it depends on which convention you're following ##-## it seems reasonable to me to interpret it it that way ##-## I interpreted it as 'for all x in A such that x is in B', but I must admit that I normally would use braces, and not parens, for that interpetation, i.e. ##\forall x \in A[x \in B]##, so I could simply be in error notationally in interpreting it as I did ##-## I would write your interpretation as ##\forall x[x \in A \Rightarrow x \in B]##.
 
  • Like
Likes strauser
  • #10
sysprog said:
I suppose that it depends on which convention you're following ##-## it seems reasonable to me to interpret it it that way ##-## I interpreted it as 'for all x in A such that x is in B', but I must admit that I normally would use braces, and not parens, for that interpetation, i.e. ##\forall x \in A[x \in B]##, so I could simply be in error notationally in interpreting it as I did ##-## I would write your interpretation as ##\forall x[x \in A \Rightarrow x \in B]##.
1. I think that I probably should have written "predicate" not "proposition"
2. I'm not sufficiently familiar with logical notation to know what the conventions are, I'm afraid.
3. I note that this wikipedia section on quantifiers suggests that ##\forall x \in A (x \in B) \Leftrightarrow \forall x (x \in A \Rightarrow x \in B)## unless I am very confused. But that also suggests that of my two initial suggestions, the second was correct, not the first.

Hmm, I think I need a "baffled by logic" emoji.
 
  • #11
fresh_42 said:
An alternative description would be
$$
A\subseteq B \Longleftrightarrow \;\forall_{x\in A}\,x\in B
$$
What does the subscripted ##x \in A## notation mean? I've never seen that before.

But if we write the RHS as ##x\in A \Longrightarrow x\in B##, then there is an "any" in front of the ##x##.
I don't follow what point you are making here; and also, there are two ##x##s - I guess you are referring to the first?
 
  • #12
strauser said:
What does the subscripted ##x \in A## notation mean? I've never seen that before.
It means: ##\forall x\in A \, : \,x\in B##. For all ##x\in A## we have ##x\in B##. As mentioned by others, this is not a sentence. It is a short way of saying ##x\in A \Longrightarrow x\in B##. You could rephrase the last statement as ##\forall x\in X \wedge x\in A \Longrightarrow x\in B## and abbreviate the first term by ##\forall x\in A##.
I don't follow what point you are making here; and also, there are two ##x##s - I guess you are referring to the first?
They are the same. It means: Any (single) ##x## which belongs to ##A## does (automatically = per definition of ##A##) also belong to ##B##.
 
  • Like
Likes strauser
  • #13
strauser said:
Hmm, I think I need a "baffled by logic" emoji.
It seems to me you are getting confused more by notation than by meaning. The concept of one set being a subset of another set seems a simple idea. All we are trying to do here is to put that in formal notation. If you know what a subset is, then that ought to help you understand the formal notation. You shouldn't have to decipher the formal notation to know what it means: it means ##A## is a subset of ##B##. The concept of subset is not being changed here.

To take an analogy, here's a dictionary defintion:

Whale: a very large marine mammal with a streamlined hairless body, a horizontal tail fin, and a blowhole on top of the head for breathing.

If you've seen a whale, that should make perfect sense. If you've never seen a whale, then you might read that definition and think "streamlined hairless body"? What does that mean?
 
Last edited:
  • Skeptical
Likes madness
  • #14
PeroK said:
It seems to me you are getting confused more by notation than by meaning. The concept of one set being a subset of another set seems a simple idea. All we are trying to do here is to put that in formal notation. If you know what a subset is, then that ought to help you understand the formal notation. You shouldn't have to decipher the formal notation to know what it means: it means ##A## is a subset of ##B##. The concept of subset is not being changed here.
To ensure that this thread doesn't derail, I ought to point out that my question is *purely* about notation. I do indeed have no confusion about the concept of a subset, but rather about the conventions used in used in logic (I guess this is first-order logic?) to notate them. I managed to get a degree in maths without studying any logic formally, so I'm rather hazy on the conventions and assumptions that logicians use.

Anyway, I'm going to have to put this to one side for now due to time constraints, but thanks for all the responses, to which I shall give due consideration. And I'm going to buy a couple of books on logic so that I can chug through some elementary problems - that will likely clear up at least some of my problems.
 
  • #15
fresh_42 said:
They are the same. It means: Any (single) ##x## which belongs to ##A## does (automatically = per definition of ##A##) also belong to ##B##.
OK, I guess that you are trying to stress that the x refers to an arbitrary element of A; typograhically however, there are two xs, and in a natural language translation of the notation, you can't put "any" in front of the second: "any x in B" doesn't make much sense.
 
  • #16
strauser said:
OK, I guess that you are trying to stress that the x refers to an arbitrary element of A; ...
No. I want to emphasize that ##x## can be an arbitrary element; even a tree if you like.
... typograhically however, there are two xs,...
No. There is only one which we are talking about, an arbitrary one, but a single one.
... and in a natural language translation of the notation, you can't put "any" in front of the second: "any x in B" doesn't make much sense.
I start with any, and proceed with the one I picked and say: "If this tree is additionally an element of plants ##A##, then it is also a living organism ##B##. The statement is still true for stones. I pick an arbitrary element, got a stone and the proceed with this stone: "If this stone is additionally a plant, then it is a living organism." That statement remains true, regardless whether a stone lives or does not.

"Any plant is a living organism" (##\forall x\in A\, : \,x\in B\,\Longleftrightarrow \,\forall_{ x\in A} \,x\in B##) and "all plants are living organisms" (##A\subseteq B##) are shortcuts.
 
  • #17
strauser said:
1. I think that I probably should have written "predicate" not "proposition"
2. I'm not sufficiently familiar with logical notation to know what the conventions are, I'm afraid.
3. I note that this wikipedia section on quantifiers suggests that ∀x∈A(x∈B)⇔∀x(x∈A⇒x∈B) unless I am very confused. But that also suggests that of my two initial suggestions, the second was correct, not the first.

Hmm, I think I need a "baffled by logic" emoji.
1. I agree, however. a predication may yield a proposition when its variable takes on a specific value.

2. Systems of formal logic might be notationally inconsistent with other such systems; it is important that the writer be self-consistent; however it is not necessarily important to be consistent with others, as long as the meaning is clear.

3. I didn't see the two suggestions as necessarily mutually exclusory.

fresh_42 said:
It means: ∀x∈A:x∈B. For all x∈A we have x∈B. As mentioned by others, this is not a sentence. It is a short way of saying x∈A⟹x∈B.
I would say that x∈A⟹x∈B is a sentence. I would interpret as not a sentence the expression ∀x∈A:x∈B, beause I would read it as meaning 'for all x in A such that x is in B' − I would not see the colon as denoting the ##\Longrightarrow##, unless that meaning were contextually inferable. The page at https://mathworld.wolfram.com/Colon.html includes:
The colon is the symbol ":". It is used in a number of different ways in mathematics.​
##\dots##​
2.To mean such that in constructions such as ##\{x:x>0\}## (voiced "the set of numbers ##x## such that ##x>0##").​
 
  • #18
sysprog said:
I would interpret as not a sentence the expression ∀x∈A:x∈B
This is hair splitting in my opinion. You can read it as ##\forall_{x\in A}\; P(x)## which reads that the statement ##P(x)## holds for all ##x\in A##, same as ##\forall_{p\in \mathbb{P}}\; p \text{ is irreducible} ##, with the only difference, that the statement in our case is ##P(x)=(x\in B)##.

I admit that this not formally correct, i.e. that it is no sentence in formal logic. But it occurs in the wild.
 
  • Like
Likes sysprog
  • #19
strauser said:
You mean using the false-implies-anything idea? If so, good point. If not, can you expand please?

Yes, I mean the false-implies-anything idea. That's what allows an algorithm testing whether ##A \subset B## to look only at elements in ##A##.As to the original question:

The definition of a subset can be written as:

## A \subset B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) ##

However, over which set is ##\forall## supposed to quantify? It seems to me that the two possibilities are that:

1) it quantifies over a perhaps-unmentioned universal set, of which A and B are subsets

1) is correct. That's the basic idea.

The quantification applies to all elements in some unmentioned set, which I suppose you could call "a" universal set. Technically that set is not "the" universal set because (in ZFC , the commonly used version of set theory) "the" universal set does not exist. (So says https://en.wikipedia.org/wiki/Universal_set )

A similar technicality arises in defining a complement of a set. A complement of the set ##A## is the set of all things in some implicit set that are not elements of ##A##. For example, the restriction to an implicit set prevents the complement of the empty set from being "the" universal set, because "complement of the empty set" does not define a particular set until we say what implicit set is being used in defining a complement.

Considering those technicalities, one might think that the empty set itself is not unique - e.g. that an empty set of animals might be a different concept that an empty set of real numbers. However, as I understand it, in ZFC there is only a single empty set.

I myself can't explain those technicalities. I've merely heard about them!
 
  • Like
Likes sysprog and PeroK
  • #20
fresh_42 said:
This is hair splitting in my opinion. You can read it as ##\forall_{x\in A}\; P(x)## which reads that the statement ##P(x)## holds for all ##x\in A##, same as ##\forall_{p\in \mathbb{P}}\; p \text{ is irreducible} ##, with the only difference, that the statement in our case is ##P(x)=(x\in B)##.

I admit that this not formally correct, i.e. that it is no sentence in formal logic. But it occurs in the wild.
My quibble is not with the particulars of how the expression may be interpreted as a predication; rather, it is with the possibility that the expression could be interpreted as merely a specification, for example:
$$\forall x : x \in A~[Px]$$ would be interpreted as 'for all ##x## such that ##x## is in ##A##, ##x## is subject to predicate ##P##', but it seems to me that the formulation $$\forall x \in A(x \in B)$$ is amphibolous (grammatically ambiguous) ##-## it could be taken to mean $$\forall x[x \in A \Rightarrow x \in B]$$ or it could be taken to mean $$\forall x \in A : (\textrm {i.e. such that}) ~x \in B$$which would mean $$\forall x \in A \cap B,$$ for which reason I think that if we mean merely to say that A is a subset of B (i.e. merely that ##A \subset B## without asserting either a proper subset (##A \subsetneq B##) or definitely not a proper subset (##A \subseteq B##) then the formulation $$\forall x [x \in A \Rightarrow x\in B]$$ is preferable as being of greater common clarity.
 
  • #21
I didn't read the whole thread, but this is probably worth a brief mention. In "language of first-order set theory**" everything is a set. So (without any further qualification) the ##x## in ##\forall x (x \in A \Rightarrow x \in B) ## ranges over the whole "universe" of sets, informally denoted as ##V## (##V## itself isn't a set). ##V## is the iteration of power-set operation running through the ordinals.

The way I think of ##\forall x (x \in A \Rightarrow x \in B) ## is that we have two "free-variables" ##A## and ##B##. When we consider both ##A## and ##B## as specific sets then the formula becomes either true or false (depending on the specific sets ##A## and ##B##).

Note: Initially I wrote a longer reply, but it seemed to digress a bit. So I wrote this shorter version.

** Searching for the quoted term gives a number of results giving the description. Probably the "first-order" part is not omitted sometimes (presumably, taken as being understood implicitly).
 
  • #22
SSequence said:
I didn't read the whole thread, but this is probably worth a brief mention. In "language of first-order set theory**" everything is a set. So (without any further qualification) the ##x## in ##\forall x (x \in A \Rightarrow x \in B) ## ranges over the whole "universe" of sets, informally denoted as ##V## (##V## itself isn't a set). ##V## is the iteration of power-set operation running through the ordinals.

The way I think of ##\forall x (x \in A \Rightarrow x \in B) ## is that we have two "free-variables" ##A## and ##B##. When we consider both ##A## and ##B## as specific sets then the formula becomes either true or false (depending on the specific sets ##A## and ##B##).

Note: Initially I wrote a longer reply, but it seemed to digress a bit. So I wrote this shorter version.

** Searching for the quoted term gives a number of results giving the description. Probably the "first-order" part is not omitted sometimes (presumably, taken as being understood implicitly).
You mean? $$\forall A, B (A \subseteq B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) )$$
 
  • Like
Likes sysprog
  • #23
PeroK said:
You mean? $$\forall A, B (A \subseteq B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B) )$$
No, I just meant ##\forall x (x \in A \Rightarrow x \in B) ##. What I was trying to say was that a sentence such as ##\forall x (x \in A \Rightarrow x \in B) ## can be thought of as an open-sentence ##P(A,B)## which only becomes true or false when ##A## and ##B## are some specific sets.

Because there is no symbol such as ##\subseteq## in (formal) set-theory language, an expression involving a symbol such as ##\subseteq## is not part of the formal language. However, it does makes sense. That's because any expression that would involve ##\subseteq## could be written without using such a symbol [but much harder to read and much longer].
 
  • #24
SSequence said:
Because there is no symbol such as ##\subseteq## in (formal) set-theory language, an expression involving a symbol such as ##\subseteq## is not part of the formal language. However, it does makes sense. That's because any expression that would involve ##\subseteq## could be written without using such a symbol [but much harder to read and much longer].
In ZFC specified in first-order logic, the principle of extension allows us to define the 3 commonly used subset symbols ##\subset##, ##\subseteq##, and ##\subsetneq##:$$^{def.}_\subset: A\subset B \Leftrightarrow \forall x [x \in A \Rightarrow x \in B]$$The definition for ##\subseteq## merely conjunctionally appends either the disjunctional tautology that ##A## and ##B## are either equal or not equal, or the disjunctional imputation that either they are equal, or by inference, ##B \not \subset A##:$$
\begin{gather}
^{def.}_\subseteq: A\subseteq B \Leftrightarrow [\forall x [x \in A \Rightarrow x \in B]]\nonumber \\ \nonumber \land \nonumber \\ [\forall x [x \in A\Leftrightarrow x \in B]\lor \neg[\forall x [x \in A \Leftrightarrow x \in B]] \nonumber \\\textrm{Or} \nonumber\\ ^{def.}_\subseteq: A\subseteq B \Leftrightarrow [\forall x [x \in A \Rightarrow x \in B]]\nonumber \\ \nonumber \land \nonumber \\ [\forall x [x \in A\Leftrightarrow x \in B]\lor \neg[\forall x [x \in B \Rightarrow x \in A]] \nonumber
\\ \nonumber\end{gather}$$The definition for ##\subsetneq## appends conjunctionally only the latter alternative of the conjunctionally appended disjunction specified in the ##\subseteq## definition:$$\begin{gather} ^{def.}_\subsetneq: A\subsetneq B \Leftrightarrow [\forall x [x \in A \Rightarrow x \in B]] \land \neg[\forall x [x \in A \Leftrightarrow x \in B]] \nonumber \\ \rm{Or} \nonumber\\ ^{def.}_\subsetneq: A\subsetneq B \Leftrightarrow [\forall x [x \in A \Rightarrow x \in B]] \land \neg[\forall x [x \in B \Rightarrow x \in A]] \nonumber \end{gather} $$Alternatively, we could use existence of a counterexample instead of explicit denial of the universal:$$^{def.}_\subsetneq: A\subsetneq B \Leftrightarrow [\forall x [x \in A \Rightarrow x \in B]] \land [\exists x [x \notin A \land x \in B]]$$Some writers use ##\subset## to mean only ##\subsetneq##, some use ##\subset## to mean only ##\subseteq##, and some use ##\subset## to mean either ##\subseteq## or ##\subsetneq##, depending on context ##-## some writers who use ##\subset## to mean merely ##\subset##, and ##\therefore \not \supset##, but not necessarily ##\subseteq## and not necessarily ##\subsetneq##, are apt to use ##\subseteq## or ##\subsetneq## when the distinction matters.

Although strictly logically ##\subset \equiv \subseteq##, I think that sometimes ##\subseteq## is preferable to ##\subset##, for the sake of perspicuity or clarity.
 
Last edited:
  • #25
sysprog said:
In ZFC specified in first-order logic, the principle of extension allows us to define the 3 commonly used subset symbols...
Yes, just to be clear, I didn't mean at all that we can't "define" further symbols (or perhaps other short-cuts) based on our convenience. After all, nearly all of the discourse/communication, both in general mathematics and in set theory occurs in ordinary language. The implicit understanding being that (nearly) all arguments can be converted to a certain base-line in principle. I wasn't saying much more than that.

For example, with regards to post#21, here are couple of links that come up (on a quick search):
https://www.math.ucsd.edu/~sbuss/CourseWeb/Math260_2012F2013W/AxiomList.pdf
https://people.maths.ox.ac.uk/knight/lectures/lst.pdf
 
  • #26
Stephen Tashi said:
Considering those technicalities, one might think that the empty set itself is not unique - e.g. that an empty set of animals might be a different concept that an empty set of real numbers. However, as I understand it, in ZFC there is only a single empty set.

I myself can't explain those technicalities. I've merely heard about them!
I'm going to reanimate this thread briefly re: the "unique empty set" question.

The way I think of this is as follows: Suppose ##\emptyset## and ##\emptyset'## are both empty sets. We need to show that ##\emptyset \subseteq \emptyset', \emptyset' \subseteq \emptyset##.

For the first, we have to consider ##x \in \emptyset \Rightarrow x \in \emptyset'## which can be difficult to swallow, given that there is no such ##x##. But if we take the contrapositive, we consider ##x \notin \emptyset' \Rightarrow x \notin \emptyset## which is "obviously" true, given that both sets are empty.
 
  • #27
strauser said:
For the first, we have to consider ##x \in \emptyset \Rightarrow x \in \emptyset'##

However, you apparently mean that we must show ##\forall x ( x \in \emptyset \Rightarrow x \in \emptyset')## and the quantifier ##\forall## applies to some set, which is not the nonexistent universal set. If ##\forall## must be associated with an implicit non-universal set, then aren't the set relations ##\subseteq## and ##=## also only defined relative to some implicit set that defines the scope of ##\forall##?
 
  • #28
Correct me if I’m wrong, but the quantifier ##\forall## applies to all sets, in the sense that for any model ##M## of set theory, the statement ##\forall x\,P(x)## quantifies over all elements of ##M##. Otherwise ##M## wouldn’t properly “model” the quantifier ##\forall##, would it?
 
  • Like
Likes SSequence
  • #29
suremarc said:
Correct me if I’m wrong, but the quantifier ##\forall## applies to all sets, in the sense that for any model ##M## of set theory, the statement ##\forall x\,P(x)## quantifies over all elements of ##M##. Otherwise ##M## wouldn’t properly “model” the quantifier ##\forall##, would it?
Yes, my understanding is that this should be more or less correct. If one is specifically considering the above sentence over a (set) model then the scope of ##x## would be over all the elements of ##M##.

Normally, without any further specification, it is over ##V## (cumulative hierarchy). I said something similar in post#21,#25 on previous page. Specifically the first link in post#25 mentions (at the very beginning): "Variables range over the universe of all sets."
 
Last edited:
  • Like
Likes suremarc
  • #30
Stephen Tashi said:
However, you apparently mean that we must show ##\forall x ( x \in \emptyset \Rightarrow x \in \emptyset')## and the quantifier ##\forall## applies to some set, which is not the nonexistent universal set. If ##\forall## must be associated with an implicit non-universal set, then aren't the set relations ##\subseteq## and ##=## also only defined relative to some implicit set that defines the scope of ##\forall##?
Yes, this is a good point. Hmm. It looks like a to-my-mind more acceptable contrapositive formulation of the statement will not be valid in ZF. That's a pain. I guess in ZF, however, we can rely on ex-falso-quodlibet to say ##\forall x, x \notin \emptyset'## and then ##x \in \emptyset' \Rightarrow x \in \emptyset## is of the form false ##\Rightarrow## true, so true.

I can't say I like this though. It seems to undermine the logical equivalence of a conditional statement and its contrapositive. On the other hand, does it really matter to the average mathematician that the uniqueness of the empty set is relative to chosen universal set? It's no different to the complement of a set being relative to a chosen universal set, is it?
 
  • #31
strauser said:
For the first, we have to consider ##x \in \emptyset \Rightarrow x \in \emptyset'## which can be difficult to swallow, given that there is no such ##x##.
Here's why you have to swallow this. Suppose we want to prove, for example, that there is no real ##x## such that ##x^2 = -1##.

We might assume such an ##x## exists, reach a contradiction and conclude that no such ##x## exists.

But, wait a minute! If no such ##x## exists, then we effectively chose ##x## initially from the empty set and applied some logic (which is what we don't accept as valid). The logical basis of our proof of the non-existence of such an ##x## by contradiction has been undermined somewhat.

That's why, even if ##x## does not exist, we must be able to proceed logically from the assumed properties of ##x##. And, thereby, swallow the concept of vacuous logic.
 
  • #32
In the language of set theory, ##\forall x \Phi(x)## is the primitive operation. Roughly speaking, it means for any set x, ##\Phi(x)## holds. Restricted quantification is a defined concept: ##\forall x \in A ~ \Phi(x)## is considered shorthand for ##\forall x (x \in A \Rightarrow \Phi(x))##.

So there is no implied universal set that is being quantified over.

The issue about ##x \in \emptyset \Rightarrow x \in \emptyset'## is not specific to set theory. It's just the usual interpretation of ##\Rightarrow##:
$$(\text{True} \Rightarrow \text{True}) ~ \text{is True}$$
$$(\text{False} \Rightarrow \text{True}) ~ \text{is True}$$
$$(\text{False} \Rightarrow \text{False}) ~ \text{is True}$$
$$(\text{True} \Rightarrow \text{False}) ~ \text{is False}$$
 
  • Like
Likes SSequence
  • #33
stevendaryl said:
In the language of set theory, ##\forall x \Phi(x)## is the primitive operation. Roughly speaking, it means for any set x, ##\Phi(x)## holds. Restricted quantification is a defined concept: ##\forall x \in A ~ \Phi(x)## is considered shorthand for ##\forall x (x \in A \Rightarrow \Phi(x))##.
Regarding this, there is one related point/question that I had in mind for some time (relation to translation of "ordinary mathematical statements" to "sets only").

Very briefly it goes like this:
Suppose we want to re-convert a statement of form:
##\forall x \in \mathbb{R} \, [\, P(x) ]##
to sets only. I think we would go like:
##\forall x [ x \in \mathbb{R} \rightarrow P(x) ]##

=============================================

It seems that such translations (like above) would be good when we are dealing with "collections" which are sets. However, it seems, I think, that in general math one has to deal with "collections" which are not sets [collections too big to be sets]. So consider such a collection ##G##. We might write:
##\forall x \in G \, [ \, P(x) ]##

But since the "collection" of objects ##G## is not a set, the primitive translation can't be like the above case for ##\mathbb{R}##. Here is how I "think" we might proceed. Make a formula like ##Q(x)## [one free variable] such that ##Q(a)## is true iff the set ##a## is in collection ##G##.
Then write:
##\forall x [x \in G \rightarrow P(x) ]##
##\forall x [ Q(x) \rightarrow P(x) ]##

(The ##x \in G## above is meant to be informal)

=============================================

It feels reasonable to some extent. However, is there something else here that one needs to keep in mind? Or perhaps other typical examples or issues that occur in re-translation?
 
Last edited:
  • #34
SSequence said:
Regarding this, there is one related point/question that I had in mind for some time (relation to translation of "ordinary mathematical statements" to "sets only").

Very briefly it goes like this:
Suppose we want to re-convert a statement of form:
##\forall x \in \mathbb{R} \, [\, P(x) ]##
to sets only. I think we would go like:
##\forall x [ x \in \mathbb{R} \rightarrow P(x) ]##

=============================================

It seems that such translations (like above) would be good when we are dealing with "collections" which are sets. However, it seems, I think, that in general math one has to deal with "collections" which are not sets [collections too big to be sets]. So consider such a collection ##G##. We might write:
##\forall x \in G \, [ \, P(x) ]##

But since the "collection" of objects ##G## is not a set, the primitive translation can't be like the above case for ##\mathbb{R}##. Here is how I "think" we might proceed. Make a formula like ##Q(x)## [one free variable] such that ##Q(a)## is true iff the set ##a## is in collection ##G##.
Then write:
##\forall x [x \in G \rightarrow P(x) ]##
##\forall x [ Q(x) \rightarrow P(x) ]##

(The ##x \in G## above is meant to be informal)

=============================================

It feels reasonable to some extent. However, is there something else here that one needs to keep in mind? Or perhaps other typical examples or issues that occur in re-translation?

You're absolutely right. If ##G## is a definable collection--definable via a formula in set theory--then you can use that formula to express quantification over all of ##G##. Quantification over the elements of a set is just a special case.
 
  • Like
Likes SSequence

1. What is a subset?

A subset is a set that contains elements from another set. It is a smaller set that is part of a larger set.

2. What is a universal quantifier?

A universal quantifier is a logical symbol that represents the phrase "for all" or "for every". It is used to express that a statement applies to every element in a set.

3. How is a universal quantifier used in subset definitions?

A universal quantifier is used in subset definitions to specify that a condition or property applies to every element in a given set. It is often used in conjunction with the subset symbol (∈) to define a subset of a larger set.

4. Can a subset definition use multiple universal quantifiers?

Yes, a subset definition can use multiple universal quantifiers to specify conditions that apply to multiple sets or elements. For example, a subset definition may use two universal quantifiers to express that a property applies to all elements in two different sets.

5. How is a subset different from a proper subset?

A subset is a set that contains elements from another set, while a proper subset is a subset that contains at least one element that is not in the original set. In other words, a proper subset is a subset that is smaller than the original set and does not contain all of its elements.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
998
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
853
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Replies
2
Views
325
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
503
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top