Wikipedia:Reference desk/Archives/Mathematics/2013 January 24

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 24

Chicken-and-Egg Problem

What do mathematicians usually define first, and how: functions from relations or ordered $n$-tuples? BCG999 (talk) 02:00, 24 January 2013 (UTC)

Well, since you've already asked questions here before about the article implementation of mathematics in set theory, I'll assume that you just can't find the answer you're looking for on that page. The section Operations on indexed families of sets covers n-tuples for n > 2, doesn't it? Once you have an ordered pair, you can define either one without needing any other definitions. « Aaron Rotenberg « Talk « 07:20, 24 January 2013 (UTC)

Thanks for pointing that part of the article out; I wasn't quite that far down yet because the article on tuples stated that they can be defined as functions, which led me to analyze the part concerning functions of the article on how mathematicians implement mathematics in set theory for clues to solving my problem. Unfortunately, the section to which you referred me seems to me to be quite hard to follow. Could you explain it to me? Maybe you could start by pointing me in the direction of an article that defines indexed families of sets…

BCG999 (talk) 00:06, 25 January 2013 (UTC)

There are two ways of defining general n-tuples, if you have already defined 2-tuples (ordered pairs). I'm going to assume ZFC here because it makes things easier.

• You can define them as syntactic sugar for recursive pairs, like this: $(1,x,0.5,a)=(1,(x,(0.5,a)))$ (or, alternatively, $(1,x,0.5,a)=(((1,x),0.5),a)$, which may be more convenient because it allows repeated uncurrying to work correctly).
• Alternatively, you can define relations as sets of ordered pairs, define functions as a special case of relations, and then define an n-tuple as a function whose domain is the natural number n (which is, under the standard set-theoretical definition of the natural numbers, equal to the set of natural numbers $\{0,...,n-1\}$).

The second definition has a number of nice properties. Since the set of all functions from $X$ to $Y$ is written as $Y^{X}$, you can write the set of all pairs of elements from the set $A$ as $A^{2}$, all triples as $A^{3}$, etc., which meshes naturally with the notation for Cartesian products. It also generalizes easily to infinite sequences: since the natural numbers are the ordinals less than $\omega$, the finite and infinite sequences together are the functions from ordinals less than or equal to $\omega$. It's common notation to write the set of all infinite sequences of elements from the set $A$ as either $A^{\omega }$ or $A^{\mathbb {N} }$. Slightly rarer is the notation $A^{<\omega }$ for the set of all finite sequences of elements from the set $A$ (computer scientists like the Kleene star instead).

Likewise, indexed families are just functions whose domain is the index set. « Aaron Rotenberg « Talk « 18:30, 26 January 2013 (UTC)

Hold on a 'sec, dude, because I'm trying to catch up; some of the stuff that you're telling me has me a tad lost! First of all, I am assuming that you imply that I use the Kuratowski definition of ordered pairs normally used to define ordered pairs when I do so as a first step. However, it seems to me that Kuratowski defined ordered pairs as objects $\left(a,b\right)_{\text{Kuratowski}}$ represented as sets of the form $\left\{\left\{a\right\},\left\{a,b\right\}\right\}$ just so that mathematicians could distinguish between the first and second terms of that defined object $\left(a,b\right)_{\text{Kuratowski}}$ within its set-theoretical definition $\left\{\left\{a\right\},\left\{a,b\right\}\right\}$ through the conventions that the first, or left, coordinate should appear within this set-theoretical definition $\left\{\left\{a\right\},\left\{a,b\right\}\right\}$ twice – that is, once within the first enclosed set and once within the second enclosed set – and that the second, or right, coordinate should appear within this set-theoretical definition $\left\{\left\{a\right\},\left\{a,b\right\}\right\}$ once – that is to say, once within the second enclosed set. Do mathematicians usually assume that they are to use these conventions when they work with the Kuratowski definition of ordered pairs? Don't you think that there should be a way to write these conventions down as conditions which one could apply to the definition as a way to show in his or her work that he or she is using these conventions in defining ordered pairs, or might this be implied by the names of the variables used in the definition? If that were so, then that would explain why a variants of the Kuratowski definition of ordered pairs exist. Second, I understand that one could define relations as ordered pairs but can't comprehend why or how this definition could be compressed to an ordered triple $\left(X,Y,R\right)$ as is used in the part of the article on relations in which they are defined in defining relations. I suppose that one could define relations as sets of some such form as $\left\{\left(x,y\right)\in R:\forall \left(x\in X\land y\in Y\right)\exists R\subset X\times Y\right\}$ to which this same person could then later go back and apply the syntactic sugar of tuples after he or she had defined them, but why would one do such a thing if the general concept of a relation is already just a set of ordered pairs, which the person in question has already defined? After all, isn't it impossible to define a concept as a construct derived from something that you haven't yet defined? And yet, as I transition into my third point of confusion, I still see members of Wikipedia, as well as mathematicians who post on other websites such as ProofWiki, doing exactly this! This is why I titled my question 'Chicken-and-Egg Problem' in the first place: everything I was trying to read for clues led me in circles! For example, the portion of the article on tuples which defines them as functions uses this tuple-based definition of a function in defining them! Fourth, the manner in which you mention indexed families of sets could additionally be construed to serve as a reference that these mathematical objects could be used in creating an alternative definition of multisets. Indexed families of sets, however, do not appear to have been defined rigorously enough to even serve as mathematical objects, even to my untrained eyes (I'm a high school senior trying to use the concept of a multiset as the underlying structure for a probability sample space – don't ask, it just makes sense to me.) Maybe indexed families of sets could be redefined as a different kind of multiset? What is your opinion of all of this, Aaron?

BCG999 (talk) 23:51, 26 January 2013 (UTC)

I have a bunch of responses to your post, so I'm just going to write a rambling list of bullet points that hopefully addresses some of your questions.

• Yes, normally when you are using the Kuratowski definition of the ordered pair, you're supposed to interpret the variables like that. Often, there's some implied use of projection functions or pattern matching going on. There is no circular dependency here because these are first-order logic class pseudo-"functions", not set functions.
• The standard way of introducing new symbols into first-order logic is definitional extension, in which you basically just declare that symbol to exist a priori, and take the desired properties of the symbol as axioms. The problem with this is of course that you could accidentally introduce a definition that creates a contradiction in your theory. To avoid this, it is typically assumed (although rarely explicitly stated) that you have to prove uniqueness quantification of the desired properties from the existing definitions before you're allowed add the new symbol and axioms. That is, you have to prove that the object exists and is unique. In the case of the Kuratowski ordered pair, the existence and uniqueness of the values of the projection functions can be proven a couple ways, such as by a messy explicit intersection like this one, or by application of the axiom of extensionality to the set representing the pair.
• The exact definitions of most of these objects is completely irrelevant once they're defined. You can define an ordered pair as a Kuratowski pair, or as any of the variants; but once you have it defined, it doesn't matter at all which one you picked. The definition serves the purpose of abstracting the details away so that you never have to think about them again. This is one reason to prefer ZFC over NFU as a set theory—you spend a lot less time trying to make sure the type levels line up with whatever you're doing. In terms of software engineering (my background) ZFC tends to provide better separation of concerns.
• Since many objects have more than possible definition, and these definitions may have different sets of prerequisites, there is no standard order in which to state definitions. Each author may have their own preferred order. If you see different articles leading you in circles on Wikipedia (or even different sections of the same article), it's probably because they were written by different people, or because they're stating different but equally-valid possibilities. Again, the entire point of writing definitions is to abstract the messy details—once you have picked a particular order, it no longer matters which one you've picked and can forget about it entirely.
• One common way of defining mathematical objects is to state a list of axioms and prove that any two objects satisfying the axioms (models) are isomorphic. Then you just write down any specific construction for those axioms, to show that a model exists, and you're done. For example, there are many different ways to construct the real numbers. However, all of them are complete ordered fields, and every complete ordered field has an isomorphism to every other complete ordered field. Therefore, if you 1) state that an ordered field is a model of the real numbers if it is complete, 2) prove that any two such models are isomorphic, and 3) construct a specifc model (like Dedekind cuts), you never have to mention a specific model again. The same principle applies to other objects: if you can categorically define an object's properties (uniqueness), and provide any specific construction satisfying those properties (existence), then you have a definition that can be treated as an opaque black box from that point forward.
• Because the exact definitions are previously-defined terms are irrelevant, mathematicians normally act like there is a "standard library" of terms they may invoke without definition. Each sub-field has their own collection of standard terms, and they're virtually always fuzzy and variable among different authors to some extent, because each definition has an essential element and a bunch of semi-irrelevant details, and mathematical writing is normally English text targeted at humans rather than computer-assisted proofs.
• "Redefinition"—in which a mathematician first defines term "A", uses that definition to define term "B", then goes back and redefines "A" in a more convenient way that has a dependency on "B"—is not unheard-of, particularly when dealing with fundamental objects like relations and tuples.
• There are also a small number of definitions which are unavoidably mutually-recursive, where "A" is dependent on "B", "B is dependent on "C", and "C" is dependent on "A". (The definition of the surreal numbers is a good example.) The general rule here is that, if you can prove simulataneously that all of the co-recursive definitions exist and are unique, then you can legitimately introduce them into your language by definitional extension.
• My personal list of definitions is: ordered pairs = Kuratowski construction, tuples = syntactic sugar for left-recursive ordered pairs, binary relations = sets of ordered pairs (without explicit domain and codomain), functions = restriction of binary relations, indexed families = syntactic sugar for functions, sequences = functions from natural numbers. This is one consistent ordering. Other consistent orderings exist.

Wow, I think that was my longest post on the Reference Desk yet. « Aaron Rotenberg « Talk « 02:53, 27 January 2013 (UTC)

Okay, I'm going to start replying to your last post by referencing your last bullet and then coming back and replying again later since this is lot to absorb. As such, I was wondering what other orders you could have from what you mentioned in your article. 'Ordered pairs = Kuratowski def., binary relations = sets of ordered pairs w/o explicit domain and codomain/range, functions = restricted binary relations, indexed families = syntactic sugar for functs., tuples = way to specify the members of the underlying set of an indexed family while allowing readers to assume that the indexing set is the set of all natural numbers $\mathbb {N} _{>0}$ greater than zero, finite sequences = another name for tuples' makes sense to me, but is it valid?

BCG999 (talk) 21:07, 27 January 2013 (UTC)

That looks fine to me. (Except I think you meant to specify finite sets of natural numbers, not all natural numbers greater than 1. That would give you infinitely long tuples.) I don't see any particular advantage, but it's legal. « Aaron Rotenberg « Talk « 00:18, 28 January 2013 (UTC)

Oops! You're right, I would want people reading my work to assume that any tuples in it are present so as to simplify the presentation of underlying sets whose indexing set is a subset of the natural numbers $\mathbb {N}$ starting at zero, not one, because the latter case would eliminate the possibility of an empty tuple's existence! Thanks for pointing that out.

BCG999 (talk) 17:56, 28 January 2013 (UTC)

P.S.: Just so you know and don't become alarmed, my signature will be 'RandomDSdevel' when I next post a reply to this thread in response to either another one of your big post's bullet points or this subthread.

In regard to your first bullet, I don't think that this standard interpretation of the Kuratowski definition of the ordered pair could utilize a projection in its definition because they are defined as functions, which I wouldn't have defined yet in the chain of definition which I proposed earlier. Could there be a logical equivalent of the function-based definition of projections that I could use to state in my work that I am using them to make sure that ordered pairs retain this standard definition for all of its potential readers – i.e.: my teacher?

RandomDSdevel (talk) 18:13, 28 January 2013 (UTC)

P.S.: With respect to your sixth bullet (the one on 'mathematicians having a standard library of functions,') the fact that I'm only in a high-school prob.-and-stats. class limits mine to arithmetic, high school algebra, trigonometry, precalculus, and basic operations from set theory assuming that my teacher knows about them (I assume that she would since she also teaches AP Calculus.)

P.P.S.: Somehow I can't seem to figure how the rest of your big post applies to my question. Could you give me more, mathematical examples, please? My end goal here is to be able to have a probability function that I can both use for either classical or empirical probability, depending on whether or not the multiplicity of any of the events that are members of the sample space with which any problem has presented to me is greater than one so that I may work with it no matter whether this sample space has a definition that either satisfies the theoretical requirements of a suggested experiment or accommodates the given data, respectively. I have already figured out how the resulting piecewise function should evaluate for sample spaces containing events which all have multiplicities of 1.

As I stated in the first bullet, since you can't use normal functions you have to use first-order logic function symbols. You can define a pair of projection function symbols in a couple ways; one axiom that works for any definition of the ordered pair is (for $P_{1}$ being the projection function returning the first element of the pair) $\forall p\forall x\forall y(p=(x,y)\implies P_{1}(p)=x)$. Note that you have to provide a proof that this definition actually results in exactly one value for each valid input before you can add the function symbol and axiom, as I stated before.

If you're still doing this for homework, I don't understand why you should need to define basic concepts like functions and n-tuples in a paper defining some kind of alternative probability space. You can just assume those exist unless your teacher has for some reason asked for a definition from axiomatic set theory. Since this section is getting so big, you might want to make a new section with a list of specific questions, and links back to this section and your previous question. That way, other people on the refdesk have an opportunity to see your questions and answer them. « Aaron Rotenberg « Talk « 03:42, 30 January 2013 (UTC)

Okay; I reposted my question here. However, I still kind of don't understand how you are creating this 'pseudo-function' of yours. Maybe I should go look at the article in whose direction you pointed me. If you want to explain how you understood that this kind of work is what I would need to do in answering my question, then could you please post this explanation under the new thread.

Thanks,

RandomDSdevel (talk) 18:59, 1 February 2013 (UTC)

traditional limit definition of continuity implies topological definition

Hi there,

Just recently I came across the claim that if a function satisfies the definition for a continuous function between metric spaces:

if $(X,d_{x})$ and $(Y,d_{y})$ are metric spaces, a function $f\colon (X,d_{x})\rightarrow (Y,d_{y})$ is continuous if given any ε > 0, there is a δ > 0 such that $d_{y}(f(x),f(y))<\epsilon$ whenever $d_{x}(x,y)<\delta$ (with $x,y\in X$) at every point $x\in X$

then it satisfies the definition for a continuous function between topological spaces:

Let $(X,T(X))$ and $(Y,T(Y))$ be topological spaces. Then a function $f\colon (X,T(X))\rightarrow (Y,T(Y))$ is said to be continuous if $f^{-1}(O)\in T(X)$ whenever $O\in T(Y)$

But I cannot seem to prove this. Could someone provide me with a proof (or a guide to construct one?) Help greatly appreciated!

66.91.80.10 (talk) 20:32, 24 January 2013 (UTC)

The definition of a continuous function in a metric space states that the preimage of the ball of radius $\epsilon$ centered at the point $f(x_{0})$ contains a ball of radius $\delta$ centered at $x_{0}$:

$B_{\delta }(x_{0})\subset f^{-1}(B_{\epsilon }(f(x_{0}))).$

Now take a union over all such balls contained in the open set $O$. Sławomir Biały (talk) 20:59, 24 January 2013 (UTC)

Okay, but how do you know that every point in the open set is such a point $f(x_{0})$?

66.91.80.10 (talk) 23:43, 24 January 2013 (UTC)

Not every point in O will be of this form, but every point in the image of f will. Sławomir Biały (talk) 19:19, 26 January 2013 (UTC)

Complex numbers

Hello. Suppose I have an even polynomial function P(x) with real coefficients but complex roots a_j±b_ji. Is it possible to apply a transform or a substitution to find a corresponding function Q(x) of the same degree with real coefficients and REAL roots a_j±b_j (so if 1+i were a root of P, 1+1 would be a root of Q), without finding the roots first of course (since that's the whole point). Clearly the roots of P(x) occur in conjugate pairs so P(x) can be factored into quadratic factors, but that hasn't helped me much. 72.128.82.131 (talk) 23:50, 24 January 2013 (UTC)

If you are allowed to factorize P into its quadratic and linear factors, each quadratic factor of the form $x^{2}+bx+c$, transforming each quadratic factor into $x^{2}+bx-c$ will work. However, there is no algorithm to factorize P into its quadratic and linear factors in general. 124.168.228.174 (talk) 01:34, 25 January 2013 (UTC)

$x^{2}+bx-c+b^{2}/2$, no? Ssscienccce (talk) 03:43, 25 January 2013 (UTC)

Yes, you're quite correct. If the quadratic factors are of the form $(x-b)^{2}+c$ then the transformation is $(x-b)^{2}-c$. 124.168.228.174 (talk) 08:02, 25 January 2013 (UTC)