Where are the main menu links created? I've been doing some w3 validation but I find that my menu's are missing a &lt;ul&gt; for the &lt;li&gt;'s. I have read Where is links__system_main_menu defined? but this doesn't really answer my question. I understand that 


  links__system_main_menu is a theme hook pattern of the form [base
  hook]__[context]. When links are themed with
  theme('links__system_main_menu', $vars), theme() will search for and
  use theme_links__system_main_menu() if it has been defined. If not, it
  will use theme_links().


The theme i'm using doesn't do much as far as modify the menu system at first glance. In the theme.php file, it contains: 

$variables['main_menu_themed'] = theme(
    'links__system_main_menu',
    array(
      'links' =&gt; $variables['main_menu'],
      'attributes' =&gt; array(
        'id' =&gt; '',
        'class' =&gt; array('links', 'clearfix'),
      ),
      'heading' =&gt; array(
        'text' =&gt; t('Main menu'),
        'level' =&gt; 'h2',
        'class' =&gt; array('element-invisible'),
      ),
    )
  );


How can I modify the actual output of the menu?
You can override theme_links__system_main_menu() by declaring a function in your theme's template.php file:

function MYTHEME_links__system_main_menu($vars) {
  $links = $vars['links'];

  $items = array();
  foreach ($links as $link) {
    $items[] = l($link['title'], $link['href']);
  }

  return theme('item_list', array('items' =&gt; $items));
}


The above is a very basic example, you'll probably want to take a look at the original code for theme_links() to make that a bit more bulletproof.