This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...
1
vote
1answer
34 views
Relation between a parameter and cardinality of a set
For some fixed $n \in \mathbb{N}$ I have a set (dependent on parameter $p$)
$$ M(p) = \left\{ \, (i,j) \mid i \cdot j \le p, \; (i,j) \in \{ \, 1,2,3,\ldots,2^n \, \}^2 \, \right\};$$
If I know a ...
0
votes
1answer
34 views
Do these two expressions mean the same?
So for a given database we have the sets Persons, Married, Women, Men and Children.
I want to express all Women who are not Children and not Married:
$$Women\setminus \left ( married \cup children ...
4
votes
3answers
93 views
Does $\bigcup\emptyset$ equal $\bigcup\{\emptyset\}$?
For any collection of sets $A = \{A_i\ : i \in I \}$, define
$$\bigcup A = \bigcup_{i \in I} A_i$$
Question: Is the following true?
$$\bigcup \emptyset = \bigcup \{\emptyset \}$$
The right-hand ...
0
votes
1answer
40 views
under what conditions is f(A ∪B)=f(A) ∪f(B) and f(A∩B)=f(A)∩f(B)? [duplicate]
Does the function need to be bijective? I know for f(A∩B)=f(A)∩f(B) the function has to be injective, but what about the first equation?
0
votes
2answers
43 views
Inverse of a function.
Let $f:\mathcal{P}(A)\mathbf{\times\mathcal{P}(}B)\rightarrow\mathcal{P}(A\cup B)$
be defined as if $A_{1}\in\mathcal{P}(A)$
and $B_{1}\in\mathcal{P}(B)$
define $f(A_{1},B_{1})=A_{1}\cup B_{1}$
...
3
votes
3answers
45 views
If the following bijective, injective, both, or neither?
$f:\:\mathbb{R}^{+}\rightarrow\mathcal{P}(\mathbb{R}^{+})$
defined by $f(x)=\{x^{n}|n\in\mathbb{Z}\}$
Let $f(q)=f(r)$
, that is $q^{n}=r^{n}$
, we see that $q=r$
. Hense, that fuction is ...
1
vote
2answers
42 views
Injection and Surjection of Sets
Let $f:\mathcal{P}(A)\mathbf{\times\mathcal{P}(}B)\rightarrow\mathcal{P}(A\cup B)$
be defined as if $A_{1}\in\mathcal{P}(A)$
and $B_{1}\in\mathcal{P}(B)$
define $f(A_{1},B_{1})=A_{1}\cup B_{1}$
...
2
votes
2answers
35 views
Can the number of numbers in two intervals over $\mathbb{R^+}$ be compared?
Every number in the interval $[2.1,4]$ can be mapped to its square in the interval $[4.41, 16]$. Conversely, every number in the interval $[4.41,16]$ can be mapped to its respective square root in the ...
1
vote
2answers
58 views
Bijection from [-1,1) to the Reals
$Proposition. [-1,1)\approx\mathbb{R}.$
I know for this problem I need to find a bijection from $[-1,1)\rightarrow\mathbb{R}$. However, I am having trouble establishing a function that fits the ...
0
votes
1answer
41 views
How should I interpret the following set notation?
If I am given a set M = {(a,b), (b,a)}, where M is a relation on a set B {a,b}
What would be the values of the set: M;M?
I know the answer is: {(a,a), (b,b)} but is it just the pair of each unique ...
0
votes
2answers
41 views
How I can prove the existence of a bijection $h\colon A\times C \to B \times D$?
Let $f\colon A \to B$ and $g \colon C\to D$ two bijections. How I can prove the existence of a bijection $h\colon A \times C \to B \times D$?
6
votes
3answers
86 views
What questions become answerable/computable given an uncountable character set?
Having reached the concluding portion of my first course in real analysis, one subject that I feel was not adequately addressed was the issue of cardinalities.
This is a subject I was interested in ...
0
votes
3answers
47 views
Set Theory: General Intersection
How to properly prove the following:
For all integers positive integers n, if A1, A2,... and B are sets, then
1
vote
3answers
46 views
Definition of Dedekind-infinity: Bijection or Injections?
I have been using the following definition of infinity (from Dedekind):
Set $S$ is infinite iff there exists a proper subset $S'$ of $S$ and bijection $f: S\rightarrow S'$.
Occasionally, I have seen ...
0
votes
2answers
30 views
Prove that if $A\triangle B = C\triangle B$, then $A = C$
I am working with proofs in discrete math.
Help to prove:
For the sets $A$ and $B$, we define the symmetric difference of $A$ and $B$ to be $A \triangle B = (A-B)\cup(B-A).$
Prove that if $A ...
0
votes
1answer
32 views
Help needed about the classes
I have been going through Simmons' book. Class is defined as the set of sets. Given this definition, I have the following claim:
$$
\text{If} \left\{ A_i \right\}\text{ and } \left\{ B_j \right\} ...
-2
votes
2answers
90 views
Proving the number of edges in the complete graph Kn
I am trying to find the number of edges in the complete graph:
$$K_n=\sum_{i=0}^{n-1} i$$
0
votes
1answer
17 views
Proving partial order set in detail
Let $\le$ be a partially ordered set on the set $M$ and $f: M \to N$ bijective. Show that there's for $n, n' \in N$ a partially orderd set on $N$ defined:
$$n\le n'\iff f^{-1}(n)\le f^{-1}(n')$$
I ...
2
votes
2answers
83 views
Partitions of a Set
Is it true that only kind of relations that can completely and uniquely define a partition in a set is the equivalence relation ?
I'm having a hard problem believing that.
Given an ...
6
votes
4answers
172 views
Is it a Transitive Relation?
I need clarification.
Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$.
Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
1
vote
1answer
38 views
composite function with conditional IF
I've been wrapping my head around my Computer and Logic Essentials class, I can do most composite functions, however there is one question that I'm confused with.
It has an if statement inside it:
...
0
votes
2answers
44 views
Elementary Set Theory - Relations
I'm not exactly sure what to search for this problem I'm having, as I don't know the keywords, so I figured the best action would be to ask a question.
I have this question:
...
5
votes
2answers
96 views
Confusion about cofinality
I'm confused about the notion of the cofinality of a cardinal. Since I think the source of the confusion is the Von Neumann cardinal assignment, my first question is:
Question 0. Is there an article ...
3
votes
2answers
32 views
Prove that the number of pairs $(A,B)$ equals ${{n}\choose{i}}{{n-i}\choose{r-i}}{{n-r}\choose{s-i}}$
Prove that the number of pairs $(A,B)$ with $A\subseteq N_n, B\subseteq N_n, |A|=r, |B|=s, and |A\cap B|=i$ equals
${{n}\choose{i}}{{n-i}\choose{r-i}}{{n-r}\choose{s-i}}$
My teacher told me ...
10
votes
1answer
68 views
a totally ordered set with small well ordered set has to be small?
doing something quite different the following question came to me:
1)If you have a totally ordered set A such that all the well ordered subset are at most countable, is it true that A has at most the ...
2
votes
2answers
75 views
Notation for number of distinct elements in a set
Let $L = \{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, ... ,a_{n}\}$ be a logtrace containing a finite set of antenna samples submitted within a time window.
What what would be a good way to express the ...
2
votes
1answer
31 views
If $cf(\kappa)=\lambda$, then is every sequence of length $\lambda$ cofinal in $\kappa$?
Take $\omega_1$ for instance. Let's say I have a sequence of (distinct) ordinals of length $\omega_1$. Will this sequence be cofinal in $\omega_1$?
0
votes
2answers
44 views
How to prove this set is denumerable?
I'm studying for an exam tomorrow and I've encountered a practice question that asks for me to explain why the set $$ \mathbb{N} - \left\{n^2 \:|\: n \in \mathbb{N} \right\} $$ is denumerable. I ...
1
vote
1answer
39 views
Natural Numbers and Well ordering
I have to show that in any non empty subset of N there is least element.
Note: This is not a homework question.
So this is how my incomplete proof looks like.And i tried this by induction
let S be ...
3
votes
1answer
30 views
About a step in the construction of the Vitali set
Accept AC. Let $x,y\in[0,1] $ and define $x\sim y$ whenever $x-y$ is rational. Consider $[0,1]/\sim$. Define the set $V$ by taking a member of each equivalence class of $[0,1]/\sim$.
Now let $q$ be ...
3
votes
2answers
40 views
Uncountability of the equivalence classes of $\mathbb{R}/\mathbb{Q}$
Let $a,b\in[0,1]$ and define the equivalence relation $\sim$ by $a\sim b\iff a-b\in\mathbb{Q}$. This relation partitions $[0,1]$ into equivalence classes where every class consists of a set of numbers ...
0
votes
1answer
35 views
Looking for a Set generator
English is not my native language.
Hello everybody.
If I have a finite set of natural numbers. It is always possible to find an algorithm that generates it (and of course not the trivial one that ...
1
vote
1answer
26 views
On the limit of a Minkowski sum
Consider an open set $\mathcal{O} \subseteq \mathbb{R}^n$.
I am wondering if the set $$ \mathcal{S} := \lim_{k \rightarrow \infty} \ \mathcal{O} + \frac{1}{k} \mathbb{B} $$
is open or closed.
With ...
1
vote
0answers
36 views
When is a matrix called well-ordered?
We have a quick question, looking for information and/or references links.
Is there a more specific mathematical definition/criteria for when matrices can be called well ordered or totally ordered? ...
0
votes
1answer
31 views
Another way to state antisymmetry of a total order?
Adapted from Wikipedia:
"Set $S$ is totally ordered under $\le$" means:
$x,y \in S \implies ((x \le y \wedge y \le x) \implies x=y)$ (antisymmetry)
and
$x,y,z \in S \implies ((x \le y \wedge y \le ...
0
votes
2answers
50 views
Help with writing proofs
Prove that for any sets A, B and C if A is a subset of B, then A – C is a subset of B – C.
2
votes
1answer
44 views
Proving this realtion is not a transitive relation
I have trouble proving how the following statement is false:
The relation $g = \{\,(x,y)\in \Bbb R\times\Bbb R\mid y = x^2\,\}$ is transitive.
I know you have to use $yRx$, $zRy$, and $xRz$, but I'm ...
0
votes
1answer
37 views
Axiom of choice and power sets
If set $A= \{1,2,3\}$ and $S=P(A)-\{\}.$
What would be an explicit example of choice function of $f : S \to \bigcup_{C \in S} C$?
9
votes
5answers
272 views
What is the canonical definition of an open set?
The definition of an open set that I see in most topology texts(like the ones found in Topology by Munkres and another w/ the same title by Hocking & Young, or Basic Topology by Armstrong) is that ...
-1
votes
0answers
25 views
Show that T is equinumerous to Reals, where T={f:r->r| f is continuous} [duplicate]
Show that T is equinumerous to Reals, where T={f:r->r such that f is continuous}
3
votes
1answer
45 views
construction set of natural number logic
I identify the natural number $0$ with the empty set $\emptyset$, $1$ with $S(0)$, $2$ with $S(1)$, etc, etc.
The axiom of infinity says $\exists x (\emptyset\in x\wedge \forall z\in x\space ...
2
votes
1answer
55 views
Axiom schema of specification - Existence of intersection and set difference
I want to prove existence of intersection $x\cap y=\{z\in x| z\in y\}$ and set difference $x\setminus y=\{z\in x| \neg z\in y\}$using an axiom schema of specification.
My first thought was to use ...
1
vote
3answers
101 views
If a relation is reflexive is it symmetric and transitive?
If a relation is reflexive is it symmetric and transitive ?
let ~ means " in relation with "
if A is a set , ~ is a relation on $A$, prove that:
if $a$~$a$ for any $a$ $\in$ A then
1- $x$~$y$ ...
2
votes
2answers
26 views
Relation ≤ on Z = ℕ x ℕ given by (a,b) ≤ (c,d) iff a + d ≤ b + c is linear ordering
Prove the relation ≤ on Z = ℕ x ℕ given by (a,b) ≤ (c,d) iff a + d ≤ b + c is a linear ordering.
Note: The set we are referring to here is not the familiar set ℤ but the set Z that is in bijection ...
2
votes
1answer
35 views
The last $\omega$ -many things in any cardinal?
Is it possible to do this? For instance, could I take the last $\omega$-many things in $\omega_1$? Maybe you could just invert the well ordering and select that way?
3
votes
4answers
58 views
Cartesian Product Proof with Set Differences
Let $A$, $B$, $C$, and $D$ be sets. Prove:
$$
(A\setminus B)\times(C\setminus D)=(A\times C) \setminus [(A\times D)\cup (B\times C)]
$$
I've spend a lot of time on this chasing elements all over the ...
2
votes
1answer
46 views
Unique sequences from different sets
I am given $n$ sets with a selection of $m$ elements, such as:
$$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$
I am trying to calculate the number of unique sequences that contain all elements ...
0
votes
0answers
70 views
Show that the fiber $f^{-1}(a)$ is finite if $a∈ℝ,a≠0$
Let $f:ℝ→ℝ$ be a real analytic function. If $f$ has infinitely many zeros, then we know that the fiber $f^{-1}(0)$ is an infinite discrete and countable set. Let $a∈ℝ,a≠0$, we know also that the fiber ...
2
votes
3answers
58 views
Lebesgue measure on $\mathbb{R}$ is not a probability measure
So I'm not a math student hence the (probably rather simple) question in the title. I could not find an answer in the slides or the internet.
My intuition is that the elements (ie. reals) of ...
1
vote
3answers
39 views
Identity Law - Set Theory
I'm trying to wrap my head around the Identity Law, but I'm having some trouble.
My lecture slides say:
$$
A \cup \varnothing = A
$$
I can understand this one. $A$ union nothing is still $A$. In the ...
