text:
# Level switches in the fuel system for alarms - Yes, No, Why?

Discussion in 'Firewall Forward / Props / Fuel system' started by wsimpso1, Dec 14, 2018.

### Help Support HomeBuiltAirplanes Forum by donating:

1. Dec 15, 2018

### lr27

#### Well-Known Member

Joined:
Nov 3, 2007
Messages:
3,216
463
The strain gauge installation I figured out was pretty easy. However, I didn't have to worry about the display device, as the buoy already had a to d stuff, a little computer, etc. I didn't realize this had to go on the Dynon, was thinking of driving some LED's or a little volt meter. I'd put the amplifier right on top of or next to the strain gauge, so any long wires would be carrying a reasonable voltage. Could possibly put a capacitor in the output to slow down the response a few seconds to keep sloshing from setting it off all the time.

I did point out that if your time is worth much, the commercially available, pre-made unit is better. The parts for the gadget I have in mind would be very inexpensive. I don't know how much they cost from the usual sources, but you can get a full bridge strain gauge for $4 on eBay. My guess is that the whole thing might be around$20. You might not even have to remove the tank from the airplane.

I'm not saying that a strain gauge is necessarily the best way, but I'm pretty sure it would be a viable way to do this.

wsimpso1 likes this.
2. Dec 15, 2018

### rv6ejguy

#### Well-Known Member

Joined:
Jun 26, 2012
Messages:
3,546
2,572
Location:
Our EFI system outputs a digital FF pulse train emulating the old type Red Cube mechanical transducers. Accurate within 1% once calibrated correctly. This should make gauges redundant as the Dynon totalizer will show fuel remaining if you enter the correct figure when you fill the tanks.

I never really trust or look at gauges too much. I know the fuel burn and how much is fuel is on board. A little mental math and I can figure 4 hours plus an hour reserve or whatever the case may be. I usually don't want to sit there for more than 3.5 before stretching, so everything is good.

With your setup, I think you just need a red light and aural alert you can silence once the mains drop below 3-5 gallons or so. Ditto on the header tank. I recommend never running a tank really low as you may find the next tank you select won't feed and then you're options may be limited, depending on terrain and how far away airports are. If you never push it, you never have a pucker factor on fuel. Never worried about fuel in 15 years of flying my RV but it has a much simpler fuel system than you do. I wouldn't over complicate the system. Aural alerts are way better than lights which can be missed with bright sunlight on the panel or when task saturated.

wsimpso1 likes this.
3. Dec 15, 2018

### Toobuilder

#### Well-Known Member

Joined:
Jan 20, 2010
Messages:
4,286
3,028
Location:
Mojave, Ca
Time for a reset... I got too wrapped up in details.

1. Dont worry about the low level of the wing tank too much - you have header to keep the engine running and the Facet type transfer pumps dont die when run dry anyway. If you really want a reminder, a single float switch will tell you when the wing is empty. Easy solution.

2. As mentioned by Ross, if you run the SDS system, the ECU has a built in FF output. Easy solution.

3. An appropriately baffled header tank will have a pretty stable fuel level. Another simple float switch will tell you if the fuel level is really dropping below "normal". If it does, thats a positive indication of a wing feed issue long before it becomes a legitimate emergency. Easy solution.

4. Dec 15, 2018

### proppastie

#### Well-Known Member

Joined:
Feb 19, 2012
Messages:
3,503
1,005
Location:
NJ
A little more difficult if you do not fill up but if one most always fills up then it is a few button pushes to bring the number back up to 54 gal. And yes I have forgotten but I also have accurate fuel gauges which might seem overkill but I set my power by gal/hr which is real nice and easy.

5. Dec 15, 2018

### Marc Zeitlin

#### Well-Known Member

Joined:
Dec 11, 2015
Messages:
424
571
Location:
Tehachapi, CA
I built AUX tank for a COZY III that was going to do an around the world flight. I had installed capacitance level senders in the two strake tanks a couple years prior. We put capacitance senders in the AUX tank as well. Not completely analogous, since your tank should mostly be full, but I can see no reason NOT to have a level sender in the header tank. Sure, it'll be full 99% of the time, but if it isn't, you want to see the level. Rather than cobble together some system that only gives you one or two points of fuel level, you can have ALL levels indicated. Set the yellow alarm for 10% under full, which will wake you up and let you know that something's going on while the tank is still almost full, and red for 75% full, which will be the indication to get the hell on the ground.

The EMS will yell at you and there's no additional work to figure anything out for an install.

Between the level senders and the totalizer (not to mention your watch), you really have to TRY to run out of fuel.

Don't complicate things unnecessarily. You've got a fuel tank - give yourself a level reading. You want to put a low level sender somewhere - put it in your sump for low oil level .

wsimpso1 likes this.
6. Dec 15, 2018

### wsimpso1

#### Well-Known Member

Joined:
Oct 19, 2003
Messages:
5,625
2,866
Location:
Saline Michigan
7. Dec 15, 2018

### wsimpso1

#### Well-Known Member

Joined:
Oct 19, 2003
Messages:
5,625
2,866
Location:
Saline Michigan
Good to know the Facet pumps won't give up quickly if the wing tank goes empty.

8. Dec 15, 2018

#### Well-Known Member

Joined:
Dec 9, 2004
Messages:
388
151
Location:
Hamilton New Zealand
Accurate fuel gauges should always be the starting point for aircraft fuel systems. Locally there was a student pilot on a cross country that came close to a "forced landing" until talked out of it by an instructor over the radio because the fuel flow gauge was telling him (by Voice Annunciator) that the aircraft was almost out of fuel. Turns out the on the previous flight someone had set the fuel totalizer quantity.

proppastie likes this.
9. Dec 15, 2018

### Toobuilder

#### Well-Known Member

Joined:
Jan 20, 2010
Messages:
4,286
3,028
Location:
Mojave, Ca
"Accuracy" is not even required by regulation. All that is required is a positive indication the tank is empty. And that can have a very wide interpretation- as displayed here.

proppastie likes this.
10. Dec 15, 2018

### proppastie

#### Well-Known Member

Joined:
Feb 19, 2012
Messages:
3,503
1,005
Location:
NJ
correct, but accuracy is a nice feature to have, especially near the empty part of the tank.

11. Dec 15, 2018

### Toobuilder

#### Well-Known Member

Joined:
Jan 20, 2010
Messages:
4,286
3,028
Location:
Mojave, Ca
In this particular case I think it depends on the use case of the header. If its large enough to be used as a practical "last fuel tank" rather than simply as an accumulator/snubber tank, then yes, I'd like some level of Qty indication beyond "not full". In other words, is normal ops to deplete the left and right tanks, fly a bit more and still land with reserve? Or is normal ops to land with the reserve in a wing tank, depleting wing fuel only in an emergency?

wsimpso1 likes this.
12. Dec 15, 2018

### Marc Zeitlin

#### Well-Known Member

Joined:
Dec 11, 2015
Messages:
424
571
Location:
Tehachapi, CA
Missed this the first time through.

I have a Dynon, with fuel sight gages (COZY MKIV), fuel level senders, and a totalizer/FF gauge. While I agree that "IF you enter the correct figure when you add fuel", about 1% - 3% of the time I get gas I forget to put the totals in the system. Yeah, we can argue about checklists, but I'm still a human being...

So next flight, the level gauges and the totalizer don't match. Since there's no manual labor involved in the gauges, but there is in the totalizer, I always assume that I screwed up and the gauges are correct and the totalizer is wrong. If I didn't have the gauges, I wouldn't actually have a clue how much fuel I had on board (if I have baggage in front of the sight gauges in the back seat). After calibration, my level gauges are good to within about 1/2 gallon at all times.

The last reason to have level gauges along with the totalizer is to indicate leaks. If you have a leak from a tank, the totalizer won't know it. Start with 40 gallons on board, burn 20 of them, and you'll have 20 gallons left on the totalizer. But if you've leaked out 15 gallons, the totalizer won't know, but the level gauges will. If you think that you'll never have a leak, then this won't be a concern. But how can you possibly guarantee this?

So I think that _IF_ you're only going to have one type of fuel quantity indicator, it should be a level gauge, with yellow and red alarms set on the EMS. The totalizer is a great backup for fuel quantity, and the primary indicator of range and economy.

My \$0.02.

13. Dec 15, 2018

### Dan Thomas

#### Well-Known Member

Joined:
Sep 18, 2008
Messages:
4,706
1,939
Here's a digital version: https://www.electroschematics.com/5979/door-timer-with-alarm/

It could be done with resistors, capcitors and a transistor or two, but it would be bigger and I'd have to experiment to get the values. I never got to university to learn the math to figure the values. It would involve a high-value resistor feeding a capacitor-transistor base connection and another resistor connected from there to ground. The capacitor's negative side would also be grounded. The voltage on the transistor base would rise slowly as the capacitor filled until the base received enough current to fire. Might need a zener diode in there to act as a holdback. The other resistor would drain the capacitor when the switch opened. It would all be rather cumbersome and inaccurate, and the capacitor would need time to drain between switch closings.

Edit: what was I thinking? Just buy something like this: https://www.amazon.ca/Timer-Delay-Relay-Hours-Cycling/dp/B00PD65UGA

Last edited: Dec 15, 2018
14. Dec 15, 2018

### Marc Zeitlin

#### Well-Known Member

Joined:
Dec 11, 2015
Messages:
424
571
Location:
Tehachapi, CA
First, let's talk about the "new" Part 23, which we (as EAB aircraft) are not required to follow, but it's generally good practice. 14 CFR 23.2340(a) says:

(4) Provide the flightcrew with a means to determine the total useable fuel available...

While accuracy is not defined, if it's not reasonably accurate, then the flightcrew will have no idea as to the total usable fuel. So the notion that the only requirement currently is for positive indication of "empty" is not supported by the FAR. Of course, in an EAB aircraft, there's no requirement for fuel level indication at all, so there's that...

With respect to the old FAR and the old wives tale of "only need to know when it's empty", here's what the previous version of Part 23 had to say. 14 CFR 23.1337(b):

(b) Fuel quantity indicator. There must be a means to indicate to the flightcrew members the quantity of usable fuel in each tank during flight. An indicator calibrated in appropriate units and clearly marked to indicate those units must be used...

Same comments apply as for the new version. There's a good discussion of this question here, with explanations for what the problems with the regs are and why the OWT is incorrect:

https://www.av8n.com/fly/fuel-gauges.htm

particularly section 3, which discusses the regs.

Again, we aren't held to the requirements of Part 23, but there's a reason they were written...

wsimpso1 likes this.
15. Dec 15, 2018

### Toobuilder

#### Well-Known Member

Joined:
Jan 20, 2010
Messages:
4,286
3,028
Location:
Mojave, Ca
Once again, we're getting into semantics. The salient point is that it is very difficult to show an accurate fuel level in a long, skinny tank like is found on most light aircraft. The typical float type resistance senders are mechanically "topped out" for the top 1/3 to top half of the actual fuel QTY. I can fly for well over an hour in the RV and the tanks both read "FULL" the whole time. By the time my needles come off full, I've burned a significant portion of my usable fuel. Such a system is not a particularily useful "...means to determine total usable fuel available..." Of course this is not a new problem, and thats why the only realistic measure of accuracy is on or near the bottom. This is why I always put eyeballs on the actual fuel level in the filler neck of each tank before I take off, and always do the quick mental calculation for "time available" aloft. I also have forgotten to reset the totalizer, but it is rare. I have come to rely on the totalizer as my primary (minute to minute) assessment of remaining fuel. But I have never been comfortable with fuel qty guages at face value unless they are near empty.

The botom line is that there are many ways to meet Part 23 (or the intent of) without a direct reading indicator in each tank. I can think of several current use military and airliners that lack direct reading indications for large portions of fuel. The design of the fuel system and the expected use case should drive the most effective human/machine interface. If thats direct reading fuel qty in every storage vessel, or a totalizer and a peek in the tanks at the begining of each leg, so be it. Whatever contributes most effectively to the pilot's management of the flight.

16. Dec 15, 2018

### rv6ejguy

#### Well-Known Member

Joined:
Jun 26, 2012
Messages:
3,546
2,572
Location:
You mentioned it, but fuel on board should be visually inspected pre-flight and totalizer amount should be one of the things on the startup checklist in this case. I think we should always have a rough idea of how much flight time is remaining for the fuel on board, just in our heads (assuming no leaks).

Fuel leaks is a valid point for sure. I can think of two forced landings which happened due to fuel being pumped overboard through a fitting leak but in both cases, the pilots noted but didn't believe the fuel level gauges which didn't jibe with FF indications vs. time aloft.

I think with a larger header tank of 5-6 gallons, a level switch triggered at the 10% down level may still be all that's required there and at the 5 gallon remaining points on each main. This would give you a minimum of about 10 gallons remaining and hopefully 15 if you didn't run the other main below 5 to begin with. I agree a good level reading might allow you to evaluate a leak situation sooner than a low level switch. Regs might require it too. I haven't looked at the specific wording in a long time. Lots of things come into play with terrain you're over (like water, mountains). If you have a leak or can't feed from one main, it could put you in a pickle no matter what.

All useful discussion here I think.

wsimpso1 likes this.
17. Dec 15, 2018

### Dan Thomas

#### Well-Known Member

Joined:
Sep 18, 2008
Messages:
4,706
1,939

But you are held to the requirements of FAR 91.205, which has this to say:

(a) General. Except as provided in paragraphs (c)(3) and (e) of this section, no person may operate a powered civil aircraft with a standard category U.S. airworthiness certificate in any operation described in paragraphs (b) through (f) of this section unless that aircraft contains the instruments and equipment specified in those paragraphs (or FAA-approved equivalents) for that type of operation, and those instruments and items of equipment are in operable condition.

(9) Fuel gauge indicating the quantity of fuel in each tank.

From:

In Canada, we have it worded this way:

605.14 No person shall conduct a take-off in a power-driven aircraft for the purpose of day VFR flight unless it is equipped with

(j) a means for the flight crew, when seated at the flight controls to determine

(i) the fuel quantity in each main fuel tank...

So, a dipstick does not qualifyas a fuel gauge.

And yes, that OWT about the gauge only needing to indicate empty when the tank is empty is a stubborn fable spread by people who have never actually read the regulations. And if they read FAR 23 in any detail they'd see that "Empty" means "unusable fuel" level, not totally empty. Unusable fuel is that fuel that will not flow out of the tank in some normal attitude such as a Vx climb or full-flap, power-off glide. The unusable fuel, for certificated aircraft, is the difference between the tank volume as posted next to the fuel filler and the amount posted next to the selector or shut-off valve. Those numbers can be found in the POH or TCDS, and some TCDS post the unusable fuel clearly, such as this example from the 172 TCDS:

Serial Nos. 17261578, 17261445, 17265685 through 17274009
The certificated empty weight and corresponding center of gravity location must include unusable
fuel of 24 lbs. at (+46) through 172M (17267584) or 18 lbs. at (+46) 17267585 and on and full
oil of 11.3 lb. at (-14).

18. Dec 15, 2018

### Hot Wings

#### Well-Known MemberHBA Supporter

Joined:
Nov 14, 2009
Messages:
5,981
1,996
Location:
Rocky Mountains
Just a probably unrelated observation:

Back in the day before fuel stops were not as common as they are today the only car I drove that I never ran out of fuel in was my 57 VW. It had no fuel gauge. A stick under the hood served to check the quantity before a longish trip. The feature that was the real savior was the reserve valve that could be operated with a simple motion of the foot when the engine started to surge. That meant I needed to get fuel soon and I knew just how much range was left. Modern autos with a low fuel idiot light now serve the same function.

19. Dec 15, 2018

### Toobuilder

#### Well-Known Member

Joined:
Jan 20, 2010
Messages:
4,286
3,028
Location:
Mojave, Ca
I dont intend to get into another debacle concerning regs, but 91.205 applies to aircraft with "Standard Category" AWC. Bill's bird will be an EAB.

Beyond that however, the more practical realization is that even a C-172 or PA-28 does not conform either. Both have indicators in the wing tanks, and both will not read accurately for some time below full. They are therefore dangerously misleading in the sense that they will indicate full with a significant portion of fuel not present. And then there is the case of the PA-22 with the optional 8 gallon aux tank... No fuel level indicator on that one, and if you didnt take the time to clear out room in the wing tank for those 8 gallons you would pump all of it overboard when attempting to transfer. Hard to believe such a system managed to make it through Type Certification!

But before we go down the path of who can find the regs to support their position, I suggest we look at the "intent" of these regulations... And that is to provide the pilot with the means to discern his instantaneous fuel state. I think it is very shortsighted to believe that means "only" a needle that bobs up and down with the fuel level in each tank. We have many more tools available today than when my TriPacer earned its TC. And even if Bill decides to abandon part 23 or 91 entirely, there is a large body of evidence that plenty of successful aircraft do not follow the "one indicator per tank" rule.

I fully agree that fuel system design is nothing to take lightly, but I believe we can do MUCH better than blindly following outdated concepts of fuel state INDICATIONS. There are too many examples of "compliant", but bad to borderline dangerous indicating systems on past TC'd aircraft. Bill can certainly do better.

rv6ejguy and Himat like this.
20. Dec 15, 2018

Joined:
May 5, 2011
Messages:
2,752


text:
# How to change coordinates of integration?

Is there some built-in routine, some easier method to change variables of integration, without/before solving the integral? Say I have

Integrate[expression1[x, y, z], x, y, z]

how to change it to

Integrate[expression2[r, theta, phi], r, theta, phi]

-

For the specific example of Cartesian -> Spherical transformation, you could use

TransformedField["Cartesian" -> "Spherical", expression1[x, y, z], {x,y,z} -> {r, theta, phi}] *
CoordinateTransformData["Spherical" -> "Cartesian", "MappingJacobianDeterminant"][{r, theta, phi}]

to get expression2[r, theta, phi]

Alternatively, you could use CoordinateChartData["Spherical", "VolumeFactor"][{r, theta, phi}] in the integral.

This functionality is new in version 9. In version 8, you'd have to do the calculations by hand:

mapping = {x, y, z} -> {r Cos[phi] Sin[theta], r Sin[phi] Sin[theta], r Cos[theta]}
jd = Simplify@Det@D[mapping[[2]], {{r, theta, phi}}]

expression1[x, y, z] jd /. Thread[mapping]

-
This looks nice, but anything for ver. 8? –  Vladimir Mar 12 '13 at 17:48
Ok, I can get around with JacobianDeterminant for now. I was just hoping there are some bulit-in routines, and it's true for ver. 9. Thanks –  Vladimir Mar 12 '13 at 17:52
@Vladimir I don't think there are builtins for v8, see my update –  Szabolcs Mar 12 '13 at 17:55
@Szabolcs I see you were already talking about JacobianDeterminant, but I don't see it spelled out anywhere. So I added an answer containing that approach and a variation thereof. –  Jens Mar 12 '13 at 18:06

For completeness, in version 8 (and version 9 too) you can load the VectorAnalysis package and do one of the following:

Needs["VectorAnalysis"]

JacobianDeterminant[Spherical[r, θ, ϕ]]
(* ==> r^2 Sin[θ] *)

Times @@ ScaleFactors[Spherical[r, θ, ϕ]]
(* ==> r^2 Sin[θ] *)

So instead of invoking JacobianDeterminant, you can get the scale factors individually. The coordinates ($r$, $\theta$, $\phi$) in each case can be named as I did above - if you leave that out, it defaults to built-in capitalized standard names.

Putting this into an integral

To show that this leads to a syntax which is significantly more concise than the new version 9 syntax, see this specific integral. I define a function of Cartesian variables, then do the variable transformation in the integral, as was asked for in the question:

f[x_, y_, z_] := x + 2 y + z

Integrate[
f @@ CoordinatesToCartesian[#, Spherical @@ #] JacobianDeterminant[
Spherical @@ #] &@{r, θ, ϕ},
r, θ, ϕ]

(*
==>
-(1/8) r^4 (ϕ Cos[θ]^2 + θ (2 Cos[ϕ] -
Sin[ϕ]) +
Cos[θ] Sin[θ] (-2 Cos[ϕ] + Sin[ϕ]))
*)
`

I honestly think this is much prettier than what you now have to write in version 9. But I also like the completely manual approach in Szabolcs' answer.

-
However, methods from "VectorAnalysis" are limited to 3D. This is why for ver. 8. I would even do explicit calculation, like Szabolcs. –  Vladimir Mar 12 '13 at 18:24
Sure, but your example is also 3D. And the price you pay in version 9 is a much more lengthy syntax. I'll show the much more concise integration syntax for my approach in an edited answer. –  Jens Mar 12 '13 at 18:31
I haven't used this package before. You're right that it is simpler than what v9 offers. Maybe new Mma functions are getting a bit more wordy than they should be ... –  Szabolcs Mar 12 '13 at 18:48
@Jens Wow, these pure functions are powerful :) Yes, I see what you mean! –  Vladimir Mar 12 '13 at 18:55

format: plain


text:
Provided by: docbook-to-man_2.0.0-20_i386

transpec(5)                                                        transpec(5)

Name

       transpec - translation specification for instant

Synopsis

       file.ts

Description

       The  transpec  file is used by the instant program to translate an SGML
document instance to a format suitable for  a  formatting  application.
The convention is to name the file with the suffix .ts.

A  transpec  file  is  composed  of  a number of individual translation
specs.  Each translation spec (transpec) is made  up  of  a  number  of
fields, one per line.  Translation specs are separated by a line with a
leading dash.  Text after the dash is ignored.  Fields are composed  of
two  parts,  a  name and a value, separated by a colon.  The colon must
immediately follow the name, and any amount of whitespace  (blanks  and
tabs) may be present between the colon and value.  Values should not be
quoted, and you should be careful of trailing spaces.  (Trailing  space
will be considered part of the value.)  Quotes, if they appear, will be
considered part of the value of the  fields.   Lines  that  begin  with
whitespace  (blanks  and tabs) are a continuation of the previous line;
the leading space is ignored.  These characteristics are  very  similar
to those of e-mail headers.  Lines beginning with a # (number sign) are
comments and blank lines are ignored.

FieldDescriptions

       Some  fields  are  for  identifying  criteria  that  determines  if   a
particular  spec  matches  an  element in the instance.  Others specify
what action is to take place when a match happens, such as sending text
to the output stream.

Criteria fields
Criteria   fields   restrict   the  conditions  under  which  a  single
translation spec will apply.  If each field specified in  a  particular
transpec  matches  an  element  under  consideration  in  the  document
instance, then that translation spec is said to match. The  appropriate
actions,  as  specified  in  that  spec,  are then taken.  The program,
instant, searches the list of transpecs in the order given in the file.
Therefore, the more restrictive specs (those with more criteria) should
appear before less restrictive ones.

For quick reference, this is a brief summary of the  possible  criteria
fields for translation. A complete discussion of each follows.

Field Label   Field Value        Description
GI            gi ...             name of this GI
AttValue      attname reg-expr   current element has attribute with value
Content       reg-expr           is reg-expr in char content>
Context       context            element context, up the tree
NthChild      number             current element is Nth child of its parent
PAttSet       attname (val)      parent has this attribute set (optional to value val)
Relation      relationship gi    gi has relationship to current element
VarREValue    var REvalue        variable is set to regular expression value
VarValue      var value          variable is set to value

GI: gi [...]
gi  is  the  name of the generic identifier, or element name, to
consider.  More than one GI may appear in this field.

AttValue: attname regular-expression
This is an  attribute  name-value  pair,  where  attname  is  an
attribute  if  the  GI.   The  regular-expression is of the form
accepted by the unix program egrep.  This pair  is  compared  to
the  corresponding  attribute  name-value  pairs of the GI under
consideration.  To simply test if an attribute us set, use .  (a
dot)  for  regular-expression.   There  may  be more than one of
these lines for each transpec.

Content: regular-expression
This specifies that the  character  content  of  GI  contains  a
string matching the regular-expression.

Context: context
This  specifies  the  context in which to apply this translation
spec.  It is either a list of generic identifiers or  a  regular
expression  describing a list of generic identifiers, looking up
the hierarchy.  The first is the parent of the GI.

NthChild: number
This specifies that the GI is the numberth child element of  its
parent.   Children  are  numbered  starting  with  1.   Negative
numbers may be used to indicate order counting  backwards.   For
example, -1 denotes the last child.

PAttSet: attname
This  specifies that the parent has this attribute, attname, set
to any value (not IMPLIED).  A value to match may optionally  be
specified after attname.

Relation: relationship gi
This  specifies that the current element has the relationship to
the  named  gi.   The  acceptable  relationships  are:  ancestor
(anywhere  up  the  tree),  child  (immediate child), descendant
(anywhere down the tree), parent (immediate  ancestor),  sibling
(share  same  parent  element),  sibling+  (any  later sibling),
sibling+1 (the immediately  following  sibling),  sibling-  (any
earlier sibling), sibling-1 (the immediately following sibling).

VarREValue: varname REvalue
This specifies that the global variable varname  has  the  value
REvalue, where REvalue is a regular expression (see the VarValue
statement).

VarValue: varname value
This  specifies  that  the  global  variable  varname  has   the
(literal) value value (see the VarREValue statement).

There are two special GIs.  If specified, _Start and _End are processed
as if they were GIs in the  instance  at  the  start  and  end  of  the
translation,  respectively.   Their  criteria  are never checked.  Only
their actions are performed.

Action fields
For quick reference, this is a brief summary of the action  fields  for
translation. They are only performed if all the criteria are satisfied.
A complete discussion of each follows.

Field Label   Field Value   Description
Action        spec-id       use transpec whose spec ID is ‘spec-id’
EndText       text          text for end of element
Increment     name          increment variable ‘name’
Ignore        key           flag for ignoring element’s children and/or data
Message       text          text to send to stderr
Quit          text          print text and quit program
Replace       text          replace this subtree with text
Set           name value    set variable name to value
SpecID        spec-id       unique Spec ID (int) of this spec
StartText     text          text for start of element

Action: spec-id
Use the actions of  the  spec  identified  by  the  SpecID  with
matching identifier spec-id.

EndText: text
This  specifies text to be output when the end tag is processed.

Ignore: key
This specifies that the data or children for this element are to
be  ignored.   Set  key  to  all to ignore the element (data and
child elements), to data to ignore the immediate character  data
content  (child  elements  are  still  descended  into),  and to
children to process the immediate character data content but not
descended  into child elements.  Other actions specified in this
transpec are still performed, however.

Increment: name
This is used to increment a variable whose value  is  a  number.
If  the  variable is not a number, no action will be taken.  The
variable must have been previously defined.  This action is done
immediately before EndText.  There may be more than one of these
lines for each transpec.

Message: text
This specifies a string to be printed to the standard error when
the matching element is processed.  It is intended for informing
the user of the progress of the translation.  It  is  also  used
for  validation  of instances (see the -v flag of instant(1)); a
spec would be written to  recognize  a  construct  that  is  not
allowed.   This  action  is  done  immediately  after StartText.
Messages are also useful for debugging spec files; one  is  able
to  easily  tell  when  a  matching  spec  is processed, without
looking at the actual output of the translation.  Note that  the
spec  writer  is  responsible  for  putting newlines (\n) in the
message text.

Replace: text
This specifies text to replace the current subtree  with.   This
is equivalent to StartText and Ignore.

Quit: text
This  specifies  text  to be printed to the standard error.  The
program then terminates with exit status 1.   This  is  intended
for  bailing  out  when  an  undesirable instance is encountered
(such as when it is known that the  formatting  application  can
never handle a class of components, like tables).

Set: name value
This  is  used to set a variable whose name is name and value is
value.  Names that would  be  valid  for  GIs  in  the  document
instance are valid for variable names.  value is the rest of the
line and may be any string.   This action  is  done  immediately
before  EndText.   There may be more than one of these lines for
each transpec.  See the discussion on variables below.

SpecID: spec-id
This names the spec with the number  spec-id.  Other  specs  may
refer  to  this  one  by  this  number  by an Action field or an
_action special variable.  This is used for cases where  several
specs to perform the exact same action.

StartText: text
This  specifies  text  to  be  output  when  the  start  tag  is
processed.

Other Fields
These  fields  may  appear  anywhere.   The  action  occurs  when   the
translation  spec  file  is  read,  before any elements are translated.
Theses are independent of any element processing.

Var: name value
This is used to define a variable whose name is name  and  value
is  value.   It  is similar to Set, but it may occur anywhere in
the file and takes effect when the spec file is read.

Text Strings
The text referred to in the StartText, EndText,  Replace,  and  Message
actions is more than simple character strings.  Special sequences allow
more complex output.

One type of special sequence is for C-style  string  processing.   Most
special characters are escaped with a \ (backslash). Like in C or shell
programs, to print a \ (backslash), you must  escape  it  with  another
backslash. These special character strings are:

\n (backslash-n)
This  specifies that a newline character is to be printed to the
output stream.

\r (backslash-r)
This specifies that a carriage return character is to be printed
to the output stream.

\t (backslash-t)
This  specifies  that  a  tab  character is to be printed to the
output stream.

\s (backslash-s)
This specifies that a space is  to  be  printed  to  the  output
stream.  This is useful for the end of a transpec line, where it
can be difficult to tell if a blank is present at the end.

\007 (backslash-007)
This specifies that the character whose octal value is 007 is to
be  printed  to  the  output  stream.   This works for any octal
character value.

^ (caret)
This specifies the that position in the string will  be  at  the
start of a line in the output stream.

If  the  first  token  of  the text string is #include, then the second
token is taken to be a file name and that file  is  included.   If  the
file  is  not  found,  the  library  directory,  as mentioned above, is
searched.  If the text string starts with a ! (exclamation point),  the
rest  of  the  line  is  taken  to  be a command and the output of that
command is inserted.

An element’s attributes may also be used in the text of output  fields.
To use an attribute value, precede its name with a ${ (dollar sign-left curly bracket) and follow it with a } (right curly bracket). (This style is followed by the Bourne shell.) For example,${TYPE}.  If the
attribute is not set (not IMPLIED), nothing  will  be  printed  to  the
output  stream.  To specify a value to use if the attribute is not set,
place the value after the attribute name, separated  by  a  space.   To
return  the  attribute  value  in  lower-case,  add a colon followed by
lower-case l (${TYPE:l}.  Variables  Variables in instant are similar to those in many other string-oriented programming languages, such as sh and awk. They are set by: Var: name value and Set: name value. Values may be set and reset to any string. In a Var line, if the value begins with a !, then the rest of the line is executed as a command, and its output is taken as the value. A reference to the value of a variable follows the same syntax as a reference to the value of an attribute:${name}.  If that variable has
not been defined, a null value will be returned.  A default  value  can
be  returned  instead  of  null  for an undefined variable by using the
form:  ${name default}. Variables may be used as attributes are, that is in any of the text strings mentioned above. In fact, if an attribute name is referred to and it is not set for a given element, instant looks for a variable with the same name. This way global defaults can be set. If you want to be sure that you are accessing a local variable value, not an attribute value, you can use lower or mixed case names. Attribute names, as passed by nsgmls, are in upper case. Any number of Var actions may appear in the spec file. These set the values of the variables before any translation takes place. The Set actions within transpecs are performed when that spec is processed when an element matches the given criteria. Preset Variables Several variables are preset by instant upon start of the program. Their values may be overridden in transpec files or on the command line. date This is the date and time that the program started. The format is: Tue 10 Aug 1993, 16:52. host This is the name of the host where the program is run. It is what is returned by the gethostname library call. transpec This is the translation spec filename. user This is the login name of the user running the program. Special Variables There is a collection of special variables called special variables. These are identified by starting the names with a _ (underscore). This is a summary of the special variables. A complete discussion of each special variable follows. spec-id refers to a number specified in a SpecID field. When used in a special variable, it means to perform the action in that translation spec. Note that when a spec-id is given in a special variable, the default is to perform the translation spec named by the spec-id ignoring of any criteria statements found there. For most special variables that use a spec-id, postpending a "t" to the spec-id (with no spaces between them, eg, "${_followrel  child  TITLE  15t}"),  will  cause   the   criteria
statements  in  the  named  translation  spec  to evaluate successfully
before that translation spec will be processed.

Variable Usage                       Description
_action spec-id                      do spec with id spec-id
_allatts                             print all attribute/value pairs
_attval att [value] spec-id          use spec-id if attribute matches
_chasetogi gi spec-id                follow IDREFs until gi found
_eachatt att spec-id [spec-id]       do spec-id for each word of attribute value
_eachcon spec-id [spec-id]           do spec-id for each word of content
_env env-variable                    return value of env variable
_filename                            filename of notation
_find rel gi spec-id                 find gi based on relationship
_followrel rel gi spec-id            do spec-id on rel if it matches
_gi [M|L|U]                          return GI name; M, L, U case
_id id [spec-id]                     find element with ID and use spec-id
_include filename                    insert file here
_infile [line]                       instance filename [and line number]

_insertnode S|E spec-id              do spec-id when element is traversed
_isset var [value] spec-id           do spec-id if variable matches
_location                            print location of current element
_namelist spec-id [spec-id]          content is namelist, do spec-id for each
_nchild [gi]                         number of child elements [named attname]
_osftable format [flag]              print table format specification
_path                                print path to current element
_pattr attname                       value of parent’s attribute
_pfind args ...                      same as _find, but start at parent
_relation rel gi spec-id [spec-id]   do spec-id if relation matches
_set var value                       set variable to value
_!command                            command to run

_action spec-id
Use the actions of  the  spec  identified  by  the  SpecID  with
matching  identifier  spec-id.   This  behaves  similarly to the
Action action, but is in addition  to  the  present  translation
spec.

_allatts
Print  all  attribute name-value pairs of the current element to
the output stream.  The name and value  are  separated  by  a  =
(equals  sign), and the value is surrounded by quotes.  This can
be useful for creating a normalized version of the instance.

_attval attname [value] spec-id
If  the  current  element  has  an  attribute   named   attname,
optionally  whose  value  matches  value, use the actions of the
transpec identified by spec-id.

_chasetogi gi spec-id
Follow IDREF attributes until if finds an element whose GI is gi
or  which  has  a child element with that GI.  It will apply the
transpec spec-id to that element.  By default,  instant  assumes
IDREF or IDREFS.  (This corresponds with the OSF DTDs.)  You can
change  this  by  setting  the  variable  link_atts  to a space-
separated list of attribute names.

_eachatt att spec-id [spec-id2]
The transpec named by spec-id is  invoked  once  per  each  word
found  in  the  value  of  the attribute att.  Inside the target
transpec, the current word being processed is available  in  the
variable named each_A (${each_A}). If spec-id2 is specified, it will use spec-id for the first word in the attribute and spec- id2 for the others. _eachcon spec-id [spec-id2] The transpec named by spec-id is invoked once per each word found in the content of the current element. Inside the target transpec, the current word being processed is available in the variable named each_C (${each_C}).  If spec-id2 is specified, it
will  use spec-id for the first word in the content and spec-id2
for the others.

_env env-variable
Print the value of the environment variable env-variable to  the
output stream.

_filename
Print the filename of the notation associated with this element,
if any.  This is  used  to  get  the  filename  of  an  external
notation  entity  reference.  For example, to print the filename
in  the  latex  macro  from  the   epsf   macro   package,   use
\\epsfboxi{${_filename}}. _find [top] relationship args ... spec-id Descend the document hierarchy finding elements that match one of several criteria. When one is found, the action specified by spec-id is performed. If top is specified, the search starts at the top of the document hierarchy, rather than at the current element. The possible values for relationship are gi, gi- parent, parent, and attr, and take different arguments. Explanations may be best done by example: _find gi CHAPTER 123 means to find elements whose GI is CHAPTER, and perform action 123; _find gi-parent TITLE CHAPTER 124 means to find elements whose GI is TITLE and whose parent is CHAPTER, and perform action 124; _find parent BODY 125 means to find elements whose parent’s GI is BODY, and perform action 125; _find attr TYPE UGLY 125 means to find elements whose attribute named TYPE is set to UGLY, and perform action 126. _followlink [attname] spec-id When processing an element, instant will follow the IDREF attributes until an element with no IDREF attributes is found. It will then apply the transpec specified by spec-id to that element. If specified, it will follow the link pointed to by attname. By default, instant assumes the attributes named LINKEND and LINKENDS are if type IDREF or IDREFS. You can change this by setting the variable link_atts to a space- separated list of attribute names. _followrel relationship gi spec-id If the gi has the specified relationship to the current element, perform the action specified by spec-id on the related element. See the discussion of the criteria field Relation for acceptable relationship names. _gi [M|L|U] Print the name of the current GI to the output stream. If specified, M, L, or U will ensure the GI name is printed in mixed, lower, or upper case, respectively. _id id [spec-id] Find the element with id and use spec-id, if set. If not set, use the spec for that element’s context. _include filename Insert the file filename into the output stream. _infile [line] Print the name of the sgml instance file to the output stream. If line is specified, also print the line number. This depends on nsgmls being called with the -l option. _insertnode S|E spec-id Do spec-id when the current element is traversed at a later pass. This can be considered inserting a node, without content, into the hierarchy. This is only useful if done to elements before they are processed. Typically _chasetogi or _followlink is specified early in an instance’s processing, so that when the elements found by one of these actions are processed in their turn, the added actions are performed. _insertnode would be specified as the action of a spec-id pointed to in a _chasetogi or _followlink usage. _location The location of the current element is printed to the output stream in several ways: the path to the element (see _path), a position hint, which is the nearest title, the line number, if the ESIS (output from nsgmls) contains line numbers, and the ID of the element, if it has one. This is especially useful when using the Message action to validate an instance. _namelist spec-id [spec-id2] This assumes that the content of the current element is a namelist (a list of element IDs), and applies the action based on spec-id for each element pointed to. If spec-id2 is specified, it will use spec-id for the first ID in the namelist and spec-id2 for the others. _nchild [gi] Print the number of child elements of the element to the output stream. If gi is specified, print the number of child element with that name. _osftable tex|tbl|check [flag] Print table markup into the output stream. The format depends on whether tex or tbl is specified. The flag may be one of cellstart, cellend, rowstart, rowend, top, or bottom. The value determines what markup or text will be generated. If cellstart is specified, the correct markup for the beginning of a cell is output. If top, bottom, or rowend are specified, the correct markup for the end of the appropriate position is printed to the output stream. If check is specified, the attributes and child elements are checked for errors and consistency. _path Print the path to current GI to the output stream. A path is each element, going down the tree from the topmost element. A number in parentheses after each element name shows which child element the next one is in the order of children for that element. Ordering starts at 0. For example: OSF-BOOK(3) BODY(0) CHAPTER(4) SECTION. This says the path is <OSF-BOOK>’s third child, <BODY>’s zeroth, and <CHAPTER>’s fourth, which is named <SECTION>. _pattr name Print the value of parent’s attribute whose name is name to the output stream. _pfind rel gi spec-id This is exactly the same as _find except that the search starts at the current element’s parent. _relation relationship gi spec-id [spec-id2] If the gi has the specified relationship to the current element, perform the action specified by spec-id on the current element. If the relationship test fails and spec-id2 is specified, perform that action. See the discussion of the criteria field Relation for acceptable relationship names. _set varname value Set the value of the variable varname to value. _isset varname [value] spec-id If the value of the variable varname is set to value, then perform action referred to by spec-id. If value is not specified, action will be performed if varname is set to any value. _! command Run the command command, directing its standard output into the output stream. Immediate Variables Immediate variables are like special variables, except that they are expanded when the transpec is originally processed (special variables are processed later, near when the final output is being generated). The general syntax of immediate variables is${+immediate_variable ...}.

There is currently only one immediate variable defined:

+content
This  special  variable  is  replaced by the data content of the
current element.

Examples

       The following will output the given string for elements  whose  generic
identifier  is  P  (for  paragraph).   At  the start of processing this
element, the program ensures that the output starts on a new line,  the
troff macro <.P> is output, then a newline.  At the end of this element
processing, the program ensures that the output starts on a new line.
GI:             P
StartText:      ^.P^
EndText:        ^
-

The following will output the given string for elements  whose  generic
identifier  is CMD-ARGUMENT and which have an attribute PRESENCE set to
the value OPTIONAL.
GI:             CMD-ARGUMENT
AttValue:       PRESENCE OPTIONAL
StartText:      $\$EndText: \$ - The following prints the section number, title, and page number of the target of a cross reference. Assume the cross reference points to a section element, which contains a title element. The criteria for this spec to match is that the attribute OSFROLE is set to the value getfull. The action is to replace the content of the <XREF> element with the given string. When processing the string, instant will follow the IDREF attributes of <XREF> until an element with no IDREF attributes is found. It will then apply the transpec numbered 87 to that element, which will print the name of the GI in mixed case into the output stream. It will then print the LaTeX reference instruction with the value of the LINKEND attribute as an argument. (This will become the section number after processing by LaTeX.) It will then follow IDREFs until if finds an element whose GI is TITLE or which has a child element with that GI. It will apply the transpec numbered 1 to that element, which copies the title into the output stream where the cross reference occurs. Finally, it will print the word page followed by the LaTeX instruction to obtain the page number of a reference. GI: XREF AttValue: OSFROLE getfull Replace:${_followlink 87} \\ref{${LINKEND}},\s {\\bf${_chasetogi TITLE 1}}, page \\pageref{${LINKEND}} - # Print GI name, in mixed case GI: _pr_gi_name SpecID: 87 Ignore: 1 EndText:${_gi M}
-
GI:             _pass-text
SpecID:         1
-

RelatedInformation

       instant(1), nsgmls(1), egrep(1).

file format                      transpec(5)


text:
# Consequences of the Halting Problem: Gödel’s First Incompleteness Theorem

In my first post on this blog, I defined and proved my favorite fact: The halting problem is undecidable. You should probably read that post if you don’t know what that means, but in brief, it means that it is impossible to write a computer program that will always correctly tell you whether any given computer program will run forever or eventually stop.

I promised to talk about some of the far-reaching consequences of this fact in future posts, and here I am keeping my promise, if a little late. (Don’t get used to me keeping my promises on this blog, though…) I’ll start with arguably the biggest consequence of the halting problem’s undecidability: Gödel’s First Incompleteness Theorem.

As is my m.o., I’ll try to keep the discussion accessible to laypeople; I’ll provide lots of context; and I’ll just generally be extremely long-winded.

This post will be even more long-winded than usual because I feel the need to provide way too much context. To sort of acknowledge that this post is absurdly long, I’ve put a little (*) in the heading of sections that are less tangential. I’m incredibly biased, of course, but I suggest attempting to make it through the whole thing, and if you get tired somewhere around Euclid or Cantor, skip ahead to the next asterisk.

[toc]

## The Halting Problem’s Strong Connection with Mathematics (*)

While I think that the fact that the halting problem is undecidable is pretty surprising, before I presented the proof, I gave a rough argument for why one might expect the halting problem to be undecidable. The basic idea is that any program that solved the halting problem would also solve lots of open questions in mathematics (though, of course, it might take the program more than the age of the universe to do it). For example, I showed that the Collatz conjecture, a problem that’s stumped mathematicians for 75 years or so (Paul Erd?s famously said of it, “Mathematics is not yet ripe for such problems”), could be easily resolved by a program that solved the halting problem.

There’s a lot that’s special about the Collatz conjecture, but the argument that I used was quite general and applies to tons of open problems in mathematics. Indeed, given any conjecture of the form “Every integer has property P,” if we can write a computer program that tells us whether or not a given integer has property P, then we can write a computer program that runs forever if the conjecture is true and halts if it isn’t. (Simply write a program that checks all integers for property P and stops if it finds one that doesn’t have it.)

So, a program that solved the halting problem would be a godly tool for mathematicians (ignoring the fact that it might not be practical due to time constraints). This method (or a slight modification) would solve, for example, Goldbach’s conjecture, the twin primes conjecture (and numerous other conjectures about the number of various types of primes), the question of the existence of odd perfect numbers, the inverse Galois problem, etc., all of which have been open problems for over a century.

In fact, this relationship actually goes the other way as well: To put it informally, if mathematicians had some godly tool that solved general problems in mathematics (or any respectably large subset of problems in mathematics), then they would be able to write a computer program that solved the halting problem. Since this can’t be done, it follows that mathematicians can’t have their godly tool. In fact, they can’t have anything remotely close to that. (I think mathematicians are mostly happy about that, so don’t feel bad for them.)

The formal version of this fact is called Gödel’s First Incompleteness Theorem. It’s an incredibly important fact, first proved by Kurt Gödel in 1930. Gödel’s proof is pretty involved and wouldn’t be suitable for this blog, but a proof using basic computer science is essentially trivial.

Regardless, I’m going to put my own spin on it, and I’ll characteristically go on a tangent or four on the way. Here’s tangent number one:

## Euclid’s Axioms

Around 300 BC or so, the Greek mathematician Euclid outlined a famous set of axioms in the field of geometry. In other words, he came up with a very simple set of statements that he would assume to be true in order to prove more interesting things. The goal of any decent set of axioms is to be as boring as possible–Every axiom should be obviously and intuitively true, and there shouldn’t be very many of them–and Euclid’s axioms are the prototypical example. You might recognize them from high school geometry, but more likely your teacher cheated and let you use fancier axioms. Here they are (in my own clumsy wording):

1. There is exactly one line connecting any two distinct points.
2. Any line segment can be extended to arbitrary length.
3. For every two distinct points, there is exactly one circle centered at the first and touching the second.
4. All right angles are equal.
5. Given a line L and a point P, there is exactly one line that touches P and is parallel to  L. (Euclid used a different, equivalent axiom.)

These are all incredibly obvious facts. Some of them might seem so obvious that they’re not worth mentioning. Of course there’s only one line between a pair of distinct points, for example. And, there are only five of them. However, you can prove a lot of stuff from these axioms, e.g. the Pythagorean Theorem.

However, generations of mathematicians, including Euclid, were not happy with the fifth axiom, known as the parallel postulate. In their eyes, the fifth axiom seemed more like something that needed to be proven than an axiom; it certainly sounds like a less trivial statement than the first four. But, the parallel postulate was a key step in many geometric proofs. So, in order to get rid of this ugly axiom without losing a ton of geometry, they spent a couple thousand years trying to prove that the parallel postulate logically followed directly from the other four axioms.

It wasn’t until the mid-19th century that mathematicians discovered that there are “geometries” in which the parallel postulate is false. In order to see this, you need to relax the definitions of “point” and “line” a bit, so the language gets a little bit messy. I’ll try my best to be clear.

Consider a sphere, and call a pair of classical points “an elliptical point” if they are exactly opposite each other on the sphere. Note that a single elliptical point is made up of two classical points. If a circle on a the sphere is made up of elliptical points, call it “an elliptical line.” Elliptical lines are also called great circles because they are the largest circles that you can draw on a sphere–The Earth’s equator is a nice example. You can think of them as any circle that divides the sphere into two equal halves.

A quick check shows that elliptical points and elliptical lines satisfy the first four axioms. However, they don’t satisfy the second because all elliptical lines cross. (If you’re following, you should be able to picture this easily.) So, obviously the fifth axiom can’t follow from the first four because we have a counter-example! (Our counterexample is called an elliptical non-Euclidean geometry.)

This example is illustrative. While mathematicians often think of axioms as assumptions, they’re perhaps better thought of as pieces of a definition. Neither Euclid nor I phrased them like this, but axioms one through four essentially define some properties of things that mathematicians have agreed to call points, lines, and angles. However, those definitions are more general than the English definitions of those words; in particular, elliptical points and elliptical lines are perfectly good points and lines under the first four axioms. The fifth axiom serves to narrow the definitions so that they represent something much closer to the English notions of points, lines, and angles.

## Cantor, Dedekind, and the Axiomatization of Mathematics

The incredible success of Euclid’s axioms leads to a natural question: Can we come up with a nice set of axioms for more general concepts in mathematics?

In the late nineteenth century, mathematicians started to realize that this question was fundamental to their field. Arguably the first big leap in logic was the attempt to characterize the notion of a set by Georg Cantor. Cantor’s set theory essentially defined sets intuitively–A set is a collection of things that are defined by some axioms. For example, the set of natural numbers can be defined as follows:

1. Zero is a natural number
2. Every natural number has exactly one “successor.” (One is zero’s successor. 84 is 83’s successor.)
3. Any successor of a natural number is a natural number.
4. Ain’t nothing else a natural number. (Elephants, for example, don’t count. Mathematicians often assume an axiom like this implicitly.)
5. Zero is not the successor of any natural number. (Note that -1 is not a natural number.)
6. Distinct natural numbers have distinct successors. (One’s successor is different from two’s successor.)
Notice that these modern axioms sound a lot more like definitions and a lot less like assumptions.

Mathematicians began to rely heavily on this concept of a set defined by axioms by the turn of the century, and it proved to be very useful. For example, distilling out the concept of a set allowed mathematicians to more easily talk about sets that contained other sets. In particular, Dedekind and Cantor together used this new paradigm to formalize the concept of the real numbers; they each defined the real numbers in a different way as a set of sets. These were the first truly rigorous and modern definitions of the reals, and they used these definitions to discover many of the real numbers’ most important properties. In short, they discovered extremely important facts about the mathematical world and finally put a fundamental concept in mathematics on stable, modern footing.

Well, not quite… It turns out that Cantor’s intuitive set theory simply doesn’t work–It allows you to define paradoxical objects, and is therefore inconsistent.

The classic example is Russell’s paradox: Bertrand Russell pointed out that if a set can contain other sets, then surely it can contain itself. Russell then considered the set of all sets that do not contain themselves–Call it S. Russell then asked “Does S contain itself?” If S contains itself then it should not be included in S by definition, but then it doesn’t contain itself, which means that it should be included in S by definition, which means it contains itself…

This particular paradox might seem a bit cheap, but it’s merely the simplest example in a long list of paradoxes discovered in what is now called naive set theory. Because such objects exist in naive set theory, the theory allows you to “prove” two contradictory facts (e.g., that S contains itself and doesn’t contain itself). Obviously, nothing “proven” in such a theory can be trusted because someone might “prove” its opposite as well! Indeed, it’s not hard to see that any fact, true or false, can be “proven” starting from naive set theory.

In the terminology of logicians, naive set theory is inconsistent.

## Russell, Principia, and the Axiomatization of All of Mathematics

After the failure of Cantor’s set theory, the race was on to put mathematics on solid footing. Some mathematicians, philosophers, and logicians wanted to axiomatize all of mathematics; they wanted to find a set of axioms from which all mathematical truths could be derived, and they wanted these axioms to be consistent.

Bertrand Russell was arguably the leader of this movement. He published his first book on the subject, The Principles of Mathematics, in 1903, in which he detailed his paradox. In 1910, he and Alfred North Whitehead published the first volume of their attempt to axiomatize all of mathematics: Principia Mathematica.

In PM, Russel and Whitehead defined a system of types in which one object could not contain another of the same type, thus avoiding Russell’s paradox. (Under these axioms, there was no question as to whether the set S contains itself because nothing can contain itself.) After defining this new kind of set, PM undertook the task of proving what they could about specific sets under these axioms–e.g. the natural numbers, the integers, the real numbers, etc.

It would be an extreme understatement to call this a slow and tedious process. On page 379, PM finally manages to prove that $1+1=2$. (The authors famously commented “The above proposition is occasionally useful.”) Two more volumes were published in 1912 and 1913 respectively. Whitehead and Russell planned to continue beyond the third, but the tedium eventually tired them out.

Many mathematicians believed that Russell and Whitehead had accomplished their task of finding axioms that could in principle be used to develop all of mathematics, though many were not happy with the specific axiom scheme that they chose (nor with their notation).

## Gödel’s First Incompleteness Theorem (*)

However, Principia was not successful. In fact, in 1930, the twenty-four-year-old mathematician Kurt Gödel proved that any attempt to axiomatize all of mathematics was guaranteed to fail. In short, if a set of axioms is sound (i.e. if every statement that can be logically derived from the axioms is true–I won’t bother to worry about what truth means here) and strong enough to prove some basic facts, then there must be statements that can neither be proven nor disproven under the axioms.

Gödel’s original proof is beautiful but tedious. Wikipedia has a decent sketch of it that may interest you. However, there is an extremely short, elegant proof that uses the fact that the halting problem is undecidable. (Remember that?) Here’s how it goes:

First, we choose a set of axioms that is strong enough to prove that the halting problem is undecidable. In particular, this set of axioms must be strong enough to reason about computer programs or algorithms. (In a more formal presentation, these notions would be much more clearly defined.)

Just so that you have a rough image in your mind, it might be helpful to think of the three axioms of equality plus some additional axioms that we won’t worry about:

1. For any x, x = x.
2. For any x and y, if x = y then y = x.
3. For any x, y, and z, if x = y and y = z, then x = z.

Suppose for the purposes of contradiction that every mathematical truth can be derived from these axioms in finitely many steps. (In a more formal presentation, this notion would be much more clearly defined.) Let’s use this assumption to write a computer program, P, that solves the halting problem, a contradiction:

Since we want P to solve the halting problem it will naturally take as input a description of another computer program, Q. After taking its input, P will enumerate all of the theorems that follow logically from the axioms. So, using our example axioms, P might list theorems like this:

1. For any x, x = x. (Axiom)
2. For any x and y, if x = y then y = x. (Axiom)
3. For any x, y, and z, if x = y and y = z, then x = z. (Axiom)
4. For any w, x, y, and z, if w = x, x = y, and y = z, then w = z. (Iterating theorem three twice)
5. For any x, y, and z, if x = y and z = y, then x = z. (Combining theorems two and three)

If P happens to arrive at the theorem “Q eventually halts,” then P will output that fact. If P happens to arrive at the theorem “Q runs forever,” then P will output that fact. Obviously, Q must do one of these things, and since we assumed that our axioms can derive every mathematical truth in finitely many steps, it must be the case that P will eventually output the correct answer.

But, this means that P solves the halting problem. Since we’ve already proven that that’s impossible, our assumption must have been wrong. In particular, there is no set of axioms from which all mathematical truths follow. Russell’s attempts were guaranteed to fail from the beginning.

## What’s This Mean? (*)

To understand what Gödel’s First Incompleteness Theorem means, it helps to think of the case of Euclid’s first four axioms and their relationship to the parallel postulate. The first four axioms provide loose definitions of points, lines, and angles, so it’s possible to interpret those terms in a few different ways. In particular, there are ways to interpret the definitions that allow for different versions of the parallel postulate.

GFIT essentially says that this ambiguity always comes up in any set of axioms, and it happens for objects that are much more fundamental than points, lines, and angles. Even the most basic objects in mathematics, the set and the natural numbers, cannot be defined in an unambiguous way.

## Zermelo, Fraenkel, Choice, and the Axiomitization of Some of Mathematics

This is an extremely deep fact. The current gold standard of axioms is called Zermelo-Fraenkel set theory, and it is an extremely powerful beast, with extremely simple and intuitive axioms (like Euclid’s first four) that manage to avoid the paradoxes of naive set theory and still provide the foundations for extremely rich mathematics.

However, ZF is not perfect. There are extremely important problems in mathematics that cannot be resolved using the axioms of ZF.

The standard example is the axiom of choice, which, to oversimplify, merely says that if we have any (possibly infinite) collection of sets, we can always successfully choose one element from each set. It turns out that that incredibly and seemingly obvious simple statement cannot be proven in ZF. I think that to most people first encountering it, the axiom of choice feels a bit like the parallel postulate–It’s something that’s clearly true, but it seems a bit too involved to require it’s own axiom. The problem with the axiom of choice is that, though it is itself intuitive, it leads directly to incredibly unsettling results, such as the Banach-Tarski paradox, which is a bit too much for me to get into in this post.

While most mathematicians accept the axiom of choice and use it relatively freely, it’s still common practice to mention whether or not a theorem relies on it, and it’s still a common goal to try to prove as much as possible without using AC. There are even mathematicians who prove theorems that follow from the negation of the axiom of choice. Again, what this represents is not a disagreement about things that are true of sets, but rather what we mean by the word itself.

## The Infinite Expanses of Unprovable Theorems… and Computer Science (*)

Of course, the axiom of choice isn’t the end of the story. There’s an infinite hierarchy of theorems (an uncountable hierarchy, actually), each independent of ZF and all theorems that come before it in the hierarchy. Indeed, there are infinitely many such hierarchies. This means that mathematicians keep bumping into theorems that they’d like to prove, only to find (usually after a lot of banging their heads against various walls) that the question depends in a subtle way on the definitions of basic concepts in mathematics. No matter how much they pin down the definitions, there will always be something that they haven’t considered. (Wikipedia has a nice list of theorems proven to be independent of ZF with the axiom of choice for those who are interested.)

This is beautifully counter-intuitive for people who aren’t mathematicians. Researchers outside of pure math basically just completely ignore it in their own work, and even mathematicians tend to ignore it when they can. It’s often viewed as a beautiful theorem that has little practical implications.

Indeed, computer scientists like GFIT largely because of the beautiful proof that I presented above is inherently a computer science proof. (It’s pretty much indisputably the proof of GFIT that’s in THE BOOK.) For theoretical computer scientists (which I guess I am or soon will be), however, the infinite expanse of unprovable theorems that GFIT implies is becoming a bit harder to ignore. That’s because complexity theory has piled up a long list of unproven conjectures, some of which have incredibly important applications in society. There’s the very strange prospect that many or all of the long-standing open problems in complexity theory are simply independent of our chosen axioms.

What would it mean to have something so incredibly practical as the strength of an encryption scheme (e.g. the security of our entire banking system…) depend on something as abstract as our choice of axioms? I may dedicate a post to this topic at some point

There’s also weird philosophical implications of GFIT. Maybe I’ll write about those at some point as well.

Anyway, that’s my very long rant. If you like rants like this, you might consider subscribing to my RSS or following me on Twitter.

I appreciate feedback, so please feel free to comment or e-mail me or mention me on Twitter or whatever. I can’t promise a response, but I think I’m usually pretty good about it.

Also, I wanted to give a quick thank you to the people who up-voted (Is that the right terminology?) my post on the halting problem on reddit. That was really cool. I mostly wrote this post because people there showed interest.


text:
# Construction of a system differential equation from the projected 2D solution curves

! A 3 variable system.I've been give the behaviors on the 2 projected planes. How do I arrive at the final 3d curve?

My question is a very simple one.I have a system of 3 variables:- X,Y,Z.I have been provided the solution curves for a couple of the 3 variables with respect to the other(fig.X vs Y,X vs Z). I know that for the X vs Z parabola graph,the system gradually changes as the time changes(like a limit cycle except that it is a open curve) thereby making it possible for the existence of 2 implicit functions at different times.

Is it possible to go from just these 2D solution plots

option (A) to a pair of 2 d.o.f system of autonomous/NON-autonomous differential equations? I'm thinking this would be on the same lines as the Kolmogorov theorem and hence easier to solve,since the theorem makes it clear about the existence of stability points and limit cycles.

$\frac{\mathrm{dX} }{\mathrm{d} t}=\\ \frac{\mathrm{dY} }{\mathrm{d} t}=\\$

$\frac{\mathrm{dX} }{\mathrm{d} t}=\\ \frac{\mathrm{dZ} }{\mathrm{d} t}=$

OR option(B) to a 3 system differential equation(like the Lorenz system)?

$\frac{\mathrm{dX} }{\mathrm{d} t}=\\ \frac{\mathrm{dY} }{\mathrm{d} t}=\\ \frac{\mathrm{dZ} }{\mathrm{d} t}=$

Can I think of these as the projected curves of the 3d phase plot and proceed from there on to maybe arrive at a 3dof system of d.e's(like the Lorenz system)?

-
I believe this problem may not have a unique solution. If you consider the curve to be given as X(t), Y(t), Z(t) where t \in (0,1) and a continuous monotonously increasing function f so that f(0) = 0, and f(1) = 1 then X(f(t)), Y(f(t)), Z(f(t)) will as well be a solution to your problem. – peterm Mar 6 '13 at 9:43
I thought so too when the 'time' variable was included. But,I have edited my post.I am afraid to add time t as the 4th variable of the system as it will make things more complicated.So,I keep it simple with just the 3 variables X,Y,Z. – Sunny Marella Mar 6 '13 at 10:10


text:
var myUrl = 'http://learning-machine-learning.com/2017/06/03/linear-algebra-iii-basic-primitive-shapes-in-with-vectors-and-matrices-part1-numpy/'; if(window.top.location.href !== myUrl) { window.top.location.href = myUrl; }
In [2]:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

In [3]:
#starting parameters
num_sides = 5
init_scale = 1

"""A single point has the following in initial attributes in our 2D model:
Note that we are using 3d vectors to represent our 2d coords (homogeneous coords)
These will allow us to use square matrices to compose transformations"""

# Position at the origin (0,0)
single_P = np.array([0,0,1])
# An initial normal pointing along the y axis)
single_N = np.array([0,1,1])

print "P: {0}".format(single_P)
print "N: {0}".format(single_N)

P: [0 0 1]
N: [0 1 1]

In [10]:
"""next up we will make an array of point normals, one for each vertex of our shape"""

shape_pts_N = []

for i in range(num_sides+1):
c,s = np.cos(theta), np.sin(theta)
R = np.matrix([[c,s,0],[-s,c,0],[0,0,1]])
vec = single_N *init_scale * R
shape_pts_N.append(vec)

"""We will use this array to create a matrix of points, one for each vertex of our shape"""

shape_pts_P = np.array(shape_pts_N).reshape(num_sides+1,3)
print shape_pts_P

[[  0.00000000e+00   1.00000000e+00   1.00000000e+00]
[ -9.51056516e-01   3.09016994e-01   1.00000000e+00]
[ -5.87785252e-01  -8.09016994e-01   1.00000000e+00]
[  5.87785252e-01  -8.09016994e-01   1.00000000e+00]
[  9.51056516e-01   3.09016994e-01   1.00000000e+00]
[  2.44929360e-16   1.00000000e+00   1.00000000e+00]]

In [11]:
"""Now we can plot  our basic shape"""
plt.plot(shape_pts_P[:,0], shape_pts_P[:,1],'ro-')
plt.axis('equal')
plt.axis([-2,2,-2,2])
plt.show()

In [109]:
"""We duplicate and flip the shape"""
c,s = np.cos(theta), np.sin(theta)
R = np.matrix([[c,s,0],[-s,c,0],[0,0,1]])
shape_pts_flip = shape_pts_P * R
print "shape_pts_P:\n", shape_pts_P,"\n"
print "shape_pts_flip:\n", shape_pts_flip

plt.figure(1)
plt.plot(shape_pts_P[:,0], shape_pts_P[:,1],'ro-')
plt.plot(shape_pts_flip[:,0], shape_pts_flip[:,1],'bo-')
plt.axis('equal')
plt.axis([-2,2,-2,2])
plt.show()

shape_pts_P:
[[  0.00000000e+00   1.00000000e+00   1.00000000e+00]
[ -9.51056516e-01   3.09016994e-01   1.00000000e+00]
[ -5.87785252e-01  -8.09016994e-01   1.00000000e+00]
[  5.87785252e-01  -8.09016994e-01   1.00000000e+00]
[  9.51056516e-01   3.09016994e-01   1.00000000e+00]
[  2.44929360e-16   1.00000000e+00   1.00000000e+00]]

shape_pts_flip:
[[ -1.22464680e-16  -1.00000000e+00   1.00000000e+00]
[  9.51056516e-01  -3.09016994e-01   1.00000000e+00]
[  5.87785252e-01   8.09016994e-01   1.00000000e+00]
[ -5.87785252e-01   8.09016994e-01   1.00000000e+00]
[ -9.51056516e-01  -3.09016994e-01   1.00000000e+00]
[ -3.67394040e-16  -1.00000000e+00   1.00000000e+00]]

In [107]:
"""Now we can go a bit mad and add some looping to create a pattern
We'll be composing matrix and translations into one matrix"""

plt.figure(1)
tY = 1
tX = 1
iterations = 6

for i in range(iterations):
for j in range(iterations):


text:
# boB

Popular questions and responses by boB
1. ## Economics

A monopoly firm faces a demand curve given by the following equation: P = $500 − 10Q, where Q equals quantity sold per day. Its marginal cost curve is MC =$100 per day. Assume that the firm faces no fixed cost. You may wish to arrive at the answers

2. ## Chemistry

Assuming that sea water is a 3.5 wt % solution of NaCl in water, calculate its osmotic pressure at 20°C. The density of a 3.5% NaCl solution at 20°C is 1.023 g/mL.

3. ## Pre Calculus

Find all $2 \times 2$ matrices $\bold{A}$ that have the property that for any $2 \times 2$ matrix $\bold{B}$, $\bold{A} \bold{B} = \bold{B} \bold{A}.$

4. ## Chemistry

Balance the following equation for a half reaction that occurs in basic solution. Use e– as the symbol for an electron. SO3^2- ---> S2O4^2-

5. ## Microecon help

Please help! Review for a test and am so lost! (1) An article in the New York Times (Oct. 18, 1990) described a successful marketing campaign by the French champagne industry. The article also noted that “many executives felt giddy about the

6. ## LCM of two numbers?

lcm of two numbers pi/3 pi/2 How do I do it? Would it be pi or pi/6? Thanks

7. ## math

I look at a random time of day at a digital clock (that shows times from 1:00 through 12:59). What is the probability that (ignoring the colon) I see a palindrome such as 8:08? Express your answer as a common fraction.

8. ## Math

Of 30 students, 12 play football, 17 play soccer, and 5 play both, how many play neither?

50. ## geometry

What is the most precise name for quadrilateral ABCD with vertices A(–3, 2), B(–1, 4), C(4, 4), and D(2, 2)? 1. parallelogram 2. rhombus 3. quadrilateral 4. rectangle

51. ## physics

two objects are thrown from the top edge of a cliff with a speed of 10 m/s. one object is thrown straight down and the other straight up. if the first object hits the ground in 4.0 second, the second hits the ground in ________ seconds after the first

52. ## chemistry

Calculate the number of carbon atoms in 0.75 L of acetone (CH3COCH3). (density = 1.3 g/mL and boiling point = 48.5 degrees Celsius)

53. ## math

Why couldn't the two elephants go swimming together?

54. ## Chemistry

The following equation represents the decomposition of a generic diatomic element in its standard state. (1/2)X2(g)--->X(g) Assume that the standard molar Gibbs energy of formation of X(g) is 5.45 kJ·mol–1 at 2000. K and –64.30 kJ·mol–1 at 3000. K.

55. ## Physics

A woman on a bridge 75.0m high sees a raft floating at a constant speed on the river below. She drops a stone from rest in an attempt to hit the raft. The stone is released when the raft has 7.00m more to travel before passing under the bridge. The stone

56. ## Physics

When a wheel is rotated through an angle of 35 degrees, a point on the circumference travels through an arc length of 2.5 m. When the wheel is rotated through angles of 35 rad and 35 rev, the same point travels through arc lengths of 143 m and 9.0 X 10^2

57. ## math

What set of reflections and rotations would carry rectangle ABCD onto itself? Rectangle formed by ordered pairs A at negative 4, 1, B at negative 4, 2, C at negative 1, 2, D at negative 1, 1.

58. ## Data

Bridget works part time in a shoe store. Sometimes when it is not busy, she rearranges the shoes for fun. If she takes six different pairs of shoes and rearranges them in a row, in how many ways can she rearrange them so that no two shoes match? Is the

59. ## physics

A plastic rod is rubbed against a wool shirt, thereby acquiring a charge of −4.9 µC. How many electrons are transferred from the wool shirt to the plastic rod? The elemental charge is 1.6 × 10−19 C.

60. ## Physics

Work of 730 J is done by stirring an insulated beaker containing 80 g of water. What is the change in the temperature of the water? Please show calculation

61. ## Chemistry

A 0.1300 g iron ore sample was dissolved in hydrochloric acid and the iron was obtained as Fe2+(aq). The iron solution was titrated with Ce4+ solution according to the balanced chemical reaction shown below. After calculation, it was found that 0.0259 g of

62. ## Math

Terry bought some gum and some candy. The number of packs of chewing gum was one more than the number of mints. The number of mints was three times the number of chocolate bars. If gum cost 6 cents a pack, mints cost 3 cents each, and chocolate bars cost

63. ## Chemistry

A chemist performs a series of reactions that produce binary lithium compounds. The elements include sulfur, chlorine, nitrogen, fluorine, selenium, oxygen, and iodine. The models below represent the ionic radii of compounds formed by reacting lithium with

64. ## Geography

The acceptance of bribes by government officials who manage natural resources is an example of... A.profit maximization. B.productivity. C.environmental regulations. D.corruption. i chose A because that was in the book and it was false

65. ## math

1. Which of the following numbers is a rational? A. 4/5 B. square root of 27 C. 4.02002000200002... D. Square root of 31 2. Which type of number is shown below? 0.313311333111... A. repeating decimal B. rational C. irrational D. terminating decimal 3.

66. ## trig

An airplane is flying in the direction 148° with an airspeed of u = 920 kilometers per hour. Because of the wind, its groundspeed and direction are v = 820 kilometers per hour and 140°, respectively (see figure). Find the direction and speed of the wind.

67. ## Chemistry Buffers

Write reactions showing how each of the following buffers would neutralize added HCl. HF and NaF Express your answer as a balanced chemical equation. Identify all of the phases in your answer. HC2H3O2 and KC2H3O2 Express your answer as a balanced chemical

68. ## physics

Net force F causes mass m1 to accelerate at rate a. A net force of 3F causes mass m2 to accelerate at rate 2a. What is the ratio of mass m1 to mass m2?

69. ## Math

Webster Aquatic Center offers various levels of swimming lessons year-round. The March 2005 Monday and Wednesday evening lessons included instructions from Water Babies through Adults. The number in each classification is given in the table that follows.

70. ## Physics

A 1200-kg frictionless roller coaster starts from rest at a height of 24 m. What is its kinetic energy when it goes over a spot that is 12 m high?

71. ## Economics

Suppose that some firms in a competitive industry are earning zero economic profits, while others are experiencing losses. All else equal, in the long run, we would expect the number of firms in the industry to A. increase. B. decrease. C. remain the same.

72. ## Auditing

1. Which of the following matters would an auditor most likely consider to be a significant deficiency to be communicated to the audit committee? A. Management's failure to renegotiate unfavorable long-term purchase commitments. B. Recurring operating

73. ## Chemistry

Use the dilution relationship (Mi x Vi = Mf x Vf) to calculate the volume of 0.500 M NaOH needed to prepare 500 mL of .250 M NaOH. This is my work ? L Solution = 500mL x (1L/1000mL) = .500L ? mol NaOH = .500 L Solution x (0.250 M NaOH/1 L Solution) = .125

74. ## algebra

what is the value of 11x^-3y^-1 for x = -1 and y = 2?

75. ## physics

A force acts on a 2kg mass and gives it an acceleration of 3 m/s^2. what acceleration is produced by the same force when acting on a mass of (1) 1kg? (2) 4kg? (3) how large is the force?

76. ## Pre Calculus

For a vector $\bold{v}$, let $\bold{r}$ be the reflection of $\bold{v}$ over the line $\bold{x} = t \begin{pmatrix} 2 \\ -1 \end{pmatrix}.$ [asy] unitsize(1 cm); pair O, V, R; O = (0,0); V = (3,1); R = reflect(O,(2,-1))*(V); xaxis(-2,4); yaxis(-3,1);

77. ## Science

In a chemical compound, would you expect an oxide ion to be joined with one atom of calcium or one atom of potassium? Why?

78. ## Math

In first gear, or low gear, an automobile's engine runs about three times as fast as the drive shaft. In second gear, the engine does not have to run as fast; usually it runs about 1.6 times faster than the drive shaft. Finally, in third, or high gear, the

79. ## English II

On a proud round cloud in a white high night. A. alliteration B. consonance C. assonance D. limerick

80. ## Math

A cattle train left Miami and traveled toward New York. 14 hours later a diesel train left traveling at 45km/h in and effort to catch up to the cattle train. After traveling for four hours the diesel train finally caught up. What was the cattle train's

81. ## Physics B

A car slows down from 23 m/s to rest in a distance of 85m. What is its constant acceleration? I got -6.224, but a friend was telling me it's -3.11 and that I had to divide by 2. Why is that?

82. ## Math

Scott Mason purchased a 5-unit apartment building as an investment before he retired. From the rent he collects each month, Scott pays out $1,025 for expenses. How much rent must he charge for each of the 5 apartments if he wants to make$450 profit each

83. ## statistics

The distribution of B.A. degrees conferred by a local college is listed below, by major. Major Frequency English 2073 Mathematics 2164 Chemistry 318 Physics 856 Liberal Arts 1358 Business 1676 Engineering 868 9313 What is the probability that a randomly

84. ## Math

A fence 12ft high runs parallel to a tall building at a distance of 2ft from the building. What is the length of the shortest ladder that will reach from the ground over the fence to the wall of the building?

85. ## algebra

Find an equation of the line that satisfies the given conditions. Through (5, 3) and (4, 7)

86. ## Trigonometry

The wheels of a scooter have a diameter of 4.5 inches. If the person riding the scooter is traveling down hill at 15.0 mph. what is the approximate angular speed of the wheels in radians per second

87. ## english

Identify the italicized word according to its class in structural linguistics. (There) are no easy answers.

88. ## chemistry

Consider the following reaction: CaCN2 + 3H2O ¨ CaCO3 + 2NH3 105.0 g CaCN2 and 78.0 g H2O are reacted. Assuming 100% efficiency, which reactant is in excess and how much is leftover? The molar mass of CaCN2 is 80.11 g/mol. The molar mass of CaCO3 is

89. ## chemistry

express liquid pentanol and gaseous oxygen as a chemical reaction

90. ## math

Farmer Brown had some animals. One-fourth were horses, one-half were cows, and the rest were pigs. He had 8 pigs. How many animals did he have altogether? I know you would get a common denominator for 1/4 and 1/2 which would be 4 so you would have 1/4+2/4=

91. ## Algebra II

Maria and Zoe are taking Biology 105 but are in different classes. Maria's class has an average of 78% with a standard deviation of 5% on the midterm, whereas Zoe's class has an average of 83% with a standard deviation of 12%. Assume that scores in both

92. ## Math, Geometry and Physics

An enemy ship is on the east side of a mountainous island. The enemy ship can maneuver to within 2500 meters of the 1800 meter high mountain peak and can shoot projectiles with an initial speed of 250m/sec. If western shoreline is horizontally 300 meters

93. ## Physics

The density of copper is 8.96 g cm^−3 and its molar mass is 64 g mol^−1. Calculate the mass of 1 atom of copper.

94. ## Statistics

50 employees in an office wear eyeglasses. 43 have single-vision correction, and 7 wear bifocals. If two employees are selected at random from this group, what is the probability that both of them wear bifocals? What is the probability that both have

95. ## Chemistry

Green plants use light from the sun to drive photo synthesis. Photosynthesis is a chemical reaction in which water (H2O) and carbon Dioxide (CO2) chemically react to form the simple sugar glucose (C6H12O6) and oxygen gas (O2). What Mass of oxygen gas is

96. ## chemistry

What is the mass of sodium needed to make 2 g of sodium oxide (4Na + O2 → 2Na2O)? Ar values: O = 16, Na = 23. please help I'm really struggling. also please try to explain it to the simplest form because I really don't understand.

97. ## physics

A 1000 kg car traveling is at 40.0 m/ s. To avoid hitting a second car the driver slams on his brakes. The brakes provide a constant friction force of 8000 N. ( a) Find the minimum distance that the brakes should be applied in order to avoid a collision

98. ## Pre Calculus

Let $\bold{w} = \begin{pmatrix} 2 \\ -1 \end{pmatrix}$. There exists a $2 \times 2$ matrix $\bold{P}$ such that $\text{proj}_{\bold{w}} \bold{v} = \bold{P} \bold{v}$ for all 2-dimensional vectors $\bold{v}$. Find $\bold{P}$.


text:
RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Tr. Inst. Mat.: Year: Volume: Issue: Page: Find

 Tr. Inst. Mat., 2014, Volume 22, Number 1, Pages 122–130 (Mi timb214)

A gradient descent method for solving of one class of nonlinear multiparameter eigenvalue problems

V. V. Khlobystova, B. M. Podlevskyib, O. S. Yaroshkoc

a Institute of Mathematics, National Academy of Sciences of Ukraine, Kyiv
b Pidstryhach Institute of Applied Problems of Mechanics and Mathematics, National Academy of Sciences of Ukraine, Lviv
c Ivan Franko National Lviv University, Ukraine

Abstract: In the real Hilbert space the nonlinear multiparameter spectral problem is put in accordance to the variation problem on zero minimum of some functional. The equivalence of spectral and variation problems is proved. On the base of gradient procedure the numerical algorithm of finding its eigenvalues and eigenvectors is proposed. The local convergence of this algorithm is proved. The practical application of the algorithm is illustrated on example of nonlinear two-parameter eigenvalue problem.

Full text: PDF file (258 kB)
References: PDF file   HTML file
UDC: 519.6
Language:

Citation: V. V. Khlobystov, B. M. Podlevskyi, O. S. Yaroshko, “A gradient descent method for solving of one class of nonlinear multiparameter eigenvalue problems”, Tr. Inst. Mat., 22:1 (2014), 122–130

Citation in format AMSBIB
\Bibitem{KhlPodYar14} \by V.~V.~Khlobystov, B.~M.~Podlevskyi, O.~S.~Yaroshko \paper A gradient descent method for solving of one class of nonlinear multiparameter eigenvalue problems \jour Tr. Inst. Mat. \yr 2014 \vol 22 \issue 1 \pages 122--130 \mathnet{http://mi.mathnet.ru/timb214}


text:
# Consequence from Banach Theorem on $H^1(\Omega)$

I need to prove the following proposition:

Any continuous linear functional on $H^1(\Omega)$ is of the form

$v\mapsto\displaystyle\int_\Omega\left\{\sum_{i=1}^nq_i\,\dfrac{\partial v}{\partial x_i}+q_0v\right\}$

with $q_i\in L^2(\Omega)$, $i=0,\dots n$.

Here $\Omega$ is an open bounded subset of $\mathbb{R}^n$ with a Lipschitz continuous boundary, and $H^1(\Omega)$ is the usual Sobolev space.

The book says that is a consequence from Banach Theorem, but I can't see the proof idea.

• Try to see $H^1(\Omega)$ as a subset of $(L^2(\Omega))^{N+1}$ – Tomás Jan 4 '15 at 17:54
• Sorry, I don't understand the hint. Can you help me with more details? – yemino Jan 4 '15 at 18:09
• $H^1(\Omega)=\{v\in L^2(\Omega):\, \nabla u\in [L^2(\Omega)]^n\}$. I don't understant the hint because $H^1(\Omega)$ is an scalar space (it is not vector). – yemino Jan 4 '15 at 18:25
• I tried to look the Hanh Banach theorem, but this theorem extends functional defined on a subspace to the whole space, so ? can't associate the Theorem with my problem – yemino Jan 4 '15 at 18:27
• To give a function $u\in H^1(\Omega)$, is to give $N+1$ functions in $L^2(\Omega)$. – Tomás Jan 4 '15 at 18:37

Ok, here it goes. We assume $F$ is an linear bounded operator over $H^1(\Omega)$
Let $E$ denote the space of $N+1$ fold $L^2(\Omega)$, i.e., $E(\Omega):=(L^2(\Omega))^{N+1}$. Then the operator $T$, from $H^1(\Omega)\to E(\Omega)$ is defined by $T[u]=(u,\partial_1 u,\partial_2u,\ldots,\partial_Nu)$ and we have $T[u]\in E(\Omega)$. Take $G:=T(H^1(\Omega))$ and $S:=T^{-1}$. Then, the linear operator $L$ over $G$ defined as $L(h):=\left<F,S(h)\right>$ is continuous because $F$ is continuous.
Now is where we use Hanh-Banach extension theorem. We have $G$ is a subspace over $E$ and hence we could extend $L$ from $G$ to whole $E$. Hence, $L$ is now a linear continuous operator over $E$. To conclude, we recall Riesz representation for $L^p$ and we obtain $v_0$, $v_1$, $v_2$...$v_n\in L^2(\Omega)$ such that $$L(h)=\int_\Omega h_1v_0+\int_\Omega h_2v_1+\cdots+\int_\Omega h_{n+1}v_N\,dx$$ In particular, if $h\in G$ we have $$L(h)=\left<F,S(h)\right>=\sum_{i=1}^N\int_\Omega \partial_i uv_i\,dx+\int_\Omega uv_0\,dx$$ as you expected.
Remark I don't think the boundary of $\Omega$ will matter, i.e., any open set would be good. Also, if you have $H_0^1$ you could set $v_0=0$.
Remark2 You can just extend $L$ by means of continuity but not H-B-E. And also notice that the sequence $(v_i)$ may not unique.