2
$\begingroup$

I'm to find a formal definition of a certain set, but I'm unsure what it means by "formal definition" (in relation to Discrete Maths)

A quick google search didn't seem to help me much. Can anyone provide me with an example of a set, and a formal definition of it?

Update: I can't really give much more detail about the question itself because it's a graded assignment. (I do study Computer Science, and the Discrete Maths course I'm doing is run by the computing department). It gives a set of vague conditions for a set A, then asks to write down a formal definition of a set B which contains all such sets.

$\endgroup$
5
  • 1
    $\begingroup$ I removed the Formal Languages tag. Tag wiki is - Formal languages are studied in computer science and linguistics. They are usually defined using various types of grammars (e.g. regular, context-free) and automata (e.g. deterministic and pushdown automata, Turing machines). There is a hierarchy of formal languages, which is based on the type of grammars and automata which can be used to generated them. $\endgroup$
    – Belgi
    Oct 13, 2014 at 20:32
  • $\begingroup$ Could you provide more context? What is the exact formulation of the question? $\endgroup$
    – Jack M
    Oct 13, 2014 at 20:33
  • 2
    $\begingroup$ A formal definition of a set $S$ often looks something like $S=\{s:\phi\}$, where $\phi$ is some property which holds only of those $s\in S$. But more detail is really needed to be useful. $\endgroup$ Oct 13, 2014 at 20:35
  • $\begingroup$ It's something in the Von Neumann hierarchy $\endgroup$
    – user40276
    Oct 13, 2014 at 20:51
  • $\begingroup$ I am going to expand Kevin's comment into an answer, but credit to Kevin, that looks to me like the right information for this user's question. $\endgroup$ Oct 13, 2014 at 21:31

6 Answers 6

2
$\begingroup$

As set is one of the things set theory talks about, so for ZFC set theory for example it is one of the sets guaranteed (or at least allowed) to exist by one or more of the axioms of ZFC. The formal definition of a specific set would consider in a proof of the existence/construction of the set in question. Most of the axioms come with the introduction of special notations for the set they guarantee to exist (provided the set is also unique). Thus for example

  • $\{a,b\}$ denotes the set guaranteed to exist by the Pairing Axiom for given sets $a,b$
  • $\mathcal P(a)$ denotes the set guaranteed to exist by the Power Set Axiom for a given set $a$
  • $\bigcup a$ denotes the set guaranteed to exist by the Union Axiom for a given set $a$
  • $\{\,x\in a\mid \phi\,\}$ denotes the set guaranteed to exist by the instance of the Axiom Schema of Comprehension for a given set $a$ and predicate $\phi$
  • $\{\,F(x)\mid x\in a\,\}$ denotes the set guaranteed to exist by the instance of the Axiom Schema of Replacement for a given set $a$ and function $F$

Combinations of these allow the formal definition of quite complex sets. As a shortcut, one often uses $\emptyset$ for $\{\,x\in a\mid x\ne x\,\}$ where $a$ is an arbitrary set (which is guaranteed to exist), or $\omega$ for a specific (namely minimal inductive) constructabel from a set that is guaranteed to exist from the Axiom of Infinity. Other constant symbols for specific sets are often introduced and can readily be used as abbreviations (for example, I won't write down a completely expanded definitoin of a set widely known as $\mathbb R$) in such formal spevcifications. In most cases, you'll write down your formal definition of a set either the Comprehension or the Replacement way.

$\endgroup$
1
$\begingroup$

daOnlyBG Gave you the basic 'definition' of set which gives a basic, yet good enough (you won't need a more formal) definition, understanding of the concept of a set.

However, Paradoxes such as "The set of all set that doesn't contain themselves" (Known as Russell's paradox) lead to the need for a more formal definition.

This is where axiomatic set theory comes into play, I suggest reading Zermelo–Fraenkel set theory to gain some more insight on this.

$\endgroup$
0
$\begingroup$

Kevin Carlson's comment is the appropriate one, considering what this assignment is. Translating "vague conditions [for a set]" into "something like $S=\{s:\phi\}$" is precisely what the assignment is asking.

Many sets are formed in this way, in naive set theory or more formal axiomatic systems -- see Hagen von Eitzen's answer, where some of the criteria he give (especially the fourth) refer to sets defined by the satisfaction of some property.

This type of notation is called "set builder notation."

For example, if I said "formally define the set of all red objects" you might say:

$$S=\{x:x\mathrm{\ is\ red}\}.$$

That would be fine, and context would tell me the universal set (from which all $x$ would be drawn) is the appropriate contextual universe (the real universe, in this case). We might have to argue whether "being red" is really a formal property, but that's an argument for philosophy or physics.

Now, if I said "formally define the set of all red real numbers" you could say:

$$S_2=\{x:x\in\mathbb{R}\mathrm{\ and\ }x\mathrm{\ is\ red}\}.$$

In order to avoid clumsy use of language in the set, you can define a logical predicate (or perhaps you'd call it a "property") $R(x)$ to denote the state of being red. This would simplify the previous:

$$S = \{x:R(x)\},$$

$$S_2 = \{x:x\in\mathbb{R}\ \&\ R(x)\}.$$

Here I'm using "&" as the formal logical operation "and." That may also be written:

$$S_2 = \{x\in\mathbb{R}:R(x)\}.$$

There, it's a little more clear that being a real number is not a condition, so much as a reminder of which universe our $x$ will come from (whereas $R(x)$ is the condition).

Here are some more examples:

Vague definition: Triangles with area 7

Formal definition: $\{\Delta PQR: A(\Delta PQR)=7\}$

Vague definition: Numbers that solve certain equations

Formal definition: $\{x\in\mathbb{R}:p(x)=0\ \& \ f(x)=0\}$

Vague definition: Numbers that are the sum of three squares

Formal definition: $\{n\in\mathbb{N}:n=a^2+b^2+c^2\}$

Note: Often we get away with being vague even in the formal definition, which might be more properly written as:

$$\{n\in\mathbb{N}:\exists a,b,c\in\mathbb{N}\mathrm{\ s.t.\ } n=a^2+b^2+c^2\}.$$

Vague definition: Numbers not divisible by 3 or 5

Formal definition: $\{n\in\mathbb{Z}:3\not|\ n\ \&\ 5\not|\ n\}$ (or many alternative expressions)

Vague definition: Non-rational numbers

Formal definition: $\{r\in\mathbb{R}:r\not\in\mathbb{Q}\}$

Vague definition: All residue classes that have multiplicative inverses mod 15.

Formal definition: $\{1, 2, 4, 7, 8, 11, 13, 14\}$

In that last case, you could write down something similar to "numbers not divisible by 3 or 5" but if you can literally list all the elements of a set, that is also a formal definition. It's more concrete, but less recognizable (given that set, would you infer the property that each one is invertible mod 15?)

Those definitions aren't "vague" so much as just "not written as a set." (If it were truly vague, you might not be able to write it formally). In some cases the universe ($\mathbb{Z},\mathbb{R}$) is inferred -- I'm assuming "Non-rational numbers" will mean reals, for example. In the case of the triangles, I'm not even stating the universal set, which is fine (where else would $\Delta PQR$ come from, if not the universe?).

Others have mentioned that not all expressions concocted this way are legitimate, due to issues with naive set theory -- you can conjure up some paradoxical predicate that will create an inconsistency. The classic example of this might be Russell's paradox, in which the predicate is $NSC(x)$, which is true when $x$ does not contain itself as a member (Not Self Containing).

It refers to sets, so $NSC(x)$ is not true for anything that is not a set. However, in a naive scheme, the set $INF$ of all infinite sets would surely have $NSC(INF)$ true, since there are (in a typical naive set theory) definitely infinitely many infinite sets.

But if $RP=\{x:NSC(x)\}$, then what is $NSC(R)$? If it is true, then $RP$ must contain itself, which means $NSC(RP)$ must be also false! (And vice-versa.)

However, I would hope that your assignment is paradox free!

$\endgroup$
0
$\begingroup$

It often helps to explicitly specify your domain of discourse, i.e. your "universe". It could be the set of real numbers, or the set of points in a plane, etc. Call it the set $U$.

It gives a set of vague conditions for a set A...

I'm guessing you mean that $A$ is subset of $U$ and every element of $A$ has some property $P$. More formally:

$$\forall y\in A :[y\in U \land P(y)]$$

where $P(y)$ is some well defined condition on $y$.

...then asks to write down a formal definition of a set B which contains all such sets.

Then we can formally define $B$:

$$ \forall x:[x\in B \iff x\subset U \land \forall y\in x :P(y)]$$

$\endgroup$
0
$\begingroup$

Let me answer the title question, even though the body asks a different question (hence the CW).

There is no formal definition of a set - at least, not in the usual approach. Instead, we write down a list of axioms about how sets ought to 'behave,' like "if two sets have the same elements, they're equal" (Axiom of Extensionality). Everything else is then defined in terms of sets, including functions, algebraic structures, Reimannian manifolds, etc.

"Set" is the only concept not given a formal definition.

$\endgroup$
-1
$\begingroup$

From the Collins Dictionary of Mathematics:

set: a collection, possibly infinite, of distinct numbers, objects, etc., that is treated as an entity in its own right, and with identity dependent only upon its members.

$\endgroup$
5
  • 3
    $\begingroup$ A logic nazi (excuse my choice of words here, a play on the more common "grammar nazi") would then ask you for your definition of "collection", "object", or "entity", and you would never hear the end of it. An alternative approach is to just accept that the word "set" designates something, without defining what. Then you let whatever axioms you use describe how it behaves, ignoring what it might in reality be. $\endgroup$
    – Arthur
    Oct 13, 2014 at 20:37
  • $\begingroup$ OK, that's fine, but a good deal of us would say that "something" can be synonymous with "object" or "entity." As for "collection," perhaps one would argue that the word implies plurality (a collection of "one thing" would be kinda lame) and would also not account for the null set. To say that a set designates "something," without defining what, isn't really constructive, though, no? $\endgroup$
    – daOnlyBG
    Oct 13, 2014 at 20:56
  • $\begingroup$ It isn't very constructive. But you have to stop demanding constructive definitions of terms at some point. Otherwise, since the number of human readable sentences is finite, demanding that every word you use has a definition gets you into trouble. You either need an infinite number of definitions, or a circular definition, since there cannot be a first definition. Many find that the word "set" is as good a place as any to begin. $\endgroup$
    – Arthur
    Oct 13, 2014 at 21:04
  • $\begingroup$ This definition seems to preclude a set being an element of another set. A set has an "identity dependent only upon its members" whereas each such member is "an entity in its own right." Now, I don't expect air-tight logic from such a dictionary, but I think this is not going to help clear up the question. $\endgroup$ Oct 13, 2014 at 21:30
  • $\begingroup$ @Arthur, OK, I guess I was being pragmatic. $\endgroup$
    – daOnlyBG
    Oct 13, 2014 at 23:37

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.