708 unfolding T_def |
708 unfolding T_def |
709 by auto (metis dist_self) |
709 by auto (metis dist_self) |
710 from 1 2 show ?lhs |
710 from 1 2 show ?lhs |
711 unfolding openin_open open_dist by fast |
711 unfolding openin_open open_dist by fast |
712 qed |
712 qed |
713 |
713 |
|
714 lemma connected_open_in: |
|
715 "connected s \<longleftrightarrow> |
|
716 ~(\<exists>e1 e2. openin (subtopology euclidean s) e1 \<and> |
|
717 openin (subtopology euclidean s) e2 \<and> |
|
718 s \<subseteq> e1 \<union> e2 \<and> e1 \<inter> e2 = {} \<and> e1 \<noteq> {} \<and> e2 \<noteq> {})" |
|
719 apply (simp add: connected_def openin_open, safe) |
|
720 apply (simp_all, blast+) |
|
721 done |
|
722 |
|
723 lemma connected_open_in_eq: |
|
724 "connected s \<longleftrightarrow> |
|
725 ~(\<exists>e1 e2. openin (subtopology euclidean s) e1 \<and> |
|
726 openin (subtopology euclidean s) e2 \<and> |
|
727 e1 \<union> e2 = s \<and> e1 \<inter> e2 = {} \<and> |
|
728 e1 \<noteq> {} \<and> e2 \<noteq> {})" |
|
729 apply (simp add: connected_open_in, safe) |
|
730 apply blast |
|
731 by (metis Int_lower1 Un_subset_iff openin_open subset_antisym) |
|
732 |
|
733 lemma connected_closed_in: |
|
734 "connected s \<longleftrightarrow> |
|
735 ~(\<exists>e1 e2. |
|
736 closedin (subtopology euclidean s) e1 \<and> |
|
737 closedin (subtopology euclidean s) e2 \<and> |
|
738 s \<subseteq> e1 \<union> e2 \<and> e1 \<inter> e2 = {} \<and> |
|
739 e1 \<noteq> {} \<and> e2 \<noteq> {})" |
|
740 proof - |
|
741 { fix A B x x' |
|
742 assume s_sub: "s \<subseteq> A \<union> B" |
|
743 and disj: "A \<inter> B \<inter> s = {}" |
|
744 and x: "x \<in> s" "x \<in> B" and x': "x' \<in> s" "x' \<in> A" |
|
745 and cl: "closed A" "closed B" |
|
746 assume "\<forall>e1. (\<forall>T. closed T \<longrightarrow> e1 \<noteq> s \<inter> T) \<or> (\<forall>e2. e1 \<inter> e2 = {} \<longrightarrow> s \<subseteq> e1 \<union> e2 \<longrightarrow> (\<forall>T. closed T \<longrightarrow> e2 \<noteq> s \<inter> T) \<or> e1 = {} \<or> e2 = {})" |
|
747 then have "\<And>C D. s \<inter> C = {} \<or> s \<inter> D = {} \<or> s \<inter> (C \<inter> (s \<inter> D)) \<noteq> {} \<or> \<not> s \<subseteq> s \<inter> (C \<union> D) \<or> \<not> closed C \<or> \<not> closed D" |
|
748 by (metis (no_types) Int_Un_distrib Int_assoc) |
|
749 moreover have "s \<inter> (A \<inter> B) = {}" "s \<inter> (A \<union> B) = s" "s \<inter> B \<noteq> {}" |
|
750 using disj s_sub x by blast+ |
|
751 ultimately have "s \<inter> A = {}" |
|
752 using cl by (metis inf.left_commute inf_bot_right order_refl) |
|
753 then have False |
|
754 using x' by blast |
|
755 } note * = this |
|
756 show ?thesis |
|
757 apply (simp add: connected_closed closedin_closed) |
|
758 apply (safe; simp) |
|
759 apply blast |
|
760 apply (blast intro: *) |
|
761 done |
|
762 qed |
|
763 |
|
764 lemma connected_closed_in_eq: |
|
765 "connected s \<longleftrightarrow> |
|
766 ~(\<exists>e1 e2. |
|
767 closedin (subtopology euclidean s) e1 \<and> |
|
768 closedin (subtopology euclidean s) e2 \<and> |
|
769 e1 \<union> e2 = s \<and> e1 \<inter> e2 = {} \<and> |
|
770 e1 \<noteq> {} \<and> e2 \<noteq> {})" |
|
771 apply (simp add: connected_closed_in, safe) |
|
772 apply blast |
|
773 by (metis Int_lower1 Un_subset_iff closedin_closed subset_antisym) |
|
774 |
714 text \<open>These "transitivity" results are handy too\<close> |
775 text \<open>These "transitivity" results are handy too\<close> |
715 |
776 |
716 lemma openin_trans[trans]: |
777 lemma openin_trans[trans]: |
717 "openin (subtopology euclidean T) S \<Longrightarrow> openin (subtopology euclidean U) T \<Longrightarrow> |
778 "openin (subtopology euclidean T) S \<Longrightarrow> openin (subtopology euclidean U) T \<Longrightarrow> |
718 openin (subtopology euclidean U) S" |
779 openin (subtopology euclidean U) S" |
1705 qed |
1765 qed |
1706 |
1766 |
1707 lemma islimpt_in_closure: "(x islimpt S) = (x:closure(S-{x}))" |
1767 lemma islimpt_in_closure: "(x islimpt S) = (x:closure(S-{x}))" |
1708 unfolding closure_def using islimpt_punctured by blast |
1768 unfolding closure_def using islimpt_punctured by blast |
1709 |
1769 |
|
1770 lemma connected_imp_connected_closure: "connected s \<Longrightarrow> connected (closure s)" |
|
1771 by (rule connectedI) (meson closure_subset open_Int open_inter_closure_eq_empty subset_trans connectedD) |
|
1772 |
|
1773 lemma limpt_of_limpts: |
|
1774 fixes x :: "'a::metric_space" |
|
1775 shows "x islimpt {y. y islimpt s} \<Longrightarrow> x islimpt s" |
|
1776 apply (clarsimp simp add: islimpt_approachable) |
|
1777 apply (drule_tac x="e/2" in spec) |
|
1778 apply (auto simp: simp del: less_divide_eq_numeral1) |
|
1779 apply (drule_tac x="dist x' x" in spec) |
|
1780 apply (auto simp: zero_less_dist_iff simp del: less_divide_eq_numeral1) |
|
1781 apply (erule rev_bexI) |
|
1782 by (metis dist_commute dist_triangle_half_r less_trans less_irrefl) |
|
1783 |
|
1784 lemma closed_limpts: "closed {x::'a::metric_space. x islimpt s}" |
|
1785 using closed_limpt limpt_of_limpts by blast |
|
1786 |
|
1787 lemma limpt_of_closure: |
|
1788 fixes x :: "'a::metric_space" |
|
1789 shows "x islimpt closure s \<longleftrightarrow> x islimpt s" |
|
1790 by (auto simp: closure_def islimpt_Un dest: limpt_of_limpts) |
|
1791 |
|
1792 lemma closed_in_limpt: |
|
1793 "closedin (subtopology euclidean t) s \<longleftrightarrow> s \<subseteq> t \<and> (\<forall>x. x islimpt s \<and> x \<in> t \<longrightarrow> x \<in> s)" |
|
1794 apply (simp add: closedin_closed, safe) |
|
1795 apply (simp add: closed_limpt islimpt_subset) |
|
1796 apply (rule_tac x="closure s" in exI) |
|
1797 apply simp |
|
1798 apply (force simp: closure_def) |
|
1799 done |
|
1800 |
|
1801 subsection\<open>Connected components, considered as a connectedness relation or a set\<close> |
|
1802 |
|
1803 definition |
|
1804 "connected_component s x y \<equiv> \<exists>t. connected t \<and> t \<subseteq> s \<and> x \<in> t \<and> y \<in> t" |
|
1805 |
|
1806 abbreviation |
|
1807 "connected_component_set s x \<equiv> Collect (connected_component s x)" |
|
1808 |
|
1809 lemma connected_component_in: "connected_component s x y \<Longrightarrow> x \<in> s \<and> y \<in> s" |
|
1810 by (auto simp: connected_component_def) |
|
1811 |
|
1812 lemma connected_component_refl: "x \<in> s \<Longrightarrow> connected_component s x x" |
|
1813 apply (auto simp: connected_component_def) |
|
1814 using connected_sing by blast |
|
1815 |
|
1816 lemma connected_component_refl_eq [simp]: "connected_component s x x \<longleftrightarrow> x \<in> s" |
|
1817 by (auto simp: connected_component_refl) (auto simp: connected_component_def) |
|
1818 |
|
1819 lemma connected_component_sym: "connected_component s x y \<Longrightarrow> connected_component s y x" |
|
1820 by (auto simp: connected_component_def) |
|
1821 |
|
1822 lemma connected_component_trans: |
|
1823 "\<lbrakk>connected_component s x y; connected_component s y z\<rbrakk> \<Longrightarrow> connected_component s x z" |
|
1824 unfolding connected_component_def |
|
1825 by (metis Int_iff Un_iff Un_subset_iff equals0D connected_Un) |
|
1826 |
|
1827 lemma connected_component_of_subset: "\<lbrakk>connected_component s x y; s \<subseteq> t\<rbrakk> \<Longrightarrow> connected_component t x y" |
|
1828 by (auto simp: connected_component_def) |
|
1829 |
|
1830 lemma connected_component_Union: "connected_component_set s x = Union {t. connected t \<and> x \<in> t \<and> t \<subseteq> s}" |
|
1831 by (auto simp: connected_component_def) |
|
1832 |
|
1833 lemma connected_connected_component [iff]: "connected (connected_component_set s x)" |
|
1834 by (auto simp: connected_component_Union intro: connected_Union) |
|
1835 |
|
1836 lemma connected_iff_eq_connected_component_set: "connected s \<longleftrightarrow> (\<forall>x \<in> s. connected_component_set s x = s)" |
|
1837 proof (cases "s={}") |
|
1838 case True then show ?thesis by simp |
|
1839 next |
|
1840 case False |
|
1841 then obtain x where "x \<in> s" by auto |
|
1842 show ?thesis |
|
1843 proof |
|
1844 assume "connected s" |
|
1845 then show "\<forall>x \<in> s. connected_component_set s x = s" |
|
1846 by (force simp: connected_component_def) |
|
1847 next |
|
1848 assume "\<forall>x \<in> s. connected_component_set s x = s" |
|
1849 then show "connected s" |
|
1850 by (metis `x \<in> s` connected_connected_component) |
|
1851 qed |
|
1852 qed |
|
1853 |
|
1854 lemma connected_component_subset: "connected_component_set s x \<subseteq> s" |
|
1855 using connected_component_in by blast |
|
1856 |
|
1857 lemma connected_component_eq_self: "\<lbrakk>connected s; x \<in> s\<rbrakk> \<Longrightarrow> connected_component_set s x = s" |
|
1858 by (simp add: connected_iff_eq_connected_component_set) |
|
1859 |
|
1860 lemma connected_iff_connected_component: |
|
1861 "connected s \<longleftrightarrow> (\<forall>x \<in> s. \<forall>y \<in> s. connected_component s x y)" |
|
1862 using connected_component_in by (auto simp: connected_iff_eq_connected_component_set) |
|
1863 |
|
1864 lemma connected_component_maximal: |
|
1865 "\<lbrakk>x \<in> t; connected t; t \<subseteq> s\<rbrakk> \<Longrightarrow> t \<subseteq> (connected_component_set s x)" |
|
1866 using connected_component_eq_self connected_component_of_subset by blast |
|
1867 |
|
1868 lemma connected_component_mono: |
|
1869 "s \<subseteq> t \<Longrightarrow> (connected_component_set s x) \<subseteq> (connected_component_set t x)" |
|
1870 by (simp add: Collect_mono connected_component_of_subset) |
|
1871 |
|
1872 lemma connected_component_eq_empty [simp]: "connected_component_set s x = {} \<longleftrightarrow> (x \<notin> s)" |
|
1873 using connected_component_refl by (fastforce simp: connected_component_in) |
|
1874 |
|
1875 lemma connected_component_set_empty [simp]: "connected_component_set {} x = {}" |
|
1876 using connected_component_eq_empty by blast |
|
1877 |
|
1878 lemma connected_component_eq: |
|
1879 "y \<in> connected_component_set s x |
|
1880 \<Longrightarrow> (connected_component_set s y = connected_component_set s x)" |
|
1881 by (metis (no_types, lifting) Collect_cong connected_component_sym connected_component_trans mem_Collect_eq) |
|
1882 |
|
1883 lemma closed_connected_component: |
|
1884 assumes s: "closed s" shows "closed (connected_component_set s x)" |
|
1885 proof (cases "x \<in> s") |
|
1886 case False then show ?thesis |
|
1887 by (metis connected_component_eq_empty closed_empty) |
|
1888 next |
|
1889 case True |
|
1890 show ?thesis |
|
1891 unfolding closure_eq [symmetric] |
|
1892 proof |
|
1893 show "closure (connected_component_set s x) \<subseteq> connected_component_set s x" |
|
1894 apply (rule connected_component_maximal) |
|
1895 apply (simp add: closure_def True) |
|
1896 apply (simp add: connected_imp_connected_closure) |
|
1897 apply (simp add: s closure_minimal connected_component_subset) |
|
1898 done |
|
1899 next |
|
1900 show "connected_component_set s x \<subseteq> closure (connected_component_set s x)" |
|
1901 by (simp add: closure_subset) |
|
1902 qed |
|
1903 qed |
|
1904 |
|
1905 lemma connected_component_disjoint: |
|
1906 "(connected_component_set s a) \<inter> (connected_component_set s b) = {} \<longleftrightarrow> |
|
1907 a \<notin> connected_component_set s b" |
|
1908 apply (auto simp: connected_component_eq) |
|
1909 using connected_component_eq connected_component_sym by blast |
|
1910 |
|
1911 lemma connected_component_nonoverlap: |
|
1912 "(connected_component_set s a) \<inter> (connected_component_set s b) = {} \<longleftrightarrow> |
|
1913 (a \<notin> s \<or> b \<notin> s \<or> connected_component_set s a \<noteq> connected_component_set s b)" |
|
1914 apply (auto simp: connected_component_in) |
|
1915 using connected_component_refl_eq apply blast |
|
1916 apply (metis connected_component_eq mem_Collect_eq) |
|
1917 apply (metis connected_component_eq mem_Collect_eq) |
|
1918 done |
|
1919 |
|
1920 lemma connected_component_overlap: |
|
1921 "(connected_component_set s a \<inter> connected_component_set s b \<noteq> {}) = |
|
1922 (a \<in> s \<and> b \<in> s \<and> connected_component_set s a = connected_component_set s b)" |
|
1923 by (auto simp: connected_component_nonoverlap) |
|
1924 |
|
1925 lemma connected_component_sym_eq: "connected_component s x y \<longleftrightarrow> connected_component s y x" |
|
1926 using connected_component_sym by blast |
|
1927 |
|
1928 lemma connected_component_eq_eq: |
|
1929 "connected_component_set s x = connected_component_set s y \<longleftrightarrow> |
|
1930 x \<notin> s \<and> y \<notin> s \<or> x \<in> s \<and> y \<in> s \<and> connected_component s x y" |
|
1931 apply (case_tac "y \<in> s") |
|
1932 apply (simp add:) |
|
1933 apply (metis connected_component_eq connected_component_eq_empty connected_component_refl_eq mem_Collect_eq) |
|
1934 apply (case_tac "x \<in> s") |
|
1935 apply (simp add:) |
|
1936 apply (metis connected_component_eq_empty) |
|
1937 using connected_component_eq_empty by blast |
|
1938 |
|
1939 lemma connected_iff_connected_component_eq: |
|
1940 "connected s \<longleftrightarrow> |
|
1941 (\<forall>x \<in> s. \<forall>y \<in> s. connected_component_set s x = connected_component_set s y)" |
|
1942 by (simp add: connected_component_eq_eq connected_iff_connected_component) |
|
1943 |
|
1944 lemma connected_component_idemp: |
|
1945 "connected_component_set (connected_component_set s x) x = connected_component_set s x" |
|
1946 apply (rule subset_antisym) |
|
1947 apply (simp add: connected_component_subset) |
|
1948 by (metis connected_component_eq_empty connected_component_maximal connected_component_refl_eq connected_connected_component mem_Collect_eq set_eq_subset) |
|
1949 |
|
1950 lemma connected_component_unique: |
|
1951 "\<lbrakk>x \<in> c; c \<subseteq> s; connected c; |
|
1952 \<And>c'. x \<in> c' \<and> c' \<subseteq> s \<and> connected c' |
|
1953 \<Longrightarrow> c' \<subseteq> c\<rbrakk> |
|
1954 \<Longrightarrow> connected_component_set s x = c" |
|
1955 apply (rule subset_antisym) |
|
1956 apply (meson connected_component_maximal connected_component_subset connected_connected_component contra_subsetD) |
|
1957 by (simp add: connected_component_maximal) |
|
1958 |
|
1959 lemma joinable_connected_component_eq: |
|
1960 "\<lbrakk>connected t; t \<subseteq> s; |
|
1961 connected_component_set s x \<inter> t \<noteq> {}; |
|
1962 connected_component_set s y \<inter> t \<noteq> {}\<rbrakk> |
|
1963 \<Longrightarrow> connected_component_set s x = connected_component_set s y" |
|
1964 apply (simp add: ex_in_conv [symmetric]) |
|
1965 apply (rule connected_component_eq) |
|
1966 by (metis (no_types, hide_lams) connected_component_eq_eq connected_component_in connected_component_maximal subsetD mem_Collect_eq) |
|
1967 |
|
1968 |
|
1969 lemma Union_connected_component: "Union (connected_component_set s ` s) = s" |
|
1970 apply (rule subset_antisym) |
|
1971 apply (simp add: SUP_least connected_component_subset) |
|
1972 using connected_component_refl_eq |
|
1973 by force |
|
1974 |
|
1975 |
|
1976 lemma complement_connected_component_unions: |
|
1977 "s - connected_component_set s x = |
|
1978 Union (connected_component_set s ` s - {connected_component_set s x})" |
|
1979 apply (subst Union_connected_component [symmetric], auto) |
|
1980 apply (metis connected_component_eq_eq connected_component_in) |
|
1981 by (metis connected_component_eq mem_Collect_eq) |
|
1982 |
|
1983 lemma connected_component_intermediate_subset: |
|
1984 "\<lbrakk>connected_component_set u a \<subseteq> t; t \<subseteq> u\<rbrakk> |
|
1985 \<Longrightarrow> connected_component_set t a = connected_component_set u a" |
|
1986 apply (case_tac "a \<in> u") |
|
1987 apply (simp add: connected_component_maximal connected_component_mono subset_antisym) |
|
1988 using connected_component_eq_empty by blast |
|
1989 |
|
1990 subsection\<open>The set of connected components of a set\<close> |
|
1991 |
|
1992 definition components:: "'a::topological_space set \<Rightarrow> 'a set set" where |
|
1993 "components s \<equiv> connected_component_set s ` s" |
|
1994 |
|
1995 lemma components_iff: "s \<in> components u \<longleftrightarrow> (\<exists>x. x \<in> u \<and> s = connected_component_set u x)" |
|
1996 by (auto simp: components_def) |
|
1997 |
|
1998 lemma Union_components: "u = Union (components u)" |
|
1999 apply (rule subset_antisym) |
|
2000 apply (metis Union_connected_component components_def set_eq_subset) |
|
2001 using Union_connected_component components_def by fastforce |
|
2002 |
|
2003 lemma pairwise_disjoint_components: "pairwise (\<lambda>X Y. X \<inter> Y = {}) (components u)" |
|
2004 apply (simp add: pairwise_def) |
|
2005 apply (auto simp: components_iff) |
|
2006 apply (metis connected_component_eq_eq connected_component_in)+ |
|
2007 done |
|
2008 |
|
2009 lemma in_components_nonempty: "c \<in> components s \<Longrightarrow> c \<noteq> {}" |
|
2010 by (metis components_iff connected_component_eq_empty) |
|
2011 |
|
2012 lemma in_components_subset: "c \<in> components s \<Longrightarrow> c \<subseteq> s" |
|
2013 using Union_components by blast |
|
2014 |
|
2015 lemma in_components_connected: "c \<in> components s \<Longrightarrow> connected c" |
|
2016 by (metis components_iff connected_connected_component) |
|
2017 |
|
2018 lemma in_components_maximal: |
|
2019 "c \<in> components s \<longleftrightarrow> |
|
2020 (c \<noteq> {} \<and> c \<subseteq> s \<and> connected c \<and> (\<forall>d. d \<noteq> {} \<and> c \<subseteq> d \<and> d \<subseteq> s \<and> connected d \<longrightarrow> d = c))" |
|
2021 apply (rule iffI) |
|
2022 apply (simp add: in_components_nonempty in_components_connected) |
|
2023 apply (metis (full_types) components_iff connected_component_eq_self connected_component_intermediate_subset connected_component_refl in_components_subset mem_Collect_eq rev_subsetD) |
|
2024 by (metis bot.extremum_uniqueI components_iff connected_component_eq_empty connected_component_maximal connected_component_subset connected_connected_component subset_emptyI) |
|
2025 |
|
2026 lemma joinable_components_eq: |
|
2027 "connected t \<and> t \<subseteq> s \<and> c1 \<in> components s \<and> c2 \<in> components s \<and> c1 \<inter> t \<noteq> {} \<and> c2 \<inter> t \<noteq> {} \<Longrightarrow> c1 = c2" |
|
2028 by (metis (full_types) components_iff joinable_connected_component_eq) |
|
2029 |
|
2030 lemma closed_components: "\<lbrakk>closed s; c \<in> components s\<rbrakk> \<Longrightarrow> closed c" |
|
2031 by (metis closed_connected_component components_iff) |
|
2032 |
|
2033 lemma components_nonoverlap: |
|
2034 "\<lbrakk>c \<in> components s; c' \<in> components s\<rbrakk> \<Longrightarrow> (c \<inter> c' = {}) \<longleftrightarrow> (c \<noteq> c')" |
|
2035 apply (auto simp: in_components_nonempty components_iff) |
|
2036 using connected_component_refl apply blast |
|
2037 apply (metis connected_component_eq_eq connected_component_in) |
|
2038 by (metis connected_component_eq mem_Collect_eq) |
|
2039 |
|
2040 lemma components_eq: "\<lbrakk>c \<in> components s; c' \<in> components s\<rbrakk> \<Longrightarrow> (c = c' \<longleftrightarrow> c \<inter> c' \<noteq> {})" |
|
2041 by (metis components_nonoverlap) |
|
2042 |
|
2043 lemma components_eq_empty [simp]: "components s = {} \<longleftrightarrow> s = {}" |
|
2044 by (simp add: components_def) |
|
2045 |
|
2046 lemma components_empty [simp]: "components {} = {}" |
|
2047 by simp |
|
2048 |
|
2049 lemma connected_eq_connected_components_eq: "connected s \<longleftrightarrow> (\<forall>c \<in> components s. \<forall>c' \<in> components s. c = c')" |
|
2050 by (metis (no_types, hide_lams) components_iff connected_component_eq_eq connected_iff_connected_component) |
|
2051 |
|
2052 lemma components_eq_sing_iff: "components s = {s} \<longleftrightarrow> connected s \<and> s \<noteq> {}" |
|
2053 apply (rule iffI) |
|
2054 using in_components_connected apply fastforce |
|
2055 apply safe |
|
2056 using Union_components apply fastforce |
|
2057 apply (metis components_iff connected_component_eq_self) |
|
2058 using in_components_maximal by auto |
|
2059 |
|
2060 lemma components_eq_sing_exists: "(\<exists>a. components s = {a}) \<longleftrightarrow> connected s \<and> s \<noteq> {}" |
|
2061 apply (rule iffI) |
|
2062 using connected_eq_connected_components_eq apply fastforce |
|
2063 by (metis components_eq_sing_iff) |
|
2064 |
|
2065 lemma connected_eq_components_subset_sing: "connected s \<longleftrightarrow> components s \<subseteq> {s}" |
|
2066 by (metis Union_components components_empty components_eq_sing_iff connected_empty insert_subset order_refl subset_singletonD) |
|
2067 |
|
2068 lemma connected_eq_components_subset_sing_exists: "connected s \<longleftrightarrow> (\<exists>a. components s \<subseteq> {a})" |
|
2069 by (metis components_eq_sing_exists connected_eq_components_subset_sing empty_iff subset_iff subset_singletonD) |
|
2070 |
|
2071 lemma in_components_self: "s \<in> components s \<longleftrightarrow> connected s \<and> s \<noteq> {}" |
|
2072 by (metis components_empty components_eq_sing_iff empty_iff in_components_connected insertI1) |
|
2073 |
|
2074 lemma components_maximal: "\<lbrakk>c \<in> components s; connected t; t \<subseteq> s; c \<inter> t \<noteq> {}\<rbrakk> \<Longrightarrow> t \<subseteq> c" |
|
2075 apply (simp add: components_def ex_in_conv [symmetric], clarify) |
|
2076 by (meson connected_component_def connected_component_trans) |
|
2077 |
|
2078 lemma exists_component_superset: "\<lbrakk>t \<subseteq> s; s \<noteq> {}; connected t\<rbrakk> \<Longrightarrow> \<exists>c. c \<in> components s \<and> t \<subseteq> c" |
|
2079 apply (case_tac "t = {}") |
|
2080 apply force |
|
2081 by (metis components_def ex_in_conv connected_component_maximal contra_subsetD image_eqI) |
|
2082 |
|
2083 lemma components_intermediate_subset: "\<lbrakk>s \<in> components u; s \<subseteq> t; t \<subseteq> u\<rbrakk> \<Longrightarrow> s \<in> components t" |
|
2084 apply (auto simp: components_iff) |
|
2085 by (metis connected_component_eq_empty connected_component_intermediate_subset) |
|
2086 |
|
2087 lemma in_components_unions_complement: "c \<in> components s \<Longrightarrow> s - c = Union(components s - {c})" |
|
2088 by (metis complement_connected_component_unions components_def components_iff) |
|
2089 |
|
2090 lemma connected_intermediate_closure: |
|
2091 assumes cs: "connected s" and st: "s \<subseteq> t" and ts: "t \<subseteq> closure s" |
|
2092 shows "connected t" |
|
2093 proof (rule connectedI) |
|
2094 fix A B |
|
2095 assume A: "open A" and B: "open B" and Alap: "A \<inter> t \<noteq> {}" and Blap: "B \<inter> t \<noteq> {}" |
|
2096 and disj: "A \<inter> B \<inter> t = {}" and cover: "t \<subseteq> A \<union> B" |
|
2097 have disjs: "A \<inter> B \<inter> s = {}" |
|
2098 using disj st by auto |
|
2099 have "A \<inter> closure s \<noteq> {}" |
|
2100 using Alap Int_absorb1 ts by blast |
|
2101 then have Alaps: "A \<inter> s \<noteq> {}" |
|
2102 by (simp add: A open_inter_closure_eq_empty) |
|
2103 have "B \<inter> closure s \<noteq> {}" |
|
2104 using Blap Int_absorb1 ts by blast |
|
2105 then have Blaps: "B \<inter> s \<noteq> {}" |
|
2106 by (simp add: B open_inter_closure_eq_empty) |
|
2107 then show False |
|
2108 using cs [unfolded connected_def] A B disjs Alaps Blaps cover st |
|
2109 by blast |
|
2110 qed |
|
2111 |
|
2112 lemma closed_in_connected_component: "closedin (subtopology euclidean s) (connected_component_set s x)" |
|
2113 proof (cases "connected_component_set s x = {}") |
|
2114 case True then show ?thesis |
|
2115 by (metis closedin_empty) |
|
2116 next |
|
2117 case False |
|
2118 then obtain y where y: "connected_component s x y" |
|
2119 by blast |
|
2120 have 1: "connected_component_set s x \<subseteq> s \<inter> closure (connected_component_set s x)" |
|
2121 by (auto simp: closure_def connected_component_in) |
|
2122 have 2: "connected_component s x y \<Longrightarrow> s \<inter> closure (connected_component_set s x) \<subseteq> connected_component_set s x" |
|
2123 apply (rule connected_component_maximal) |
|
2124 apply (simp add:) |
|
2125 using closure_subset connected_component_in apply fastforce |
|
2126 using "1" connected_intermediate_closure apply blast+ |
|
2127 done |
|
2128 show ?thesis using y |
|
2129 apply (simp add: Topology_Euclidean_Space.closedin_closed) |
|
2130 using 1 2 by auto |
|
2131 qed |
1710 |
2132 |
1711 subsection \<open>Frontier (aka boundary)\<close> |
2133 subsection \<open>Frontier (aka boundary)\<close> |
1712 |
2134 |
1713 definition "frontier S = closure S - interior S" |
2135 definition "frontier S = closure S - interior S" |
1714 |
2136 |